# Proving a set in $\mathbb{Q}$ that is bounded above to have no largest number (greatest element)

I'm studying the set $Q$. At this point I don't know the real numbers. This is the theorem:

Let $A$ be the set such that $A=\{p\in \mathbb{Q}^{+}:p^{2}<2\}$. Then $A$ contains no largest number.

The prove given in Rudin's book of analysis goes something like this:

Given $p\in A$, let's consider the number $q=p-\dfrac{p^2-2}{p+2}=\dfrac{2p+2}{p+2}$. Then $q^2-2=\dfrac{2(p^2-2)}{(p+2)^2}$. This prove that if $p\in A$ then $p^2-2<0$, $q>p$, and $q^2<2$. Thus $q\in A$ and $q>p$. Therefore, for every $p\in A$ we can find a rational $q\in A$ such that $p<q$.

Now here is my problem. First of all I understand the proof perfectly, but I don't see the motivation for finding $q$. Let's suppose I wanted to find $q$ in the set $B=\{p\in Q^{+}: p^{2}<3\}$. I wouldn't now how to find it.

Also I would like to know some 'standard', if there is some, process to apply in this cases. For example in my try, before looking at the solution, I was thinking in this way:

I need to find a number $q$ such that $p^{2}<q^{2}<2$ in such a way that $p<q$". If I set this numbers on the real line I can observe essentially two ways to follow.

