Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $S=\{r\in \mathbb{Q}\mid r\leq\sqrt{3}\}$.

Now prove that $S$ is bounded above in $\mathbb{Q}$ but it does not have a supremum in $\mathbb{Q}$.

The following is the proof I came up with, but I do not feel confident with it. Please let me know what is incorrect or could be written better.

Proof.
Let $m=\sqrt{3}$.

Then their exists an $m$ that belongs to the set of real numbers $\mathbb{R}$ such that $r\leq m$ for all $r$ that belong to the set $S$. Hence, $S$ is bounded above in $\mathbb{Q}$.

Now, suppose that there exists a smaller upper bound in $S$, $t$. Then $t<\sqrt{3}$, and as $t$ is an upper bound of $s$, $t\geq s$ for all $s\in S$.

Therefore, $s\leq t<\sqrt{3}$, and $s\leq \sqrt{3}\leq t$, which implies $\sqrt{3}\leq t\leq \sqrt{3}$, which is impossible.

Therefore, $S$ does not have a supremum in $\mathbb{Q}$.

Edit (added by Arturo Magidin, taken from comment made by OP)

2nd Attempt:
Proof Let $m=\sqrt{3}$. Then $m\geq r$ for all $r$ that belong to $S$. Hence, $S$ is bounded above by $m$ in $\mathbb{R}$. Therefore, $S$ is bounded above in $\mathbb{Q}$. Now, suppose $m=\sup(S)$ in $\mathbb{R}$. Let $t$ be an upper bound in $\mathbb{Q}$ and $t\leq m$. Hence, there exists $t$ that belongs to $\mathbb{Q}$ such that $m>t\geq r$ for every $r$ that belongs to $S$. Then there would exist an $r$ that belongs to $S$ such that $r>t$. Which contradicts $t\geq r$. Therefore, $S$ doesn't have a supremum in $\mathbb{Q}$.

3rd Attempt:
Proof
Since for every $r \in S$ $r<3$ and $3 \in \mathbb{Q}$, we know $S$ is bounded above in $Q$.
To prove it doesn't have a supremum in $\mathbb{Q}$, I will use contradiction.
Suppose m were the supremum of $S$ in $\mathbb{Q}$, then m does not equal $\sqrt{3}$, and $m\in \mathbb{Q}$.

If $m\lt \sqrt{3}$, by Archmedian's Property, their exists $t$ that belongs to $\mathbb{Q}$ such that $m\lt t\lt \sqrt{3}$.
This is a contradiction, because $m$ isn't an upper bound.
If $m\gt\sqrt{3}$, by Archmedian's Property, their exists $u$ that belongs to $\mathbb{Q}$ such that $\sqrt{3}\lt u\lt m$
This is also a contradiction.
Hence, $S$ does not have a supremum in $\mathbb{Q}$

share|improve this question
    
@enlgmatic: Add it to the body as an edit marked as an edit, not as a comment, and not twice (once here, once as a response to my answer). –  Arturo Magidin Mar 30 '11 at 2:29
2  
If you are trying to prove something in $\mathbb{Q}$ you should not make reference to $\mathbb{R}$-unless you want to prove $\mathbb{R}$ exists and has the properties you need. Otherwise, you can just show that given any upper bound in $\mathbb{Q}$, there is a smaller one, also in $\mathbb{Q}$, so the first was not a supremum. –  Ross Millikan Mar 30 '11 at 3:31
    
