# Long up Short Down

Long up short down

by Hubert Shutrick

It is known that the real numbers between 0 and 1 are not countable. The axiom of choice implies that they can be well ordered and so, in this ordering, let \omega_{1} be the least element such that, for x \lt \omega_{1},  the set of elements less than x is countable or finite. The relationship between the axiom of choice and well order will be discussed in the next section.

Let us start counting. There is a least element so call it 1.  Its successor is 2 etc., and we continue to get the ordered set of positive integers \bf{N}.  The set of all elements that are greater than the elements of \bf{N} has a minimum that we denote by \omega.  It is the smallest limit point if we topologise the set by letting the open sets be the unions of open intervals ]a, b[  = \{x: a\lt{x}\lt{b}\},  where the ordering is, of course, the well ordering. In this topology, the integers are discrete but \omega is a limit point of \bf{N}.  Counting is continued with discrete points \omega +1, \omega +2, \ldots and then the next limit point is 2\omega.  Continuing like this, gives a sequence \omega, 2\omega, 3\omega, \ldots and a new, more complicated, limit point \omega^{2}.  Not deterred, we continue \omega^{2} +1,\omega^{2}+2, \ldots heading to \omega^{2} + \omega.  You see the pattern . we eventually get 2\omega^{2} and after integer multiples of \omega^{2},  there is \omega^{3}.  The sequence \omega, \omega^{2}, \omega^{3}, \ldots  has the limit point \omega^{\omega}.  The sequence \omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \ldots,  has a limit point so call it \epsilon_{1} since it has left the realms of our usual notation. It leads to a sequence \epsilon_{1}, \epsilon_{2}, \epsilon_{3}, \ldots.  Well, the ordinals seem to be getting rather big but they are all countable. We can just go on making up new notation until we are blue in the face, but we don't get to \omega_{1}

The ordinals do not stop at \omega_{1}.  The set of all subsets of the set of ordinals less than \omega_{1} has a bigger cardinality and it can be well ordered so we count its elements 1, 2, 3, \ldots \omega_{1}, \omega_{1}+1, \omega_{1}+2, \ldots until we come to the least element \omega_{2} such that the set of elements less than \omega_{2} has cardinality greater than \omega_{1}.  This can be continued to get limit points \omega_{3}, \omega_{4}, \ldots  with increasing cardinality. When all the integer suffices have been used up, we continue using ordinals. That means that \omega_{\omega_{\omega}} is very big so let's start there and choose a strictly descending sequence of ordinals. There are plenty to choose from, but, no matter how hard we try, we reach 1 after a finite number of choices because the sequence, a subset of the well ordered set, has a minimum.

Any set of ordinals must be bounded because unbounded collections of ordinals are too big to be called sets. Therefore, any set of ordinals has a least upper bound which is either its maximum or a limit ordinal of the set.

In analysis courses, compact is usually defined as bounded and closed. This definition does not work for general spaces. On the face of it, one wouldn't expect it to work for the ordinals, but it does. In general, a subset is said to be compact if, no matter what open covering of it is given, we can find finitely many of the open sets from the cover that cover it. Consider an open cover of a closed set V of the ordinals. Since open sets are unions of open intervals, we can, without loss, assume that the covering consists of open intervals. The least upper bound v_{1} of V must be its maximum since a closed set contains its limit points. Choose an open interval U_{1} from the cover containing v_{1}. Let v_{2} be the maximum of the points in V that are not in U_{1} and choose U_{2} from the cover containing it. Continuing in this way we get a finite descending sequence of ordinals and the corresponding open intervals cover V

Axiom of Choice

Zermelo noticed that a property of sets that seemed plausible was not easy to prove from the axioms of set theory at that time and he maintained that it could not be. He was later proved correct by Gödel and Cohen who showed that it was independent of and consistent with the usual axioms.

It is the axiom of choice and it is very plausible because it can be formulated in the following way. In the ordinary axioms, it is always possible to choose an element from a non-empty set. Given sets X_{1}, X_{2}, X_{3},  one can form the product set X_{1}\times X_{2}\times X_{3}  which is the set of all triples (x_{1}, x_{2}, x_{3}),  where x_{i} \in X_{i} for i \in I =\{1,2,3\}.  The number of elements in this product set is |X_{1}||X_{2}||X_{3}|.  Product generalises to families (X_{i})_{i \in I} of sets where the index set I can be infinite. The notation is

\Pi_{i \in I}X_{i}=\{(x_{i})_{i \in I}; x_{i} \in X_{i}\}

If all the sets in the family are non-empty, one would expect that there were plenty of elements in the product, but it was not possible to prove that the product of infinitely many non-empty sets was non-empty. The axiom of choice says that it is indeed non-empty. Choosing an element in the product is the same as choosing an element in each of the sets X_{i}.  The well ordering theorem states that any set can be well ordered, that is, be given a total ordering such that each subset has a minimum. It is equivalent to the axiom of choice. That it implies the axiom of choice is rather obvious because, the disjoint union of the family (X_{i})_{I} of sets can be well ordered and the minimum of each set is a choice.

Conversely, suppose that X is the set to be well ordered. Use the axiom of choice to choose an element c(U) that is not in the subset U for each subset of X that is not the whole set. Starting with the empty set, the singeton \{c(\emptyset)\} is vacuously ordered and off we go by requiring that, if the subset U has been ordered and has a maximum, then c(U) is adjoined as the successor of the maximum and, if it has no maximum, then c(U) is adjoined as its supremum.

This shows how the axiom of choice is involved without going into the formalities of a rigorous proof.

Details of theorems that are equivalent to the axiom of choice using the other axioms of set theory are given in http://en.wikipedia.org/wiki/Axiom_of_choice