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