9 - Proof by contradiction

To prove this, draw a truth table.

Another way to think about this theorem is that if by assuming $\neg R$ we can reach some false statement, then R must have been true after all.

There are some limitations:

• When you assume $\mathrm{\neg }R$ you are working in an imaginary world.
• It can be difficult to find the contradition within $\mathrm{\neg }R$.

The negation of

is:

An easy way to remember what to assume when proving an im- plication by contradiction is that you have the same assumptions as in both a direct proof and a contrapositive proof.

First, sometimes one can tell that a result could be proved by contradiction because the statement R itself has some negative sounding words. For instance, in this section we proved the following statements R:

• There is no smallest positive rational number.

• The number 2 is not rational.

• If x is even, then 2 does not divide $x^2+1$.

Try to prove w/o contradiction first!

In Class Practice

$R$: There is no smallest positive rational number.
$\mathrm{\neg }R$: There exists a smallest positive rational number.

Assume, by way of contradiction, that there exists a smallest positive rational number $x$. Now consider the number $\frac{x}{2}$. Since $x$ is a rational number, $\frac{x}{2}$ is also a rational number and $\frac{x}{2}>0$. But $\frac{x}{2}<x$, which is a contradiction. $◻$

$R$: $\mathrm{\forall }x\in S,P(x)=>Q(x)$
$\mathrm{\neg }R:\mathrm{\exists }x\in S,P(x)\wedge \mathrm{\neg }Q(x)$

Proposition: Let $x\in \mathbb{Z}$. If $2\mid x$, then $x\nmid (x^{2+}1)$.

Proof: By way of contradiction, assume there exists $x\in \mathbb{Z}$ such that $2\mid x$ and $2\mid x^2+1$. Thus $x=2k$ for some $k\in \mathbb{Z}$ and $x^2+1=2j$ for some $j\in \mathbb{Z}$.

Proposition: Given $x\in \mathbb{Z}$, if $x^2+2x-3$ is odd, then $x^2+4x-5$ is odd.

Proof: By way of contradiction that $x^2+2x-3$ is odd and $x^2+4x-5$ is even. Thus $x^2+2x-3=2k+1$ for some $k\in \mathbb{Z}$. We find

which is odd. This contradicts our assumption that $x^2+4x-5$ is even. $◻$

Proposition: If $x\in \mathbb{Z}$ is even, then $x$ is not the sum of three integers with an odd number of them being odd.

Proof: Let $x\in \mathbb{Z}$. By of contradiction, assume that there exists $x$ such that $x$ is even and $x$ is the sum of three integers with an odd number of them being odd. There are two cases:

Case 1: Assume $x=y+w+z$ where, without loss of generality, $y$ is odd and $w,z$ are even. Hence $y=2k+1,w=2j,z=2h$, $x=2l$ where $k,j,h,x\in \mathbb{Z}$.

Thus

HW 9

Ben Finch

E 9.1

The table does indeed verify that the only row where $S$ is false and $(\neg R)\Rightarrow S$ is true occurs when $R$ is true.

E 9.2
Proposition: Given $x\in \mathbb{Z}$, if $3x+1$ is even, then $5x+2$ is odd.

Direct Proof:
Let $x\in \mathbb{Z}$. We work directly. Assume $3x+1$ is even, thus $3x+1=2k$ for some $k\in \mathbb{Z}$. Hence, $3x=2k-1$. We find

is an odd integer. $◻$

Contrapositive Proof:
Let $x\in \mathbb{Z}$. We work contrapositively. Assume $5x+2$ is even. Thus $5x+2=2k$ for some $k\in \mathbb{Z}$. We find $3x+1=2k-2x-1=2(k-x)-1$ is an odd integer. $◻$

Proof by Contradiction:
Assume, by way of contradiction, that both $3x+1$ and $5x+2$ are even. Thus $3x+1=2n$ and $5x+2=2k$ for some $n,k\in \mathbb{Z}$. Plugging the two equations into each other, we get $3x+1=5x+2$. Therefore, $1=2x+2=2(x+1)$ is even, which is false. Thus, the original implication is true. $◻$

E 9.3
Proposition: Given $a,b,c\in \mathbb{Z}$ with $a^2+b^2=c^2$, then $a$ is even or $b$ is even.