@enlgmatlc: The fact that $S$ is bounded above in $\mathbb{Q}$ is now good (except for the fact that you have a dangling sentence; these should not be two separate sentences, but two clauses of the same sentence, connected by a comma). The second part doesn't do anything (and you're still trying to bring in the reals into the picture), and doesn't say who $y$ is. Right now, the final sentence doesn't go anywhere or prove anything. –  Arturo Magidin Mar 30 '11 at 19:55
1  
@enlgmatlc: Your text disappeared because you are not using mark-up correctly; < and > outside of dollar signs are HTML mark-up, and the renderer tries to interpret them as such. Please look at other people's postings to see how to render math formula correctly; in particular, $\mathbb{Q}$ produces the nice $\mathbb{Q}$. –  Arturo Magidin Mar 30 '11 at 20:26
1  
@enlgmatic: That's better, though it depends a bit on what you understand to be "the Archimedean property" (note spelling). For instance, one way to phrase the Archimedean property is that for all $\delta\gt 0$ and all $M\gt 0$ there is a natural number $n$ such that $n\delta\gt M$; but this by itself would not guarantee that you can also make $n\delta$ *smaller$ than some $N\gt M$. But if you've proven that given any $0\lt M\lt N$, you can find a rational $q$ with $M\lt q\lt N$, then that's what you want to use. –  Arturo Magidin Mar 30 '11 at 20:28
show 2 more comments

3 Answers

up vote 13 down vote accepted

Let me give you an example to show you why talk about the real numbers and the supremum in the reals is really not a good idea in general.

Consider the set $\mathfrak{Q}=\mathbb{Q}\cap \Bigl((-\infty,0)\cup[1,\infty)\Bigr)$. That is, $\mathfrak{Q}$ consists of all rationals that are either negative, or greater than or equal to $1$.

Now let $\mathcal{S}=\{q\in\mathbb{Q}\mid q\lt 0\}$, the negative rationals.

Notice that $\mathcal{S}$ is a subset of $\mathfrak{Q}$, and is bounded above in $\mathfrak{Q}$, since $1\in\mathfrak{Q}$, and for all $s\in \mathcal{S}$, $s\leq 1$.

Now, let me take a parallel argument to the one you are attempting to "show" that $S$ does not have a supremum in $\mathfrak{Q}$: Take $m=0$; then $m$ is the supremum of $\mathcal{S}$ in $\mathbb{R}$. Now suppose that $t\in\mathfrak{Q}$ is an upper bound on $\mathcal{S}$, and that $t\lt 0$. Then because $t\lt 0$ and $0$ is the supremum of $\mathcal{S}$ in $\mathbb{R}$, there exists $s\in \mathcal{S}$ such that $t\lt s\leq 0$. So $t$ is not an upper bound for $\mathcal{S}$ in $\mathfrak{Q}$, a contradiction. "Therefore", $\mathcal{S}$ does not have a supremum in $\mathfrak{Q}$.

Of course, the argument is completely false: because $1\in\mathfrak{Q}$ is the supremum of $\mathcal{S}$ in $\mathfrak{Q}$: note that $s\leq 1$ for all $s\in \mathcal{S}$; and if $t\in\mathfrak{Q}$ is strictly smaller than $1$, then because it is in $\mathfrak{Q}$ it must also be strictly smaller than $0$, so there exists $s\in \mathcal{S}$ with $t\lt s\leq 1$. That is:

  • For all $s\in \mathcal{S}$, $s\leq 1$.
  • For all $t\in\mathfrak{Q}$, if $t\lt 1$ then there exists $s\in \mathcal{S}$ such that $t\lt s$.

These two properties show that $1$ is the supremum of $\mathcal{S}$ in $\mathfrak{Q}$. Notice that $1$ is not the supremum of $\mathcal{S}$ in $\mathbb{R}$, or even in $\mathbb{Q}$. But it is the supremum of $\mathcal{S}$ in $\mathfrak{Q}$.

So you should really not use the supremum of your $S$ in $\mathbb{R}$, except perhaps as a "behind the scenes" guide to what you want. It could be, at least in principle, possible for a subset of $\mathbb{Q}$ to have a supremum in $\mathbb{Q}$ which is different from its supremum in $\mathbb{R}$ (the supremum in $\mathbb{Q}$ would have to be larger than the supremum in $\mathbb{R}$, just as it is in my example above).


