The purpose of a proof in mathematics is to convince a reader (or a listener) that a certain statement is true. So, besides being correct, it must be understandable and as easy as possible to follow. Usually we are interested in proving that a statement of the form \({\cal P} \Rightarrow {\cal Q}\) is true, where \(\cal P\) is a statement containing all the assumptions and \(\cal Q\) is a statement containing the conclusions. We will discuss four different types of proofs, with examples.
Subsection1.5.1Direct proofs
In this type of proof, if we want to prove that \({\cal P} \Rightarrow {\cal Q}\) is true, we derive logical consequences from the assumptions contained in \(\cal P\) until we reach the conclusion that \(\cal Q\) is true.
Example1.5.1.
Prove that if \(n\) is an even integer, then \(3n\) is divisible by 6.
In this problem, the given assumptions consist in the statement
\begin{equation*}
{\cal P}: n \mbox{ is an even integer}
\end{equation*}
the conclusion is the statement
\begin{equation*}
{\cal Q}: 3n \mbox{ is divisible by 6}
\end{equation*}
and we want to prove \({\cal P}\Rightarrow {\cal Q}\text{.}\) Think about what it means for \(n\) to be even.
Proof We start deriving logical conclusions. \(\cal P\) is saying that \(n\) is even, so we can write \(n=2m\) for some integer \(m\text{.}\) Then \(3n=3(2m)=6m\text{.}\) But this means that \(3n\) is divisible by 6. So we conclude that \(\cal Q\) is true.
Subsection1.5.2Contrapositive
Instead of proving \({\cal P} \Rightarrow {\cal Q }\text{,}\) it is sometimes easier to prove its contrapositive \(\sim {\cal Q} \Rightarrow \sim{\cal P }\text{.}\) The two statements are logically equivalent, so proving one we also prove the other.
Example1.5.2.
Suppose that \(n\) is a positive integer. Prove that if \(n^2\) is even, then \(n\) is even.
We start assuming \(n\) is a positive integer and we let
\begin{equation*}
{\cal P}: n^2 \mbox{ is even },
\end{equation*}
\begin{equation*}
{\cal Q}: n \mbox{ is even }.
\end{equation*}
Now write the contrapositive of \({\cal P}\Rightarrow {\cal Q}\) and use a direct proof.
Proof We want to prove \({\cal P} \Rightarrow {\cal Q }\text{.}\) But if we start by assuming that \(n^2\) is even, that is, \(n^2=2m\) for some \(m\text{,}\) it is not clear what we should do next. It would be a lot easier if we could start with a statement about \(n\text{,}\) not \(n^2\text{.}\) Since \(\sim {\cal Q}: n \mbox{ is odd }\) and \(\sim {\cal P}: n^2 \mbox{ is odd }\text{,}\) the contrapositive says that if \(n\) is odd, then \(n^2\) is also odd. So we start by assuming that \(n\) is odd. This means that \(n=2m+1\) for some integer \(m\text{.}\) But then \(n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1\) and we can re-write \(n^2=2k+1\) where \(k=2m^2+2m\) is an integer. So we see that \(n^2\) is also odd, and we conclude that \(\sim {\cal Q} \Rightarrow \sim{\cal P }\) is true, and so \({\cal P} \Rightarrow {\cal Q }\) is also true and we are done.
Subsection1.5.3Contradiction
Suppose we know that a statement \(\cal Q\) is false. If we can prove that \(\sim {\cal P} \Rightarrow {\cal Q }\text{,}\) then \(\sim {\cal P}\) cannot be true (because it leads to a false statement), and so \(\cal P\) must be true. Usually we do not know what the false statement \(\cal Q\) is at the beginning of a proof by contradiction. The strategy is to start from the negation of the statement we want to prove, then derive logical consequences until we reach a statement that we recognize as false. We then say that we have reached a contradiction, and the original statement must be true.
We want to prove the statement \({\cal P}: \sqrt{2}\not \in {\mathbb Q}\text{.}\) We give hints for two different proofs, both by contradiction.
Assume \(\sqrt{2}\in {\mathbb Q}\) and write it as a fraction in lowest terms. Then multiply by the denominator, and square the equation.
If \(\sqrt{2}\in {\mathbb Q}\text{,}\) then the set \(\{n\in {\mathbb N}: n\sqrt{2}\in {\mathbb N}\}\) is not empty, and if \(m\) is its least element, consider \(m\sqrt{2} -m\)
Proof
Assume that \(\sim {\cal P}: \sqrt{2}\in {\mathbb Q}\) is true. This means that \(\sqrt{2}=\frac{n}{m}\) where \(n\) and \(m\) are integers. Now let \(d=\gcd(m,n)\text{.}\) Then we can write \(n=du, m=dv\text{,}\) where \(\gcd(u,v)=1\text{,}\) and \(\sqrt{2}=\frac{n}{m}=\frac{du}{dv}=\frac{u}{v}\text{,}\) and \(\frac{u}{v}\) is a fraction in lowest terms. Squaring the equation \(\sqrt{2}=\frac{u}{v}\text{,}\) we find that \(2=\frac{u^2}{v^2}\text{,}\) that is the same as \(u^2=2v^2\text{.}\) Since \(v^2\) is an integer, this is telling us that \(u^2\) is even. By Example 1.5.2, \(u\) must be even. So we can write \(u=2k\) for some integer \(k\text{.}\) But then we find \((2k)^2=2v^2\text{,}\) or \(4k^2=2v^2\text{,}\) and dividing this equation by 2, we get \(2k^2=v^2\text{.}\) But this means that \(v\) is also even, and we reach the conclusion that \(u\) and \(v\) are both even. We know this to be false, because the fraction \(\frac{u}{v}\) is in lowest terms. So we have reached a contradiction, and we conclude that \(\sqrt{2}\) is not a rational number.
Let \(m\) be the least element of the set \(S=\{n\in {\mathbb N}: n\sqrt{2}\in {\mathbb N}\}\text{.}\) Then \(m\sqrt{2} -m\) is smaller than \(m\text{,}\) but it is also in \(S\text{,}\) because \((m\sqrt{2}-m)\sqrt{2}=2m-m\sqrt{2} \in {\mathbb N}\text{.}\) This is a contradiction.
Subsection1.5.4Induction
A useful way to prove statements that involve positive integers is by induction, as is discussed in the Discrete course. We will now review the concepts involved, and state our first theorem.
Theorem1.5.4.Principle of Mathematical Induction.
Suppose that for each positive integer \(n\text{,}\)\({\cal P}(n)\) is a statement. Suppose that \({\cal P}(1)\) is true and\({\cal P}(n)\Rightarrow {\cal P}(n+1)\) for all \(n\in {\mathbb N}\text{.}\) Then \({\cal P}(n)\) is true for all \(n\in {\mathbb N}\text{.}\)
It’s important to note that in the Principle of Mathematical Induction (that we abbreviate as PMI) there are three statements involved:
\({\cal P}(1)\) is true
\({\cal P}(n)\Rightarrow {\cal P}(n+1)\) for all \(n\in {\mathbb N}\)
\({\cal P}(n)\) is true for all \(n\in {\mathbb N}\text{.}\)
and the PMI says that if both a. and b. are true, then c. is true. So the PMI is the implication statement:
(a. and b.) \(\Rightarrow \) c.
The implication \({\cal P}(n)\Rightarrow {\cal P}(n+1)\) is often called the induction step and it is usually here that the hard part of the proof is found. When proving the induction step, the statement \({\cal P}(n)\) is called the induction hypothesis.
The PMI is a theorem because it can be proved from the Well-Ordering Principle. In fact, we could also take a different point of view. We could say that the PMI is an axiom, and then the WOP can be proved from it. In other words, WOP and PMI are equivalent statements. They cannot both be proved, but if we assume one as an axiom, then the other follows as a theorem.
Example1.5.5.
Prove that \(n\lt 2^n\) for all positive integers \(n\text{.}\)
Write down what the statement \({\cal P}(n)\) is, check that \({\cal P}(1)\) is true, and then prove \({\cal P}(n+1)\) assuming that \({\cal P}(n)\) is true.
Proof Let \({\cal P}(n): n\lt 2^n\text{,}\) and this is statement c. in our discussion of PMI above. Statement a. is \({\cal P}(1): 1\lt 2^1\text{,}\) which is surely true. So if we prove the induction step b., that is: \({\cal P}(n)\Rightarrow {\cal P}(n+1)\text{,}\) then we are done, because PMI tells us that a. and b. imply c.
So we start by assuming the induction hypothesis, that is \(n\lt 2^n\text{.}\) Then we note that, for any \(n\gt 1\text{,}\)\(n+1\lt n+n=2n\text{.}\) Since we are assuming \(n\lt2^n\text{,}\) we find \(n+1\lt 2n \lt 2(2^n) = 2^{n+1}\text{,}\) so that \({\cal P}(n+1)\) is true. We have now shown that \({\cal P}(n+1)\) follows from \({\cal P}(n)\text{,}\) or \({\cal P}(n)\Rightarrow {\cal P}(n+1)\text{,}\) and that is statement b., and so by the PMI we conclude that c. is true.
If you work on the proof in the previous example, you will find that a crucial step is the statement that \(n+1\lt n+n\) for every positive integer \(n\gt 1\text{.}\) While this is obvious once we see it, it’s not so easy to think of it as a necessary step in the proof. This is a fact with a lot of mathematical proofs. The crucial idea behind a proof is often the result of some insight that can only come with a lot of practice and experience.
Subsection1.5.5Cases in proofs
It often happens that a statement is most easily understood and proved if we break it down into two or more cases, as the next example illustrates.
Example1.5.6.
Prove that for every positive integer \(n\text{,}\) the fraction \(\frac{n(n+1)}{2}\text{,}\) in spite of its appearance, is actually an integer.
