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.

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.

share|improve this question
2  
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. –  Dustan Levenstein Dec 14 '11 at 19:42
    
What if you set $\varepsilon =1/3$? I bet you can complete your proof with almost the same argument. ;-) –  Pacciu Dec 14 '11 at 19:47
    
Write $a_{\epsilon}$ instead of $a$, and things will not look so good. –  André Nicolas Dec 14 '11 at 19:55
add comment

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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}$. –  JavaMan Dec 14 '11 at 19:58
    
@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$. –  Arturo Magidin Dec 14 '11 at 20:15
    
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. –  JavaMan Dec 14 '11 at 21:36
add comment

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.

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.