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?
On
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.
On
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$.
On
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}$.
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}$.