# Rudin's proof on the Analytic Incompleteness of Rationals [duplicate]

In Rudin's classical "Principles of Mathematical Analysis," he gave a proof like this:

Claim: Let $A= \{p\in \mathbb{Q} | p>0, p^2 <2\}$. Then A contains no largest number.

Proof: Given any $p\in A$. Let $q = p-\frac{p^2 -2}{p+2}$.

Later Rudin claimed that $q^2<2,$ and $q>p$. My instructor asks us to think about a question on our own: Why is such $q$ a natural choice in this proof?

I can see that in this way, $q>p$ is for sure. However, how does it become a natural choice?

## marked as duplicate by Hans Lundmark, jvdhooft, Ethan Bolker, rtybase, José Carlos Santos real-analysis StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 10 '18 at 23:10

The idea is that as $p \to \sqrt{2}^-$, you want to add something scaling like $2-p^2$ to $p$, so that what you add goes to zero as $p \to \sqrt{2}^-$. But you can't just add $2-p^2$ to $p$. Consider for instance $p=0$, then $p+2-p^2=2$ which is too big.

How much is it too big by? Well, $p^2-2=(p+\sqrt{2})(p-\sqrt{2})$, so it is too big by a factor of $p+\sqrt{2}$. So it would be enough to divide it by any rational number greater than $p+\sqrt{2}$. $p+2$ is just what you get when you use the trivial estimate $\sqrt{2}<2$. Numerous other options would have worked, though, for example $q=p+\frac{2-p^2}{4}$.

• Why is it necessary to divide $p^2 -2$ by a RATIONAL number? For example, would $p+\sqrt{3}$ work? – Chunjing GU Jun 8 '18 at 19:50
• @ChunjingGU Because $2-p^2$ is already rational, so whatever you divide it by needs to be rational so that you stay in $A$ (which only contains rationals). – Ian Jun 8 '18 at 19:51

I've always thought Rudin is kind of lame here. He has a fondness for pulling rabbits out of a hat, and this is not the last time you will see it.

It seems to me easier to consider

$$(p+1/n)^2 <2,\, n=1,2,\dots$$

The intuition is then clear: Surely this will be true for large enough $n,$ let's go find one, call it $n_0,$ and then $p+1/n_0$ does the job.

• But the whole point is that you need to show that such an $n_0$ exists, using only the fact that $p^2<2$ (and $p>0$). Rudin constructs a number $q$ that is certainly larger than $p$, but certainly satisfies $q^2<2$, using only the properties that it is known that $p$ satisfies. – Glen O Jun 9 '18 at 8:47
• @GlenO But that argument is easy: We have $$(p+1/n)^2 = p^2 +2p/n +1/n^2 \le p^2 +2p/n +1/n = p^2 +(2p+1)/n.$$ If that last expression is $<2$ we're done. But that's the same as saying $n>(2p+1)/(2-p^2).$ Choose any such an $n$ and we're good to go. – zhw. Jun 10 '18 at 20:26
• See my second paragraph and the link. Rudin simply takes a somewhat arbitrary rational point to the right of the root (he uses (2,2)) and his construction is simply looking at the chord through that point and the previous solution. Not lame. Good geometry...but it would have been nice for him to have drawn the picture. – Robert McLean MD PhD Jun 11 '18 at 5:16
• @RobertMcLeanMDPhD Rudin is doing this literally on page 2 of his book. There is about zero machinery available to the student at this point. You are talking about Newton's method, convexity, etc in your answer. I find the $(p+1/n)^2<2$ approach more intuitive, and it leads to an easy answer. – zhw. Jun 11 '18 at 18:23
• @zhw. - Now you're pulling a rabbit out of a hat by introducing a new step with "$1/n^2\leq1/n$" - it's certainly right, but no less arbitrary as an approach than Rudin's. And what's more, it produces a very similar expression - since the value you obtain that $n$ must be larger than is rational, you can just use $p-(p^2-2)/(2p+1)$... which is just a variation of Rudin's expression with $2p+1$ instead of $p+2$. I really don't see why your approach is any more intuitive than Rudin's, and I really can't see why, in a question about how it works, you chose to attack it. – Glen O Jun 12 '18 at 15:20

This cries out Newton's method looking for the root of $f(x)=x^2-2$. But Newton's method will give a rational number bigger than $\sqrt{2}$, i.e., outside of $A$. All the iterations of Newton will give a rational point greater than $\sqrt{2}$ (due to the positive second derivative at the root) (thanks to Ian for correcting this). This shows incompleteness of the set of rationals greater than $\sqrt{2}$.

We simply take a rational number bigger than the square root of 2, say 2. We form the chord between the point $(p,f(p))$ and $(2,f(2))=(2,2)$. We take the intersection of the chord with the $x$-axis as our new point. I drew the picture with geogebra: https://ggbm.at/nkfcPUB4 You simply need to verify that the Rudin's formula gives you the intersection of the chord with the $x$-axis.

Convexity of the graph of $y=x^2-2$ ensures the new point is in $A$.

• Interesting perspective, but the choice of the outside point is still somewhat arbitrary. (The point is that the "rise" from $(p,f(p))$ to $(q,0)$ is $-f(p)$, but the "run" is $(r-p)\frac{-f(p)}{f(r)-f(p)}=\frac{2-p^2}{r+p}$, where $(r,f(r))$ is the external point. This $r$ is more or less arbitrary.) Also the first iteration of Newton's method won't necessarily go past $2$ but it will definitely go past $\sqrt{2}$. But subsequent iterations will never return to $A$, they will stay on $A^c$ forever. – Ian Jun 9 '18 at 14:44
• Sorry, you are correct. I meant to put the square root on the 2's in the first paragraph. I have corrected it. Also, the point on the graph is absolutely random. One could have taken another rational point on the curve, say (1.5,0.25). The convexity of the quadratic ensures the ensuing point will be larger but less than 2. The arithmetic is uglier and there isn't a need. – Robert McLean MD PhD Jun 9 '18 at 18:40
• Subsequent iterations of Newton's method will still remain in $A^c$, so your third and fourth sentences are still not correct. – Ian Jun 10 '18 at 4:11
• I love this answer! It has cleared up long standing question for me. It is reminiscent of the chord tangent process for adding points on an elliptic curve. Newton's method is after all used to double a point on an elliptic curve. But in this case we seek chords-not tangents-to find rational points on $x^2 - 2$, and the convexity of this function is crucial. – student Feb 7 at 22:30

Consider this alternative choice of $q$.

By Archimedes' axiom there exists $n \in \mathbb{N}$ such that $n(2-p^2) > 2p+1$.

Set $q = \left(p+\frac1n\right)^2 \in \mathbb{Q}$.

We have $$n^2(2-p^2) > n(2p+1) = 2np+n \ge 2np + 1$$

Dividing by $n^2$ we get

$$2-p^2 > \frac{2p}{n} + \frac1{n^2} \implies q = \left(p+\frac1n\right)^2 = p^2 + \frac{2p}n + \frac1{n^2}< 2$$

Therefore $q \in A$ and $q > p$ so the set $A$ has no maximum in $\mathbb{Q}$.