Logic-Basic Proof Methods II

Proof by contraposition P => Q
Suppose ~Q.
     .
     .
     .
Therefore, ~P ( via direct proof)
Thus, ~Q => ~P.
Therefore, P => Q.

QED

Example. Let m be an integer. Prove that if m^2 is odd, then m is odd.
In this example the symbol "^" means power.

Proof. Supposed m is not odd. [Suppose ~Q.] Then m is even. Thus, m = 2k for some integer k. Then m^2 = (2k)^2 = 4k^2 = 2 (2k^2). Since m^2 is twice the integer  2k^2, m^2 is even. [Deduce ~P.] Thus, if m is even, then m^2 is even; so, by contraposition, if m^2 is odd, then m is odd.

Example. Let x and y be real numbers such that x , 2y. [The second assumption (~Q) begins our proof by contraposition.]  then 2y - x > 0 and 3x - y > 0. Therefore, (2y - x)(3x - y) = 7x - 3x^2 -2y^2 > 0. Hence, 7xy > 3x^2 + 2y^2. We have shown that if 3x > y, then 7xy > 3x^2 + 2y^2. We conclude that if 7xy <=(equal sign) 3x^2 + 2y^2, then 3x <=(equal sign) y.

QED

Example. Prove that the graphs of y = x^2 + x + 2 and y = x - 2 do not intersect.

Proof. Suppose that the graphs of y = x^2 + x + 2 and y = x - 2 do intersect at some point (a,b0. [Suppose ~P.] Since (a,b) is a point on both graphs, b= a^2 + a +2 and b = a -2. Therefore, a-2 = a^2 +a +2, so a^2 = -4. Thus, a^2 < 0. But a is a real number, so a >=0. This is impossible..[ The statement a^2 < 0 ^(and) a^2 >= 0 is a contradiction.] Therefore, the graphs do not intersect.

QED

Proof of P by Contradiction
Suppose ~P.
     .
     .
     .
Therefore, Q.
Hence, Q ^ ~Q, a contradiction.
Thus, P.

QED

Example.
Prove that square root(2), or sqrt(2) is an irrational number.

Proof. Suppose that sqrt(2) is a irrational number. [Assume ~P.] Then sqrt(20 = s/t, where s and t are integers. Thus, 2 = s^2/t^2, and 2t^2 = s^2. Since s^2 and t^2 are squares, s^2 contains an even number of 2's as prime factors [This is our Q statement.], and t^2 contains an even number of 2's. But then 2t^2 contains an odd number of 2's as factors. Since 2t^2 = s^2, s^2 has an odd number of 2's. [This statement ~Q.] This is a contradiction, because s^2 cannot have  both an even and an odd number of 2's as factors. We conclude that sqrt(2) is irrational.

QED