3.3: Proof by Contradiction
- Page ID
- 7048
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Preview Activity 1 (Proof by Contradiction)
In Section 2.1, we defined a tautology to be a compound statement \(S\) that is true for all possible combinations of truth values of the component statements that are part of S. We also defined contradiction to be a compound statement that is false for all possible combinations of truth values of the component statements that are part of \(S\).
That is, a tautology is necessarily true in all circumstances, and a contradiction is necessarily false in all circumstances.
- Use truth tables to explain why \(P \vee \urcorner P\) is a tautology and \(P \wedge \urcorner P\) is a contradiction.
Another method of proof that is frequently used in mathematics is a proof by contradiction. This method is based on the fact that a statement \(X\) can only be true or false (and not both). The idea is to prove that the statement \(X\) is true by showing that it cannot be false. This is done by assuming that \(X\) is false and proving that this leads to a contradiction. (The contradiction often has the form \(R \wedge \urcorner R\), where \(R\) is some statement.) When this happens, we can conclude that the assumption that the statement \(X\) is false is incorrect and hence \(X\) cannot be false. Since it cannot be false, then \(X\) must be true.
A logical basis for the contradiction method of proof is the tautology \[[\urcorner X \to C] \to X,\] where \(X\) is a statement and \(C\) is a contradiction. The following truth table establishes this tautology.\(X\) \(C\) \(\urcorner X\) \(\urcorner X \to C\) \((\urcorner X \to C) \to X\) T F F T T F F T F T
This tautology shows that if \(\urcorner X\) leads to a contradiction, then \(X\) must be true. The previous truth table also shows that the statement \(\urcorner X \to C\) is logically equivalent to \(X\). This means that if we have proved that \(\urcorner X\) leads to a contradiction, then we have proved statement \(X\). So if we want to prove a statement \(X\) using a proof by contradiction, we assume that \(\urcorner X\) is true and show that this leads to a contradiction.When we try to prove the conditional statement, “If \(P\) then \(Q\)” using a proof by contradiction, we must assume that \(P \to Q\) is false and show that this leads to a contradiction.
- Use a truth table to show that \(\urcorner (P \to Q)\) is logical equivalent to \(P \wedge \urcorner Q\).
The preceding logical equivalency shows that when we assume that \(P \to Q\) is false, we are assuming that \(P\) is true and \(Q\) is false. If we can prove that this leads to a contradiction, then we have shown that \(\urcorner (P \to Q)\) is false and hence that \(P \to Q\) is true. - Given a counterexample to show that the following statement is false.
For each real number \(x\), \(\dfrac{1}{x(1 - x)} \ge 4\). - When a statement is false, it is sometimes possible to add an assumption that will yield a true statement. This is usually done by using a conditional statement. So instead of working with the statement in (3), we will work with a related statement that is obtained by adding an assumption (or assumptions) to the hypothesis.
For each real number \(x\), if \(0 < x < 1\), then \(\dfrac{1}{x(1 - x)} \ge 4\).
To begin a proof by contradiction for this statement, we need to assume the negation of the statement. To do this, we need to negate the entire statement, including the quantifier. Recall that the negation of a statement with a universal quantifier is a statement that contains an existential quantifier. (See Theorem 2.16 on page 67). With this in mind, carefully write down all assumptions made at the beginning of a proof by contradiction for this statement.
Preview Activity 2 (Constructing a Proof by Contradiction)
Consider the following proposition:
Proposition. For all real numbers \(x\) and \(y\), if \(x \ne y\), \(x > 0\), and \(y > 0\), then \(\dfrac{x}{y} + \dfrac{y}{x} > 2\).
To start a proof by contradiction, we assume that this statement is false; that is, we assume the negation is true. Because this is a statement with a universal quantifier, we assume that there exist real numbers \(x\) and \(y\) such that \(x \ne y\), \(x > 0\), \(y > 0\) and that \(\dfrac{x}{y} + \dfrac{y}{x} \le 2\). (Notice that the negation of the conditional sentence is a conjunction.)
For this proof by contradiction, we will only work with the know column of a know-show table. This is because we do not have a specific goal. The goal is to obtain some contradiction, but we do not know ahead of time what that contradiction will be. Using our assumptions, we can perform algebraic operations on the inequality
\[\dfrac{x}{y} + \dfrac{y}{x} \le 2\]
until we obtain a contradiction.
- Try the following algebraic operations on the inequality in (2). First, multiply both sides of the inequality by \(xy\), which is a positive real number since \(x > 0\) and \(y > 0\). Then, subtract \(2xy\) from both sides of this inequality and finally, factor the left side of the resulting inequality.
- Explain why the last inequality you obtained leads to a contradiction.
By obtaining a contradiction, we have proved that the proposition cannot be false, and hence, must be true.
Writing Guidelines: Keep the Reader Informed
A very important piece of information about a proof is the method of proof to be used. So when we are going to prove a result using the contrapositive or a proof by contradiction, we indicate this at the start of the proof.
- We will prove this result by proving the contrapositive of the statement.
- We will prove this statement using a proof by contradiction.
- We will use a proof by contradiction.
We have discussed the logic behind a proof by contradiction in the preview activities for this section. The basic idea for a proof by contradiction of a proposition is to assume the proposition is false and show that this leads to a contradiction. We can then conclude that the proposition cannot be false, and hence, must be true. When we assume a proposition is false, we are, in effect, assuming that its negation is true. This is one reason why it is so important to be able to write negations of propositions quickly and correctly. We will illustrate the process with the proposition discussed in Preview Activity \(\PageIndex{1}\).
For each real number \(x\), if \(0 < x < 1\), then \(\dfrac{1}{x(1 - x)} \ge 4\)
- Proof
-
We will use a proof by contradiction. So we assume that the proposition is false, or that there exists a real number \(x\) such that \(0 < x < 1\) and
\[\dfrac{1}{x(1 - x)} < 4.\]
We note that since \(0 < x < 1\), we can conclude that \(x > 0\) and that \((1 - x) > 0\). Hence, \(x(1 - x) > 0\) and if we multiply both sides of inequality (1) by \(x(1 - x)\), we obtain
\(1 < 4x(1 - x).\)
We can now use algebra to rewrite the last inequality as follows:
\(1 < 4x - 4x^2\)
\(4x^2 - 4x + 1 < 0\)
\((2x - 1)^2 < 0\)
However, \((2x - 1)\) is a real number and the last inequality says that a real number squared is less than zero. This is a contradiction since the square of any real number must be greater than or equal to zero. Hence, the proposition cannot be false, and we have proved that for each real number \(x\), if \(0 < x < 1\), then \(\dfrac{1}{x(1 - x)} \ge 4\).
One of the most important parts of a proof by contradiction is the very first part, which is to state the assumptions that will be used in the proof by contradiction. This usually involves writing a clear negation of the proposition to be proven. Review De Morgan’s Laws and the negation of a conditional statement in Section 2.2. (See Theorem 2.8 on page 48.) Also, review Theorem 2.16 (on page 67) and then write a negation of each of the following statements. (Remember that a real number is “not irrational” means that the real number is rational.)
- For each real number \(x\), if \(x\) is irrational, then \(\sqrt[3] x\) is irrational.
- For each real number \(x\), \((x + \sqrt 2)\) is irrational or \((-x + \sqrt 2)\) is irrational.
- For all integers \(a\) and \(b\), if 5 divides \(ab\), then 5 divides \(a\) or 5 divides \(b\).
- For all real numbers \(a\) and \(b\), if \(a > 0\) and \(b > 0\), then \(\dfrac{2}{a} + \dfrac{2}{b} \ne \dfrac{4}{a + b}\).
- Answer
-
Add texts here. Do not delete this text first.
A proof by contradiction is often used to prove a conditional statement \(P \to Q\) when a direct proof has not been found and it is relatively easy to form the negation of the proposition. The advantage of a proof by contradiction is that we have an additional assumption with which to work (since we assume not only \(P\) but also \(\urcorner Q\)). The disadvantage is that there is no well-defined goal to work toward. The goal is simply to obtain some contradiction. There usually is no way of telling beforehand what that contradiction will be, so we have to stay alert for a possible absurdity. Thus, when we set up a know-show table for a proof by contradiction, we really only work with the know portion of the table.
Consider the following proposition:
For each integer \(n\), if \(n \equiv 2\) (mod 4), then \(n \not\equiv 3\) (mod 6).
- Determine at least five different integers that are congruent to 2 modulo 4, and determine at least five different integers that are congruent to 3 modulo 6. Are there any integers that are in both of these lists?
- For this proposition, why does it seem reasonable to try a proof by contradiction?
- For this proposition, state clearly the assumptions that need to be made at the beginning of a proof by contradiction, and then use a proof by contradiction to prove this proposition.
- Answer
-
Add texts here. Do not delete this text first.
Proving that Something Does Not Exist
In mathematics, we sometimes need to prove that something does not exist or that something is not possible. Instead of trying to construct a direct proof, it is sometimes easier to use a proof by contradiction so that we can assume that the something exists. For example, suppose we want to prove the following proposition:
For all integers \(x\) and \(y\), if \(x\) and \(y\) are odd integers, then there does not exist an integer \(z\) such that \(x^2 + y^2 = z^2\).
Notice that the conclusion involves trying to prove that an integer with a certain property does not exist. If we use a proof by contradiction, we can assume that such an integer z exists. This gives us more with which to work.
Complete the following proof of Proposition 3.17:
Proof. We will use a proof by contradiction. So we assume that there exist integers \(x\) and \(y\) such that \(x\) and \(y\) are odd and there exists an integer \(z\) such that \(x^2 + y^2 = z^2\). Since \(x\) and \(y\) are odd, there exist integers \(m\) and \(n\) such that \(x = 2m + 1\) and \(y = 2n + 1\).
- Use the assumptions that \(x\) and \(y\) are odd to prove that \(x^2 + y^2\) is even and hence, \(z^2\) is even. (See Theorem 3.7 on page 105.)
We can now conclude that \(z\) is even. (See Theorem 3.7 on page 105.) So there exists an integer \(k\) such that \(z = 2k\). If we substitute for \(x\), \(y\), and \(z\) in the equation \(x^2 + y^2 = z^2\), we obtain
\[(2m + 1)^2 + (2n + 1)^2 = (2k)^2.\] - Use the previous equation to obtain a contradiction. Hint: One way is to use algebra to obtain an equation where the left side is an odd integer and the right side is an even integer.
- Answer
-
Add texts here. Do not delete this text first.
Rational and Irrational Numbers
One of the most important ways to classify real numbers is as a rational number or an irrational number. Following is the definition of rational (and irrational) numbers given in Exercise (9) from Section 3.2.
A real number \(x\) is defined to be a rational number provided that there exist integers \(m\) and \(n\) with \(n \ne 0\) such that \(x = \dfrac{m}{n}\). A real number that is not a rational number is called an irrational number.
This may seem like a strange distinction because most people are quite familiar with the rational numbers (fractions) but the irrational numbers seem a bit unusual. However, there are many irrational numbers such as \(\sqrt 2\), \(\sqrt 3\), \(\sqrt[3] 2\), \(\pi\), and the number \(e\). We are discussing these matters now because we will soon prove that \(\sqrt 2\) is irrational in Theorem 3.20.
We use the symbol \(\mathbb{Q}\) to stand for the set of rational numbers. There is no standard symbol for the set of irrational numbers. Perhaps one reason for this is because of the closure properties of the rational numbers. We introduced closure properties in Section 1.1, and the rational numbers \(\mathbb{Q}\) are closed under addition, subtraction, multiplication, and division by nonzero rational numbers. This means that if \(x, y \in \mathbb{Q}\), then
- \(x + y\), \(xy\), and \(xy\) are in \(\mathbb{Q}\); and
- If \(y \ne 0\), then \(\dfrac{x}{y}\) is in \(\mathbb{Q}\).
The basic reasons for these facts are that if we add, subtract, multiply, or divide two fractions, the result is a fraction. One reason we do not have a symbol for the irrational numbers is that the irrational numbers are not closed under these operations. For example, we will prove that \(\sqrt 2\) is irrational in Theorem 3.20. We then see that
\(\sqrt 2 \sqrt 2 = 2\) and \(\dfrac{\sqrt 2}{\sqrt 2} = 1\).
which shows that the product of irrational numbers can be rational and the quotient of irrational numbers can be rational.
It is also important to realize that every integer is a rational number since any integer can be written as a fraction. For example, we can write \(3 = \dfrac{3}{1}\). In general, if \(n \in \mathbb{Z}\), then \(n = \dfrac{n}{1}\), and hence, \(n \in \mathbb{Q}\).
Because the rational numbers are closed under the standard operations and the definition of an irrational number simply says that the number is not rational, we often use a proof by contradiction to prove that a number is irrational. This is illustrated in the next proposition.
For all real numbers \(x\) and \(y\), if \(x\) is rational and \(x \ne 0\) and \(y\) is irrational, then \(x \cdot y\) is irrational.
- Proof
-
We will use a proof by contradiction. So we assume that there exist real numbers \(x\) and \(y\) such that \(x\) is rational, \(y\) is irrational, and \(x \cdot y\) is rational. Since \(x \ne 0\), we can divide by \(x\), and since the rational numbers are closed under division by nonzero rational numbers, we know that \(\dfrac{1}{x} \in \mathbb{Q}\). We now know that \(x \cdot y\) and \(\dfrac{1}{x}\) are rational numbers and since the rational numbers are closed under multiplication, we conclude that
\[\dfrac{1}{x} \cdot (xy) \in \mathbb{Q}\]
However, \(\dfrac{1}{x} \cdot (xy) = y\) and hence, \(y\) must be a rational number. Since a real number cannot be both rational and irrational, this is a contradiction to the assumption that \(y\) is irrational. We have therefore proved that for all real numbers \(x\) and \(y\), if \(x\) is rational and \(x \ne 0\) and \(y\) is irrational, then \(x \cdot y\) is irrational.
The Square Root of 2 Is an Irrational Number
The proof that the square root of 2 is an irrational number is one of the classic proofs in mathematics, and every mathematics student should know this proof. This is why we will be doing some preliminary work with rational numbers and integers before completing the proof. The theorem we will be proving can be stated as follows:
If \(r\) is a real number such that \(r^2 = 2\), then \(r\) is an irrational number.
This is stated in the form of a conditional statement, but it basically means that \(\sqrt 2\) is irrational (and that \(-\sqrt 2\) is irrational). That is, \(\sqrt 2\) cannot be written as a quotient of integers with the denominator not equal to zero.
In order to complete this proof, we need to be able to work with some basic facts that follow about rational numbers and even integers.
- Each integer \(m\) is a rational number since \(m\) can be written as \(m = \dfrac{m}{1}\).
- Notice that \(\dfrac{2}{3} = \dfrac{4}{6}\), since
\[\dfrac{4}{6} = \dfrac{2 \cdot 2}{3 \cdot 2} = \dfrac{2}{2} \cdot \dfrac{2}{3} = \dfrac{2}{3}\]
We can also show that \(\dfrac{15}{12} = \dfrac{5}{4}\), \(\dfrac{10}{-8} = \dfrac{-5}{4}\), and \(\dfrac{-30}{-16} = \dfrac{15}{8}\)
Item (2) was included to illustrate the fact that a rational number can be written as a fraction in "lowest terms" with a positive denominator. This means that any rational number can be written as a quotient \(\dfrac{m}{n}\), where \(m\) and \(n\) are integers, \(n > 0\), and \(m\) and \(n\) have no common factor greater than 1. - If \(n\) is an integer and \(n^2\) is even, what can be conclude about \(n\). Refer to theorem 3.7 on page 105.
In a proof by contradiction of a conditional statement \(P \to Q\), we assume the negation of this statement or \(P \wedge \urcorner Q\). So in a proof by contradiction of Theorem 3.20, we will assume that \(r\) is a real number, \(r^2 = 2\), and \(r\) is not irrational (that is, \(r\) is rational).
If \(r\) is a real number such that \(r^2 = 2\), then \(r\) is an irrational number.
- Proof
-
We will use a proof by contradiction. So we assume that the statement of the theorem is false. That is, we assume that
\(r\) is a real number, \(r^2 = 2\), and \(r\) is a rational number.
Since r is a rational number, there exist integers \(m\) and \(n\) with \(n > 0\0 such that
\(r = \dfrac{m}{n}\)
and \(m\) and \(n\) have no common factor greater than 1. We will obtain a contradiction by showing that \(m\) and \(n\) must both be even. Squaring both sides of the last equation and using the fact that \(r^2 = 2\), we obtain
\(2 = \dfrac{m^2}{n^2}\)
\[m^2 = 2n^2\]
Equation (1) implies that \(m^2\) is even, and hence, by Theorem 3.7, \(m\) must be an even integer. This means that there exists an integer \(p\) such that \(m = 2p\). We can now substitute this into equation (1), which gives
\((2p)^2 = 2n^2\)
\[4p^2 = 2n^2.\]
We can divide both sides of equation (2) by 2 to obtain \(n^2 = 2p^2\). Consequently, \(n^2\) is even and we can once again use Theorem 3.7 to conclude that \(m\) is an even integer.
We have now established that both \(m\) and \(n\) are even. This means that 2 is a common factor of \(m\) and \(n\), which contradicts the assumption that \(m\) and \(n\) have no common factor greater than 1. Consequently, the statement of the theorem cannot be false, and we have proved that if \(r\) is a real number such that \(r^2 = 2\), then \(r\) is an irrational number.
- This exercise is intended to provide another rationale as to why a proof by contradiction works.
Suppose that we are trying to prove that a statement P is true. Instead of proving this statement, assume that we prove that the conditional statement “If \(\urcorner P\), then \(C\) ” is true, where \(C\) is some contradiction. Recall that a contradiction is a statement that is always false.
(a) In symbols, write a statement that is a disjunction and that is logically equivalent to \(\urcorner P \to C\).
(b) Since we have proven that \(\urcorner P \to C\) is true, then the disjunction in Exercise (1a) must also be true. Use this to explain why the statement \(P\) must be true.
(c) Now explain why \(P\) must be true if we prove that the negation of \(P\) implies a contradiction. - Are the following statements true or false? Justify each conclusion.
(a) For all integers \(a\) and \(b\), if \(a\) is even and \(b\) is odd, then 4 does not divide \((a^2 + b^2)\).
(b) For all integers \(a\) and \(b\), if \(a\) is even and \(b\) is odd, then 6 does not divide \((a^2 + b^2)\).
(c) For all integers \(a\) and \(b\), if \(a\) is even and \(b\) is odd, then 4 does not divide \((a^2 + 2b^2)\).
(d) For all integers \(a\) and \(b\), if \(a\) is odd and \(b\) is odd, then 4 divides \((a^2 + 3b^2)\). - Consider the following statement:
If \(r\) is a real number such that \(r^2 = 18\), then \(r\) is irrational.
(a) If you were setting up a proof by contradiction for this statement, what would you assume? Carefully write down all conditions that you would assume.
(b) Complete a proof by contradiction for this statement. - Prove that the cube root of 2 is an irrational number. That is, prove that if \(r\) is a real number such that \(r^3 = 2\), then \(r\) is an irrational number.
- Prove the following propositions:
(a) For all real numbers \(x\) and \(y\), if \(x\) is rational and \(y\) is irrational, then \(x + y\) is irrational.
(b) For all nonzero real numbers \(x\) and \(y\), if \(x\) is rational and \(y\) is irrational, then \(\dfrac{x}{y}\) is irrational. - Are the following statements true or false? Justify each conclusion.
(a) For each positive real number \(x\), if \(x\) is irrational, then \(x^2\) is irrational.
(b) For each positive real number \(x\), if \(x\) is irrational, then \(\sqrt x\) is irrational.
(c) For every pair of real numbers \(x\) and \(y\), if \(x + y\) is irrational, then \(x\) is irrational and \(y\) is irrational.
(d) For every pair of real numbers \(x\) and \(y\), if \(x + y\) is irrational, then \(x\) is irrational or \(y\) is irrational. - (a) Give an example that shows that the sum of two irrational numbers can be a rational number.
(b) Now explain why the following proof that \((\sqrt 2 + \sqrt 5)\) is an irrational number is not a valid proof: Since \(\sqrt 2\) and \(\sqrt 5\) are both irrational numbers, their sum is an irrational number. Therefore, \((\sqrt 2 + \sqrt 5)\) is an irrational number
Note: You may even assume that we have proven that \(\sqrt 5\) is an irrational number. (We have not proven this.)
(c) is the real number \(\sqrt 2 + \sqrt 5\) a rational number or an irrational number? Justify your conclusion. - (a) Prove that for each reach number \(x\), \((x + \sqrt 2)\) is irrational or \((-x + \sqrt 2)\) is irrational.
(b) Generalize the proposition in Part(a) for any irrational number (instead of just \(\sqrt 2\)) and then prove the new proposition. - Is the following statement true or false?
For all positive real number \(x\) and \(y\), \(\sqrt{x + y} \le \sqrt x + \sqrt y\). - Is the following proposition true or false? Justify your conclusion.
For each real number \(x\), \(x (1 - x) \le \dfrac{1}{4}\). - (a) Is the base 2 logarithm of 32, \(log_2 32\), a rational number or an irrational number? Justify your conclusion.
(b) Is the base 2 logarithm of 3, \(log_2 3\), a rational number or an irrational number? Justify your conclusion. - In Exercise (15) in Section 3.2, we proved that there exists a real number solution to the equation \(x^3 - 4x^2 = 7\). Prove that there is no integer \(x\) such that \(x^3 - 4x^2 = 7\).
- Prove each of the following propositions:
(a) For each real number \(\theta\), if \(0 < \theta < \dfrac{\pi}{2}\), then \((sin \theta + cos \theta) > 1\).
(b) For all real numbers \(a\) and \(b\), if \(a \ne 0\) and \(b \ne 0\), then \(\sqrt {a^2 + b^2} \ne a + b\).
(c) If \(n\) is an integer greater than 2, then for all integers \(m\), \(n\) does not divide \(m\) or \(n + m \ne nm\).
(d) For all numbers \(a\) and \(b\), if \(a > 0\) and \(b > 0\), then
\[\dfrac{2}{a} + \dfrac{2}{b} \ne \dfrac{4}{a + b}.\] - Prove that there do not exist three consecutive natural numbers such that the cube of the largest is equal to the sum of the cubes of the other two.
- Three natural numbers \(a\), \(b\), and \(c\) with \(a < b < c\) are called a Pythagorean triple provided that \(a^2 + b^2 = c^2\). For example, the numbers 3, 4, and 5 form a Pythagorean triple, and the numbers 5, 12, and 13 form a Pythagorean triple.
(a) Verify that if \(a = 20\), \(b = 21\), and \(c = 29\), then \(a^2 + b^2 = c^2\), and hence, 20, 21, and 29 form a Pythagorean triple.
(b) Determine two other Pythagorean triples. That is, find integers \(a\), \(b\), and \(c\) such that \(a^2 + b^2 = c^2\).
(c) Is the following proposition true or false? Justify your conclusion.
For all integers \(a\), \(b\), and \(c\), if \(a^2 + b^2 = c^2\), then \(a\) is even or \(b\) is even. - Consider the following proposition: There are no integers a and b such that \(b^2 = 4a + 2\).
(a) Rewrite this statement in an equivalent form using a universal quantifier by completing the following:
For all integers \(a\) and \(b\), ...
(b) Prove the statement in Part (a). - Is the following statement true or false? Justify your conclusion.
For each integer \(n\) that is greater than 1, if a is the smallest positive factor of \(n\) that is greater than 1, then a is prime.
See Exercise (13) in Section 2.4 (page 78) for the definition of a prime number and the definition of a composite number. - A magic square is a square array of natural numbers whose rows, columns, and diagonals all sum to the same number. For example, the following is a 3 by 3 magic square since the sum of 3 numbers in each row is equal to 15, the sum of the 3 numbers in each column is equal to 15, and the sum of the 3 numbers in each diagonal is equal to 15.
8 3 4 1 5 9 6 7 2 Prove that the following 4 by 4 square cannot be completed to form a magic square.
1 2 3 4 5 6 7 8 9 10 Hint: Assign each of the six blank cells in the square a name. One possibility is to use \(a\), \(b\), \(c\), \(d\), \(e\), and \(f\).
- Using only the digits 1 through 9 one time each, is it possible to construct a 3 by 3 magic square with the digit 3 in the center square? That is, is it possible to construct a magic square of the form
a b c d 3 e f g h where \(a\), \(b\), \(c\), \(d\), \(e\), \(f\), \(g\), \(h\) are all distinct digits, none of which is equal to 3? Either construct such a magic square or prove that it is not possible.
- Evaluation of proofs
See the instructions for Exercise (19) on page 100 from Section 3.1For each real number \(x\), if \(x\) is irrational and \(m\) is an integer, then \(mx\) is irrational.
- Proof
-
We assume that \(x\) is a real number and is irrational. This means that for all integers \(a\) and \(b\) with \(b \ne 0\), \(x \ne \dfrac{a}{b}\). Hence, we may conclude that \(mx \ne \dfrac{ma}{b}\) and, therefore, \(mx\) is irrational.
For all real numbers \(x\) and \(y\), if \(x\) is irrational and \(y\) is rational, then \(x + y\) is irrational.
- Proof
-
We will use a proof by contradiction. So we assume that the proposition is false, which means that there exist real numbers \(x\) and \(y\) where \(x \notin \mathbb{Q}\), \(y \in \mathbb{Q}\), and \(x + y \in \mathbb{Q}\). Since the rational numbers are closed under subtraction and \(x + y\) and \(y\) are rational, we see that
\[(x + y) - y \in \mathbb{Q}\].
However, \((x + y) - y = x\), and hence we can conclude that \(x \in \mathbb{Q}\). This is a contradiction to the assumption that \(x \notin \mathbb{Q}\). Therefore, the proposition is not false, and we have proven that for all real numbers \(x\) and \(y\), if \(x\) is irrational and \(y\) is rational, then \(x + y\) is irrational.
For each real number \(x\), \(x(1 - x) \le \dfrac{1}{4}\).
- Proof
-
A proof by contradiction will be used. So we assume the proposition is false. This means that there exists a real number \(x\) such that \(x(1 - x) > \dfrac{1}{4}\). If multiply both sides of this inequality by 4, we obtain \(4x(1 - x) > 1\). However, if we let \(x = 3\), we then see that
\(4x(1 - x) > 1\)
\(4 \cdot 3(1 - 3) > 1\)
\(-12 > 1\)The last inequality is clearly a contradiction and so we have proved the proposition.
Explorations and Activities
21. A Proof by Contradiction. Consider the following proposition:
Proposition. Let \(a\), \(b\), and \(c\) be integers. If 3 divides \(a\), 3 divides \(b\), and \(c \equiv 1\) (mod 3), then the equation
\(ax + by = c\)
has not solution in which both \(x\) and \(y\) are integers.
Proof. A proof by contradiction will be used. So we assume that the statement is false. That is, we assume that there exist integers \(a\), \(b\), and \(c\) such that 3 divides both \(a\) and \(b\), that \(c \equiv 1\) (mod 3), and that the equation
\(ax + by = c\)
has a solution in which both \(x\) and \(y\) are integers. So there exist integers \(m\) and \(n\) such that
\(am + bn = c\)
Hint: Now use the facts that 3 divides \(a\), 3 divides \(b\), and \(c \equiv 1\) (mod 3).
22. Exploring a Quadratic Equation. Consider the following proposition:
Proposition. For all integers \(m\) and \(n\), if \(n\) is odd, then the equation
\(x^2 + 2mx + 2n = 0\)
has no integer solution for x.
(a) What are the solutions of the equation when \(m = 1\) and \(n = 1\)? That is, what are the solutions of the equation \(x^2 + 2x - 2 = 0\)?
(b) What are the solutions of the equation when \(m = 2\) and \(n = 3\)? That is, what are the solutions of the equation \(x^2 + 4x + 2 = 0\)?
(c) Solve the resulting quadratic equation for at least two more examples using values of \(m\) and \(n\) that satisfy the hypothesis of the proposition.
(d) For this proposition, why does it seem reasonable to try a proof by contradiction?
(e) For this proposition, state clearly the assumptions that need to be made at the beginning of a proof by contradiction.
(f) Use a proof by contradiction to prove this proposition.
- Answer
-
Add texts here. Do not delete this text first.