There's a Woset in My Closet!

In our everyday lives we are used to ordering sets such as the positions of individuals or teams in a sporting competition (i.e. 1st, 2nd, 3rd, etc.). We also generally have an ordering of the set with the most well known examples being < (less than) and > (greater than). In the above example of sporting competitions we would define the ordering as greater than (>) with 1st being the greatest.

We can extend this idea of orderings of sets by defining what is known as a woset (well ordered set). A set that has an ordering defined on it is well ordered if for any subset we can find a unique minimal element. So in the sporting example we could take the persons or teams that got 3rd 5th and 8th and order them like so: 3rd>5th>8th, thus we have the unique minimal element is 8th. Repeating this for all possible subsets we find that all subsets have a unique minimal element meaning that the set is well ordered. An easier way to see that a set is well ordered is to find an ordering of the entire set which contains a unique minimal element. So an order in our example would be:

1st>2nd>3rd>4th>...>last

From an ordering like this it becomes obvious that the set is well ordered. We note here that not all sets can be well ordered as trivially, as an example consider the integers. We can define the below ordering on the integers.

...<-3<-2<-1<0<1<2<3<...

It seems as though we have a well ordering, however on careful inspection we notice that we can not find a least integer as the negative integers go on forever so there is no unique minimal negative integer and hence no well ordering. However if we consider a different ordering a ≺ b when |a|<|b| or when |a|=|b| where a is a negative integer and b is a positive integer (here |.| is the absolute value). This gives a well ordering of the integers by allowing us to not worry about negative values as the ordering is:

0 ≺-1 ≺ 1 ≺ -2 ≺ 2 ≺ ...

This becomes a lot more complicated when we try to order the real numbers, in fact very quickly you will realise there is no simple way to obtain a well ordering. Paul Cohen in 1963 even proved that the continuum hypothesis (\(2^{\aleph_0}={\aleph_1}\)) which is equivalent to finding a well ordering of the reals [3] can neither be proven true or false in set theory [1][2] (refer to (1) for an explanation of cardinals and ordinals).

So after seeing that result it may seem that not all sets can be well ordered, however in what will intially seem like a complete contradiction is the well ordering theorem which asserts that every set can be well ordered!

To see why this isn't a contradiction we reframe the problem of finding a well ordering as finding an algorithm to well order any arbitrarily large interval of the given set in a finite amount of time. From our first two examples we can use the orderings we defined as the algorithm, i.e. using the ordering, order elements of any given arbitrarily large interval of the set until it is well ordered. For an arbitrary interval on an arbitrary set given an arbitrary ordering rule this algorithm is equivalent to the halting problem as there is no way to check if an arbitrary ordering on an arbitrary set will lead to the algorithm terminating (finding a well ordering). In fact for the reals Paul Cohens result [1][2] ensures that no ordering can be defined such that our algorithm will halt. To see why this is the case we can look at any interval of the reals. For example if we look at the interval [0,1] we can always construct a number that is arbitrarily close to 1, i.e. 0.9999, 0.9999999, 0.99999...999. This is the case for any number in this interval, and so it becomes obvious that no matter what ordering rule that is defined we will not be able to order the set in a finite amount of time. As the algorithm will never halt with an input of the reals it doesn't imply that there is no well ordering but that such an ordering can not be found in a finite amount of time and hence the well ordering theorem is not contradicted.

The well ordering theorem has been the source of possibly the biggest controversy in mathematics due to it's completely unintuitive nature. Quite often in textbooks and the literature it is presented in such a way that anyone unfamiliar with the obscure mathematics surrounding cardinals and ordinals will find themselves quickly confused by this theorem when applying it to sets such as the reals. Generally in maths it is important to reframe ideas to provide new perspectives that may make the problem easier to understand and I hope to have achieved that here in order to quell the anxieties of anyone faced with the monumentous task of grasping these concepts.

References

[1] Paul Cohen, The Independence of the Continuum Hypothesis,1963

[2] Paul Cohen, The Independence of the Continuum Hypothesis 2,1963

[3] Stanford Encylopedia of Philosophy, The Continuum Hypothesis,2013

Further Resources

(1) Vsauce, How To Count Past Infinity,2016

Home