Proof of Well Ordering Property

[bfh227]

Homework Statement

I am working through an introductory real analysis textbook and am having a little trouble with certain aspects of the proof of the well ordering property (I am new to proving).

Theorem: Every nonempty subset of the natural numbers (N) has a smallest element.

Proof:

Let S$\subset$N and S≠∅. Then inf(S) must exist and be a real number because N has lower bound. If inf(S) $\in$ S, we are done.

If inf(S) $\notin$ S, then it is the greatest lower bound of S but is not min(S). There must be an element x $\in$ S that is smaller than inf(S)+1 since inf(S) is the greatest lower bound of S. Thus we have inf(S) < x < inf(S)+1.

-This is the first part I had trouble with. What is the justification for the fact that inf(S)+1 is greater than some x$\in$S? From which axiom(s)/definition(s) can we infer that inf(S) is a real number that is greater than the greatest integer not in S?

Since x > inf(S), it is not a lower bound of S. This means there must be another element y$\in$S such that inf(S) < y < x < inf(S)+1.

-Perhaps due to the earlier misunderstanding,the existence of such a y does not seem readily apparent to me. These two points are my main stumbling blocks and the rest of the proof is clear to me (contingent upon the existence of y). Any elucidation would be greatly appreciated.

 

[CAF123]

If inf(S) $\notin$ S, then it is the greatest lower bound of S but is not min(S). There must be an element x $\in$ S that is smaller than inf(S)+1 since inf(S) is the greatest lower bound of S. Thus we have inf(S) < x < inf(S)+1.


Since x > inf(S), it is not a lower bound of S. This means there must be another element y$\in$S such that inf(S) < y < x < inf(S)+1.

I believe these both follow from the Approximation Property for Infima. If you haven't seen this before, then it can be proved using the equivalent statement for suprema by considering $-S$. (and clearly $\sup(-S)$ exists by the Completness axiom)

 

[HallsofIvy]

Homework Statement

I am working through an introductory real analysis textbook and am having a little trouble with certain aspects of the proof of the well ordering property (I am new to proving).

Theorem: Every nonempty subset of the natural numbers (N) has a smallest element.

Proof:

Let S$\subset$N and S≠∅. Then inf(S) must exist and be a real number because N has lower bound. If inf(S) $\in$ S, we are done.

If inf(S) $\notin$ S, then it is the greatest lower bound of S but is not min(S). There must be an element x $\in$ S that is smaller than inf(S)+1 since inf(S) is the greatest lower bound of S. Thus we have inf(S) < x < inf(S)+1.

-This is the first part I had trouble with. What is the justification for the fact that inf(S)+1 is greater than some x$\in$S? From which axiom(s)/definition(s) can we infer that inf(S) is a real number that is greater than the greatest integer not in S?

For any real number x, there exist at least one integer, N, such that $x\le N\le x+ 1$.

Since x > inf(S), it is not a lower bound of S. This means there must be another element y$\in$S such that inf(S) < y < x < inf(S)+1.

"inf" means, of course "greatest lower bound". Since inf(S) is the "greatest lower bound" of S there cannot be a lower bound greater than inf(S). Since x> inf(S), x cannot be a lower bound for S. If there did not exist another integer, y, in S, less than x, x would be a lower bound for S.

-Perhaps due to the earlier misunderstanding,the existence of such a y does not seem readily apparent to me. These two points are my main stumbling blocks and the rest of the proof is clear to me (contingent upon the existence of y). Any elucidation would be greatly appreciated.

 

[bfh227]

Thanks a lot for the responses. The approximation property for infima does indeed seem to close the gap. Funnily, it wasn't in the textbook.

 

[CAF123]

Thanks a lot for the responses. The approximation property for infima does indeed seem to close the gap. Funnily, it wasn't in the textbook.

That's okay, it will be in the exercises