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$.
Best Answer
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}$."