3.4 Disproofs
The idea of a “disproof” is really just semantics — in order to disprove a statement we need to prove its negation.
So far we’ve been discussing proofs quite a bit but have paid very little attention to a really huge issue. If the statements we are attempting to prove are false, no proof is ever going to be possible. Really, a prerequisite to developing a facility with proofs is developing a good “lie detector.” We need to be able to guess, or quickly ascertain, whether a statement is true or false. If we are given a universally quantified statement, the first thing to do is try it out for some random elements of the universe we’re working in. If we happen across a value that satisfies the statement’s hypotheses but doesn’t satisfy the conclusion, we’ve found what is known as a counterexample.
Consider the following statement about integers and divisibility:Conjecture 3.1 \[ \forall a,b,c \in {\mathbb Z}, \; a \!\mid\!bc \; \implies \; a \!\mid\!b \, \lor \, a \!\mid\!c. \]
This is phrased as a UCS, so the hypothesis is clear. We’re looking for three integers so that the first divides the product of the other two. In the following table, we have collected several values for \(a\), \(b\) and \(c\) such that \(a \!\mid\!bc\).
\[\begin{array}{c|c|c|c} a & b & c & a \!\mid\!b \, \lor \, a \!\mid\!c ? \\ \hline 2 & 7 & 6 & \text{yes} \\ 2 & 4 & 5 & \text{yes} \\ 3 & 12 & 11 & \text{yes} \\ 3 & 5 & 15 & \text{yes} \\ 5 & 4 & 15 & \text{yes} \\ 5 & 10 & 3 & \text{yes} \\ 7 & 2 & 14 & \text{yes} \\ \end{array}\]
Exercise 3.5 As noted in Section 1.2, the statement above is related to whether or not \(a\) is prime. Note that in the table, only prime values of \(a\) appear. This is a rather broad hint. Find a counterexample to Conjecture 3.1.
There can be times when the search for a counterexample starts to feel really futile. Would you think it likely that a statement about natural numbers could be true for (more than) the first 50 numbers and yet still be false?
Exercise 3.6 Find a counterexample to the following statement: \[ \forall n \in {\mathbb Z}^+, \; n^2 - 79n + 1601 \, \mbox{is prime.} \]
Hidden within Euclid’s proof of the infinitude of the primes is a sequence. Recall that in the proof, we deduced a contradiction by considering the number \(N\) defined by
\[ N = 1 + \prod_{k=1}^n p_k. \]
Define a sequence by
\[ N_n = 1 + \prod_{k=1}^n p_k, \]
where \(\{p_1, p_2, \ldots , p_n\}\) are the actual first \(n\) primes. The first several values of this sequence are: \[\begin{array}{c|c} n & N_n \\ \hline 1 & 1+(2) = 3 \\ 2 & 1+(2\cdot 3) = 7\\ 3 & 1+(2\cdot 3\cdot 5) = 31\\ 4 & 1+(2\cdot 3\cdot 5\cdot 7) = 211\\ 5 & 1+(2\cdot 3\cdot 5\cdot 7\cdot 11) = 2311\\ \vdots & \vdots \\ \end{array}\]
In the proof, we deduced a contradiction by noting that \(N_n\) is much larger than \(p_n\). So if \(p_n\) is the largest prime, it follows that \(N_n\) can’t be prime — but what really appears to be the case (just look at that table!) is that \(N_n\) actually is prime for all \(n\).
Exercise 3.7 Find a counterexample to the conjecture that \(1+\prod\limits_{k=1}^n p_k\) is itself always a prime.
3.4.1 Exercises
Find a polynomial that assumes only prime values for a reasonably large range of inputs.
Find a counterexample to the conjecture that \(\forall a,b,c \in {\mathbb Z}, a \!\mid\!bc \; \implies \; a \!\mid\!b \, \lor \, a \!\mid\!c\) using only powers of 2.
The alternating sum of factorials provides an interesting example of a sequence of integers. \[\begin{gather*} 1! = 1 \\ 2! - 1! = 1\\ 3! - 2! + 1! = 5 \\ 4! - 3! + 2! - 1! = 19 \\ \text{etc.} \end{gather*}\] Are they all prime? (After the first two 1’s.)
It has been conjectured that whenever \(p\) is prime, \(2^p - 1\) is also prime. Find a minimal counterexample.
True or false: The sum of any two irrational numbers is irrational. Prove your answer.
True or false: There are two irrational numbers whose sum is rational. Prove your answer.
True or false: The product of any two irrational numbers is irrational. Prove your answer.
True or false: There are two irrational numbers whose product is rational. Prove your answer.
True or false: Whenever an integer \(n\) is a divisor of the square of an integer, \(m^2\), it follows that \(n\) is a divisor of \(m\) as well. (In symbols, \(\forall n \in {\mathbb Z}, \forall m \in {\mathbb Z}, n \!\mid\!m^2 \; \implies \; n \!\mid\!m\) .) Prove your answer.
In an exercise in Section 3.2, we proved that the quadratic equation \(ax^2 + bx + c = 0\) has two solutions if \(ac < 0\). Find a counterexample which shows that this implication cannot be replaced with a biconditional.