Proof by Contradiction

Section 3.3 Proof by Contradiction

Beginning Activity Beginning Activity 1: Proof by Contradiction
A4 US

In a Definition 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.

🔗

1.

Use truth tables to explain why $(P \lor \neg P)$ is a tautology and $(P \land \neg 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 \land \neg 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

[\neg X \to C] \to X,

🔗

where

X

is a statement and

C

is a contradiction. The following truth table establishes this tautology.

$X$	$C$	$\neg X$	$\neg X \to C$	$(\neg X \to C) \to X$
T	F	F	T	T
F	F	T	F	T

This tautology shows that if

\neg X

leads to a contradiction, then

X

must be true. The previous truth table also shows that the statement

\neg X \to C

is logically equivalent to

X .

This means that if we have proved that

\neg 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

\neg 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.

🔗

2.

Use a truth table to show that $\neg (P \to Q)$ is logically equivalent to $P \land \neg Q .$

🔗

The preceding logical equivalency shows that when we assume that \mbox{

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

\neg (P \to Q)

is false and hence that

P \to Q

is true.

🔗

3.

Give a counterexample to show that the following statement is false.

For each real number $x,$ $\frac{1}{x (1 - x)} \geq 4 .$

🔗

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 Exercise 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 $\frac{1}{x (1 - x)} \geq 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.24.) With this in mind, carefully write down all assumptions made at the beginning of a proof by contradiction for this statement.

🔗

Beginning Activity Beginning Activity 2: Constructing a Proof by Contradiction
A4 US

🔗

Consider the following proposition:

🔗

Proposition 3.17.

For all real numbers $x$ and $y,$ if $x \neq y,$ $x > 0, and y > 0,$ then $\frac{x}{y} + \frac{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 \neq y,

x > 0, y > 0

and that

\frac{x}{y} + \frac{y}{x} \leq 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

\begin{matrix} (4) & \frac{x}{y} + \frac{y}{x} \leq 2 \end{matrix}

🔗

until we obtain a contradiction.

🔗

1.

Try the following algebraic operations on the inequality in (4). First, multiply both sides of the inequality by $x y,$ which is a positive real number since $x > 0$ and $y > 0 .$ Then, subtract $2 x y$ from both sides of this inequality and finally, factor the left side of the resulting inequality.

🔗

2.

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.

🔗

Subsection 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 beginning 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 Beginning Activity 1.

🔗

Proposition 3.18.

For each real number $x,$ if $0 < x < 1,$ then $\frac{1}{x (1 - x)} \geq 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

\begin{matrix} (5) & \frac{1}{x (1 - x)} < 4 . \end{matrix}

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 (5) by $x (1 - x),$ we obtain

1 < 4 x (1 - x) .

We can now use algebra to rewrite the last inequality as follows:

\begin{aligned} 1 & < 4 x - 4 x^{2} \\ 4 x^{2} - 4 x + 1 & < 0 \\ (2 x - 1)^{2} & < 0 \end{aligned}

However, $(2 x - 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 $\frac{1}{x (1 - x)} \geq 4 .$

🔗

Progress Check 3.19. Starting a Proof by Contradiction.

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.12.) Also, review Theorem 2.24 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.)

🔗

(a)

For each real number $x,$ if $x$ is irrational, then $\sqrt[3]{x}$ is irrational.

Solution.

There exists a real number $x$ such that $x$ is irrational and $\sqrt[3]{x}$ is rational.

🔗

(b)

For each real number $x,$ $(x + \sqrt{2})$ is irrational or $(- x + \sqrt{2})$ is irrational.

Solution.

There exists a real number $x$ such that $(x + \sqrt{2})$ is rational and $(- x + \sqrt{2})$ is rational.

🔗

(c)

For all integers $a$ and $b,$ if 5 divides $a b,$ then 5 divides $a$ or 5 divides $b .$

Solution.

There exist integers $a$ and $b$ such that 5 divides $a b$ and 5 does not divide $a$ and 5 does not divide $b .$

🔗

(d)

For all real numbers $a$ and $b,$ if $a > 0$ and $b > 0,$ then $\frac{2}{a} + \frac{2}{b} \neq \frac{4}{a + b} .$

Solution.

There exist real numbers $a$ and $b$ such that $a > 0$ and $b > 0$ and $\frac{2}{a} + \frac{2}{b} = \frac{4}{a + b} .$

🔗

Subsection Important Note

🔗

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

\neg 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.

🔗

Progress Check 3.20. Exploration and a Proof by Contradiction.

Consider the following proposition:

For each integer $n,$ if $n \equiv 2 (\mod 4),$ then $n ≢ 3 (\mod 6) .$

🔗

(a)

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?

Solution.

Some integers that are congruent to 2 modulo 4 are $- 6, - 2, 2, 6, 10,$ and some integers that are congruent to 3 modulo 6 are: $- 9, - 3, 3, 9, 15 .$ There are no integers that are in both of the lists.

🔗

(b)

For this proposition, why does it seem reasonable to try a proof by contradiction?

Solution.

For this proposition, it is reasonable to try a proof by contradiction since the conclusion is stated as a negation.

🔗

(c)

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.

Solution.

🔗

Proof.

We will use a proof by contradiction. Let $n \in Z$ and assume that $n \equiv 2 (\mod 4)$ and that $n \equiv 3 (\mod 6) .$ Since $n \equiv 2 (\mod 4),$ we know that 4 divides $n - 2 .$ Hence, there exists an integer $k$ such that

\begin{matrix} (6) & n - 2 = 4 k . \end{matrix}

We can also use the assumption that $n \equiv 3 (\mod 6)$ to conclude that 6 divides $n - 3$ and that there exists an integer $m$ such that

\begin{matrix} (7) & n - 3 = 6 m . \end{matrix}

If we now solve equation (6) and equation (7) for $n$ and set the two expressions equal to each other, we obtain

4 k + 2 = 6 m + 3 .

However, this equation can be rewritten as

2 (2 k + 1) = 2 (3 m + 1) + 1 .

Since $2 k + 1$ is an integer and $3 m + 1$ is an integer, this last equation is a contradiction since the left side is an even integer and the right side is an odd integer. Hence, we have proven that if $n \equiv 2 (\mod 4),$ then $n ≢ 3 (\mod 6) .$

🔗

Subsection 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:

🔗

Proposition 3.21.

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.

🔗

Progress Check 3.22.

Complete the following proof of Proposition 3.21:

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 = 2 m + 1$ and $y = 2 n + 1 .$

🔗

(a)

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.8.)