In the first one, if try to find the number $q^2$ such that $p^{2}<q^{2}<2$ I can think of some of the form $q^{2}=p^{2}+(\dfrac{2-p^2}{n})$ where $n$ is a natural number sufficiently large as necessary (here I'm using Archimedian property) to find a perfect square.

In my second approach I'd like to find the number $q$ such that $p<q$. In this case I would think almost in the same way as before. I can think of $q$ as something sufficiently close to $p$ in the form $q=p+\dfrac{1}{n}$ with $n$ sufficiently large so that $p^2<q^{2}<2$.

So far I haven't been able to solve the problem with any of my tries and I don't know if I'm in the right direction or it's just an obsession to use the Archimedian property.

-
Notable nitpickery: it's very easy to show that there's a set in $\mathbb{Q}$ with no largest member: just consider the set $\{1, 2, 3, \ldots\}$! I presume you mean to note that there's a bounded infinite set in $\mathbb{Q}$ with no largest member, which is where the interesting analysis starts to lie. –  Steven Stadnicki Jun 29 '13 at 0:24
@StevenStadnicki Excellent observation!!. I just changed my question title so there's no problem to other users that might find the question useful. –  Daniela Diaz Jun 29 '13 at 0:36
Isn't it still very easy with the "bounded above" restriction? Why not $\{x \in \mathbb{Q} : x < 0 \}$? –  Henry Swanson Jun 29 '13 at 1:23
If all he really wanted was a set satisfying the condition in your first gray box, then of course the set of all rational numbers less than $1$ would suffice. Evidently what he did want was an upper-bounded set without a least upper bound. –  Lubin Jun 29 '13 at 1:25
@HenrySwanson Now edited, thanks again. –  Daniela Diaz Jun 29 '13 at 2:03

Eventually we’re going to have the reals, and we know how we want them to behave, so pretend for a moment that we do have them; then we want to find a rational number $q$ such that $p<q<\sqrt2$. Setting $r=q-p$, we want to find a positive rational $r<\sqrt2-p$. This inequality is equivalent to the inequality $r(\sqrt2+p)<2-p^2$, so what we want is a rational $r$ such that

$$0<r<\frac{2-p^2}{\sqrt2+p}\;.\tag{1}$$

$(1)$ still has that pesky $\sqrt2$ that we don’t really have yet. However, we know that it will be true that $\sqrt2<2$, so it will also be true (when we actually do have $\sqrt2$) that

$$0<\frac{2-p^2}{2+p}<\frac{2-p^2}{\sqrt2+p}\;.$$

Thus, if we set

$$r=\frac{2-p^2}{2+p}\;,$$

we ought to be able to prove that $p<p+r$ and $(p+r)^2<2$. And indeed the proof that you included in the question shows that we can.

If you follow the same heuristic reasoning for your set $B$, you find that setting

$$r=\frac{3-p^2}{3+p}$$

and hence

$$q=p+r=p+\frac{3-p^2}{3+p}=p-\frac{p^2-3}{p+3}$$

ought to work, and indeed it does.

-

Note that $$\frac{2p+2}{p+2}=p$$ gives $$2p+2=p^2+2p$$ $$p^2=2$$

Thus, we're playing around the fixed point of $f(x)=\dfrac{2x+2}{x+2}$ which is $\sqrt 2$. If we choose $x^2<2$, then iterating with $f$ will get use closer to $\sqrt 2$, and because the fixed point is attractive, and the function is monotone increasing, we get closer to $\sqrt 2$ from below, with increasing values.

This is another example. Suppose $r$ is rational, positive, and $$r<\sqrt 2$$

Then $$r+1<\sqrt 2+1$$ $$\frac{1}{r+1}>\sqrt 2-1$$

$$\frac{r+2}{r+1}>\sqrt 2$$

We used $(\sqrt 2-1)(\sqrt 2+1)=1$. Thus, we have obtained a new rational $q=\frac{r+2}{r+1}$ with $q>\sqrt 2$. Repeating the process we arrive at $$\frac{q+2}{q+1}<\sqrt 2$$ and replacing what $q$ was we obtain $$\frac{{3r + 4}}{{2r + 3}} < \sqrt 2$$

It turns out this new rational, call it $r$, is such that $r<r'$ and $r'^2<2$. The motivation: we played with the fixed point of $\dfrac{3x+4}{2x+3}$ which is $\sqrt 2$ again.

-

I’ll do something almost as good as the two answers so far, namely I’ll describe an explicit way of finding a sequence of negative rationals whose squares are all greater than $2$, that is rationals less than $-\sqrt2$, upper bounded (by $-1$), with no least upper bound. Here’s my method, using Newton-Raphson, which I’m very fond of, and which is (or should be) standard first-year Calculus material.

Apply Newton-Raphson to $f(x)=x^2-2$ to find a negative root. The procedure is $$z_i\mapsto z_{i+1}= z_i-f(z_i)/f'(z_i) =\frac{z_i^2+2}{2z_i}\,.$$ When you look at the picture of what’s going on, you see that if you start with a negative $z$ so that $(z,0)$ is under (to the left of) the graph, all the resulting approximations will also be to the left of the graph, so that the successive $z$’s will all be less than $-\sqrt2$, i.e. their squares will be bigger than $2$. If you start with $z_0=-2$, for instance, you get the sequence $$-2, -3/2,-17/12,-577/408\ldots$$

-

Suppose you found $~p=\max\limits_{x^2<M,x\in\mathbb Q}x~$ for some $M$. $M=2$ in your example, but it doesn't matter. Let $\Delta = \sqrt{M} - p > 0$. There is always a number $n$ such that $\frac 1 n<\Delta$, because $\frac 1 n \to 0$ (for example, $n={1+\left\lceil\frac{1}{\Delta}\right\rceil}$). But then $p < p + \frac 1 n = q < p + \Delta = \sqrt{M}$, so $p^2 < q^2 < M$.

-
I think there is something wrong in your solution, or I'm confused at something. Yo're actually supposing that there exists a greatest element, namely $~\max\limits_{p^2<M}p~=\sqrt{M}$. But if such is the case, what is the contradiction? What you proved is that if $p$ is in the set then there exists $q>p$. But again $\sqrt{M}>q$, which is fine by definition . This is the approach I was taking so I'm interested in understanding your solution. Could you elaborate more? –  Daniela Diaz Jun 29 '13 at 5:41
The contradiction is that your set has no maximum(largest number), only the supremum, because if you have the maximum, there is always some another number in this set, larger, than the largest. –  Harold Jun 29 '13 at 6:03
Oh, I see your point, thanks for clarifying. But then something is wrong because if you suppose the existence of a greatest element, such an element is also the supremum, so your $\sqrt {M}$ is at the same time the maximum and the supremum so there is actually no contradiction in your final step. What I think you're doing is considering that you have a least upper bound and then proving that such a number cannot be the largest number in the set, which is possible if you are working inside the real numbers but not if just working inside the rationals, right? –  Daniela Diaz Jun 29 '13 at 6:42
I don't know, I think I'm missing something. You're notation is not very clear. What is $~\max\limits_{p^2<M}p~$? is it $p$ or is it $\sqrt {M}$. If $p$ is your máximum then $\sqrt {M}$ is the least upper bound of the set and then your proof is correct if you're working in $\mathbb{R}$. If your $p$ is not the maximum and then $\sqrt {M}$ is, then you don't get to a contradiction. –  Daniela Diaz Jun 29 '13 at 8:58
I used the supremum just in explanation, so you can forget about the words "..., only the supremum, ...", they are useless for the proof. And yes, you are right, I wrote the estimation for $\frac 1 n$, not for $n$, foolish mistake. –  Harold Jun 29 '13 at 18:44