Processing math: 100%

Contradiction and contraposition

Kevin Cheung

MATH 1800

Proof by contraposition

Recall that AB and ¬B¬A are logically equivalent and that ¬B¬A is called the contrapositive of AB. Very often, mathematical statements of the form x,P(x)Q(x) are established by proving its contrapositive: x,¬Q(x)¬P(x). A proof that proves the contrapositive is called a proof by contraposition.

Examples

  1. xZ,3x23x

    Let P(x) denote the predicate “3x2” and Q(x) denote the predicate “3x”, the statement can be rewritten as xZ,P(x)Q(x). The contrapositive, xZ,¬Q(x)¬P(x), is xZ,3x3x2

    Proof.

    We prove the contrapositive: xZ,3x3x2.

    Let a be an integer such that 3a. Then by definition of , there exists an integer k such that a=3k. Hence, a2=(3k)2=(3k)(3k)=3(3k2). Since 3k2 is an integer, we have 3a2 as desired.

  2. nZ,(1)n=12n.

    Proof.

    We prove the contrapositive: nZ,2n(1)n1.

    Let n be an integer such that 2n. Thus, n is odd and so there exists an integer k such that n=2k+1. Thus, (1)n=(1)2k+1=(1)2k(1)=((1)2)k=1k=11.

Proof by contradiction

A proof by contradiction is based on the logical equivalence A¬A.

Example

  1. There is no smallest positive rational number.

    Proof.

    Assume that there is a rational number q that is less than every other rational number. Consider q=q2. Note that q is a positive rational number that is less than q, contradicting that q is the smallest positive rational number.

  2. There are infinitely many primes.

    Proof.

    We prove the equivalent statement: assuming that there are finitely many primes leads to a contradiction.

    Before we proceed with the proof, it is informative to see how the given statement can be written symbolically in the language of predicate logic: nN,|{xNpxp=1p=x}|>n.

    The negation of the above statement is nN,|{xNpxp=1p=x}|n.

    Assuming this holds, we derive a contradiction. Let N be such that the cardinality of the set of primes is at most N. Thus, the primes can be listed as p1,,pk for some positive integer kN. Consider the number n=1+ki=1pi. Since n>pi for all i=1,,k, n cannot be a prime. As n>2, n must have a prime factor. But for each i=1,,k, n1(mod pi. Thus, n is not divisible by any prime. This contradicts that n has a prime factor.

To prove x,P(x)Q(x) by contradiction, one can prove x,P(x)¬Q(x) instead since AB(AB)(identity)¬(¬(AB))(double negation)¬(AB)(implication)¬(¬AB)(implication)(¬(¬A)¬B)(De Morgan)(A¬B)(double negation)

In practice, one can adopt the following proof outline:

Theorem. xU,P(x)Q(x)

Proof.

Let a be an arbitrary element of U such that P(a) holds. Assume by way of contradiction that ¬Q(a) holds.

We obtain a contradiction.

Quite often, the contradiction obtained is in fact ¬P(a)P(a). In this case, one might wonder why we have a proof by contradiction instead of a proof by contraposition since we end up with ¬p(a) anyway. The difference is that in a proof by contradiction, we have the extra assumption P(a) to work with and in certain situations, it provides us with a more convenient way of arriving at a contradiction.

Examples

  1. If a is rational and b is irrational, then a+b is irrational.

    Proof.

    Assume by way of contradiction a is a rational number and b is an irrational number such that a+b is rational; i.e. a+b=mn for some integers m and n with n0.

    As a is rational, there exist integers p and q with q0 such that a=pq. Thus, b=mna=mnpq=mqpnnq. Since mqpn and nq are integers, b is rational, contradicting that b is irrational.

  2. If a and b are real numbers such that the equation ax=b has two distinct solutions, then a=b=0.

    Proof.

    We will prove instead that if a and b are real numbers such that the equation ax=b has two distinct solutions, then a=0. The original statement follows from this because when a=0, the equation becomes 0x=b giving b=0.

    Assume by way of contradiction that a0 and that r and s are distinct solutions to ax=b; i.e ar=b and as=b.

    Thus, ar=as, implying that aras=0. But aras=a(rs), giving a(rs)=0. Since a0, we must have rs=0, implying that r=s, which contradicts that r and s are distinct.

  3. Prove that for every nN, if n3 (mod 4), then n is not the square of an integer.

    Let n be a natural number such that n3 (mod 4). Hence, n must be odd.

    Assume by way of contradiction that n is the square of an integer. That is n=k2 for some integer k. By Exercise 1 in the previous set of notes, if k is even, then k2 is also even. Thus, k must be odd since n is odd, implying that k=2m+1 for some integer m. Hence, n=(2m+1)2=4(m2+m)+1. It follows that if n1 (mod 4), contradicting that n3 (mod 4).

Summary of proof techniques for ϕψ

Exercises

  1. Prove (by contraposition) that if x is a real number satisfying x33x2+2x+1=0, then x1.

  2. Let xZ. Prove (by contraposition) that if x3+1 is even, then x is odd.

  3. Prove (by contradiction) that for every natural number n, if n3(mod 4), then n is not the square of an integer.

  4. Let a and b be integers such that xa+yb=1 for some integers x and y. Prove (by contradiction) that gcd(a,b)=1.

  5. Let n be an odd natural number at least 3. Prove that if 2n+1 is prime, then n is prime.