1

I realize this is pretty basic but recently became unsure of how to justify proof by contradiction. Is it that case that I can show $A\Rightarrow B$ by assuming $A$ and NOT $B$, and showing this leads to a contradiction? How can this be justified?

Also, let's say I want to show $A$ and $B$ imply $C$. Is it sufficient to show $A, B$ and NOT $C$ leads to a contradiction? Seems this would not be the case, as a contrapositive would be NOT $C$ implies NOT $A$ OR NOT $B$.

Thanks!

xxxxxxxxx
  • 13,302
manofbear
  • 2,271
  • Proof by contradiction. – Em. Feb 09 '16 at 16:30
  • I'm not very familiar with the calculus of logic (e.g. Don't know how to negate the proposition "S and T implies Z"). Hence why I am asking basic questions. A response with some references to basic logic books or a summary of the basic computations necessary would be far more useful to me – manofbear Feb 09 '16 at 16:36
  • That's why you need to be very detailed in your questions. We cannot guess how much you do or do not understand. I also assume you did not actually read the article since the "Principle" section gives an overview using simple words. – Em. Feb 09 '16 at 16:40
  • Its best not to accept answers quite so quickly. I usually wait a day or two before accepting any answers, or even up to a week. This makes people more likely to give their own unique answer to the question, with their own unique spin, and this can be very useful. – goblin GONE Feb 09 '16 at 16:57

4 Answers4

2

If you want to prove by contradiction that ($A$ AND $B$)$\implies C$, you assume that $A$ AND $B$ AND (NOT $C$) and show that this leads to a contradiction. Here's why:

$a\implies b$ means $b$ OR (NOT $a$). So [($A$ AND $B$)$\implies C$] means [$C$ OR (NOT ($A$ AND $B$))] ie [$C$ OR (NOT $A$) OR (NOT $B$)]. If you negate this, you get $A$ AND $B$ AND (NOT $C$).

Augustin
  • 8,446
  • Thanks very much, this is exactly what I was hoping for! Do you know of any basic texts or references so I can see how to interpret implications as AND/OR statements? – manofbear Feb 09 '16 at 16:52
2

I write $\top$ for true and $\bot$ for false. The basic principle is that to prove $\varphi$, it suffices to:

  • assume $\neg \varphi,$
  • and then derive $\bot$ (i.e. a contradiction).

Intuitively, this works because (and only because) it is a theorem of Boolean algebra that for all $\varphi \in \{\top,\bot\}$, we have: $$\varphi = (\neg \varphi \rightarrow \bot).$$

This means that to prove $\alpha \rightarrow \beta$, it suffices to assume $\neg(\alpha \rightarrow \beta)$ and derive $\bot$. But some basic Boolean algebra tells us that:

$$\neg(\alpha \rightarrow \beta) = \neg(\neg\alpha \vee \beta) = \neg \neg \alpha \wedge \neg \beta = \alpha \wedge \neg \beta.$$

So assuming $\neg(\alpha \rightarrow \beta)$ is the same as assuming $\alpha$ and $\neg \beta$. Hence, to prove $\alpha \rightarrow \beta$, you should assume $\alpha$ and $\neg \beta$, and attempt to derive $\bot$.

goblin GONE
  • 67,744
2

A and NOT B leading to a contradiction, means:

A and NOT B simultaneous can not both be, means:

If A occurs, it will be impossible for NOT B to occur, means:

If A occurs, then B must occur, means:

A $\implies$ B.

===

"Also, let's say I want to show A and B imply C. Is it sufficient to show A,B and NOT C leads to a contradiction?"

Yes. By the same reasons.

=====

"Seems this would not be the case, as a contrapositive would be NOT C implies NOT A OR NOT B."

This is consistent. You can prove $(A \& B) \implies C$ in one of three ways:

1) directly: Assume $A$ and $B$ and show directly that $C$ must follow.

2) contradiction Assume $A$ and $B$ and $NOT C$ and show this leads to a contradiction. (Thus $NOT C$ can not exist with $A \& B$ so $A \& B \implies C$)

3) contrapositive: Assume $NOT C$ and show this leads to NOT $A$ OR NOT $B$. (Thus NOT $C$ can only exist with either NOT A or NOT B so NOT $C$ can not exist with both $A$ and $B$ so $A \& B \implies C$.

The three methods are all compatible. 2 and 3 are very closely related and as NOT A OR NOT B is a contradiction to A AND B, 3 can be seen as a subset of 2. (That is; assuming A and B and NOT C and concluding NOT A OR NOT B is an adequate contradiction. But 2 can be demonstrated by any contradiction.)

fleablood
  • 124,253
1

If you want to prove $A \implies B$, you assume $A \not \implies B$ and show this leads to some contradiction, so it is impossible. Since the impossibility is only based on the assumption $A \not \implies B$, this assumption must be incorrect. Hence $A \implies B$.

gt6989b
  • 54,422
  • So it suffices to show that A and NOT B leads to a contradiction? Further, if the claim is $A$ and $B$ imply $C$, then I can show $A$, $B$, and NOT $C$ leads to a contradiction? – manofbear Feb 09 '16 at 16:40
  • 1
    $A \not \implies B$ means A and NOT B are both simultaneously possible. You show that A and NOT B lead to a contradiction. So A and NOT B are not simultaneously possible. So whenever you have A you can't have NOT B. So you must have B. So $A \implies B$. (BTW you have also proven $NOT B \implies NOT A$, as whenever you have NOT B, you can not have A. These are equivalent statements. $A \implies B$, $NOT B \implies NOT A$, $NOT (A & NOT B)$, (A & B) $ OR $ NOT A$ are all equivalent statements.) – fleablood Feb 09 '16 at 17:50