Proof by Contrapositive

We can prove the truth of some assertion by proving the contrapositive of the assertion instead. It might be easier to attack the contrapositive, for example.

What is the contrapositive?

Consider this assertion which will call R: P => Q
This says

    "if P is true, then Q is true", 
or more simply
    "P implies Q".
An example with words is
    "if this car is mine, then this car is blue".

The contrapositve of R is this assertion: ~Q => ~P
This says

    "if Q is not true, then P is not true", 
or more directly
    "not Q implies not P".

In our word example, the contrapositive is 
    "if this car is not blue, then it is not mine".

How does a proof work?

Proof by contrapositive works because of this fact:

   If R is true, then contrapos(R) is also true;
   If contrapos(R) is true, then R is also true.

We say this result this way:

    R if and only if contrapos(R)
which is written symbolically as
    R <==> contrapos(R)
We sometimes shorten "if and only if" to "iff".


For an example, check this link:

In class, I proved the truth of this assertion R:

   if x and y are two integers for which even(x+y), 
   then x and y have the same parity.
I did it by proving instead this assertion contrapos(R):
   if x and y are two integers with opposite parity, 
   then ~even(x+y).

Finally, since contrapos(R) is true, we conclude R is true.