# Constructing the proof that $\sup \{x:x\in\mathbb Q \wedge x<\sqrt 2 \}$ doesn't exist.

I know there is a very well known proof that for any rational such that

$$x=\frac p q < \sqrt 2$$

there exists another rational $y=\dfrac mn$ such that

$$x=\frac p q < \frac m n <\sqrt 2$$

Happily I've forgotten most of the proof, which lets me try and build it myself.

Could someone provide a hint to produce a proof? I guess I should start with $2p<3q$ to produce a number larger than $p/q$ but smaller than $\sqrt 2$.

In parenthesis, would this prove that $\sqrt 2 \notin \mathbb Q$?

-
Multiply $p-q\sqrt{2}$ by $3-2\sqrt{2}$, and you get a new number of the form $p'-q'\sqrt{2}$. Now, $0<3-2\sqrt{2}<1$, so $p'-q'\sqrt{2}$ is the same sign as $p-q\sqrt{2}$ and it is smaller in magnitude. So if $p,q>0$ and $p/q<\sqrt{2}$ then $p/q<p'/q' < sqrt{2}$. (You need to show $p',q'>0$, but that's easy.) –  Thomas Andrews Apr 11 '12 at 17:22

Following my comment above, if $p,q>0$ and $\frac p q < \sqrt{2}$, then define $p'=3p+4q$ and $q'=2p+3q$. Then you can show that $\frac{p}{q}<\frac{p'}{q'} < \sqrt{2}$.

This comes from noting that $0<3-2\sqrt{2}<1$, so if $p-q\sqrt{2}<0$ then $$p-q\sqrt{2}<(p-q\sqrt{2})(3-2\sqrt{2})=p'-q'\sqrt{2} <0$$.

But dividing by $-q$, and noting $q'>q$, we get $$\sqrt{2}-\frac{p}{q}> \frac{1}{q}(q'\sqrt{2}-p') > \frac{1}{q'}(q'\sqrt{2}-p') = \sqrt{2}-\frac{p'}{q'}>0$$

As noted by Chaz, this doesn't prove that $\sqrt{2}$ is not rational.

More generally, if $n$ is not a perfect square, let $r=\lceil\sqrt{n}\rceil$. Then $0<r - \sqrt{n}<1$, so if $p/q<\sqrt{n}$, set $p'=rp+nq$ and $q'=p+rq$. Then $p/q<p'/q'<\sqrt{n}$.

-
What motivates the multiplication? I'm much more interested in the logical or rationale of the procedure rather than the procedure itself. –  Pedro Tamaroff Apr 11 '12 at 17:29
The general reason for this is related to continued fraction expansions of $\sqrt{2}$ and solutions of the equation $u^2-2v^2=1$. In particular, one of the interesting properties of numbers of the form $x^2-2y^2$ is that a product of two numbers of this form are also of this form. In algebra, this is related to the ring $\mathbb Z[\sqrt{2}]$. –  Thomas Andrews Apr 11 '12 at 17:34
(+1) for answering the question :) –  The Chaz 2.0 Apr 11 '12 at 17:44
I suppose we could have just used $2-\sqrt{2}$ rather than $3-2\sqrt{2}$ - I'm only using the fact that the number is between $0$ and $1$. –  Thomas Andrews Apr 11 '12 at 17:52
Using $2-\sqrt2$ you replace $p/q$ with $(2p+2q)/(p+2q)$. Another (standard) approach is to use Newton's method en.wikipedia.org/wiki/Newton's_method to approximate roots. We would then replace $p/q$ with $(p/2q)+1/(p/q)=(p^2+2q^2)/(2pq)$. (The function $f$ is here $f(x)=x^2-2$, and the method replaces an approximation $x_0$ to a root of $f$ with the new approximation $\displaystyle x_1=x_0-\frac{f(x_0)}{f'(x_0)}$.) The advantage of this approach is that the sequence we obtain converges very quickly to $\sqrt{2}$: Each iteration about doubles the number of correct digits. –  Andres Caicedo Apr 11 '12 at 18:30

Hint: Let $x > 0 \in Q$ such that $x^2 < 2$.

Let $q = 2 \dfrac{x + 1}{x + 2} = x - \dfrac{x^2 - 2}{x + 2}$

Clearly $q \in Q$.

Notice that $q^2 - 2 = 2 \dfrac{(x^2 - 2)}{(x + 2)^2}$

Proceed to show that $2 > q^2 > x^2 > 0$

-
@Chaz As I told Mathew I'm much more interested in the logical or rationale of the procedure rather than the procedure itself, i.e. what motivates such new numbers to be defined? –  Pedro Tamaroff Apr 11 '12 at 17:30
I haven't seen your conversation with Mathew, and I must have misunderstood the question. It appeared as though you were looking for a constructive proof of a number between $x$ and $\sqrt 2$. –  The Chaz 2.0 Apr 11 '12 at 17:36
@Chaz I meant Thomas, sorry. –  Pedro Tamaroff Apr 11 '12 at 17:39
This would most certainly not prove that $\sqrt2\notin\mathbb{Q}$.
In fact, for every $x = p/q<2$, exists $m/n;\,p/q<m/n<2$ and certainly $2\in\mathbb{Q}$.
The proof as I remember is to suppose that $\sqrt2$ is rational, take the smallest $m/n$ which describes $\sqrt2$ (that is, cannot be simplified) and show that both are even (edit), which contradicts them being the smallest.