0

In section 6.1 of Richard Hammack's Book of Proof, they use the following proof (by contradiction) that $\sqrt{2}$ is irrational.

Suppose that $\sqrt{2}$ is rational, such that $$ \exists a,b \in \mathbb{Z}, \sqrt{2} = \frac{a}{b} \tag{1} \label{eq1} $$ Let the statement $C$ be defined as $$ C : a \ \text{is odd and} \ b \ \text{is odd}, $$ and suppose that $C$ is true. Squaring both sides of equation \ref{eq1} and re-arranging yields $$ a^2 = 2b^2, $$ which means that $a^2$ is even, and hence $a$ is even. Does this not contradict the original assumption that $C$ is true, and hence complete the proof? Instead, the proof continues to show that $b$ is also even, which then completes the proof, but I am not sure why. I know that the negation of $C$ is $$ \sim C : a \ \text{is even or} \ b \ \text{is even}, $$ so if $a$ is even, then both $C$ and $\sim C$ are true, which is a contradiction.

Atticus Stonestrom
  • 11,426
mhdadk
  • 1,403
  • 2
    A priori, once $\frac ab$ is written in lowest terms, there are three cases to consider: $a$ even and $b$ odd, $a$ odd and $b$ even, both $a$ and $b$ odd. If you want to argue along those lines, you'd need to rule out all three cases, not just one of them. Not sure I see the advantage in following this line of reasoning, but it does work. – lulu Jul 02 '21 at 00:15
  • 6
    Are you sure that $C$ isn't "$a$ is odd or $b$ is odd? You can assume that to be true, by reducing $a/b$ to lowest terms, but assuming $C$ as you've written would lose generality. – Theo Bendit Jul 02 '21 at 00:17
  • 3
    @TheoBendit You are correct. My mistake. The exact wording in the book is "a and b are not both even", which confused me. In that case, $\sim C$ would be "$a$ is even and $b$ is even", which explains why the author showed both cases to be true to complete the proof. – mhdadk Jul 02 '21 at 00:19
  • 2
    @mhdadk So, I take it that you can see the answer to your question now? :-) – Theo Bendit Jul 02 '21 at 00:20
  • You have a nested proof. Not just any contradiction let’s you finish a proof. You’ve only shown that C is false - you still need to show that that causes a contradiction. Otherwise within any proof by contradiction, you could just say “assume that 1+1=0, it doesn’t! Contradiction!”. – Eric Jul 02 '21 at 00:24

1 Answers1

4

If a fraction $\frac{a}{b}$ is fully reduced then $a$ is odd or $b$ is odd, and so the statement $C$ would actually be $$ C : a \ \text{is odd or} \ b \ \text{is odd}, $$ and its negation would be $$ \sim C : a \ \text{is even and} \ b \ \text{is even}. $$ Since both $C$ and $\sim C$ being true implies a contradiction, then $\sim C$ is only true when both $a$ is shown to be even and $b$ is shown to be even.

mhdadk
  • 1,403