# Proving the real numbers are complete

In Rudin's book, the following proof is published:

Let $A$ be the set of all positive rationals $p : p^2 < 2$. Let $B$ be the set of all positive rationals $p : p^2 > 2$. $A$ contains no largest number and $B$ contains no smallest.

Let q be a rational. More explicitly, $$\forall p \in A, \exists q \in A : p < q$$

and $$\forall p \in B, \exists q \in B : q < p$$

This needs proof.

Now he introduces a couple of equations which are not clear where they are derived from. As follows,

To do this, we associate with each rational $p > 0$ the number $$q = p - {\frac{p^2-2}{p+2}} = {\frac{2p+2}{p+2}}$$

then $$q^2 - 2 = {\frac {2(p^2-2)}{(p+2)^2}}$$

He then goes on to prove how $p \in A \rightarrow q \in A$; similarly for the set B.

My question is: How did he arrive at those equations - particularly, the first one (since the second is clear)?

-
possible duplicate of How to show that we can always choose a smaller number? – Steven Stadnicki Aug 26 '13 at 21:10

If $p\in\mathbb{Q}$ is smaller than $\sqrt{2}$, we want to find another rational $p<q<\sqrt{2}$. Now, this can easily be handled with decimal fractions, but if you want something neater that relies solely on $p$, then what we basically want to do is find a rational $r\in\mathbb{Q}\cap(0,\sqrt{2}-p)$ and define $q=p+r$.

Note that $\sqrt{2}-p\not\in\mathbb{Q}$, but $2-p^2 = (\sqrt{2}-p)(\sqrt{2}+p)\in\mathbb{Q}$. If we want it to be small enough, it suffices that $\frac{\sqrt{2}+p}{2+p} < 1$, so that $$\frac{2-p^2}{2+p} = (\sqrt{2}-p)\frac{\sqrt{2}+p}{2+p}<\sqrt{2}-p.$$

-
Amazing trick. But how does one come up with these sorts of formulas? – Don Larynx Aug 26 '13 at 21:13
I tried to explain the intuition involved. We try to dance on two weddings here: remain in $\mathbb{Q}$ while being bounded by an irrational number. Using $\sqrt{2}<2$, we're able to do so here. – Jonathan Y. Aug 26 '13 at 21:18

The formula is unimportant. Teaching how to come up with nice formulas like that is beyond the scope of the book: it is more in the domain of numerical methods or possibly number theory. (although maybe Newton's method is talked about in the book; it's sort of lucky that that works out nicely here)

Focusing on how to come up with the formula is a red herring -- while it may be interesting as an independent study, it is really irrelevant to what you're trying to learn from his book: all that matters is that it can be done. If you didn't have that nice formula, you would simply do something tedious and straightforward; e.g. something with decimal approximations.

Doing the tedious and straightforward thing, however, would distract from the idea he's trying to teach you. Not only would you get bogged down in details, but suddenly you're trying to learn two things rather than just one.

Thus, Rudin pulled something nice out of a hat -- a simple way to blitz through the technical details of an otherwise simple idea that he wants to convey about the very basics of the field of real numbers so that he can get on with teaching you analysis.

-
He should state that in the book. – Don Larynx Aug 27 '13 at 1:00

Formally? The formula for $q$ doesn't come from anywhere; it's just pulled out of a hat. He uses it to define $q$. Since what you're seeking to prove is just that a $q$ with such-and-such properties exists, you're allowed to produce such a $q$ in whichever crazy way you want to, as long as you're able to prove afterwards that it has such-and-such properties.

-
The problem is pulling the equation "out of a hat". Thanks for your helpful answer! – Don Larynx Aug 26 '13 at 21:21

I wondered the same thing when I read this section in Rudin's text. I believe he is using a modified form of Newton's method to find a rational number $q$ satisfying $p<q$ and $q^2<2$, as follows:

Because $y=x^2-2$ is concave up, using the Newton's method approximation $q=p-\frac{f(p)}{f^{\prime}(p)}=p-\frac{p^2-2}{2p}$ would give a number $q$ with $q^2>2$, so he wants to get a smaller approximation by replacing $2p$ by $p+a$ for some constant $a$. In order for this to actually be smaller, he needs $p+a>2p$ or, equivalently, $a>p$.

If he chooses any $a$ with $a^2>2$ (so then $a>p$ is also satisfied), then he will get a $q$ that gives what he wants, since $q=p+\frac{2-p^2}{p+a}>p$ and

$p^2<2\implies(a^2-2)p^2<2(a^2-2)\implies a^2p^2-2p^2<2a^2-4$

$\implies a^2p^2+4ap+4<2p^2+4ap+2a^2\implies (ap+2)^2<2(p+a)^2\implies$$q^2=\bigg(\frac{ap+2}{p+a}\bigg)^2<2$.

This shows that Rudin could have chosen $q=p-\frac{p^2-2}{p+a}$ for any $a$ with $a^2>2$, and that's my best guess as to how he found this approximation.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Another way he could have found a suitable value of $q$ is to use Newton's method with $f(x)=x-\frac{2}{x}$, since this function is concave down, and this would give $q=p-\frac{f(p)}{f^{\prime}(p)}=p-\frac{p-\frac{2}{p}}{1+\frac{2}{p^2}}=\frac{\frac{4}{p}}{1-\frac{2}{p^2}}=\frac{4p}{p^2+2}$.

-

As Henning Makholm says, it is not very important to know where the formula comes from. However, we might try to guess how it was found.

A more natural way to get nearer to $\sqrt{2}$ it to consider $q_1=(p+2/p)/2)$. Unfortunately, it is on the wrong side of $\sqrt{2}$. To go back on the right side, you could use the formula twice, letting $q_2=(q_1+2/q_1)/2.$ This would give an alternate proof with a more complicated looking formula than the one chosen by Rudin.

Now, look at $q_1-p=-\frac{p^2-2}{2p}.$ Does the numerator ring a bell ?

-

if $p^2<2$ let's add 2p to both sides of the inequality then $p^2+2p<2+2p$ then $p(p+2)<2(p+1)$ then $p<\frac{2(p+1)}{p+2}$ so let's set $q=\frac{2(p+1)}{p+2}$ then we have if $p^2<2$ then $p<q$. what is left to show is that $q^2<2$ and that would show that $0<p<q$ and $q \in A$

-