Possible Duplicate:
Rational Numbers

Suppose $\{x \in \mathbb{Q}|x>0,x^2<2\}$ has a supremum. Call this supremum $c$. In order to show that this cannot be the case, we learned that we need to introduce $\xi$ with $\xi=\frac{2c+2}{c+2}$ and then find a contradiction. But why this $\xi$? Why not another $\xi$? How do you find this choice?


marked as duplicate by Qiaochu Yuan Dec 13 '11 at 20:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Because we want $\sqrt 2$ to be this supremum. We choose $\xi$ to fit the proof that $\sqrt 2$ is irrational. $\endgroup$ – Asaf Karagila Dec 13 '11 at 14:24
  • 1
    $\begingroup$ (This comment doesn't address your actual question). You should be careful about your statement. When you say "In order to show that this cannot be the case", what do you mean by this? What I am getting at is that the set in question does have a supremum, but you are trying to show that the supremum is not in the set itself. In other words, the set does not have a maximum. $\endgroup$ – JavaMan Dec 13 '11 at 14:52
  • $\begingroup$ @JavaMan: Actually, I believe he's trying to show that the supremum isn't rational. Even if he took $\{x\in\mathbb{R} : 0<x, x^2<2\}$, the set still wouldn't have a maximum, but it would have a supremum in $\mathbb{R}$. $\endgroup$ – jwodder Dec 13 '11 at 17:24
  • $\begingroup$ @jwodder: Even if you take it in $\mathbb R$ it still won't have a maximum. $(\sqrt 2)^2 = 2$, therefore $\sqrt 2$ is not in the set $\{x\in\mathbb R\mid x^2<2\}$. $\endgroup$ – Asaf Karagila Dec 13 '11 at 17:32
  • $\begingroup$ @Qiaochu.. the question isn't really an exact duplicate. The old one dealt with motivation for the transformation, while the answers here give the proof itself that the set doesn't have a rational supremum. $\endgroup$ – Zarrax Dec 13 '11 at 21:07

First of all, I think you and Zarrax are both a little confused about what you are showing (or you are using a nonstandard definition of supremum). The supremum of a set is its least upper bound. Now, in the real numbers, your set has the least upper bound $\sqrt{2}$. What I suspect you are trying to show is that this set does not have any least upper bound in the rationals.

Let $f(c) = \frac{2c+2}{c+2}$.

The key properties of $f$ are

(1) $f$ maps $\mathbb{Q}$ to $\mathbb{Q}$.
(2) If $c$ is a rational upper bound for $\{ x : x^2<2 \}$, then $f(c)$ is a smaller upper bound.

If you'll allow me to mention real numbers, then property (2) can be rephrased as:
(2') If $\sqrt{2} < c$, then $\sqrt{2} < f(c) < c$.
Notice that my inequalities in (2') go the opposite direction from Zarrax's; I think that is because he read your question differently than I did.

So, any function which obeys (1) and (2') will make this proof work, and you shouldn't get too focused on which one your book uses. I would have thought of $c \mapsto \frac{c+2/c}{2}$.

  • $\begingroup$ I just meant my answer as a proof by contradiction, and I edited my post accordingly. Incidentally the map $f(c) = {1 \over 2}(c + {2 \over c})$ takes numbers below $\sqrt{2}$ to numbers above $\sqrt{2}$ so it doesn't serve an identical purpose. $\endgroup$ – Zarrax Dec 13 '11 at 17:08
  • $\begingroup$ So, I understand the definition of a supremum to be a least upper bound. So the way I would set up this proof is "Let $c$ be an upper bound. Then $\frac{1}{2}(c+2/c)$ is a lesser upper bound, so $c$ is not the least upper bound. We have shown that the set has no supremum." Thus, it is irrelevant what $f$ does to a $c$ which is less than $\sqrt{2}$, since such a $c$ would not be an upper bound. I imagine you are thinking of the proof differently? $\endgroup$ – David E Speyer Dec 13 '11 at 17:27
  • $\begingroup$ Incidentally, in (2) of your answer one still has to show that $f(c)$ is an upper bound for $\{x \in {\mathbb Q}: x^2 < 2\}$. $\endgroup$ – Zarrax Dec 13 '11 at 17:47
  • $\begingroup$ I am using the fact that if $x$ is the least upper bound of a set $A$, then there cannot be a $y \in A$ with $x<y$; $x$ is not an upper bound for $A$ if such a $y$ existed. We are reading the question the same way here, just our proofs are different. $\endgroup$ – Zarrax Dec 13 '11 at 18:09

The significance of the set $S:=\{x\in{\mathbb Q}_{>0}\ |\ x^2<2\}$ is the following: It is a nonempty subset of ${\mathbb Q}$ which is obviously bounded above, but which has no least upper bound (called supremum) in ${\mathbb Q}$. As a consequence, the ground set ${\mathbb Q}$ is not "order complete" and should better be replaced by a more encompassing set of numbers, which of course is ${\mathbb R}$.

In order to show that $S$ has no supremum in ${\mathbb Q}$ one has to show that no number $c\in{\mathbb Q_{>0}}$ qualifies as supremum of $S$.

Given any trial $c\in{\mathbb Q_{>0}}$ then we all know that $c^2\ne2$, whence either $c^2<2$ or $c^2>2$. The "tricky" number

$$\xi:={2c+2\over c+2}\in{\mathbb Q}_{>0}$$


$$\xi -c={2-c^2\over c+2}\ ,\qquad \xi^2-2={2(c^2-2)\over(c+2)^2}\ .$$

Now, if $\ {\rm (a)}\ c^2<2$ then it follows that $\xi>c$ and $\xi^2<2$, whence $\xi\in S$, so $c$ is not an upper bound for $S$.

If $\ {\rm (b)} \ c^2>2$ then $\xi<c$ and $\xi^2>2>x^2$ for all $x\in S$. As $t\to t^2$ is strictly increasing for $t>0$ it follows that $\xi>x$ for all $x\in S$, whence $\xi$ is an upper bound for $S$ strictly smaller than $c$.

It follows that in both cases (a) and (b) the number $c$ does not qualify as a supremum for the set $S$.

I don't think there is a systematic procedure to "invent" such a $\xi$ (after all, it is not uniquely determined). You have to fiddle around with inequalities until you hit the expression which is "just right".


Suppose {$ x\in {\mathbb Q}: x^2 < 2$} had a supremum $c$ that is rational. We will derive a contradiction. Note $c$ is positive since $1$ is in the above set.

Case 1: $c^2 < 2$: Use algebra to show that $\displaystyle{c < {2 + 2c \over c + 2}}$, and then use some more algebra to show $\displaystyle{\bigg({2 + 2c \over c + 2}\bigg)^2} < 2$. So $\displaystyle{{2 + 2c \over c + 2}}$ is another rational number with $\displaystyle{c < {2 + 2c \over c + 2}}$ and ${\displaystyle \bigg({2 + 2c \over c + 2}\bigg)^2 < 2}$. Hence a contradiction since $c$ is supposed to be the supremum.

Case 2: $c^2 > 2$: Reverse the inequalities above. Get ${\displaystyle c > {2 + 2c \over c + 2}}$ and ${\displaystyle\bigg({2 + 2c \over c + 2}\bigg)^2 > 2}$. If $x > 0$ were rational such that $x^2 < 2$, we must have $x < {\displaystyle{2 + 2c \over c + 2}}$ (Square both sides, using that ${\displaystyle{2 + 2c \over c + 2}}$ is positive). This means that ${\displaystyle{2 + 2c \over c + 2}}$ is greater than any $x$ such that $x^2 < 2$; ${\displaystyle{2 + 2c \over c + 2}}$ is an upper bound for {$ x\in {\mathbb Q}: x^2 < 2$}. this contradicts that $c$ is a least upper bound.

Case 3: $c^2 = 2$: Show no rational number squared is equal to 2, using prime factorizations for example.

Thus in all three cases we get a contradiction. (This aint as easy at it looks :). And thanks to Christian Blatter for making me realize I overlooked Case 2.)

As for how they thought of this, there are various iterative procedures to get closer and closer to square roots of natural numbers, and when you apply it to a rational number $c$ you get another rational number. This one has the property that you stay between $c$ and $\sqrt{2}$ at the next iteration.


Not the answer you're looking for? Browse other questions tagged or ask your own question.