Cardinality, The Well Ordering Principle

The Well Ordering Principle

First assume the well ordering principle holds, hence every set can be well ordered. We want to prove the axiom of choice.

Consider an indexed collection of sets A_x for every x in S. (Here S is the indexing set.) Assume each A_x is nonempty. Let U be the union over A_x and let P be the product set. Let w be any well ordering on U, which exists by the well ordering principle. Write a formula that pairs each x with the least element in A_x, according to w. Turn this formula into a set by comprehension, and realize that this set belongs to P. Thus P is nonempty, and the axiom of choice is true.

Conversely, assume the axiom of choice and let S be a set that cannot be well ordered. Let W be the set of subsets of S that can be well ordered. Verify that W is indeed a set, an application of the formula "can be well ordered" applied to the power set of S. Note that S ∉ W, since S cannot be well ordered.

Let f be any function from W into S. In other words, the well ordered subsets of S are mapped back into S. We wish to show there is some subset q ∈ W such that f(q) ∈ q.

If S is the integers, such a function f might start out looking like this. Each subset maps to a point not in the subset, for a while, but eventually this must fail.

(2,5,7) → 13
(5,6,9,23) → 4
(6) → 19
(even numbers) → 17
(prime numbers) → 77
…
q = (4,37,93,105,433,629,1383,…) → 93

Let f be any function as described above. Let S₀ = f(∅). Let S₁ = f(S₀), S₂ = f({S₀,S₁}), S₃ = f({S₀,S₁,S₂}), and so on. We are defining a new function e(ordinals) recursively. At each step the value of e() is determined by the value of f on a well ordered subset of S. At some point e is applied to an ordinal that will not fit into S, hence e is not a 1-1 function. Let b be the least ordinal such that e(b) = e(c) for some c < b. Let q be the set of points S₀ S₁ S₂ .. up to but not including S_b. Now f(q) = S_c, which is contained in q. We have produced a subset q such that f(q) belongs to q.

Let P be the direct product of the power set of S, without the empty set and without S itself. Imagine selecting an element from each subset. In other words, a choice function maps each subset to an element in that subset. Let c() be such a function. We know c() exists, thanks to the axiom of choice.

Build a new function f(), on the subsets of S, such that f(x) is c applied to the complement of x. Now f maps every subset to an element outside of that subset. Bring in an ordered pair that maps the empty set to something in S. Now the domain of f is all the proper subsets of S, and f never maps a subset to any element of that subset. Our previous collection W, well ordered subsets of S, does not include S, and is part of the domain of f. Yet we showed that such a function cannot exist. There will always be some f(q) ∈ q. Therefore S can be well ordered.

The axiom of choice is equivalent to the well ordering principle, which asserts a well ordering on every set. Either implies the other.

Given the well ordering principle, every set is represented by a cardinal. Any two sets can be compared, and the "sizes" of sets are linearly ordered. In fact they are well ordered, according to the cardinals.

As a corollary, a function from S onto T implies |S| ≥ |T|. Take the inverse of f, selecting the least element in each preimage, and build a 1-1 map from T into S.

If separate functions map S onto T, and T onto S, then two injections embed T in S, and S in T. Use the Schroder Bernstein theorem to produce a bijection between S and T, hence they have the same cardinality. But again, this is only valid if the axiom of choice holds.