First: Since you are saying what $m$ is, you should not then follow it up with "There exists an $m$ that belongs to the real numbers." You would just say "Then $m$ belongs to the real numbers and..."

Second: That said, that part of the argument is incorrect.

To show that a subset $S$ of $\mathbb{Q}$ is bounded above in $\mathbb{Q}$, you need to exhibit an element $m$ of $\mathbb{Q}$ such that $s\leq m$ for all $s\in \mathbb{Q}$. Showing an element not in $\mathbb{Q}$ does not show the set is bounded above in $\mathbb{Q}$. So your argument about $m$ doesn't work.

Third: You cannot conclude that an upper bound of $S$ in $\mathbb{Q}$ will be strictly smaller than $\sqrt{3}$. And if you assume it, then you are assuming your own contradiction:

You know that if $t$ is an upper bound to $S$ in $\mathbb{Q}$, then by virtue of being in $\mathbb{Q}$, $t$ is also in $\mathbb{R}$ and an upper bound to $S$. And therefore $t$ will be greater than or equal to the supremum of $S$ in $\mathbb{R}$, since $S$ is also bounded above in $\mathbb{R}$. So you know that $t\geq \mathrm{sup}_{\mathbb{R}}(S)$. Now, $\mathrm{sup}_{\mathbb{R}}(S)$ happens to be $\sqrt{3}$, but you haven't proven that this is the case, so you cannot invoke that. And you don't explain how you get that $\sqrt{3}\leq t$ (presumably from the supremum property, but you haven't shown that $\sqrt{3}$ is the supremum in $\mathbb{R}$, so you cannot invoke the supremum property for $\sqrt{3}$).

Fourth: So if you know anything about a possible supremum of $S$ in $\mathbb{Q}$, it is that it is greater than $\sqrt{3}$ (the supremum of $S$ in $\mathbb{R}$), since it must be greater than or equal, and cannot be equal. So even if your argument about what happens if $t\lt\sqrt{3}$ were correct (well, technically it is because your assumption is an impossibility, which is why you get a contradiction), you would not be done; you would still need to consider the possibility that the supremum $t$ of $S$ in $\mathbb{Q}$ is greater than $\sqrt{3}$, instead of smaller.

Added. Comment on 2nd attempt.

To show that $S$ is bounded above in $\mathbb{Q}$, you should produce an element of $\mathbb{Q}$ that bounds $S$ above. Going around to $\mathbb{R}$ does not do it. Your argument is "gappy", in that it assumes without stating that you can take $m$ and produce a rational bigger than $m$ in order to conclude that there is a rational that bounds $S$ above. Well, why not produce one?

I could argue that the set $\{1.5\}$ of rationals is bounded above in the rationals by saying "Well, $\pi\in\mathbb{R}$ is greater than all elements of $\{1.5\}$, and so $\{1.5\}$ is bounded above in $\mathbb{R}$, and therefore $\{1.5\}$ is bounded above in $\mathbb{Q}$." But isn't it so much better, clearer, and simpler, to just say "$2\in\mathbb{Q}$, and $2$ is an upper bound for ${1.5}$"?

You merely assert that $m$ is greater than or equal to all $r\in\mathbb{Q}$; it should be proven.

Even assuming the rest of the argument were correct (it isn't), you cannot simply assume that $m=\sup(S)$ in $\mathbb{R}$. If you don't prove it, then your argument is contingent on that extra assumption. To complete the proof, you would have to also consider the case in which $m$ is not the supremum of $S$ in $\mathbb{R}$.

Next: You continue to introduce your own contradiction when you assume that $t$ is both an upper bound to $S$ in $\mathbb{Q}$ and that $t\lt m$. That is impossible to begin with because you are assuming that $m$ is the supremum of $S$ in $\mathbb{R}$: any upper bound to $S$ has to be greater than or equal to the supremum of $S$ (any upper bound in $\mathbb{Q}$ is also in $\mathbb{R}$). So you would still need to consider the possibility that $t\geq m$, which you never do. So even if your argument about $t$ were correct (it's not), it would still be incomplete.

Finally: you merely assert "there would exist an $r\in S$ such that $r\gt t$. Just saying so doesn't prove it. You have to prove that there is such a thing.


Here's the issue here: you know that $S$ has a supremum in $\mathbb{R}$; call it $m$. If $t$ is any element of $\mathbb{Q}$ that is an upper bound to $S$ in $\mathbb{Q}$, then it is also an upper bound to $S$ in $\mathbb{R}$, so by definition of the supremum, you must have $m\leq t$. If $m\lt t$, then by the properties of the rationals, you should show or justify that there has to be a number $t'$ which (i) is an upper bound to $S$; (ii) is in $\mathbb{Q}$; and (iii) is strictly between $m$ and $t$, $m\lt t' \lt t$. That means that the only number that has a shot at being the supremum of $S$ in $\mathbb{Q}$ is $m$ itself, the supremum of $S$ in $\mathbb{R}$ (why? You need to explain this). So then you should prove that the supremum of $S$ in $\mathbb{R}$ is not a rational number, and that will give you a correct argument.

share|improve this answer
    
Excellent insight. –  copper.hat Oct 10 '13 at 1:04
add comment

There is no need to mention the real numbers.

As Pacciu says, we have $S=\{ r\in \mathbb{Q}:\ r\leq 0 \text{ or } r^2\leq 3\}$. So $\frac{2}{1}$ is an upper bound for $S$ since $\frac{2}{1} \gt 0$ and if $ r \gt \frac{2}{1}$ then $r^2 \gt \left(\frac{2}{1}\right)^2 = 4 \gt 3$.

Now suppose $\frac{p}{q}$ with $p$ and $q$ positive integers is an upper bound for $S$, i.e. $p^2 \ge 3 q^2 $. Then $\frac{3q^2+4pq-p^2}{4q^2}$ is a smaller upper bound for $S$ and so there is no lowest upper bound or supremum for $S$ in $\mathbb{Q}$.

Incidentally, this gives the sequence $\frac{2}{1}, \frac{7}{4}, \frac{111}{64}, \frac{28383}{16384}, \cdots$, approaching $\sqrt{3}$ from above.

share|improve this answer
    
I fixed your LaTeX. There was a superfluous $. By the way: It is better to use \gt and \lt instead of > and < because sometimes the parser gets confused by trying to interpret everything in between < and > as HTML. –  t.b. Mar 30 '11 at 12:52
    
@Theo Buehler: Thank you - I cannot see the rendered LaTeX so I am just guessing what it looks like. –  Henry Mar 30 '11 at 13:05
add comment

Maybe you can argue as follows.

It is obvious that $S=\{ r\in \mathbb{Q}:\ r\leq 0 \text{ or } r^2\leq 3\}$. Hence each $p\in \mathbb{Q}$ s.t. $3< p^2$ is an upper bound for $S$; therefore $S$ is bounded from above in $\mathbb{Q}$.

Assume, by contraddiction, that $S$ has the supremum $m\in \mathbb{Q}$; then clearly $m^2\geq 3$ (for $m$ is the least upper bound of $S$), but indeed $m^2=3$: in fact, using an algorithm for the computation of the square root, one can generate a sequence of rational numbers $p_n\in \mathbb{Q}$ s.t. $p_n^2\geq 3$ and $p_n^2-3\leq \frac{1}{n}$; on the other hand $0\leq m^2-3\leq p_n^2-3$, thus $0\leq m^2-3\leq \frac{1}{n}$ for all $n$; therefore $m^2-3=0$ as claimed. But this is a contraddiction, because it is well known that there doesn't exist any $m\in \mathbb{Q}$ s.t. $m^2=3$. Hence $S$ doesn't have a supremum in $\mathbb{Q}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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