Proof by Contradiction
Proving Statements by Contradiction
As we discussed when we first introduced the concept of a mathematical statement, it MUST be the case that a statement is either true or false (but not both or neither). So, if one is trying to prove a statement \(P\), one course of action could be to assume that \(P\) is false, and then, using that assumption, prove that some other mathematical statement \(Q\) (that is already known to be absolutely and undeniably true) is false. Since \(Q\) is already known to be true, and because our reasoning from \(\neg P\) is logically correct, the only thing that could have “gone wrong” is our initial assumption that \(P\) was false!
Let’s illustrate this method of proof with a verbal example. Suppose I want to prove the statement
“I am not allergic to pizza.”
A proof by contradiction could go as follows:
Suppose, for the sake of argument (or “the sake of contradiction”), that I AM allergic to pizza. Then, since pizzas consist of a simple tomato sauce, mozzarella cheese, and (essentially) white bread, I must be allergic to at least one of these ingredients. Suppose I am allergic to tomato sauce. Then, based on this assumption, I should have died yesterday when I ate three platefuls of spaghetti and meatballs, because tomato sauce is (usually) a less complicated marinara. I stand here before you having not risen from the dead. Speaking of “rising,” suppose I am allergic to white bread. That massive baguette I ate with my spaghetti, too, should have killed me, and yet I live on. Lastly, I can’t be allergic to mozzarella cheese the mozarella stuffed cheese sticks I ate last night around 2am should have killed me, but they didn’t! Therefore, we have contradicted the fact that I must be allergic to at least one of the ingredients of pizza, and therefore have proved that I am not allergic to pizza. QED.
Technically, the above has several mini “proofs by contradiction” baked into it with the argument made for each ingredient. The above argument somewhat indicates why “Proof by contradiction” is often called “Reducto ad absurdum” in more philosophical circles.
Proving More Mathematical Statements by Contradiction
We don’t really have much to work with here, nor can we really make any assumptions to prove this statement directly. So, we will prove this by contradiction, and use an argument employed by every elementary school teacher to prove there is no greatest number.
Proof (by contradiction): Suppose not. That is, suppose there IS a greatest natural number; call it \(n\). Then let \(m=n+1\). Certainly, adding \(1\) to a number results in a number greater than the first (i.e. \(m>n\)). But this immediately contradicts the original assumption that \(n\) was the greatest natural number (we constructed a bigger natural number). Therefore, the original assumption must be false, and we can thus conclude that there is indeed no largest natural number.
Note that, as stated, we really don’t have many facts to work with. All we really have to go with is what little we know about \(\sqrt{2}\), specifically that \(\sqrt{2}^2=2\), but this too isn’t much. However, if we suppose the OPPOSITE, namely that \(\sqrt{2}\) is rational… now THAT gives us something to work with.
Proof: Suppose for the sake of contradiction that \(\sqrt{2}\) is rational. We will show that this leads to a contradiction (i.e. a mathematical impossibility). Then, since \(\sqrt{2}\) is rational, there are integers \(n\) and \(m\) (with \(m\neq 0\)) such that
$$\sqrt{2}=\frac{n}{m}.$$
where \(\frac{n}{m}\) is a fraction in lowest terms (i.e. \(gcd(n,m)=1\), i.e. \(n\) and \(m\) share no common factors; i.e. the fraction cannot be reduced). Squaring both sides gives us
$$\begin{align}\sqrt{2}^2&=\left(\frac{n}{m}\right)^2\\2&=\frac{n^2}{m^2}\end{align}$$
Multiplying both sides of this equation by \(m^2\) gives us
$$2m^2=n^2$$
This implies that \(n^2\) is even (since it equals a multiple of \(2\)). In one of the examples in the last lesson (on proof by contrapositive) we proved that “if \(n^2\) is even, then \(n\) is even.” Using this fact, we have that \(n=2k\) for some integer \(k\). Then the last equation gives us
$$2m^2=(2k)^2=2^2k^2=4k^2.$$
Dividing both sides by \(2\) gives us \(m^2=2k^2\), which implies that \(2\) divides \(m^2\). By the fact we used earlier (“if \(n^2\) is even, then \(n\) is even”), we have that \(m\) is even.
So thus far, we have shown that \(n\) and \(m\) both have a factor of \(2\) (i.e. they’re both even), which contradicts the original assumption that \(\sqrt{2}=\frac{n}{m}\) is an irreducible fraction (i.e. \(n\) and \(m\) have no common factors).
Therefore, we can conclude that the original assumption was false, namely that \(\sqrt{2}\) is rational. Thus, it follows that \(\sqrt{2}\) must be irrational. QED
\(n^2\) is odd AND \(n\) is even.
Proof: Suppose for the sake of contradiction that \(n^2\) is odd and that \(n\) is even. Then, there are integers \(m\) and \(k\) such that \(n^2=2m+1\) and \(n=2k\). Substituting \(n=2k\) into the equation \(n^2=2m+1\) gives us
$$(2k)^2=2m+1$$
which implies that \(2^2k^2=4k^2=2m+1\) (distributing the power to each factor of the left-hand-side of the equation above). Now, notice that subtracting \(2m\) from both sides of the last equation gives us
$$4k^2-2m=1.$$
But this implies that \(2(2k^2-m)=1\) and therefore that \(2\vert 1\), since \(2k^2-m\) is an integer. Therefore, since the only two numbers that divide \(1\) are \(1\) and \(-1\), it follows that \(2=1\) or \(2=-1\), which is absurd (i.e. a contradiction). Therefore, we can conclude that the initial assumption, that is “\(n^2\) is odd AND \(n\) is even” was fallacious, and therefore that the original statement “If \(n^2\) is odd, then \(n\) is odd” must be true.
“The sum of a rational number and an irrational number is rational”
Proof: Suppose not. That is, suppose that the sum of a rational number \(r\) and an irrational number \(i\) is rational. Then, this implies that \(r=\frac{n}{m}\) for some integers \(n\) and \(m\), where \(m\neq 0\), and that \(r+i=\frac{p}{q}\) where \(p\) and \(q\) are integers and \(q\neq 0\). Substituting \(r=\frac{n}{m}\) into the equation \(r+i=\frac{p}{q}\), we get
$$\frac{n}{m}+i=\frac{p}{q}.$$
Subtracting \(\frac{n}{m}\) from both sides, and then finding a common denominator gives
$$i=\frac{p}{q}-\frac{n}{m}=\frac{mp-nq}{qm}.$$
Note that \(mp-nq\) and \(qm\) are integers (because products and differences of integers are integers). Therefore, the above equation \(i=\frac{mp-nq}{qm}\) indicates that \(i\) is rational. This is a contradiction because we assumed that \(i\) is irrational.
Therefore, we can conclude that the original statement “the sum of a rational number and an irrational number is irrational” is true.
We assume that the opposite of the original statement “If \(p\vert n\) then \(p\not| (n+1)\)”, namely “\(p\vert n\) AND \(p\vert (n+1)\)” is true. We then show that this leads to a contradiction/mathematical impossibility.
Proof: Suppose for the sake of contradiction that \(p\vert n\) and \(p\vert (n+1)\). Then, this implies that \(n=pm\) for some integer \(m\), and that \((n+1)=pk\) for some integer \(k\). Then, substituting \(n=pm\) into the equation \((n+1)=pk\) we get
$$pm+1=pk$$
Subtracting \(pm\) from both sides gives us
$$1=pk-pm$$
Factoring out \(p\) gives us \(1=p(k-m)\) which implies \(p\) divides \(1\). The only numbers that divide \(1\) evenly are \(1\) and \(-1\). Therefore \(p=1\) or \(p=-1\). This is impossible since \(p\) is prime and primes are greater than or equal to \(2\), giving us the desired contradiction.
Therefore, we can conclude that the original statement, “If \(p\vert n\) then \(p\not| (n+1)\),” is true. QED.