Think you have a choice? Vitali’s revenge

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 \{1,2,3\}, \{4,5,6\}, \{7,8,9\}. From each of those sets, one can choose a representant, say, here, the smallest element, so that a new set is formed: \{1,4,7\}. 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 X of nonempty sets, let us call a function f \colon X \to \bigcup X a choice function if for every A \in X, f(A) \in A. The Axiom of Choice can now be defined explicitly.

The Axiom of Choice: For any collection X 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.

black and white game match chess
Usually, the Axiom of Determinacy is introduced together with a particular game.

Let A 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 a_1,a_2,\ldots.

\begin{array}{r|rrrrrrr} \text{Player I } & a_1 &  & a_3 &  & a_5 & & \ldots \\ \text{Player II} &  & a_2 &  & a_4 & & \ldots \end{array}

Player I wins whenever (a_1,a_2,\ldots) \in A, Player II wins otherwise.

The Axiom of Determinacy: For every subset A 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.
multicolored broken mirror decor
The Banach-Tarski paradox is a unit-ball decomposition into erratic pieces such that putting them back together gives you two unit balls instead of one.

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 A is a finite set. Player I has a winning strategy if and only if

\exists_{a_1} \forall_{a_2} \exists_{a_3} \forall_{a_4} \exists_{a_5} \ldots (a_1,a_2,a_3,a_4,a_5,\ldots) \in A.

Since A is finite, we can assume the sequence a_n 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

\forall_{a_1} \exists_{a_2} \forall_{a_3} \exists_{a_4} \forall_{a_5} \ldots (a_1,a_2,a_3,a_4,a_5,\ldots) \not\in A.

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.

assorted color macrons
It’s sort of like cutting a cake and getting more pieces of cake than the cake itself!

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 \mathbb{R} is (Lebesgue) measurable.

Proof. See here.


Theorem. Assume the Axiom of Determinacy. Let \mathbb{R}/\mathbb{Q} be a partition of \mathbb{R} such that x,y \in \mathbb{R} are in the same piece of the partition if and only if x-y \in \mathbb{Q}. Then |\mathbb{R}/\mathbb{Q}| > |\mathbb{R}|.

To prove this theorem, which is an AD curse, we will need the following lemma.

Lemma. Suppose A is measurable, then \frac{\mu(A \cap (x-r,x+r))}{2r} tends to 1 for almost every x \in A when r \to 0^+, where \mu is the Lebesgue’s measure. This limit is called a relative density at x.

Proof of the lemma. It is the Fundamental Theorem of Calculus stating that for almost all x, we have

f(x) = \frac{d}{dx} \int_{0}^{x} f(t)dt.

Which is equivalent to

f(x) = \lim_{r \to 0} \frac{1}{2r} \int_{x-r}^{x+r} f(t)dt.

The characteristic function \chi_A \colon \mathbb{R} \to \{0,1\} is defined to take the value 1 at the point x \in \mathbb{R} if and only if x \in A. If A is measurable, its characteristic function \chi_A is measurable. Thus, we can apply it to the Fundamental Theorem of Calculus and get

\chi_A(x) = \lim_{r \to 0} \frac{1}{2r} \cdot \mu(A \cap (x-r,x+r)).

Thus, for x \in A the limit above equals 1 and we are done.


Proof of the theorem. It is easy to see that |\mathbb{R}/\mathbb{Q}| \geq |\mathbb{R}|. Assume that |\mathbb{R}/\mathbb{Q}| = |\mathbb{R}|. Ordering of the reals, induces an ordering of |\mathbb{R}/\mathbb{Q}|. Let

A = \{ x \not\in \mathbb{Q} \mid x + \mathbb{Q} < -x +\mathbb{Q}\}.

By the Mycielski-Świerczkowski theorem, A must be measurable, so of relative density 1 almost everywhere. Choose a point x \in A and consider relative density c of A at x. Let r_m \to 0^+ and let R_n \to 2x^+. Then -x-r_m+R_n \to x-r_m and -x + r_m +R_n \to x + r_m. Thus, by diagonalization,

\frac{1}{2r} \cdot \mu((\mathbb{R} \setminus \mathbb{Q}) \setminus A \cap (x-r,x+r)) \to 1

almost surely as r \to 0^+, which contradicts the measurability of A, i.e., the fact that A has relative density 1 almost everywhere. Therefore, |\mathbb{R}/\mathbb{Q}| > |\mathbb{R}|.


Can you do the same for the Projective Determinacy? I asked about this on Mathematics StackExchange. You can find a link to the question in a tweet embedded below.

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.

3 thoughts on “Think you have a choice? Vitali’s revenge

  1. Isn’t the proposition that the Vitali equivalences classes are linearly ordered a consequence of AC? It shows up as Form306 in Howard and Rubin’s Consequences of the Axiom of Choice

  2. The proof “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.” seems to involve something similar to the Vitali set..l

  3. Also, the partition paradox does seemt to hold for not only the axiom of determinacy, but all axioms in which every set of real numbers is measurable, as the proof itself does not use the axiom of determinacy itself, bu the fact that every set of real number is measurable.

Leave a Reply

Your email address will not be published. Required fields are marked *