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