MATH 1800
Recall that A⇒B and ¬B⇒¬A are logically equivalent and that ¬B⇒¬A is called the contrapositive of A⇒B. 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.
∀x∈Z,3∤x2⇒3∤x
Let P(x) denote the predicate “3∤x2” and Q(x) denote the predicate “3∤x”, the statement can be rewritten as ∀x∈Z,P(x)⇒Q(x). The contrapositive, ∀x∈Z,¬Q(x)⇒¬P(x), is ∀x∈Z,3∣x⇒3∣x2
Proof.
We prove the contrapositive: ∀x∈Z,3∣x⇒3∣x2.
Let a be an integer such that 3∣a. 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 3∣a2 as desired.
∀n∈Z,(−1)n=1⇒2∣n.
Proof.
We prove the contrapositive: ∀n∈Z,2∤n⇒(−1)n≠1.
Let n be an integer such that 2∤n. 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=−1≠1.
A proof by contradiction is based on the logical equivalence A≅¬A⇒⊥.
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.
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: ∀n∈N,|{x∈N∣p∣x⇒p=1∨p=x}|>n.
The negation of the above statement is ∃n∈N,|{x∈N∣p∣x⇒p=1∨p=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 k≤N. Consider the number n=1+k∏i=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, n≡1(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 A⇒B≅(A⇒B)∨⊥(identity)≅¬(¬(A⇒B))∨⊥(double negation)≅¬(A⇒B)⇒⊥(implication)≅¬(¬A∨B)⇒⊥(implication)≅(¬(¬A)∧¬B)⇒⊥(De Morgan)≅(A∧¬B)⇒⊥(double negation)
In practice, one can adopt the following proof outline:
Theorem. ∀x∈U,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.
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 n≠0.
As a is rational, there exist integers p and q with q≠0 such that a=pq. Thus, b=mn−a=mn−pq=mq−pnnq. Since mq−pn and nq are integers, b is rational, contradicting that b is irrational.
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 a≠0 and that r and s are distinct solutions to ax=b; i.e ar=b and as=b.
Thus, ar=as, implying that ar−as=0. But ar−as=a(r−s), giving a(r−s)=0. Since a≠0, we must have r−s=0, implying that r=s, which contradicts that r and s are distinct.
Prove that for every n∈N, if n≡3 (mod 4), then n is not the square of an integer.
Let n be a natural number such that n≡3 (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 n≡1 (mod 4), contradicting that n≡3 (mod 4).
A direct proof requires assuming ϕ and deriving ψ.
A proof by contraposition requires assuming ¬ψ and deriving ¬ϕ.
A proof by contradiction requires assuming ϕ∧¬ψ and deriving ⊥.
Prove (by contraposition) that if x is a real number satisfying x3−3x2+2x+1=0, then x≠1.
Let x∈Z. Prove (by contraposition) that if x3+1 is even, then x is odd.
Prove (by contradiction) that for every natural number n, if n≡3(mod 4), then n is not the square of an integer.
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.
Let n be an odd natural number at least 3. Prove that if 2n+1 is prime, then n is prime.