How to prove that the set $A = \left\{ {p:{p^2} < 2,p \in {\Bbb Q^+}} \right\}$ has no greatest element? More specifically, I have to find a $q$ in $A$ such that $q$ is larger than any $p$ in $A$.
The only thing I can think of is using (${2 - {p^2}}$) somehow, or ${(p+x)^2}<2$, but other than that I don't know how to proceed. This exercise is taken from the very first chapter of Walter Rudin's Principles of Mathematical Analysis. Quoting the exercise:

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}}$$

But he didn't explain how he came up with that number. 
The only thing I've thought of is the following procedure:
$$\eqalign{
  & {p^2} + (2 - {p^2}) = 2 \Rightarrow {p^2} + (\frac{{2 - {p^2}}}{2}) < 2,{\text{ and since }}2 - {p^2}{\text{ is always positive,}}  \cr 
  & {p^2} < \left[ {{p^2} + (\frac{{2 - {p^2}}}{2})} \right] < 2  \cr 
  & {\text{Therefore, let }}q = \sqrt {{p^2} + (\frac{{2 - {p^2}}}{2})} ,{\text{ then:}}  \cr 
  & p < q < \sqrt 2  \cr} $$
However, my result doesn't necessarily belong to ${\Bbb Q}$. I wonder how did he obtain the value of $q$ in the book.
EDIT: Feel free to point out if there are more appropriate tags for this question.
 A: To show that $A$ has no greatest element, you have to show that there is no $q\in A$ which is greater than any $p\in A$, the opposite of your first line.
If $p^2<2$, we take the number $q=p+\frac{2-p^2}{p+2}=2\frac{p+1}{p+2}$. Then $p<q$ and $q^2=4\frac{(p+1)^2}{(p+2)^2}$. From $p^2<2$ you can infer $\frac{(p+1)^2}{(p+2)^2}<\frac{1}{2}$, so $q^2<2$.
This shows that to every rational $p<2$ we can associate $q=2\frac{p+1}{p+2}$, which will also be rational, and satisfying $p<q$, $q^2<2$, so $p$ is not the largest rational with this property.

