I learned a fascinating fact a few weeks ago at the Philosophy of Mathematics, graduate lecture seminar at the University of Oxford. That week’s discussion was led by Professor Hamkins and concerned a remarkable book Defending the Axioms: On the Philosophical Foundations of Set Theory written by Penelope Maddy, logic and philosophy of science Distinguished Professor at the University of California, Irvine.
I’ve always been fascinated with mutual inconsistency between the Axiom of Choice (AC) and the Axiom of Determinacy (AD). So when we drew near this topic, I spammed the seminar with questions. I have learned a lot from the discussion that followed.
First of all, let me quickly explain the setup.
The Axiom of Choice is a principle that asserts one can take an element from each set in a given family of nonempty sets so as to form a new set. To illustrate the idea, consider a family constituted by sets From each of those sets, one can choose a representant, say, here, the smallest element, so that a new set is formed: Incidentally, this particular example does not require the Axiom of Choice; still, the idea remains the same for all instances, including those that require AC to be valid. For any collection of nonempty sets, let us call a function a choice function if for every The Axiom of Choice can now be defined explicitly.
The Axiom of Choice: For any collection of nonempty sets, there exists a choice function.
The Axiom of Determinacy is a little bit more complicated. Or is it? It turns out that one can forego the classic game-theoretic definition and introduce AD in a much more intuitive way; this, I shall do. However, for completeness, let us recall the standard definition.
Let be a subset of the set of all infinite sequences of natural numbers. Consider the Gale-Stewart game for two players, Player I and Player II, who alternatively pick natural numbers
Player I wins whenever Player II wins otherwise.
The Axiom of Determinacy: For every subset of the set of all infinite sequences of natural numbers, the Gale-Stewart game is determined, that is, there is an “optimal strategy” that allows one player to win regardless of the other player’s strategy.
The Axiom of Determinacy is as true as the Axiom of Choice is.
My claim in this post is that the Axiom of Determinacy is as plausible as the Axiom of Choice, contrary to the commonly held view. One can give many reasons for which people tend to favor the Axiom of Choice. Perhaps historical reasons are the most evident here. However, I shall describe a different approach. For each of the axioms, I shall introduce one set-theoretic blessing and one set-theoretic curse. I used to think that AD seems to be a little bit artificial; while I knew that there is a very natural intuition behind AC on the one hand and an immeasurable paradox (pun intended!) on the other, only after the seminar did I realize that AD draws parallels to this phenomenon.
The following are well-known:
- It is provable from ZF that there is a choice function for finite collections of nonempty sets. In simple words, AC is a natural generalization, not known to be inconsistent with the basic laws of mathematics, of a certain theorem.
- The Banach-Tarski paradox is true in ZF+AC. One can use the Axiom of Choice to decompose a unit ball and put it back together in such a way to obtain two unit balls.
To draw a parallel between AC and AD, one needs to find similar consequences of the Axiom of Determinacy. That is, one should give one equally benevolent set-theoretical blessing and one equally cruel curse.
The blessing of AD
Consider a Gale-Stewart game where is a finite set. Player I has a winning strategy if and only if
Since is finite, we can assume the sequence is also finite. One can therefore apply De Morgan’s law to the above expression and say that Player I does not have a winning strategy if and only if
But this is equivalent to the statement that Player II has a winning strategy. Thus, the Axiom of Determinacy restricted to finite sets is true (this can be strengthened considerably). That should ring a bell – the Axiom of Determinacy is a natural generalization of a certain theorem. This analysis also amounts to the promised definition of the Axiom of Determinacy, which does not require any game-theoretical concepts. The Axiom of Determinacy is just De Morgan’s law for infinitary logic!
The curse of AD
Fascinated with the fact that AD is the infinitary De Morgan’s law, I asked Professor Hamkins whether one can also find an AD counterpart to the Banach-Tarski paradox. And in fact, yes! He referred me to this Mathematics Stack Exchange question for details.
What a fascinating paradox! It seems that the Axiom of Determinacy allows one to partition the real line in such a way that the number of pieces obtained is strictly greater than the amount of all real numbers. It’s sort of like cutting a cake and getting more pieces of cake than the cake itself! I shall now formalize this. First, let me recall a very important result obtained by Mycielski and Świerczkowski in 1964.
Theorem. (Mycielski, Świerczkowski) Assume the Axiom of Determinacy. Every subset of is (Lebesgue) measurable.
Proof. See here.
Theorem. Assume the Axiom of Determinacy. Let be a partition of such that are in the same piece of the partition if and only if Then
To prove this theorem, which is an AD curse, we will need the following lemma.
Lemma. Suppose is measurable, then tends to for almost every when where is the Lebesgue’s measure. This limit is called a relative density at
Proof of the lemma. It is the Fundamental Theorem of Calculus stating that for almost all we have
Which is equivalent to
The characteristic function is defined to take the value at the point if and only if If is measurable, its characteristic function is measurable. Thus, we can apply it to the Fundamental Theorem of Calculus and get
Thus, for the limit above equals and we are done.
Proof of the theorem. It is easy to see that Assume that Ordering of the reals, induces an ordering of Let
By the Mycielski-Świerczkowski theorem, must be measurable, so of relative density almost everywhere. Choose a point and consider relative density of at Let and let Then and Thus, by diagonalization,
almost surely as which contradicts the measurability of i.e., the fact that has relative density almost everywhere. Therefore,
As Asaf Karagila rightly pointed out in his comment, the Banach-Tarski paradox still holds in ZF+PD, though its power is rather qualified.
Update: Noah Schweber answered my question on MSE.