By far, the stupidest thing that exists in set theory is the Axiom of Choice. Anybody who reads this blog is already familiar with it, but I might as well give my formal statement of it:
Given a collection of nonempty sets S, there exists a function f such that for all sets X in S, f(X) is an element of X.
Specifically, f is a function that chooses exactly one element from each set X in S, and f(X) tells you specifically which element the function has chosen.
This can sound innocent enough, all it says is that if you have a bunch of sets, it is possible to choose one element from each of those sets. The problem can come if the collection is infinitely big, its not clear that there would be a "rule" to tell you exactly how to select exactly one element from each of those sets.
For example, consider that we are only using the natural numbers, {0,1,2,3,...}. Then if we are told that S contains only nonempty subsets of the naturals, it is easy to find a choice function, simply always choose the smallest element of X (as it turns out, the Axiom of Choice is trivially true in a universe that only has the natural numbers). However, now let us suppose that we are using the real numbers, S might be the set of all nonempty subsets of real numbers, the function that would allow us to select exactly one element from each of these sets would be difficult to construct indeed. The Axiom of Choice is the postulate that there is such a function that would allow us to do just that, even though it gives no hint as to what such a function would look like.
How about some sort of middle ground, let us consider the integers, {....-3,-2,-1,0,1,2,3,.....}. If S contains nonempty subsets of the integers, you can still come up with a choice function without the Axiom of Choice. Specifically one can just use "If X contains any nonnegative integers, pick the smallest nonnegative one. If X contains only negative integers just use the largest negative integer." This rule will always pick out an element, so the Axiom of Choice is also not needed for the integers.
This is actually as if we had rearranged the order of the integers to be {0,1,2,3,....-1,-2,-3,....}, lining up all the positive integers in correct order, and then saying that -1 is greater than all the positive ones and then moving 'up' with the negative integers. Now under this new ordering of the integers, the rule is simply to "pick the smallest one". One could imagine that if there was some way to line up the reals such that every subset had a smallest element that the Axiom of Choice would then be unnecessary.
This leads us to a pretty general statement about the Axiom of Choice. Specifically, we ("we" being basically every set theorist on the planet) will consider orderings on sets, a concept of "greater than". First, an ordering will be called a "partial order" if whenever a>b and b>c then a>c follows. This is a reasonable demand to make on something you would want to call a concept of "greater than". Next, a partial ordering will be called a "total order" if for all a and b in the set, exactly one of these is true: a>b, b>a, a=b. Note that a partial ordering did not demand this, partial orderings can have elements where two elements are incomparable. Most orderings that one deals with in math are total orderings (like the usual one on the reals). Finally a total ordering is called a "well order" if for any subset there is a smallest element. The only well ordering that one deals with normally is that on the naturals, but one can see that you can give the integers a well ordering as well.
We can see that if you can find a well ordering for a set, you get a choice function right away and the Axiom of Choice is not needed. The "Well-ordering theorem" is the idea that every set can be well ordered (and needs that Axiom of Choice to prove). We have seen that if the Well-ordering theorem were to be true on its own, the Axiom of Choice would come for free, so you can see that the Axiom of Choice will be true if and only if the well-ordering theorem were true.
Alright, that is all fun and good (and probably most of you stopped reading ages ago), but what is really the problem with the Axiom of Choice? I mean, it seems intuitive enough, and probably helps prove some things (like the Well-ordering theorem), what could go wrong?
One of the basic problems shows up with the Banach-Tarski paradox. You can go look it up if you like, and I'll give a proper proof of it in the next few weeks, but the paradox is that it is possible to take a solid sphere, divide the sphere up into a number of disjoint pieces and, using only translation and rotation of the pieces, reassemble them into two copies of the original sphere, each the size of the original sphere. It seems like it might be a trick using an infinite number of pieces or something, but you can actually do it using just 5 pieces.
One might be concerned about conservation of volume in the Banach-Tarski paradox, how you could cut up a sphere of fixed volume and make something with twice as much volume using just translation and rotation. The trick is that the pieces do not have any well defined volume, and so conservation goes out the window. Actually, it is convenient to show how to use the Axiom of Choice to construct an object with no well-defined volume.
We will constrain ourselves to the one dimensional real line here, and we will have a concept of length. The length of a set S will be denoted L(S). We will denote adding a number to a set to mean that we construct a new set by adding that number to each element of the set, se {1,2,4}+5 is the set {6,7,9}. It is clear that we would want our length function to be translation invariant, so that L(S+x)=L(S) for any real number x. Next, if we take the union of two disjoint sets we want the lengths to add, so that L(S ∪ P)=L(S)+L(P) if S and P are disjoint (this also means that if P is a subset of Q then L(P) ≤ L(Q)). Finally, we want the length of intervals to be what we expect them to be, that being L([a,b])=b-a for b>a. Note that there can be nonempty sets with zero length, such as a set with only single point elements.
Alright, this is enough properties of length to prove that (with the Axiom of Choice) there exists a set that cannot be evaluated with this function. Let us consider an equivalence relation on the real numbers, two real numbers will be said to be equivalent if they differ by a rational number (this means that for each number, the set of numbers equivalent to it is a pattern that looks like the rationals). The set V will be constructed by choosing one element from each equivalence class that is also between 0 and 1. So, every real number differs from exactly one element of this set by a rational number, and does not differ from any other elements of this set by a rational number.
Next, list all the rational numbers between -1 and 1 and assign then each to a natural number, so that xn represents the list of all rationals between -1 and 1. It is clear that for every real number y between 0 and 1 there is an n such that y+xn is an element of V, so that y is an element of V-xn. V-xn will also spill out past (0,1) and hit some reals between -1 and 2, but will not get all of them. We also know that V+xn is disjoint from every V+xm for n and m different, as V had only one number from each equivalence class.
Now, we can consider E to be the union of the disjoint sets V+xn. It is clear that (0,1) is a subset of E and E is a subset of (-1,2). Thus 1 ≤ L(E) ≤ 3, but we also know that L(V+xn)=L(V). So If L(V) is zero, then E is the disjoint union of sets of length zero, and it has length zero, but if L(V) is nonzero, then E is the disjoint union of infinitely many sets with nonzero length and has infinite length.
Thus, we cannot have a function L that consistently assigns length to every set that exists in a world with the Axiom of Choice. This sort of thing will come up again later when I show the proof of the Banach-Tarski paradox and have to deal with the issue of volume conservation.
For now, its time for a logic puzzle (using the word "logic" loosely here), I first learned this one on the forums at xkcd:
You have a countably infinite number of logicians standing in a semi-infinite line. Each of them is wearing a hat which is either white or black. They can all see the (infinite number of) hats in front of them, none of the (finitely many) hats behind them and not their own hat and they all know their own position in the line. They must each simultaneously write down a guess about their own hat colour. They win the game if only finitely many of them are wrong, they lose if an infinite number of them guess wrong. Before the hats are assigned they may strategize. Using the Axiom of Choice, prove the existence of a strategy that guarantees their victory.
