But since \(2kj+k+j\) is an integer, this says that the integer \(n\) is equal to a non-integer, which is impossible.
Let \(ab\) be an even number, say \(ab=2n\text<,>\) and \(a\) be an odd number, say \(a=2k+1\text<.>\) \begin ab \amp =(2k+1)b\\ 2n \amp =2kb+b\\ 2n-2kb\amp =b\\ 2(n-kb)\amp =b\text \end Therefore \(b\) must be even.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>\text\) 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.
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\text<.>\) Consider the number
\begin N = p! + 1 = (p \cdot (p-1) \cdot \cdots 3\cdot 2 \cdot 1) + 1\text \endNow \(N\) is certainly larger than \(p\text<.>\) Also, \(N\) is not divisible by any number less than or equal to \(p\text\) since every number less than or equal to \(p\) divides \(p!\text<.>\) Thus the prime factorization of \(N\) contains prime numbers (possibly just \(N\) itself) all greater than \(p\text<.>\) 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\text<.>\) [follows from line 1, by the definition of “finitely many.”]
Let \(N = p! + 1\text<.>\) [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\text<.>\) [by the definition of \(p!\) ]\(N\) is not divisible by any number less than or equal to \(p\text<.>\) [by definition, \(p!\) is divisible by each number less than or equal to \(p\text\) so \(p! + 1\) is not.]
The prime factorization of \(N\) contains prime numbers greater than \(p\text<.>\) [since \(N\) is divisible by each prime number in the prime factorization of \(N\text\) and by line 5.]
Therefore \(p\) is not the largest prime. [by line 6, \(N\) is divisible by a prime larger than \(p\text<.>\) ]
This is a contradiction. [from line 2 and line 7: the largest prime is \(p\) and there is a prime larger than \(p\text<.>\) ]
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 . 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\text<.>\) Explain, explain, …, explain. Therefore \(Q\text<.>\)Often we want to prove universal statements, perhaps of the form \(\forall x (P(x) \imp Q(x))\text<.>\) Again, we will want to assume \(P(x)\) is true and deduce \(Q(x)\text<.>\) But what about the \(x\text\) We want this to work for all \(x\text<.>\) 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.
The format of the proof will be this: Let \(n\) be an arbitrary integer. Assume that \(n\) is even. Explain explain explain. Therefore \(n^2\) is even.
To fill in the details, we will basically just explain what it means for \(n\) to be even, and then see what that means for \(n^2\text<.>\) Here is a complete proof.
Let \(n\) be an arbitrary integer. Suppose \(n\) is even. Then \(n = 2k\) for some integer \(k\text<.>\) Now \(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\text<.>\) Since \(2k^2\) is an integer, \(n^2\) is even.
Prove: For all integers \(a\text<,>\) \(b\text<,>\) and \(c\text<,>\) if \(a|b\) and \(b|c\) then \(a|c\text<.>\) (Here \(x|y\text<,>\) read “ \(x\) divides \(y\) ” means that \(y\) is a multiple of \(x\text<,>\) i.e., that \(x\) will divide into \(y\) without remainder).
Even before we know what the divides symbol means, we can set up a direct proof for this statement. It will go something like this: Let \(a\text<,>\) \(b\text<,>\) and \(c\) be arbitrary integers. Assume that \(a|b\) and \(b|c\text<.>\) Dot dot dot. Therefore \(a|c\text<.>\)
How do we connect the dots? We say what our hypothesis ( \(a|b\) and \(b|c\) ) really means and why this gives us what the conclusion ( \(a|c\) ) really means. Another way to say that \(a|b\) is to say that \(b = ka\) for some integer \(k\) (that is, that \(b\) is a multiple of \(a\) ). What are we going for? That \(c = la\text<,>\) for some integer \(l\) (because we want \(c\) to be a multiple of \(a\) ). Here is the complete proof.
Let \(a\text<,>\) \(b\text<,>\) and \(c\) be integers. Assume that \(a|b\) and \(b|c\text<.>\) In other words, \(b\) is a multiple of \(a\) and \(c\) is a multiple of \(b\text<.>\) So there are integers \(k\) and \(j\) such that \(b = ka\) and \(c = jb\text<.>\) Combining these (through substitution) we get that \(c = jka\text<.>\) But \(jk\) is an integer, so this says that \(c\) is a multiple of \(a\text<.>\) Therefore \(a|c\text<.>\)
Recall that an implication \(P \imp Q\) is logically equivalent to its contrapositive \(\neg Q \imp \neg P\text<.>\) 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 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\text<.>\) Explain, explain, … explain. Therefore \(\neg P\text<.>\)As before, if there are variables and quantifiers, we set them to be arbitrary elements of our domain. Here are two examples:
This is the converse of the statement we proved above using a direct proof. From trying a few examples, this statement definitely appears to be true. So let’s prove it.
A direct proof of this statement would require fixing an arbitrary \(n\) and assuming that \(n^2\) is even. But it is not at all clear how this would allow us to conclude anything about \(n\text<.>\) Just because \(n^2 = 2k\) does not in itself suggest how we could write \(n\) as a multiple of 2.
Try something else: write the contrapositive of the statement. We get, for all integers \(n\text<,>\) if \(n\) is odd then \(n^2\) is odd. This looks much more promising. Our proof will look something like this:
Let \(n\) be an arbitrary integer. Suppose that \(n\) is not even. This means that …. In other words …. But this is the same as saying …. Therefore \(n^2\) is not even.
Now we fill in the details:We will prove the contrapositive. Let \(n\) be an arbitrary integer. Suppose that \(n\) is not even, and thus odd. Then \(n= 2k+1\) for some integer \(k\text<.>\) Now \(n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\text<.>\) Since \(2k^2 + 2k\) is an integer, we see that \(n^2\) is odd and therefore not even.
The problem with trying a direct proof is that it will be hard to separate \(a\) and \(b\) from knowing something about \(a+b\text<.>\) On the other hand, if we know something about \(a\) and \(b\) separately, then combining them might give us information about \(a+b\text<.>\) The contrapositive of the statement we are trying to prove is: for all integers \(a\) and \(b\text\) if \(a\) and \(b\) are even, then \(a+b\) is even. Thus our proof will have the following format:
Let \(a\) and \(b\) be integers. Assume that \(a\) and \(b\) are both even. la la la. Therefore \(a+b\) is even.
Here is a complete proof:Let \(a\) and \(b\) be integers. Assume that \(a\) and \(b\) are even. Then \(a = 2k\) and \(b = 2l\) for some integers \(k\) and \(l\text<.>\) Now \(a + b = 2k + 2l = 2(k+l)\text<.>\) Since \(k + l\) is an integer, we see that \(a + b\) is even, completing the proof.
Note that our assumption that \(a\) and \(b\) are even is really the negation of \(a\) or \(b\) is odd. We used De Morgan’s law here.
We have seen how to prove some statements in the form of implications: either directly or by contrapositive. Some statements are not written as implications to begin with.
Consider the following statement: for every prime number \(p\text<,>\) either \(p = 2\) or \(p\) is odd. We can rephrase this: for every prime number \(p\text<,>\) if \(p \ne 2\text<,>\) then \(p\) is odd. Now try to prove it.
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\text<.>\) 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\text<.>\) 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\text\) It must be false as well, which makes \(P\) true!
This is why 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.