\). Since it is an implication, we could use a direct proof: Assume \(\overline\) is true (hence, assume \(q\) is false). Show that \(\overline
\) is true (that is, show that \(p\) is false). The proof may proceed as follow:
Proof: We want to prove the contrapositive of the stated result. Assume \(q\) is false, . . . . . . . . . Therefore \(p\) is false.
Example \(\PageIndex<1>\label\) Let \(n\) be an integer. Show that if \(n^2\) is even, then \(n\) is also even. Solution Proof by contrapositive: We want to prove that if \(n\) is odd, then \(n^2\) is odd. If \(n\) is odd, then \(n=2t+1\) for some integer \(t\). Hence, \[n^2 = 4t^2+4t+1 = 2(2t^2+2t)+1\] is odd. This completes the proof.
Example \(\PageIndex<2>\label\) Show that if \(n\) is a positive integer such that the sum of its positive divisors is \(n+1\), then \(n\) is prime. Solution We shall prove the contrapositive of the given statement. We want to prove that if \(n\) is composite, then the sum of its positive divisors is not \(n+1\). Let \(n\) be a composite number. Then its divisors include 1, \(n\), and at least one other positive divisor \(x\) different from 1 and \(n\). So the sum of its positive divisors is at least \(1+n+x\). Since \(x\) is positive, we gather that \[1+n+x > 1+n.\] We deduce that the sum of the divisors cannot be \(n+1\). Therefore, if the sum of the divisors of \(n\) is precisely \(n+1\), then \(n\) must be prime.
Example \(\PageIndex<3>\label\) Let \(x\) be a real number. Prove that if \(x^3-7x^2+x-7=0\), then \(x=7\). Solution Assume \(x\neq7\), then \[x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1) (x-7) \neq 0.\] Thus, if \(x^3-7x^2+x-7=0\), then \(x=7\).
hands-on exercise \(\PageIndex<1>\label\) Let \(x\) be a real number. Prove that if \((2x^2+3)(x+5)(x-7)=0\), then either \(x=-5\), or \(x=7\).
hands-on exercise \(\PageIndex<2>\label\) Let \(x\) and \(y\) be two real numbers. Prove that if \(x\neq0\) and \(y\neq0\), then \(xy\neq0\).
Another indirect proof is the proof by contradiction. To prove that \(p \Rightarrow q\), we proceed as follows: Suppose \(p\Rightarrow q\) is false; that is, assume that \(p\) is true and \(q\) is false. Argue until we obtain a contradiction, which could be any result that we know is false. How does this prove that \(p\Rightarrow q\)? Assuming that the logic used in every step in the argument is correct, yet we still end up with a contradiction, then the only possible flaw must come from the supposition that \(p\Rightarrow q\) is false. Consequently, \(p\Rightarrow q\) must be true. This is what a typical proof by contradiction may look like:
Proof: Suppose \( p \Rightarrow q\) is false. Then \(p\) is true and \(q\) is false. Then . . . . . . . . . which is a contradiction. Therefore, \( p \Rightarrow q\) must be true.
There is a more general form for proving a statement \(r\), which needs not be an implication. To prove the proposition \(r\) by contradiction, we follow these steps: Suppose \(r\) is false. Argue until we obtain a contradiction.
Proof: Suppose \(r\) is false. Then . . . . . . . . . which is a contradiction. Therefore, \(r\) must be true.
Example \(\PageIndex<4>\label\) Show that if \(x^3-7x^2+x-7=0\), then \(x=7\). Solution Assume \(x^3-7x^2+x-7=0\), we want to show that \(x=7\). Suppose \(x\neq7\), then \(x-7\neq0\), and \[0 = x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1)(x-7)\] would have implied that \(x^2+1=0\), which is impossible. Therefore, we must have \(x=7\).
Example \(\PageIndex<5>\label\) Show that if \(P\) is a point not on a line \(L\), then there exists exactly one perpendicular line from \(P\) onto \(L\). Solution Suppose we can find more than one perpendicular line from \(P\) onto \(L\). Pick any two of them, and denote their intersections with \(L\) as \(Q\) and \(R\). Then we have a triangle \(PQR\), where the angles \(PQR\) and \(PRQ\) are both \(90^\circ\). This implies that the sum of the interior angles of the triangle \(PQR\) exceeds \(180^\circ\), which is impossible. Hence, there is only one perpendicular line from \(P\) onto \(L\).
Example \(\PageIndex<6>\label\) Show that if \(x^2\). Solution Assume \(x^2\). Suppose, on the contrary, we have \(|x|\geq\sqrt\). Then either \(x\geq\sqrt\), or \(x\leq-\sqrt\). If \(x\geq\sqrt\), then \(x^2\geq5\). If \(x\leq-\sqrt\), we again have \(x^2\geq5\). In either case, we have a contradiction. Hence \(|x|<\sqrt\).
hands-on exercise \(\PageIndex<3>\label\) Prove that if \(x^2\geq49\), then \(|x|\geq7\).For the conjunction \((p\Rightarrow q) \wedge p\) to be true, we need
Having \(p\) true and \(q\) false would make \(p\Rightarrow q\) false. This directly contradicts what we have found. Therefore, the logical formula \([(p\Rightarrow q) \wedge p] \Rightarrow q\) is always true, hence it is a tautology.
Prove, by contradiction, that if \(x\) is rational and \(y\) is irrational, then \(x+y\) is irrational.
Solution
Let \(x\) be a rational number and \(y\) an irrational number. We want to show that \(x+y\) is irrational. Suppose, on the contrary, that \(x+y\) is rational. Then \[x+y = \frac\] for some integers \(m\) and \(n\), where \(n\neq0\). Since \(x\) is rational, we also have \[x = \frac
\] for some integers \(p\) and \(q\), where \(q\neq0\). It follows that \[\frac = x+y = \frac
+ y.\] Hence, \[y = \frac-\frac
= \frac,\] where \(mq-np\) and \(nq\) are both integers, with \(nq\neq0\). This makes \(y\) rational, which contradicts the assumption that \(y\) is irrational. Thus, \(x+y\) cannot be rational, it must be irrational.
Prove that \[\sqrt \neq \sqrt+\sqrt\] for any positive real numbers \(x\) and \(y\).
Hint
The words “for any” suggest this is a universal quantification. Be sure you negate the problem statement properly.
Prove that \(\sqrt\) is irrational.
Solution
Suppose, on the contrary, \(\sqrt\) is rational. Then we can write \[\sqrt = \frac\] for some positive integers \(m\) and \(n\) such that \(m\) and \(n\) do not share any common divisor except 1 (hence \(\frac\) is in its simplest term). Squaring both sides and cross-multiplying yields \[2n^2 = m^2.\] Thus, 2 divides \(m^2\). Consequently, 2 must also divide \(m\). Then we can write \(m=2s\) for some integer \(s\). The equation above becomes \[2n^2 = m^2 = (2s)^2 = 4s^2.\] Hence, \[n^2 = 2s^2,\] which implies that 2 divides \(n^2\); thus, 2 also divides \(n\). We have proved that both \(m\) and \(n\) are divisible by 2. This contradicts the assumption that \(m\) and \(n\) do not share any common divisor. Therefore, \(\sqrt\) must be irrational.
Prove that \(\sqrt\) is irrational.
Very often, a proof by contradiction can be rephrased into a proof by contrapositive or even a direct proof, both of which are easier to follow. If this is the case, rewrite the proof.
Show that \(x^2+4x+6=0\) has no real solution. In symbols, show that \(\nexists x\in\mathbb,(x^2+4x+6=0)\).
Solution
Consider the following proof by contradiction:
Suppose there exists a real number \(x\) such that \(x^2+4x+6=0\).
Using calculus, it can be shown that the function $f(x)=x^2+4x+6$
has an absolute minimum at \(x=-2\). Thus, \(f(x) \geq f(-2) = 2\) for
any \(x\). This contradicts the assumption that there exists an \(x\)
such that \(x^2+4x+6=0\). Thus, \(x^2+4x+6=0\) has no real solution.
A close inspection reveals that we do not really need a proof by contradiction. The crux of the proof is the fact that \(x^2+4x+6 \geq 2\) for all \(x\). This already shows that \(x^2+4x+6\) could never be zero. It is easier to use a direct proof, as follows.
Using calculus, we find that the function \(f(x)=x^2+4x+6\) has an
absolute minimum at \(x=-2\). Therefore, for any \(x\), we always have
\(f(x) \geq f(-2) = 2\). Hence, there does not exist any \(x\) such that
\(x^2+4x+6=0\).
Do you agree that the second proof (the direct proof) is more elegant?
Recall that a biconditional statement \(p\Leftrightarrow q\) consists of two implications \(p\Rightarrow q\) and \(q\Rightarrow p\). Hence, to prove \(p\Leftrightarrow q\), we need to establish these two “directions” separately.
Let \(n\) be an integer. Prove that \(n^2\) is even if and only if \(n\) is even.
Solution
(\(\Rightarrow\)) We first prove that if \(n^2\) is even, then \(n\) must be even. We shall prove its contrapositive: if \(n\) is odd, then \(n^2\) is odd. If \(n\) is odd, then we can write \(n=2t+1\) for some integer \(t\). Then \[n^2 = (2t+1) = 4t^2+4t+1 = 2(2t^2+2t)+1,\] where \(2t^2+2t\) is an integer. Thus, \(n^2\) is odd.
(\(\Leftarrow\)) Next, we prove that if \(n\) is even, then \(n^2\) is even. If \(n\) is even, we can write \(n=2t\) for some integer \(t\). Then \[n^2 = (2t)^2 = 4t^2 = 2\cdot 2t^2,\] where \(2t^2\) is an integer. Hence, \(n^2\) is even, which completes the proof.
Let \(n\) be an integer. Prove that \(n\) is odd if and only if \(n^2\) is odd.
Let \(n\) be an integer. Prove that if \(n^2\) is even, then \(n\) must be even. Use
The two proofs are very similar, but the wording is slightly different, so be sure you present your proofs clearly.
Let \(n\) be an integer. Show that if \(n^2\) is a multiple of 3, then \(n\) must also be a multiple of 3. Use
Let \(n\) be an integer. Prove that if \(n\) is even, then \(n^2=4s\) for some integer \(s\).
Let \(m\) and \(n\) be integers. Show that \(mn=1\) implies that \(m=1\) or \(m=-1\).
Let \(x\) be a real number. Prove by contrapositive: if \(x\) is irrational, then \(\sqrt\) is irrational. Apply this result to show that \(\sqrt[4]\) is irrational, using the assumption that \(\sqrt\) is irrational.
Let \(x\) and \(y\) be real numbers such that \(x\neq0\). Prove that if \(x\) is rational, and \(y\) is irrational, then \(xy\) is irrational.
Prove that \(\sqrt\) is irrational.
Prove that \(\sqrt[3]\) is irrational.
Let \(a\) and \(b\) be real numbers. Show that if \(a\neq b\), then \(a^2+b^2 \neq 2ab\).
Use contradiction to prove that, for all integers \(k\geq1\), \[2\sqrt + \frac<\sqrt> \geq 2\sqrt.\]
Let \(m\) and \(n\) be integers. Show that \(mn\) is even if and only if \(m\) is even or \(n\) is even.
Let \(x\) and \(y\) be real numbers. Show that \(x^2+y^2=0\) if and only if \(x=0\) and \(y=0\).
Prove that, if \(x\) is a real number such that \(0\).
Let \(m\) and \(n\) be positive integers such that 3 divides \(mn\). Show that 3 divides \(m\), or 3 divides \(n\).
Prove that the logical formula \[(p\Rightarrow q) \vee (p\Rightarrow \overline)\] is a tautology.
Prove that the logical formula \[[(p\Rightarrow q) \wedge (p\Rightarrow \overline)] \Rightarrow \overline
\] is a tautology.
This page titled 3.3: Indirect Proofs is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .
