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.

$\endgroup$
3
  • 2
    $\begingroup$ The problem is your argument assumes that the same $a$ satisfies $s_0 - \epsilon < a < s_0$ for every $\epsilon$. This is not always true of the supremum of a set in general. $\endgroup$ Dec 14, 2011 at 19:42
  • $\begingroup$ What if you set $\varepsilon =1/3$? I bet you can complete your proof with almost the same argument. ;-) $\endgroup$
    – Pacciu
    Dec 14, 2011 at 19:47
  • $\begingroup$ Write $a_{\epsilon}$ instead of $a$, and things will not look so good. $\endgroup$ Dec 14, 2011 at 19:55

2 Answers 2

7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Does the seemingly obvious statement that "since $|a_n - a_m| <1 $ they must be the same integer" need to be rigorously proven? I suppose the answer may depend on the level of the course and the construction of the set $\mathbb{N}$. $\endgroup$
    – JavaMan
    Dec 14, 2011 at 19:58
  • $\begingroup$ @JavaMan: The difference between integers must be an integer; so $|a_n-a_m|$ must be a nonnegative integer. Since it must be smaller than $1$, and there is no integer strictly between $0$ and $1$, then $|a_n-a_m|=0$. $\endgroup$ Dec 14, 2011 at 20:15
  • $\begingroup$ I understand your reasoning, but I'm just playing devil's advocate here. Depending on the rigor desired by the professor, one still needs to show that there are no integers in the set $(0,1)$. This can be shown, for example, using the well-ordering principle. \textsc{Sketch:} Let $X$ denote the integers in $(0,1)$. Let $b$ be the least positive element in $X$ (such a $b$ exists by WOP). Then $0 < b < 1$ implies $0 < b^2 < b < 1$ which is a contradiction. Again, I apologize for discussing silly things, but different professors expect different amounts of rigor. Cheers. $\endgroup$
    – JavaMan
    Dec 14, 2011 at 21:36
  • $\begingroup$ @JavaMan: this also follows directly from a reasonable definition of order and integers. First, if $a, b \in \mathbb{Z}$ and $a<b+1$, 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$. $\endgroup$
    – Yibo Yang
    Jul 26, 2018 at 16:32
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .