MHB Understanding Proof by Contradiction in Logic and Mathematics

AI Thread Summary
Proof by contradiction involves assuming the negation of a statement and demonstrating that this leads to a contradiction, thereby proving the original statement. It can be closely related to proof by contrapositive, where one proves the contrapositive of a statement instead. Both methods are often used interchangeably, but they differ in their approach: proof by contrapositive starts from a point of negation, while proof by contradiction moves from an assumption that leads to a falsehood. The discussion highlights that while the techniques may appear similar, their logical flows and implications can differ subtly. Understanding these distinctions is crucial for effectively applying these proof techniques in logic and mathematics.
Poirot1
Messages
243
Reaction score
0
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.
 
Physics news on Phys.org
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.
 
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.
 
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. :(
 
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top