Saturday 29 November 2014

Indirect Proofs - Proof by Contradiction

Proof by contradiction starts with an assumption that the proposition in question is false, followed by a series of logical deductions that lead to a contradiction of something that we all know to be true, then we can say that the proposition must be true. In simpler terms... if a proposition were false, then something false would be true, and since false cannot be true, our proposition better not be false.

This all sounds very abstract... so lets break it down.
Let P be a proposition
To prove P is true,
    we assume P is false (not P is True)
        this leads to some falsehood (such as 2 is not an even number)
    then not P -> falsehood is True (How? Remember truth tables?)
        the only way for this to work is if not P is false, which means P is true.
This is the same as proving the contrapositive of Truth -> P

No comments:

Post a Comment