The following is the truth table for an implication:
$(T\Rightarrow T) = T$
$(T\Rightarrow F) = F$
$(F\Rightarrow T) = T$
$(F\Rightarrow F) = T$
Now, in an implication involved in a proof by contradiction I want to know which of the above row applies.
Example:
The square root of a prime number is irrational. [$s1$]
Proof:
Assume that the square root of a prime number is rational. [$s2$]
Then, $\sqrt n = p/q$ where n is any prime and p and q are integers with no common factors. [$s3$]
…
(logical follow-ups)
…
p and q have at least one common factor. [$s4$]
$s2$ is false.
$s1$ is true.
QED
In the above proof, all of the following are true:
$s1 = \neg s2 \\
s2 \implies s3 \\
s3 \implies s4 \\
s3 = \neg s4\\
s3\text{ and } s4\text{ are contradictory: they cannot be true at the same time}$
Now what I am trying to do is to see how the truth of $s1$ follows from the true statements above and the truth table even above.
Row 1 in the truth table does not apply to $s3 \implies s4$ because $s3$ and $s4$ cannot both be true.
Row 2 does not apply because $s3 \implies s4$ is true.
Row 4 does not apply because $s3$ and $s4$ are negatives of each other: the consequent and the antecedent are not both false.
Only row 3 can apply because we have a true implication relating the consequent and antecedent. Since, s3 has to be the negative of s4, s3 is false and s4 is true. Hence, this is the row that applies our implication.
Now, going back to $s2 \implies s3$ we can determine that s2 is false because s3 is false the the implication was true.
Hence, s1 is true.
Is the analysis above correct?
Best Answer
I think you are misunderstanding how a proof by contradiction really works. First consider a simple example (the propositional calculus explanation will follow):
Proposition: Suppose $n$ is an odd integer. Then $n^2$ is an odd integer.
Proof. Suppose that $n$ is an odd integer but the conclusion is false; that is, suppose $n$ is an odd integer but $n^2$ is an even integer. Since $n$ is odd, we may write $n=2k+1$ for some $k\in\mathbb{Z}$. Thus, $$ n^2=(2k+1)^2=4k+2k+1, $$ but this contradicts that $n^2$ is even. Thus the assumption that $n^2$ is even must be wrong; that is, $n^2$ must be odd.
Explanation: The proposition above has the form $P\implies Q$. In general, if we assume such a statement to be false, then we are assuming that $P\land\neg Q$ because this is the negation of $P\implies Q$. Hence, to use contradiction, we then have to show that $P\land\neg Q$ leads to something false. Make sense now?