As to where $q=p+\frac{2-p^2}{p+2}$ comes from: We are basically trying to find a root of $t^2-2$, by starting with some non-root $p$ and trying to make a better approximation to $\sqrt{2}$.
Note that the equation $q=p+\frac{2-p^2}{p+2}$ is equivalent to
$$(p^2-2)+(p+2)(q-p)=0$$
In other words, $q$ is a root of $t\mapsto (p^2-2)+(p+2)(t-p)$, which is the line which passes through $(p,p^2-2)$ with slope $(p+2)$. If you look at this line, and compare it with the graph of $t\mapsto t^2-2$, you will see that the intersection of the line and the $x$-axis will be closer to $\sqrt{2}$, and still smaller because $p+2>p+\sqrt{2}=\frac{2-p^2}{\sqrt{2}-p}$ (and this is the slope of the secant of the graph of $t^2-2$ passing through $(p,p^2-2)$ and $(\sqrt{2},0)$).
In fact, the slope $(p+2)$ works to make the inequalities in the exercise easier to deal with, but any number greater than $p+\sqrt{2}$ would work as well. Indeed, if $\alpha>p+\sqrt{2}$ and $(p^2-2)+\alpha(q-p)=0$, then
$$q=p+\frac{2-p^2}{\alpha}$$
so $q>p$, and
$$q<p+\frac{2-p^2}{p+\sqrt{2}}=p+(\sqrt{2}-p)=\sqrt{2}$$
i.e., $q^2<2$. If we choose $\alpha$ rational (so we'd need to know in advance more-or-less how much $\sqrt{2}$ is), then $q$ given as above will also be rational.
A: Let me share to you how I think Rudin did his magic in a more logical/principled way.
So what we want is to show that for any $p \in A = \{ p \in Q_+ : 0<p^2 <2\}$ we can always find a larger $q \in A$. The way I thought of it is that we want a $q = p+\epsilon, \epsilon>0$ such that:
$$ 0<p<(p+\epsilon)^2 = p^2 + 2 \epsilon p + \epsilon^2< 2$$
if you make $\epsilon$ the subject its really difficult to come up with a way to have its solution not involving square roots as you might have noticed. I realized that was really annoying and that was the issue. So with that intuition in mind I tried re-writing $p^2 + 2 \epsilon p + \epsilon^2$ so that maybe with some inspiration I could get rid of the term $\epsilon^2$. The first thing I tried was to write it without any squares at all it by factor $\epsilon$ and $p$. This lead to:
$$ p^2 + 2 \epsilon p + \epsilon^2 = p^2 + \epsilon p + \epsilon p+ \epsilon^2= p(p+\epsilon)+\epsilon (p+\epsilon)$$
then I stared at this equation and wondered if there was anything else I knew about the problem so that I could "get rid" of one of the terms in $\epsilon (p+\epsilon)$ with the goal of removing the $\epsilon^2$ and maybe having something in the rationals for sure. Doing that I noticed involved some type of knowledge of $q = p+\epsilon$ or $\epsilon$. I knew $\epsilon>0$ which was not  terribly helpful but I noticed that for sure $p+ \epsilon < 2$ (by drawing some diagrams, then I discovered I could "cheat" by using the fact that I knew $q = p+ \epsilon < \sqrt 2 < 2$ to justify it to myself, though you can easily prove it by contradiction if you want a rigorous reason). At this point I noticed that by using the inequality I actually introduced knew knowledge to the problem and not just playing around with the rules of algebra, which was quintessential because otherwise things are just re-writting things in terms of others for hours as it happened to me. 
Anyway this lead to realization that I could indeed remove the $\epsilon^2$ as follows:
$$ p(p + \epsilon) + \epsilon(p+\epsilon) < p^2 + p \epsilon + 2 \epsilon $$
hoping that it wouldn't lead to an upper bound that wasn't too high/large, since I introduced the fact $p+\epsilon < 2$ which is an upper bound (lets hope its not too large!). Right now I intuitively though I bet this will work because I indeed can control how small I make $\epsilon$ in order to make $p \epsilon + 2 \epsilon$ sufficiently small. I proceeded by just enforcing that it was indeed smaller than 2:
$$ q = (p+\epsilon)^2 < p^2 + p \epsilon + 2 \epsilon < 2 $$
then I proceeded to make $\epsilon$ the subject to get:
$$ 0 < \epsilon < \frac{2 - p^2}{p+2} = -\frac{p^2 - 2}{p+2}$$
at this point I realized that choosing $\frac{2 - p^2}{p+2}$ would make the upper bound (introduced after using the fact $q =p+\epsilon<2$) equal to 2 but if we applied it to $q = p+\epsilon$ itself then since it was strictly less than the upper bound, that it we would be safe and have $q$ still be less than $2$. That happened to be correct and so I choose that value $\epsilon = -\frac{p^2 - 2}{p+2} $. 
Notice however that any rational constant should work to bound $p+\epsilon$ as long as its constant. Though, larger bounds would obviously require smaller $epsilon$'s (which is fine as long they are rationals).
A: Rudin was most likely using facts about linear fractional transformations.
Let $S > 0$, $K > 0$ with $K^2 > S$
Set $F(x) = (S + Kx)/(K + x)$
IF $p > 0$ AND $p^2 < S$ THEN $p < F(p)$ AND $[F(p)]^2 < S$
PROOF
Since $F(x) = x + (S - x^2)/(K + x)$, it is clear that $p < F(p)$.
$[F(p)]^2 < S$ iff $S^2 + 2KSp + K^2p^2 < SK^2 +2KSp + Sp^2$ iff
$(K^2 -S) p^ 2 < SK^2 -S^2$ iff
$p^2 < (SK^2 -S^2)/(K^2 -S)$
But you can easily see that $(SK^2 -S^2)/(K^2 -S) = S$.
A: I think he came up with it by endless division of guessing the square root.
$p <q $
and $p^2 <q^2< 2$  (but symmetrically we want the opposite if $p^2 > 2$
$q^2 - p^2 =(q+p)(q-p)<2 - p^2$
$q< p + \frac {2-p^2}{p+q} $
$q < p - \frac {p^2-2}{p+q}=\frac {qp+2}{p+q}$
$q $ can be anything that satisfies that.
Meh.... $q =p - \frac {p^2-2}{p+2}=\frac {2p+2}{p+2}$ makes the math easy.
