# Need help proving least upper bound property for non-empty subsets of N

I am working on a formal proof of the upper bound property of non-empty subsets of N:

Every non-empty subset of N that is bounded from above has within it, the least upper bound of that set.

I can't seem to get anywhere. Here are my thoughts so far, such as they are:

Let x be a non-empty subset of N. Let b be an upper bound of x. Suppose to the contrary that for every element of x, there is a still larger element in x. I should be able to obtain a contradiction from this, but how? Should I consider another approach? Any help would be appreciated.

-
Is N the natural numbers? I may be wrong, but any set of natural numbers which is bounded above is necessarily finite. Could you then maybe use induction to prove that any nonempty finite set of natural numbers has a maximum element? –  yunone Jun 6 '11 at 4:56
Does $N = \mathbb{N}$? If so, then if $b$ is a least upper bound for a set $S,$ but $b \notin S,$ then $b-1$ is an upper bound for $S.$ –  Kopper Jun 6 '11 at 4:57

What should be considered the "right" solution depends very much on what facts about $\mathbb{N}\,$ that you are allowed to use.

It is not unlikely that you have been told, and can use, the following basic property of $\mathbb{N}$:

Every non-empty subset of $\mathbb{N}$ has a smallest element.

This is sometimes called the least number property, or, in more fancy language, the fact that under the natural ordering on $\mathbb{N}$, the set of natural numbers is well-ordered.

If you are allowed to use the least number property, let $X\,$ be your subset of $\mathbb{N}$. Let $S\,$ be the set of all upper bounds of $X$. You know that $S\,$ is non-empty, since you were told that $X\,$ is bounded above.

It follows that $S\,$ has a smallest element $m$. We show that $m\,$ is the least upper bound of $X$.

Suppose to the contrary that $m\,$ is not the least upper bound of $X$. Then there is an upper bound $b\,$ for $X\,$ which is $<m$. But then $b \in S$. Since $b<m$, this contradicts the fact that $m\,$ is the smallest element of $S$.

Or else possibly what you know about $\mathbb{N}$ is the Induction Principle. The solution given above can be rewritten in terms of that, but it is a little less clean. I can do it if you indicate that the tool I used is not part of your official toolchest.

-

The following steps lead to a solution:

(1) We will prove that every non-empty subset of $\mathbb{N}$ bounded below has a greatest lower bound. In fact, we will show that every non-empty subset of $\mathbb{N}$ bounded below has a minimum.

(2) Let $X_n=\{1,\cdots,n\}$ for all $n\geq 1$. If $A\subseteq \mathbb{N}$ is a non-empty subset, consider the intersections $X_n\cap A$ for all $n\geq 1$. Note that the intersections are all finite. Since $A\neq \emptyset$, there exists $k\in A$ for some $k\geq 1$ and in this case $k\in X_k\cap A$. Therefore, $X_k\cap A$ is a non-empty finite set and consequently has a minimum element $x$. Prove that $x$ is the minimum element of $A$.

I hope this helps!

-

Thanks all for your suggestions. Following is an outline of the proof:

Let a x be a non-empty subset of N. Let b be an upper bound of x. Suppose to the contrary that there is no least upper bound within x. Use proof by induction to show that we would then have to have, for all natural numbers, a larger number that is also in x. This cannot be true for b. By contradiction, there must be a least upper bound within x.

Formal proof written with the aid my DC Proof program: http://www.dcproof.com/LUBN.html

Dan

-
I have uploaded a new version of my proof. I'm afraid the original didn't make much sense. –  Dan Christensen Jun 25 '11 at 5:40

(1) Every set of nonnegative integers bounded above are finite.

(2) If a set of real numbers is finite, then they have a minimum element, and obviously it is a lower bound for that set and contained in the set.

Explanations:

(1) Let set S be a set bounded above, and let b an upper bound for set S, then obviously S has a maximum cardinality of $|S| = b$, since we have every integer in the set, allowed to occur only once.

(2) Real numbers is an ordered field, so "the completeness axiom" (least-upper-bound property) satisfies this.

-