Solution.

$x^{2} + y^{2} = (2 m + 1)^{2} + (2 n + 1)^{2} = 2 (2 m^{2} + 2 m + 2 n^{2} + 2 n + 1) .$

🔗

(b)

We can now conclude that $z$ is even. (See Theorem 3.8.) So there exists an integer $k$ such that $z = 2 k .$ If we substitute for $x,$ $y,$ and $z$ in the equation $x^{2} + y^{2} = z^{2},$ we obtain

(2 m + 1)^{2} + (2 n + 1)^{2} = (2 k)^{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.

Solution.

Using algebra to rewrite the last equation, we obtain

4 m^{2} + 4 m + 4 n^{2} + 4 n + 2 = 4 k^{2} .

If we divide both sides of this equation by 2, we see that $2 m^{2} + 2 m + 2 n^{2} + 2 n + 1 = 2 k^{2}$ or

2 (m^{2} + m + n^{2} + n) + 1 = 2 k^{2} .

However, the left side of the last equation is an odd integer and the right side is an even integer. This is a contradiction, and so we have proved that 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} .$

🔗

Subsection 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.

🔗

Definition.

A real number $x$ is defined to be a rational number provided that there exist integers $m$ and $n$ with $n \neq 0$ such that $x = \frac{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},

π,

and the number

e .

We are discussing these matters now because we will soon prove that

\sqrt{2}

is irrational in Theorem 3.24.

🔗

We use the symbol

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

Q

are closed under addition, subtraction, multiplication, and division by nonzero rational numbers. This means that if

x, y \in Q,

then

$x + y,$ $x - y,$ and $x y$ are in $Q;$ and
If $y \neq 0,$ then $\frac{x}{y}$ is in $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.24. We then see that

