2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Also, it should be $s_2\to s_3$: it's precisely because we assume $s_2$, i.e. that $\sqrt{n}$ is rational, that we can write it as an irreducible fraction of integers ($s_3$). $\endgroup$
    – Demosthene
    Mar 21, 2015 at 10:52
  • $\begingroup$ Your analysis must be rewritten as : $s_1 = \lnot s_2$, $s_2 \to s_3$, $s_2 \to s_4$ and $s_4 = \lnot s_3$. Thus we have $s_2 \to s_3$, $s_2 \to \lnot s_3$. Using the tautology : $(p \to q) \to ((p \to \lnot q) \to \lnot p)$ and modus ponens twice, we conclude with : $\lnot s_2$, i.e. $s_1$. $\endgroup$ Mar 21, 2015 at 13:08

3 Answers 3

3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ edited question for better explanation. perhaps, you could tell where the misunderstanding is? Do I understand what a contradiction means? $\endgroup$ Mar 21, 2015 at 5:40
  • $\begingroup$ @lopi It looks like Mauro has written half a book on an answer to your question and you accepted his answer so I imagine everything is clear now :) $\endgroup$ Mar 21, 2015 at 19:24
  • $\begingroup$ Accepting an answer is temporary. Yes, it did not answer the question "Is the analysis above correct?", but it made use of the terminology used in the question. It is also true that the question was edited since you last answered it. Perhaps, you can answer the question in totality? $\endgroup$ Mar 21, 2015 at 19:45
1
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ added explanation above--would be helpful if you could point out whether the analysis is wrong or right $\endgroup$ Mar 21, 2015 at 5:39
  • $\begingroup$ @lopi: From your follow up edit it seems that you don't really understand proofs. Do you understand what I said in my answer or not? If you fully understand it, then it is enough. Proof by contradiction does not directly have anything to do with the truth table of implication. $\endgroup$
    – user21820
    Mar 21, 2015 at 6:39
  • $\begingroup$ I understand what you said. Yes, $Q \land \space \neg Q$ is false. But how does that imply $\neg P$ is impossible (false?)? You say it has nothing to directly with the truth table of implication. But how can you explain the implication you indirectly refer to? $\endgroup$ Mar 21, 2015 at 6:53
  • $\begingroup$ Also, the question is not whether I understand proof by contradiction. The question is to see if there is a mistake in the analysis above. $\endgroup$ Mar 21, 2015 at 6:56
  • $\begingroup$ @lopi: Well your comment shows that you didn't understand my answer. We cannot get false statements under correct assumptions. So if under the assumption of $\neg P$ we get a false statement, then the assumption must be incorrect. A contradiction is equivalent to a false statement because it is accepted that there is no statement that is both true and false. $\endgroup$
    – user21820
    Mar 21, 2015 at 6:58
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.