2

I use strong induction on $p$.

Proof:

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.

Community
  • 1
KeyC0de
  • 1,232
  • 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})$" ? – Stefan Perko Dec 13 '15 at 13:44
  • 3
    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$? – lulu Dec 13 '15 at 13:45

1 Answers1

1

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$

Dan Brumleve
  • 17,796