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