Investigate!27
Suppose you have a collection of 5-cent stamps and 8-cent stamps. We saw earlier that it is possible to make any amount of postage greater than 27 cents using combinations of both these types of stamps. But, let's ask some other questions:
What amounts of postage can you make if you only use an even number of both types of stamps? Prove your answer.
Suppose you made an even amount of postage. Prove that you used an even number of at least one of the types of stamps.
Suppose you made exactly 72 cents of postage. Prove that you used at least 6 of one type of stamp.
Anyone who doesn't believe there is creativity in mathematics clearly has not tried to write proofs. Finding a way to convince the world that a particular statement is necessarily true is a mighty undertaking and can often be quite challenging. There is not a guaranteed path to success in the search for proofs. For example, in the summer of 1742, a German mathematician by the name of Christian Goldbach wondered whether every even integer greater than 2 could be written as the sum of two primes. Centuries later, we still don't have a proof of this apparent fact (computers have checked that “Goldbach's Conjecture” holds for all numbers less than \(4\times 10^{18}\), which leaves only infinitely many more numbers to check).
Writing proofs is a bit of an art. Like any art, to be truly great at it, you need some sort of inspiration, as well as some foundational technique. Just as musicians can learn proper fingering, and painters can learn the proper way to hold a brush, we can look at the proper way to construct arguments. A good place to start might be to study a classic.
Theorem3.4.1
There are infinitely many primes.
Proof
Suppose this were not the case. That is, suppose there are only finitely many primes. Then there must be a last, largest prime, call it \(p\). Consider the number
\begin{equation*}
N = p! + 1 = (p \cdot (p-1) \cdot \cdots 3\cdot 2 \cdot 1) + 1.
\end{equation*}
Now \(N\) is certainly larger than \(p\). Also, \(N\) is not divisible by any number less than or equal to \(p\), since every number less than or equal to \(p\) divides \(p!\). Thus the prime factorization of \(N\) contains prime numbers (possibly just \(N\) itself) all greater than \(p\). So \(p\) is not the largest prime, a contradiction. Therefore there are infinitely many primes.
This proof is an example of a proof by contradiction, one of the standard styles of mathematical proof. First and foremost, the proof is an argument. It contains sequence of statements, the last being the conclusion which follows from the previous statements. The argument is valid so the conclusion must be true if the premises are true. Let's go through the proof line by line.
Suppose there are only finitely many primes.
{this is a premise. Note the use of “suppose.”}
There must be a largest prime, call it \(p\).
{follows from line 1, by the definition of “finitely many.”}
Let \(N = p! + 1\).
basically just notation, although this is the inspired part of the proof; looking at \(p! + 1\) is the key insight.
- \(N\) is larger than \(p\).
by the definition of \(p!\)
- \(N\) is not divisible by any number less than or equal to \(p\).
by definition, \(p!\) is divisible by each number less than or equal to \(p\), so \(p! + 1\) is not.
The prime factorization of \(N\) contains prime numbers greater than \(p\).
since \(N\) is divisible by each prime number in the prime factorization of \(N\), and by line 5.
Therefore \(p\) is not the largest prime.
by line 6, \(N\) is divisible by a prime larger than \(p\).
This is a contradiction.
from line 2 and line 7: the largest prime is \(p\) and there is a prime larger than \(p\).
Therefore there are infinitely many primes.
from line 1 and line 8: our only premise lead to a contradiction, so the premise is false.
We should say a bit more about the last line. Up through line 8, we have a valid argument with the premise “there are only finitely many primes” and the conclusion “there is a prime larger than the largest prime.” This is a valid argument as each line follows from previous lines. So if the premises are true, then the conclusion must be true. However, the conclusion is NOT true. The only way out: the premise must be false.
The sort of line-by-line analysis we did above is a great way to really understand what is going on. Whenever you come across a proof in a textbook, you really should make sure you understand what each line is saying and why it is true. Additionally, it is equally important to understand the overall structure of the proof. This is where using tools from logic is helpful. Luckily there are a relatively small number of standard proof styles that keep showing up again and again. Being familiar with these can help understand proof, as well as give ideas of how to write your own.
The simplest (from a logic perspective) style of proof is a direct proof. Often all that is required to prove something is a systematic explanation of what everything means. Direct proofs are especially useful when proving implications. The general format to prove \(P \imp Q\) is this:
Assume \(P\). Explain, explain,, explain. Therefore \(Q\).
Often we want to prove universal statements, perhaps of the form \(\forall x (P(x) \imp Q(x))\). Again, we will want to assume \(P(x)\) is true and deduce \(Q(x)\). But what about the \(x\)? We want this to work for all \(x\). We accomplish this by fixing \(x\) to be an arbitrary element (of the sort we are interested in).
Here are a few examples. First, we will set up the proof structure for a direct proof, then fill in the details.
Example3.4.2
Prove: For all integers \(n\), if \(n\) is even, then \(n^2\) is even.
Example3.4.3
Prove: For all integers \(a\), \(b\), and \(c\), if \(a|b\) and \(b|c\) then \(a|c\). Here \(x|y\), read “\(x\) divides \(y\)” means that \(y\) is a multiple of \(x\) (so \(x\) will divide into \(y\) without remainder).
Recall that an implication \(P \imp Q\) is logically equivalent to its contrapositive \(\neg Q \imp \neg P\). There are plenty of examples of statements which are hard to prove directly, but whose contrapositive can easily be proved directly. This is all that proof by contrapositive does. It gives a direct proof of the contrapositive of the implication. This is enough because the contrapositive is logically equivalent to the original implication.
The skeleton of the proof of \(P \imp Q\) by contrapositive will always look roughly like this:
Assume \(\neg Q\). Explain, explain, \ldots, explain. Therefore \(\neg P\).
As before, if there are variables and quantifiers, we set them to be arbitrary elements of our domain. Here are a couple examples.
Example3.4.4
Is the statement “for all integers \(n\), if \(n^2\) is even, then \(n\) is even” true?
Example3.4.5
Prove: for all integers \(a\) and \(b\), if \(a + b\) is odd, then \(a\) is odd or \(b\) is odd.
We have seen how to prove some statements in the form of implications: either directly or by contrapositive. Some statements aren't written as implications to begin with.
Example3.4.6
Consider the statement, for every prime number \(p\), either \(p = 2\) or \(p\) is odd. We can rephrase this: for every prime number \(p\), if \(p \ne 2\), then \(p\) is odd. Now try to prove it.
Proof
Let \(p\) be an arbitrary prime number. Assume \(p\) is not odd. So \(p\) is divisible by 2. Since \(p\) is prime, it must have exactly two divisors, and it has 2 as a divisor, so \(p\) must be divisible by only 1 and 2. Therefore \(p = 2\). This completes the proof (by contrapositive).
There might be statements which really cannot be rephrased as implications. For example, “\(\sqrt 2\) is irrational.” In this case, it is hard to know where to start. What can we assume? Well, say we want to prove the statement \(P\). What if we could prove that \(\neg P \imp Q\) where \(Q\) was false? If this implication is true, and \(Q\) is false, what can we say about \(\neg P\)? It must be false as well, which makes \(P\) true!
This is why proof by contradiction works. If we can prove that \(\neg P\) leads to a contradiction, then the only conclusion is that \(\neg P\) is false, so \(P\) is true. That's what we wanted to prove. In other words, if it is impossible for \(P\) to be false, \(P\) must be true.
Here are a couple examples of proofs by contradiction.
Example3.4.7
Prove that \(\sqrt{2}\) is irrational.
Proof
Suppose not. Then \(\sqrt 2\) is equal to a fraction \(\frac{a}{b}\). Without loss of generality, assume \(\frac{a}{b}\) is in lowest terms (otherwise reduce the fraction). So,
\begin{equation*}
2 = \frac{a^2}{b^2}
\end{equation*}
\begin{equation*}
2b^2 = a^2
\end{equation*}
Thus \(a^2\) is even, and as such \(a\) is even. So \(a = 2k\) for some integer \(k\), and \(a^2 = 4k^2\). We then have,
\begin{equation*}
2b^2 = 4k^2
\end{equation*}
\begin{equation*}
b^2 = 2k^2
\end{equation*}
Thus \(b^2\) is even, and as such \(b\) is even. Since \(a\) is also even, we see that \(\frac{a}{b}\) is not in lowest terms, a contradiction. Thus \(\sqrt 2\) is irrational.
Example3.4.8
Prove: there are no integers \(x\) and \(y\) such that \(x^2 = 4y + 2\).
Proof
We proceed by contradiction. So suppose there are integers \(x\) and \(y\) such that \(x^2 = 4y + 2 = 2(2y + 1)\). So \(x^2\) is even. We have seen that this implies that \(x\) is even. So \(x = 2k\) for some integer \(k\). Then \(x^2 = 4k^2\). This in turn gives
\(2k^2 = (2y + 1)\). But \(2k^2\) is even, and \(2y + 1\) is odd, so these cannot be equal. Thus we have a contradiction, so there must not be any integers \(x\) and \(y\) such that \(x^2 = 4y + 2\).
Example3.4.9
The Pigeonhole Principle: if more than \(n\) pigeons fly into \(n\) pigeon holes, then at least one pigeon hole will contain at least two pigeons. Prove this!
Proof
Suppose, contrary to stipulation, that each of the pigeon holes contain at most one pigeon. Then at most, there will be \(n\) pigeons. But we assumed that there are more than \(n\) pigeons, so this is impossible. Thus there must be a pigeon hole with more than one pigeon.
While we phrased this proof as a proof by contradiction, we could have also used a proof by contrapositive since our contradiction was simply the negation of the hypothesis. Sometimes this will happen, in which case you can use either style of proof. There are examples however where the contradiction occurs “far away” from the original statement.
It is almost NEVER okay to prove a statement with just an example. Certainly none of the statements proved above can be proved through an example. This is because in each of those cases we are trying to prove that something holds of all integers. We claim that \(n^2\) being even implies that \(n\) is even, no matter what integer \(n\) we pick. Showing that this works for \(n = 4\) is not even close to enough.
This cannot be stressed enough. If you are trying to prove a statement of the form \(\forall x P(x)\), you absolutely CANNOT prove this with an example.
However, existential statements can be proven this way. If we want to prove that there is an integer \(n\) such that \(n^2-n+41\) is not prime, all we need to do is find one. This might seem like a silly thing to want to prove until you try a few values for \(n\).
| \(n\) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
|
|
|
|
|
| \(n^2 - n + 41\) |
41 |
43 |
47 |
53 |
61 |
71 |
83 |
So far we have gotten only primes. You might be tempted to conjecture, “For all positive integers \(n\), the number \(n^2 - n + 41\) is prime.” If you wanted to prove this, you would need to use a direct proof, a proof by contrapositive, or another style of proof, but certainly it is not enough to give even 7 examples. In fact, we can prove this conjecture is false by proving its negation: “There is a positive integer \(n\) such that \(n^2 - n + 41\) is not prime.” Since this is an existential statement, it suffices to show that there does indeed exist such a number.
In fact, we can quickly see that \(n = 41\) will give \(41^2\) which is certainly not prime. You might say that this is a counterexample to the conjecture that \(n^2 - n + 41\) is always prime. Since so many statements in mathematics are universal, making their negations existential, we can often prove that a statement is false (if it is) by providing a counterexample.
Example3.4.10
Above we proved, “for all integers \(a\) and \(b\), if \(a+b\) is odd, then \(a\) is odd or \(b\) is odd.” Is the converse true?
We could go on and on and on about different proof styles (we haven't even mentioned induction or combinatorial proofs here), but instead we will end with one final useful technique: proof by cases. The idea is to prove that \(P\) is true by proving that \(Q \imp P\) and \(\neg Q \imp P\) for some statement \(Q\). So no matter what, whether or not \(Q\) is true, we know that \(P\) is true. In fact, we could generalize this. Suppose we want to prove \(P\). We know that at least one of the statements \(Q_1, Q_2, \ldots, Q_n\) are true. If we can show that \(Q_1 \imp P\) and \(Q_2 \imp P\) and so on all the way to \(Q_n \imp P\), then we can conclude \(P\). The key thing is that we want to be sure that one of our cases (the \(Q_i\)'s) must be true no matter what.
If that last paragraph was confusing, hopefully an example will make things better.
Example3.4.11
Prove: for any integer \(n\), the number \((n^3 -n)\) is even.
1
Consider the statement “for all integers \(a\) and \(b\), if \(a + b\) is even, then \(a\) and \(b\) are even”
Write the contrapositive of the statement.
Write the converse of the statement.
Write the negation of the statement.
Is the original statement true or false? Prove your answer.
Is the contrapositive of the original statement true or false? Prove your answer.
Is the converse of the original statement true or false? Prove your answer.
Is the negation of the original statement true or false? Prove your answer.
2
Consider the statement: for all integers \(n\), if \(n\) is even then \(8n\) is even.
Prove the statement. What sort of proof are you using?
Is the converse true? Prove or disprove.
3
Prove that \(\sqrt 3\) is irrational.
4
Consider the statement: for all integers \(a\) and \(b\), if \(a\) is even and \(b\) is a multiple of 3, then \(ab\) is a multiple of 6.
Prove the statement. What sort of proof are you using?
State the converse. Is it true? Prove or disprove.
5
Prove the statement: For all integers \(n\), if \(5n\) is odd, then \(n\) is odd. Clearly state the style of proof you are using.
6
Prove the statement: For all integers \(a\), \(b\), and \(c\), if \(a^2 + b^2 = c^2\), then \(a\) or \(b\) is even.
7
The game TENZI comes with 40 six-sided dice (each numbered 1 to 6). Suppose you roll all 40 dice. Prove that there will be at least seven dice that land on the same number.
8
How many dice would you have to roll before you were guaranteed that some four of them would all match or all be different? Prove your answer.
9
Prove that \(\log(7)\) is irrational.
10
Prove that there are no integer solutions to the equation \(x^2 = 4y + 3\).
11
Prove that every prime number greater than 3 is either one more or one less than a multiple of 6. Hint: prove the contrapositive by cases.
12
For each of the statements below, say what method of proof you should use to prove them. Then say how the proof starts and how it ends. Bonus points for filling in the middle.
There are no integers \(x\) and \(y\) such that \(x\) is a prime greater than 5 and \(x = 6y + 3\).
For all integers \(n\), if \(n\) is a multiple of 3, then \(n\) can be written as the sum of consecutive integers.
For all integers \(a\) and \(b\), if \(a^2 + b^2\) is odd, then \(a\) or \(b\) is odd.
