Truth table of proof by contradiction

Question

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?

Answer 1

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?

Answer 2

I don't really know what you are trying to say, but here is how to understand proof by contradiction.

In classical logic, we know that for any boolean statement $P$ we have only two possible cases, namely either $P$ or $\neg P$. If we want to prove $P$, we just have to prove that $\neg P$ cannot happen. If under the assumption of $\neg P$ we get a false statement such as $Q \land \neg Q$, then we know that $\neg P$ is impossible, and so the only possible case is $P$.

A proof by contradiction will look like:

~~~

If $P$:

  ...

  $Q \land \neg Q$.

  1

2

Therefore $\neg P$.

~~~

Note that what you have at 1 (under the assumption of $P$) is not the same as at 2 (outside that assumption). At 2 we may not know anything about $Q$, because whatever we deduced about it under the assumption is invalid outside the assumption. However, at 1 we know about $Q$. Specifically, we know both that $Q$ is true and that $Q$ is false! In fact for any proof by contradiction we must have such a situation.

In some cases we can separately deduce the truth of $Q$ outside the assumption about $P$, but in other cases we may not be able to. The point is that the more restricted the context, the more we can derive, but restrict too much and we may have an impossible context, and so we can conclude that the innermost assumption is false within the remaining context.

Answer 3

Your implication $(T \Rightarrow T) = T$ would be the correct one because the proof by contradiction, for your specific case, would be $( \lnot s1 \vdash s4 \land \lnot s4 ) \to ( \vdash s1)$; both the left and right side of the implication are true.

The implication inside the proof is $(F \to F) = T$ because, for your case, both $\lnot s1$ and $s4 \land \lnot s4$ (from $\lnot s1 \to s4 \land \lnot s4$) are false.