Relationship between completeness and well ordering (meta).

Question

Here is the definition for completeness of the reals (there are many equivalent formulations but I am interested in this one);

Completeness: Every non-empty subset of the reals which is bounded above has a least upper bound.

This can be translated to the following: Suppose $ \displaystyle A$ is a non-empty set of real numbers bounded above. Then the set $ \displaystyle B = \{ b \in \mathbb{R} : (\text{ for all } a \in A)(b \ge a)\}$ has a minimum element.

In other words, given a non-empty (bounded above) subest of real numbers, we can produce a natural set which has a minimum element.

Well ordering: Every non-empty subset of the natural numbers has a least element.

In other words, given a non-empty subest of natural numbers, we can produce a natural set which has a minimum element.

Question: Is this a coincidence, or is there some deeper structure or theory which can encapsulate this kind of behaviour, for the formulations are very close (almost) identical, i.e. beginning with an arbitrary subset which is non-empty and producing a minimum element?

Answer 1

The notions of completeness and well-orderedness apply in any set with a linear order (in the sense that their definition can be checked). There is only so much that is definable by having a linear order, and indeed considering minimums and maximums of subsets is quite basic.

You argument basically shows that a well-ordered set is always complete (in this definition): if a subset $A$ (of a well-ordered set $X$) has an upper bound, its set of upper bounds is non-empty so has a minimum by the well-orderedness. So $X$ is complete. So there is a connection between these notions, as you noted.

Answer 2

I think it's worth noting that the cases are a bit different then they might seem at first glance. You say that in both cases you start with an arbitrary non-empty subset and then produce a minimum. The thing is that in each case you produce a minimum of a very different set.

In the case of the naturals (since they are well ordered) you can actually produce minimums of non-empty subsets.

On the other hand in the case of the Reals you are only producing minimums of extremely special sets; the sets of all upper bounds of a bounded set. If you look at the Reals as originating from the Dedekind cuts construction the specialness of this set is particularly well pronounced because it is the upper half of the cut that ends up being the real which is your minimum.

The other thing to note is that completeness for the reals is a property of the metric and not the topology (which comes from the order).