MHB Understanding Proof by Contradiction in Logic and Mathematics

[Poirot1]

Is this how proof by condraction works?
Say we want to prove A-> B.
We prove by showing the statement 'A and not B' implies some statement C which is false (since it contradicts a known fact). Therefore, anything which implies C must itself be false, so 'A and not B' is false. I.e. A implies B.

 

[I like Serena]

Yes.
Note that this is a special case of a proof by contradiction.
Not all proofs by contradiction will fit the pattern you suggest.

More generally, suppose we want to prove A, then assume A to be false, and show that this leads to a contradiction.

 

[Evgeny.Makarov]

I agree. Here is what I posted on the other forum concerning proofs by contradiction and contrapositive.

Proofs by contrapositive and by contradiction are closely related. To remind, a contrapositive of P -> Q is ~Q -> ~P. A statement and its contrapositive are equivalent, so instead of one it is possible to prove the other. In a proof by contradiction, instead of proving Q one shows ~Q -> F where F is falsehood; then Q follows.

Formally, proving P -> Q in this way involves both proof by contrapositive and proof by contradiction. Namely, one assumes P and then proves Q by contradiction. For this, one assumes ~Q and from here derives ~P (this is the contrapositive of P -> Q). Combining ~P with the first assumption P gives falsehood, so Q follows.

In practice, the names "proof by contrapositive" and "proof by contradiction" are often used interchangeably.

 

[Deveno]

the difference between the two i see is this:

proof by contrapositive uses:

~A v B = B v ~A = ~(~B) v ~A (switching the "order" of A and B).

proof by contradiction uses:

~A v B = ~(~(~A v B)) = ~(A & ~B) (changing the "or-ness" of implication, to "and-ness").

this is most evident in "the flow" of the proofs: proofs by contrapositive seem "backwards" (we start where we don't want to be, and end where we aren't, so it's good), whereas proofs by contradiction go "the right way" from the wrong starting place.

for example, if i wish to show that every multiple of 4 is even by proving the contrapositive, i show that no odd number is divisible by 4.

if i wish to prove that every multiple of 4 is even by contradiction, i assume there is some 4k that is odd, and derive the contradiction that 1 is even. there is often some "blurring" of these distinctions, and a formal codification of either proof may wind up looking much the same (as it should!).

loosely speaking it's the (subtle) difference between:

for all...(somethings, some statement is true)

there does not exist...(a counter-example)

and when I'm really confused, i often forget which one I'm in the middle of. :(