# 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 of sets each of cardinality exactly . The statement says every such family has a choice function: More precisely, there is a function from sets to elements so,

for every set . Jech gives several theorems, but the most interesting ones solve the following problem: when does imply ? Here are two key examples:

Theorem:The statement implies .

Theorem:The statement does not imply .

What I find interesting is the non-monotone nature: the relationship from to is not simple.

Let me prove the first, implies . In the spirit of Russell this implication says

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 we can tell the cardinality of the set.
- Given a set and 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 of four element sets, and are looking for a way to select among any four elements. We will construct the choice function using the above properties—the existence of is critical.

Let be in the family . There are six two-element subsets of . For every , let

Obviously cannot be the same for all : if all had this would be too few choices, if all had this would be too many choices. Let be the least positive value of over all . Then, define as

Thus, must have or elements.

- Suppose has one element. Then use this element as the choice for the set .
- Suppose has two elements. Then use to choose among the two elements and this is the choice for the set .
- Suppose has three elements. Then use the unique 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 : Say satisfy condition provided there is **no** decomposition of into a sum of primes,

such that for all .

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, does satisfy property .

He also shows the condition can be used to completely characterize when implies . The technically harder direction is to show that a does not imply a , since this requires set theory independence machinery. If you are interested please check his book for the details. It allows him to prove:

Theorem:If does not satisfy condition , then there is a model of set theory in which holds for every but fails.

** Open Problems **

Can we use this finite AC in any part of complexity theory? Does the “trick” of proving implies have any application in any part of theory?

Neat argument indeed! Though it is just barely related, this seems an opportunity to mention the delightful paper

Division by threeby 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 functionas used above in describing the function g(a,b)?The reason I ask is this. If

universalmeans 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.