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

share|improve this question
1  
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
1  
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.$ –  Jay Kopper Jun 6 '11 at 4:57

4 Answers 4

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

share|improve this answer

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

Download my DC Proof software at http://www.dcproof.com

 

 

 

share|improve this answer
    
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

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.

share|improve this answer

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!

share|improve this answer

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.