\sqrt{2} \sqrt{2} = 2 and \frac{\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 = \frac{3}{1} .

In general, if

n \in Z,

then

n = \frac{n}{1},

and hence,

n \in 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.

🔗

Proposition 3.23.

For all real numbers $x$ and $y,$ if $x$ is rational and $x \neq 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, $x \neq 0,$ $y$ is irrational, and $x \cdot y$ is rational. Since $x \neq 0,$ we can divide by $x,$ and since the rational numbers are closed under division by nonzero rational numbers, we know that $\frac{1}{x} \in Q .$ We now know that $x \cdot y$ and $\frac{1}{x}$ are rational numbers and since the rational numbers are closed under multiplication, we conclude that

\frac{1}{x} \cdot (x y) \in Q .

However, $\frac{1}{x} \cdot (x y) = 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 \neq 0$ and $y$ is irrational, then $x \cdot y$ is irrational.

🔗

Subsection 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:

🔗

Theorem 3.24.

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 = \frac{m}{1} .$
Notice that $\frac{2}{3} = \frac{4}{6},$ since

$\frac{4}{6} = \frac{2 \cdot 2}{3 \cdot 2} = \frac{2}{2} \cdot \frac{2}{3} = \frac{2}{3}$

We can also show that

$\frac{15}{12} = \frac{5}{4}, \frac{10}{- 8} = \frac{- 5}{4}, and \frac{- 30}{- 16} = \frac{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 $\frac{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 concluded about $n .$ Refer to Theorem 3.8.

🔗

In a proof by contradiction of a conditional statement

P \to Q,

we assume the negation of this statement or

P \land \neg Q .

So in a proof by contradiction of Theorem 3.24, we will assume that

r

is a real number,

r^{2} = 2,

and

r

is not irrational (that is,

r

is rational).

🔗

Theorem 3.25.

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$ such that

r = \frac{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

\begin{aligned} (8) & 2 & = \frac{m^{2}}{n^{2}} \\ (9) & m^{2} & = 2 n^{2} \end{aligned}

Equation (9) implies that $m^{2}$ is even, and hence, by Theorem 3.8, $m$ must be an even integer. This means that there exists an integer $p$ such that $m = 2 p .$ We can now substitute this into equation (9), which gives

\begin{aligned} {(2 p)}^{2} & = 2 n^{2} \\ (10) & 4 p^{2} & = 2 n^{2} \end{aligned}

We can divide both sides of equation (10) by 2 to obtain $n^{2} = 2 p^{2} .$ Consequently, $n^{2}$ is even and we can once again use Theorem 3.8 to conclude that $n$ 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.

🔗

Exercises Exercises

🔗

1.

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 $\neg 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 $\neg P \to C .$

Answer.

$P \lor C$

🔗

(b)

Since we have proven that $\neg P \to C$ is true, then the disjunction in Task 1.a 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.

🔗

2.

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}) .$

Answer.

This statement is true. Use a proof by contradiction. So assume that there exist integers $a$ and $b$ such that $a$ is even, $b$ is odd, and 4 divides $a^{2} + b^{2} .$ So there exist integers $m$ and $n$ such that

a = 2 m and a^{2} + b^{2} = 4 n .

Substitute $a = 2 m$ into the second equation and use algebra to rewrite in the form $b^{2} = 4 (n - m^{2}) .$ This means that $b^{2}$ is even and hence, that $b$ is even. This is a contradiction to the assumption that $b$ is odd.

🔗

(b)

For all integers $a$ and $b,$ if $a$ is even and $b$ is odd, then $6$ does not divide $(a^{2} + b^{2}) .$

Answer.

This statement is true. Use a proof by contradiction. So assume that there exist integers $a$ and $b$ such that $a$ is even, $b$ is odd, and 6 divides $a^{2} + b^{2} .$ So there exist integers $m$ and $n$ such that

a = 2 m and a^{2} + b^{2} = 6 n .

Substitute $a = 2 m$ into the second equation and use algebra to rewrite in the form $b^{2} = 2 (3 n - 2 m^{2}) .$ This means that $b^{2}$ is even and hence, that $b$ is even. This is a contradiction.

🔗

(c)

For all integers $a$ and $b,$ if $a$ is even and $b$ is odd, then $4$ does not divide $(a^{2} + 2 b^{2}) .$

🔗

(d)

For all integers $a$ and $b,$ if $a$ is odd and $b$ is odd, then $4$ divides $(a^{2} + 3 b^{2}) .$

Answer.

This statement is true. Use a direct proof. Let $a$ and $b$ be integers and assume they are odd. So there exist integers $m$ and $n$ such that

a = 2 m + 1 and b = 2 n + 1 .

We then see that

\begin{aligned} a^{2} + 3 b^{2} & = 4 m^{2} + 4 m + 1 + 12 n^{2} + 12 n + 3 \\ = 4 (m^{2} + m + 3 n^{2} + 3 n + 1) . \end{aligned}

This shows that 4 divides $a^{2} + 3 b^{2} .$

🔗

3.

Consider the following statement:

For each positive real number $r,$ if $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.

Answer.

We would assume that there exists a positive real number $r$ such that $r^{2} = 18$ and $r$ is a rational number.

🔗

(b)

Complete a proof by contradiction for this statement.

Answer.

Do not attempt to mimic the proof that the square root of 2 is irrational (Theorem 3.24). You should still use the definition of a rational number but then use the fact that $\sqrt{18} = \sqrt{9 \cdot 2} = \sqrt{9} \sqrt{2} = 3 \sqrt{2} .$ So, if we assume that $r = \sqrt{18} = 3 \sqrt{2}$ is rational, then $\frac{r}{3} = \frac{\sqrt{18}}{3}$ is rational since the rational numbers are closed under division. Hence, $\sqrt{2}$ is rational and this is a contradiction to Theorem 3.24.

🔗

4.

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.

🔗

5.

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.

Answer.

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 + y$ is rational. Since the rational numbers are closed under addition, this implies that $(x + y) - x$ is a rational number. Since $(x + y) - x = y,$ we conclude that $y$ is a rational number and this contradicts the assumption that $y$ is irrational.

🔗

(b)

For all nonzero real numbers $x$ and $y,$ if $x$ is rational and $y$ is irrational, then $x y$ is irrational.

Answer.

Use a proof by contradiction. So, we assume that there exist nonzero real numbers $x$ and $y$ such that $x$ is rational, $y$ is irrational, and $x y$ is rational. Since the rational numbers are closed under division by nonzero rational numbers, this implies that $\frac{x y}{x}$ is a rational number. Since $\frac{x y}{x} = y,$ we conclude that $y$ is a rational number and this contradicts the assumption that $y$ is irrational.

🔗

6.

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.

Answer.

This statement is false. A counterexample is $x = \sqrt{2} .$

🔗

(b)

For each positive real number $x,$ if $x$ is irrational, then $\sqrt{x}$ is irrational.

Answer.

This statement is true since the contrapositive is true. The contrapositive is:

For any real number $x,$ if $\sqrt{x}$ is rational, then $x$ is rational.

If there exist integers

a

and

b

with

b \neq 0

such that

\sqrt{x} = \frac{a}{b},

then

x^{2} = \frac{a^{2}}{b^{2}}

and hence,

x^{2}

is rational.

🔗

(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.

🔗

7.

Complete the following.

🔗

(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.

🔗

8.

Complete the following.

🔗

(a)

Prove that for each real 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.

🔗

9.

Is the following statement true or false?

For all positive real numbers $x$ and $y,$ $\sqrt{x + y} \leq \sqrt{x} + \sqrt{y} .$

🔗

10.

Is the following proposition true or false? Justify your conclusion.

For each real number $x,$ $x (1 - x) \leq \frac{1}{4} .$

🔗

11.

Justify your conclusion for each of the following.

🔗

(a)

Is the base 2 logarithm of 32, $\log_{2} (32),$ a rational number or an irrational number?

Answer.

Recall that $\log_{2} (32)$ is the real number $a$ such that $2^{a} = 32 .$ That is, $a = \log_{2} (32)$ means that $2^{a} = 32 .$ If we assume that $a$ is rational, then there exist integers $m$ and $n,$ with $n \neq 0,$ such that $a = \frac{m}{n} .$

🔗

(b)

Is the base 2 logarithm of 3, $\log_{2} (3),$ a rational number or an irrational number?

🔗

12.

In Exercise 15 in Section 3.2, we proved that there exists a real number solution to the equation $x^{3} - 4 x^{2} = 7 .$ Prove that there is no integer $x$ such that $x^{3} - 4 x^{2} = 7 .$

Hint.

The only factors of 7 are $- 1, 1, - 7,$ and $7 .$

🔗

13.

Prove each of the following propositions:

🔗

(a)

For each real number $θ,$ if $0 < θ < \frac{π}{2},$ then $[\sin (θ) + \cos (θ)] > 1 .$

Hint.

What happens if you expand $[\sin (θ) + \cos (θ)]^{2} ?$ Don't forget your trigonometric identities.

🔗

(b)

For all real numbers $a$ and $b,$ if $a \neq 0$ and $b \neq 0,$ then $\sqrt{a^{2} + b^{2}} \neq a + b .$

🔗

(c)

If $n$ is an integer greater than 2, then for all integers $m,$ $n$ does not divide $m$ or $n + m \neq n m .$

🔗

(d)

For all real numbers $a$ and $b,$ if $a > 0$ and $b > 0,$ then

\frac{2}{a} + \frac{2}{b} \neq \frac{4}{a + b} .

🔗

14.

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.

Hint.

Three consecutive natural numbers can be represented by $n,$ $n + 1,$ and $n + 2,$ where $n \in N,$ or three consecutive natural numbers can be represented by $m - 1,$ $m,$ and $m + 1,$ where $m \in N .$

🔗

15.

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.

🔗

16.

Consider the following proposition: There are no integers $a$ and $b$ such that $b^{2} = 4 a + 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 Task 16.a.

🔗

17.

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 Activity 8 in Section 2.4 for the definition of a prime number and the definition of a composite number.

🔗

18.

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 the 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

🔗

19.

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.

🔗

20. Evaluation of Proofs.

See the instructions for Exercise 19 from Section 3.1.

🔗

(a)

Proposition: For each real number $x,$ if $x$ is irrational and $m$ is an integer, then $m x$ 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 \neq 0,$ $x \neq \frac{a}{b} .$ Hence, we may conclude that $m x \neq \frac{m a}{b}$ and, therefore, $m x$ is irrational.

🔗

(b)

Proposition

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 Q,$ $y \in Q,$ and $x + y \in Q .$ Since the rational numbers are closed under subtraction and $x + y$ and $y$ are rational, we see that

(x + y) - y \in Q .

However, $(x + y) - y = x,$ and hence we can conclude that $x \in Q .$ This is a contradiction to the assumption that $x \notin 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.

🔗

(c)

Proposition

For each real number $x,$ $x (1 - x) \leq \frac{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) > \frac{1}{4} .$ If we multiply both sides of this inequality by 4, we obtain $4 x (1 - x) > 1 .$ However, if we let $x = 3,$ we then see that

\begin{aligned} 4 x (1 - x) & > 1 \\ 4 \cdot 3 (1 - 3) & > 1 \\ - 12 & > 1 \end{aligned}

The last inequality is clearly a contradiction and so we have proved the proposition.

🔗

Activity 14. 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

a x + b y = c

has no solution in which both $x$ and $y$ are integers.

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

a x + b y = c

has a solution in which both $x$ and $y$ are integers. So there exist integers $m$ and $n$ such that

a m + b n = c .

Hint.

Now use the facts that 3 divides $a,$ 3 divides $b,$ and $c \equiv 1 (\mod 3) .$

🔗

Activity 15. Exploring a Quadratic Equation.

Consider the following proposition:

🔗

Proposition.

For all integers $m$ and $n,$ if $n$ is odd, then the equation

x^{2} + 2 m x + 2 n = 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} + 2 x - 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} + 4 x + 6 = 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.

Section 3.3 Proof by Contradiction

Beginning Activity Beginning Activity 1: Proof by Contradiction A4US

1.

2.

3.

4.

Beginning Activity Beginning Activity 2: Constructing a Proof by Contradiction A4US

Proposition 3.17.

1.

2.

Subsection Writing Guidelines: Keep the Reader Informed

Proposition 3.18.

Proof.

Progress Check 3.19. Starting a Proof by Contradiction.

(a)

(b)

(c)

(d)

Subsection Important Note

Progress Check 3.20. Exploration and a Proof by Contradiction.

(a)

(b)

(c)

Proof.

Subsection Proving that Something Does Not Exist

Proposition 3.21.

Progress Check 3.22.

(a)

(b)

Subsection Rational and Irrational Numbers

Definition.

Proposition 3.23.

Proof.

Subsection The Square Root of 2 Is an Irrational Number

Theorem 3.24.

Theorem 3.25.

Proof.

Exercises Exercises

1.

(a)

(b)

(c)

2.

(a)

(b)

(c)

(d)

3.

(a)

(b)

4.

5.

(a)

(b)

6.

(a)

(b)

(c)

(d)

7.

(a)

(b)

(c)

8.

(a)

(b)

9.

10.

11.

(a)

(b)

12.

13.

(a)

(b)

(c)

(d)

14.

15.

(a)

Beginning Activity Beginning Activity 1: Proof by Contradiction
A4 US

Beginning Activity Beginning Activity 2: Constructing a Proof by Contradiction
A4 US