Proof.
Assume, by way of contradiction, that $a^2+b^2=c^2$ and that $a$ is odd and $b$ is odd. Thus $a=2k+1$ and $b=2n+1$ for some $k,n\in \mathbb{Z}$. We find

which indicates that $c^2$ is also even, which implies that $c$ is even (since if a number's square is even, then it must also be even). Thus $c=2p$ for some $p\in \mathbb{Z}$. Subbing $2p$ in for $c$ yields:

which suggests some odd integer is equivalent to some even integer, which is false. Thus the original implication is true. $◻$

E 9.4
Proof:
Assume, by way of contradiction, that $\sqrt{3}\in \mathbb{Q}$. We can then write $\sqrt{3}=\frac{a}{b}$ for some $a,b\in \mathbb{N}$, with $\frac{a}{b}$ in lowest terms. By squaring and clearing the denominators, we have $a^2=2b^2$. Thus $2|a^2$ and hence $2\mid a$. So $a=2k$ for some $k\in \mathbb{Z}$. Plugging $2k$ for $a$ in the original equation, we find

Thus, $2\mid b^2$ and hence $2\mid b$. However, now $a$ and $b$ are even, which contradicts
the fact that $\frac{a}{b}$ was assumed to be in lowest terms. Hence $\sqrt{3}$ is irrational. $◻$

E 9.5
Proof:
Assume, by way of contradiction, that $\sqrt[3]{2}\in \mathbb{Q}$. We can then write $\sqrt[3]{2}=\frac{a}{b}$ for some $a,b\in \mathbb{N}$, with $\frac{a}{b}$ in lowest terms. By cubing and clearing the denominators, we have $a^3=2b^3$. Thus $2\mid a^3$ and hence $2\mid a$ (by proposition 8.5). So $a=2k$ for some $k\in \mathbb{Z}$. Plugging $2k$ for $a$ in the original equation, we find

Thus, $2\mid b^3$ and hence $2\mid b$ (by a proof in the book). However, now $a$ and $b$ are even, which contradicts the fact that $\frac{a}{b}$ was assumed to be in lowest terms. Hence $\sqrt[3]{2}$ is irrational. $◻$

E 9.6
Assume, by way of contradiction, that $x$ is rational, $y$ is irrational, and $x+y$ is rational. We can then write $x+y=\frac{a}{b}$ and $x=\frac{k}{j}$ for some $a,b,k,j\in \mathbb{Z}$ (where $b,j\ne 0$). We find

where $ak-bj$ and $bj$ are integers (and $bj\ne 0$). Thus $y$ can be expressed as a rational number, which contradicts our assumption that $y$ is irrational. Thus, our assumption that $x+y$ is rational must be false. Therefore, $x+y$ is irrational if $x$ is rational and $y$ is irrational. $◻$

E 9.7
Assume, by way of contradiction, that $x$ is rational & $x\ne 0$, $y$ is irrational, and $xy$ is rational. We can then write $x=\frac{a}{b}$ and $xy=\frac{k}{j}$ for some $a,b,k,j\in \mathbb{Z}$ (where $b,j\ne 0$). We find

which is rational (since the product of any two rational numbers is also rational). This contradicts our original assumption that $y$ is irrational. Therefore, if $x$ is rational (and $x\ne 0$) and $y$ is irrational, then $xy$ is irrational. $◻$

E 9.8
Assume, by way of contradiction, that there is a smallest positive irrational number $l$. Now consider the number $m=\frac{l}{2}$. From exercise 9.7, we know that if we multiply a non-zero rational number ($1/2$) and an irrational number ($l$), we will get an irrational number. This contradicts our assumption that $l$ is the smallest positive irrational number since we have found a smaller positive irrational number $m$. Thus we find that there is no smallest positive irrational number. $◻$

E 9.9
Let $x,y\in \mathbb{Z}$.
Assume, by way of contradiction, that $33x+132y=57$. We can simplify the equation to $33(x+4y)=57$. Since $33$ and $57$ are integers, we can assume $x+4y$ is also an integer, since the product of two integers is an integer. However, if we divide both sides of the equation by $33$ we get $x+4y=\frac{57}{33}$, which is not an integer. Thus our original assumption that there exists some integer $x$ and $y$ such that $33x+132y=57$ is false. $◻$