2
$\begingroup$

I refer to Exercise 2 of Section 6.4 of Velleman's book. As the title says, we want to prove that $\sqrt{2}$ is irrational using strong induction to prove that $\forall q\in\mathbb{N}[q>0\rightarrow \neg \exists p\in\mathbb{N}(p/q=\sqrt{2})]$. Here we include zero as part of the natural numbers. We know that $P(q)=q>0\rightarrow \neg \exists p\in\mathbb{N}(p/q=\sqrt{2})$ and so we need to prove that $\forall q P(q)$. This is what I got thus far:

  • Let $q\in\mathbb{N}$ and suppose that $\forall k<q P(k)$
  • Let $q>0$ and since we want to prove this by contradiction, we suppose that $\exists p\in\mathbb{N} p/q=\sqrt{2}$. Then, there is some $p\in\mathbb{N}$ such that $p/q=\sqrt{2}$
  • It is clear that $p,q$ are even, so let $p'\in\mathbb{Z}^+$ such that $p=2p'$ and let $q'\in\mathbb{Z}^+$ such that $q=2q'$. Then $p/q=p'/q'=\sqrt{2}$
  • Using our inductive hypothesis, since $q'=q/2<q$ then $q'>0 \rightarrow \neg\exists p\in\mathbb{N}(p/q'=\sqrt{2})$. Since we assumed that $q>0$, then $q'>0$ and by modus ponens we have that $\neg\exists p\in\mathbb{N}(p/q'=\sqrt{2})$
  • We already know that $p/q=p/(2q')=\sqrt{2}$, which also means that $(p/2)/q'=\sqrt{2}$. From this, is it correct to conclude that $\exists p\in\mathbb{N} p/q'=\sqrt{2}$? This would clearly contradict the inductive hypothesis and finish the proof. However, I have some concerns about this. Saying that $p'\in\mathbb{N}$ would imply that $p/2\in\mathbb{N}$, and since $p=2p'$ are we not necessarily forcing $p=p'=0$? If so, then $p'/q'=\sqrt{2}$ does not make sense at all, and also $0\notin\mathbb{Z}^+$ and thus there is no even number $p$? I would appreciate very much any guide you can offer.

Also, I checked this post, where I think I found the most explicit explanation for this proof, but I still don't understand how the contradiction is generated. I feel that we would end up imposing the same condition that $p=p'=0$.

$\endgroup$
1
$\begingroup$

This question is equivalent to Exercise 9 in Sec 5.2 of "Discrete math and its application" by Rosen, the answer for which you can easily find somewhere elsewhere. Nevertheless, I'll post it here. Let P(n) be the statement that $\sqrt{2} \neq n/b$ for any positive integer b. The base case $n = 0$ is trivial. Suppose inductively that P(i) holds for all $i \leq k$, suppose also for the sake of contradiction that $(k + 1)/b = \sqrt{2}$ for some b. Then $(k + 1)^2 = 2b^2$ implies that $k + 1$ is even. ie, $k + 1 = 2a$ for some $a$. Similarly $(k + 1)^2 = 2b^2 = (2a)^2 = 4a^2$ implies that b is even. ie, $b = 2c$ for some $c$. Hence we have $\sqrt{2} = (k + 1)/b = 2a/2c = a/c$, where $a \leq k$, a contradiction. By the principle of strong induction, we're done.

$\endgroup$
1
$\begingroup$

There is a small typo at the end of the 4th bullet point; it should say $\neg\exists p \in \mathbb{N}(p/q' = \sqrt{2})$. Other than that, your proof is fine until the last bullet point.

In the last bullet point, I would start with $p'/q' = \sqrt{2}$, which you already have in your 3rd bullet point. You also already have $p' \in \mathbb{Z}^+$, so $p' \in \mathbb{N}$. So yes, you are justified in saying at this point that $\exists p \in \mathbb{N}(p/q' = \sqrt{2})$, which is a contradiction and finishes the proof.

I'm not sure why you think $p=p'$, which together with $p = 2p'$ would indeed imply $p=p'=0$. But let me take a guess. Perhaps you are confusing two uses of the letter $p$. At the end of the second bullet point, you introduced $p$ as the name for a particular natural number such that $p/q = \sqrt{2}$. And in the last bullet point, you used the letter $p$ as a bound variable in the statement $\exists p \in \mathbb{N}(p/q' = \sqrt{2})$. Those two $p$'s are not the same. In particular, $\exists p \in \mathbb{N}(p/q' = \sqrt{2})$ just means "there is some natural number such that, when you divide it by $q'$, you get $\sqrt{2}$." That natural number doesn't have to be the one you called $p$ earlier. If it would help, use different letters in these two contexts. For example, you could write $\exists r \in \mathbb{N}(r/q' = \sqrt{2})$, which means exactly the same thing as $\exists p \in \mathbb{N}(p/q' = \sqrt{2})$. Or, in the second bullet point, you could say "let $r$ be a natural number such that $r/q = \sqrt{2}$."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.