I use strong induction on $p$.


We want to show that $\forall q\in \mathbb{N} \big[q>0 \rightarrow \neg\exists p\in\mathbb{N}\big(p/q=\sqrt{2}\big)\big]$. Let $q$ be arbitrary natural number and $q>0$.

Inductive Hypothesis :

Let $k\in\mathbb{N}$ and $k<p$ such that $\big[q>0 \rightarrow \neg\exists k\in\mathbb{N}\big(k/q=\sqrt{2}\big)\big]$.

Inductive Step :

If $p=0$ then $k<0$ therefore the statement $\big[q>0 \rightarrow \neg\exists p\in\mathbb{N}\big(k/q=\sqrt{2}\big)\big]$ is vacuously true. If $p>0$ to see that $\sqrt{2}$ is irrational, suppose it isn't. This means that $\big[\exists p\in\mathbb{N}\big(p/q=\sqrt{2}\big)\big]$. So $p/q=\sqrt{2} \iff q=p/\sqrt{2}$. It follows that $k=\frac{p}{\sqrt{2}}\sqrt{2} \iff k=p$. Then if we let $p=k$ we get $\big[\exists k\in\mathbb{N}\big(k/q=\sqrt{2}\big)\big]$. This contradicts our inductive hypothesis. Thus $\sqrt{2}$ is irrational.

If the proof is not correct then what have I gone wrong? Thanks in advance.

  • $\begingroup$ I'm confused. Should'nt the hypothesis be: "For all $k<p$ we have $q>0 \to \neg \exists k\in \mathbb{N}: (k/q = \sqrt{2})$" ? $\endgroup$ – Stefan Perko Dec 13 '15 at 13:44
  • 3
    $\begingroup$ This is hard to follow. In your "Inductive Hypothesis, should it read $\big[q>0 \rightarrow \neg\exists k\in\mathbb{N}\big(k/q=\sqrt{2}\big)\big]$? And in your argument, where do you use the fact that we have $\sqrt 2$? If I replaced that with any real number $\alpha$, where would your argument change? And In your logic...to proceed by induction, don't you need to show that if $p$ provided a solution then you could construct a solution with a smaller $p$? $\endgroup$ – lulu Dec 13 '15 at 13:45

I can see that you've done something wrong because you haven't used the definition of $\sqrt{2}$ anywhere, so the same argument would seemingly apply to any number.

I understand the setup and the base case but it's hard to follow the rest of your argument. For strong induction you are supposed to be trying to prove that if $\sqrt{2}$'s numerator is at least $p$ then it's also at least $p+1$, but I don't know how to prove $\sqrt{2}$ is irrational this way either.

Try setting up the problem this way instead, with the definition unpacked immediately:

$\forall p \in \mathbb{N} : \forall q \in \mathbb{N}: q \gt 0 \rightarrow p^2 \ne 2 \cdot q^2$


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.