MATH 1800
Recall that \(A \Rightarrow B\) and \(\neg B \Rightarrow \neg A\) are logically equivalent and that \(\neg B \Rightarrow \neg A\) is called the contrapositive of \(A \Rightarrow B\). Very often, mathematical statements of the form \(\forall x, P(x) \Rightarrow Q(x)\) are established by proving its contrapositive: \(\forall x, \neg Q(x) \Rightarrow \neg P(x)\). A proof that proves the contrapositive is called a proof by contraposition.
\(\forall x \in \mathbb{Z}, 3 \nmid x^2 \Rightarrow 3 \nmid x\)
Let \(P(x)\) denote the predicate “\(3 \nmid x^2\)” and \(Q(x)\) denote the predicate “\(3 \nmid x\)”, the statement can be rewritten as \(\forall x \in \mathbb{Z}, P(x) \Rightarrow Q(x)\). The contrapositive, \(\forall x \in \mathbb{Z}, \neg Q(x) \Rightarrow \neg P(x)\), is \(\forall x \in \mathbb{Z}, 3 \mid x \Rightarrow 3 \mid x^2\)
Proof.
We prove the contrapositive: \(\forall x \in \mathbb{Z}, 3 \mid x \Rightarrow 3 \mid x^2.\)
Let \(a\) be an integer such that \(3 \mid a\). Then by definition of \(\mid\), there exists an integer \(k\) such that \(a = 3k\). Hence, \(a^2 = (3k)^2 = (3k)\cdot(3k) = 3(3k^2)\). Since \(3k^2\) is an integer, we have \(3 \mid a^2\) as desired.
\(\forall n \in \mathbb{Z}, (-1)^n = 1 \Rightarrow 2 \mid n\).
Proof.
We prove the contrapositive: \(\forall n \in \mathbb{Z}, 2 \nmid n \Rightarrow (-1)^n \neq 1\).
Let \(n\) be an integer such that \(2 \nmid 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 = -1^k = -1 \neq 1.\]
A proof by contradiction is based on the logical equivalence \(A \cong \neg A \Rightarrow \bot\).
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' = \frac{q}{2}\). 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: \[\forall n \in \mathbb{N}, |\{ x \in \mathbb{N} \mid p \mid x \Rightarrow p = 1 \vee p = x\}| > n.\]
The negation of the above statement is \[\exists n \in \mathbb{N}, |\{ x \in \mathbb{N} \mid p \mid x \Rightarrow p = 1 \vee p = x\}| \leq 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 \(p_1,\ldots,p_k\) for some positive integer \(k \leq N\). Consider the number \(n = 1 + \displaystyle\prod_{i = 1}^k p_i\). Since \(n > p_i\) for all \(i = 1,\ldots, k\), \(n\) cannot be a prime. As \(n > 2\), \(n\) must have a prime factor. But for each \(i = 1,\ldots, k\), \(n \equiv 1 (\text{mod } p_i\). Thus, \(n\) is not divisible by any prime. This contradicts that \(n\) has a prime factor.
To prove \(\forall x, P(x) \Rightarrow Q(x)\) by contradiction, one can prove \(\forall x, P(x) \wedge \neg Q(x) \Rightarrow \bot\) instead since \[\begin{align} A \Rightarrow B & \cong (A \Rightarrow B) \vee \bot && (\text{identity}) \\ & \cong \neg (\neg (A \Rightarrow B)) \vee \bot && (\text{double negation})\\ & \cong \neg(A \Rightarrow B) \Rightarrow \bot && (\text{implication})\\ & \cong \neg(\neg A \vee B) \Rightarrow \bot && (\text{implication})\\ & \cong (\neg (\neg A) \wedge \neg B) \Rightarrow \bot && (\text{De Morgan})\\ & \cong (A \wedge \neg B) \Rightarrow \bot && (\text{double negation})\\ \end{align}\]
In practice, one can adopt the following proof outline:
Theorem. \(\forall x \in U, P(x) \Rightarrow Q(x)\)
Proof.
Let \(a\) be an arbitrary element of \(U\) such that \(P(a)\) holds. Assume by way of contradiction that \(\neg Q(a)\) holds.
…
We obtain a contradiction.
Quite often, the contradiction obtained is in fact \(\neg P(a) \wedge 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 \(\neg 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 = \frac{m}{n}\) for some integers \(m\) and \(n\) with \(n\neq 0\).
As \(a\) is rational, there exist integers \(p\) and \(q\) with \(q \neq 0\) such that \(a = \frac{p}{q}\). Thus, \(b = \frac{m}{n} -a = \frac{m}{n} - \frac{p}{q} = \frac{mq - pn}{nq}\). 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 \neq 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 \neq 0\), we must have \(r - s = 0\), implying that \(r = s\), which contradicts that \(r\) and \(s\) are distinct.
Prove that for every \(n \in \mathbb{N}\), if \(n \equiv 3~(\text{mod } 4)\), then \(n\) is not the square of an integer.
Let \(n\) be a natural number such that \(n \equiv 3~(\text{mod } 4)\). Hence, \(n\) must be odd.
Assume by way of contradiction that \(n\) is the square of an integer. That is \(n = k^2\) for some integer \(k\). By Exercise 1 in the previous set of notes, if \(k\) is even, then \(k^2\) 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(m^2+m) + 1\). It follows that if \(n \equiv 1~(\text{mod } 4)\), contradicting that \(n \equiv 3~(\text{mod } 4)\).
A direct proof requires assuming \(\phi\) and deriving \(\psi\).
A proof by contraposition requires assuming \(\neg \psi\) and deriving \(\neg \phi\).
A proof by contradiction requires assuming \(\phi \wedge \neg \psi\) and deriving \(\bot\).
Prove (by contraposition) that if \(x\) is a real number satisfying \(x^3 - 3x^2 + 2x + 1 = 0\), then \(x \neq 1\).
Let \(x \in \mathbb{Z}\). Prove (by contraposition) that if \(x^3 + 1\) is even, then \(x\) is odd.
Prove (by contradiction) that for every natural number \(n\), if \(n \equiv 3 (\text{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 \(2^n + 1\) is prime, then \(n\) is prime.