Socks, Shoes, and The Axiom of Choice
A finite version of the Axiom of Choice
Thomas Jech is a set theorist and logician, who among many other things wrote a classic classic book on The Axiom of Choice (AC). I strongly recommend this book for its wonderfully lucid explanation of many aspects of AC—including Kurt Gödel’s and Paul Cohen’s results on the independence of AC from ZF set theory.
Today I want to discuss an old result about the famous Axiom of Choice. The result concerns a finite version of AC, and may be related to some of our problems in complexity theory. In any event it is a quite neat result, in my opinion.
At the recent Association of Symbolic Logic meeting, hosted by George Washington University in Washington, DC., a group of us went to dinner after our session on complexity theory. As usual we discussed many things during dinner: who is hiring, who is moving, P=NP, but somehow the conversation hit upon the AC. I told the group, I recalled vaguely a result on the AC for finite sets—no one seemed to be aware of such a result. I was a bit embarrassed, since I could not recall the exact statement of the theorem, but did recall it concerned choice on finite sets. We then moved onto other topics.
This is my attempt to make up for forgetting these pretty theorems about the AC for finite sets.
Finite Choice
“The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes.” — Bertrand Russell
Recall the AC is all about choice functions, since we are computer scientists we will only consider choices among finite objects. Consider a family 
for every set 
Theorem: The statement
implies
.
Theorem: The statement
.
What I find interesting is the non-monotone nature: the relationship from
Let me prove the first, 
The ability to choose from “socks” implies the ability to choose from “four dinning table chairs”.
I will follow Jech’s proof almost exactly. It is important to understand what we can do with sets:
- Given a finite set
- Given a set
we can form the set difference
.
- Given any set
of two elements, there is a universal function
that is a choice function:
where
or
.
The last property follows from the assumption
We now assume we have a family
Let 
Obviously 
Thus, 
- Suppose
- Suppose
- Suppose
as the choice for the set
Pretty neat argument—no?
The General Theorem
In order to define the general relationship we need what Jech calls condition 
such that 
Theorem: If
satisfy condition
and if
holds for every
, then
holds.
See his book for the details of the proof. The proof is an induction argument and uses some simple properties of binomials. Note, 
He also shows the condition
Theorem: If
Open Problems
Can we use this finite AC in any part of complexity theory? Does the “trick” of proving
Neat argument indeed! Though it is just barely related, this seems an opportunity to mention the delightful paper Division by three by Doyle and Conway. “In this paper we show that it is possible to divide by three.”
This is tangential to the main content of your post but I hope it is interesting. Martin Escardo has been doing some intriguing work on searching infinite sets in finite time. Programs that implement such search are available on his page.
A hands-on demonstration is given here. There is a LICS paper that provides more details.
Whoops! The demonstration link is here.
Great post. You are really raising two interesting questions. The first whether AC has direct application (I suppose there might be a meta result in which choice is essential) the second is whether the methods of independence proofs can be applied. I think the answer is almost certainly yes. In fact our early independence results used some related methods although I think Paul Young eventually showed they were not needed.
I heard about this type of problem once. I managed to figure out that C2 implies C4, but couldn’t prove any other nice relation. It’s nice to know about the last result you mention (and to have the reference, too!).
For what it’s worth, here’s my seemingly ungeneralizable argument for C2 implies C4:
Each four element set can be expressed as the disjoint union of two two element sets in three different ways. Using a choice function for two element sets you can select, for each of those three ways, one of the two element sets. Think of the four element set as the complete graph on four vertices; we are choosing one edge out of each of the three pairs of disjoint edges. Three such edges either form a triangle or a K1,3. Define the choice function on the four element set as follows: if the edges from a triangle, pick the fourth vertex; if they form a K1,3, pick the degree 3 vertex.
I’m biased of course, but I like my argument slightly better than Jech’s. :)
Very nice argument. I like it very much.
I can’t thank you enough for this blog. Every post is a gem, although sometimes I have to work pretty hard to understand exactly what’s being said (a reflection on me, not on Dr. Lipton’s excellent expository skills).
Would someone mind pointing me to a definition of universal function as used above in describing the function g(a,b)?
The reason I ask is this. If universal means something like Turing computable, then wouldn’t the arguments to g(a,b) need to be encoded as marks on a tape, or more familiarly as strings of bits? And if that’s the case, wouldn’t you be able to make a choice function for families of sets of cardinality n just by looking at the bit-representations of the elements and simply returning the least one in lexicographic order?
They helped me out over at http://mathoverflow.net/questions/21879/what-is-a-universal-function.