4
$\begingroup$

I am working on the following problem: If a set of integers $S \subset \mathbb{N}$ has a supremum, show that $\sup S \in S$.

My approach is as follows:

Let $s_0 = \sup S$ and suppose $s_0 \notin S$. It is a fact that for every $\epsilon > 0$ there exists $a \in S$ such that $ s_0 - \epsilon < a \leq s_0. $ However, since $s_0 \notin S$ and $a \in S$ we in fact have $ s_0 - \epsilon < a < s_0 $ But since $\epsilon > 0$ it follows that $ s_0 - \epsilon < a < s_0 + \epsilon \implies -\epsilon < a - s_0 < \epsilon \implies |a - s_0| < \epsilon $

Since this is true for every $\epsilon > 0$, $a - s_0 = 0 \implies a = s_0$, a contradiction. Therefore, $s_0 \in S$

My question then is whether this argument is valid. I believe it is correct but it is significantly different from the author's solution so I would like a second opinion.

  • 0
    Write $a_{\epsilon}$ instead of $a$, and things will not look so good.2011-12-14

2 Answers 2

7

Note that nowhere in your argument did you use the fact that $S$ is a set of integers. If the argument were valid, why is it not valid for sets of real numbers?

The error is that the witness $a$ actually depends on $\epsilon$. You have no warrant for assuming a priori that you can always pick the same $a$, regardless of what $\epsilon$ is, so the implication that leads to $a-s_0=0$ is invalid.

To write this properly, you would have to say:

For every $\epsilon\gt 0$ there exists $a(\epsilon)$ (that depends on $\epsilon$) such that $a(\epsilon)\in S$ and $s_0-\epsilon\lt a(\epsilon)\leq s_0$. Therefore, for every $\epsilon\gt 0$ there exists $a(\epsilon)\in S$ such that $|a(\epsilon)-s_0|\lt\epsilon$.

And now it should be clear why you cannot go from this to "Therefore, $a(\epsilon)-s_0 = 0$."

Again: the tip-off should have been that you never used the fact that every element of $S$ is an integer.

Now, to fix this, we can actually proceed directly: let $s_0$ be the supremum of $S$. Then, since $s_0$ is the supremum, for every $n\gt 1$ there exists $a_n\in S$ such that $s_0-\frac{1}{n} \lt a_n \leq s_0.$ Now notice that for all $n$ and $m$, then $|a_n-a_m|\leq |a_n-s_0|+|s_0-a_m| \lt \frac{1}{n}+\frac{1}{m}\leq \frac{1}{2}+\frac{1}{2} = 1.$ So $|a_n-a_m|\lt 1$. But $a_n$ and $a_m$ are both integers. (Aha! We knew we had to use that sometime...) Since they are both integers, and they differ by less than $1$, then $a_n=a_m$.

Therefore, there is a single $a\in S$ such that $s_0-\frac{1}{n}\lt a\leq s_0$ for all $n\gt 1$.

Now you can finish the argument as you did, to conclude that $|a-s_0|=0$, so $a=s_0$, hence $s_0\in S$.

  • 0
    @JavaMan: this also follows directly from a reasonable definition of order and integers. First, if $a, b \in \mathbb{Z}$ and a, by definition of order on $\mathbb{Z}$, $b+1-a$ is a positive integer, hence $b+1-a \geq 1$ and $a\leq b$. Now |a_n - a_m| < 1 implies a_n < a_m +1 and a_m < a_n +1, thus $a_n \leq a_m \leq a_n \leq a_m$, $a_n=a_m$.2018-07-26
2

Arturo gave a good answer; I'm just going to point out that you don't actually need to build a sequence of $s_i$.

Instead, since you can choose any $\epsilon$ you want, use the fact that there exists an $\epsilon>0$ such that no integer $n$ satisfies $s_0 - \epsilon < n < s_0$. This is accomplished simply by making $\epsilon$ smaller than the step to the next smaller integer. Then no $a$ in $S$ can possibly satisfy that inequality. This is your contradiction.