Determinacy

Complex Projective 4-Space 2021-07-11

I’d like to take this opportunity to highly recommend Oscar Cunningham’s blog. One of the posts, entitled A Better Representation of Real Numbers, describes an elegant order-preserving* bijection between the nonnegative reals [0, ∞) and ‘Baire space‘, $\mathbb{N}^{\mathbb{N}}$ , the space of infinite sequences of nonnegative integers.

*where the order on the Baire space is defined by lexicographical order.

Ultimately, it is built up recursively from just two ideas:

There is an order-preserving homeomorphism between [0, 1) and [0, ∞), namely x → x/(1 − x).
[0, ∞) can be partitioned into countably many copies of [0, 1), stacked end-to-end, one for each natural number.

Baire space and [0, ∞) both admit natural topologies (the product topology and the usual topology, respectively) and this order-preserving bijection is continuous in one direction: from Baire space to the nonnegative reals.

If we allow the first element of the integer sequence to be negative, then this gives an order-preserving bijection between the entirety of $\mathbb{R}$ and the space $\mathbb{Z} \times \mathbb{N}^{\mathbb{N}}$ . Rather similarly to the better known continued fraction representation, rationals are mapped to eventually-zero sequences and quadratic irrationals to eventually-periodic sequences.

Gale-Stewart games

Given a subset X of Baire space, there is an associated two-player game (the Gale-Stewart game G(X)) where players alternately exclaim nonnegative integers:

Player A plays a nonnegative integer z0;
Player B plays a nonnegative integer z1;
Player A plays a nonnegative integer z2;
Player B plays a nonnegative integer z3;
…

and so on, ad infinitum. Player A wins if the sequence (z0, z1, z2, z3, …) belongs to the set X; Player B wins otherwise.

A game G(X) and the corresponding set X are described as determined if one of the players has a winning strategy. To be precise, a strategy is a function from finite initial segments of play to the nonnegative integers, specifying which move one makes after seeing a particular sequence of moves.

It is somewhat unintuitive that non-determined games can exist: after all, it’s impossible for a game to end in a draw, so one may naively conclude that ‘under perfect play’ the game will be won by A or by B. However, ‘perfect play’ is not well defined for these infinite games, and it’s possible to have an undetermined game with the following properties:

for every strategy of player A, there exists a player B strategy that beats it;
for every strategy of player B, there exists a player A strategy that beats it;

and these are perfectly consistent statements. In ZFC, it’s possible to build an undetermined game using transfinite induction. The idea is to iterate over the tuples of the form (player, strategy, initial_segment_of_play) and to ‘foil’ that strategy by fixing the game outcome to be a loss for that player if that player follows the strategy and the other player plays some other strategy. This is possible because the other player can force the game to hit any of $|\mathbb{R}|$ different outcomes, and thus far in the transfinite induction we’ve fixed strictly fewer than that many points in the Baire space, so there’s always a game outcome that we haven’t yet fixed and can freely set to be a win for the other player. (At the end of this transfinite induction, we likely only have a partially-specified game, but that’s fine; we just set the remaining outcomes arbitrarily, e.g. to be wins for Player B.)

Surprisingly, it’s consistent with ZF (sans choice) that every Gale-Stewart game is determined. This is called the axiom of determinacy. It’s false in ZFC, for the reasons stated above, but weaker versions of this axiom can be proved in ZFC. For instance:

Every open subset of Baire space is determined

and, more generally:

Every Borel subset of Baire space is determined

Consequences of large cardinals

Assuming certain large cardinal axioms, it is possible to show that various generalisations of Borel sets are also determined.

One example of a large cardinal axiom is the existence of a measurable cardinal, an uncountable cardinal S such that there exists a two-valued measure $\mu : \mathbb{P}(S) \rightarrow \{0, 1\}$ satisfying:

μ(A) = 0 if and only if μ(S \ A) = 1;
if μ(A) = 0 and B is a subset of A, then μ(B) = 0;
singletons are small, i.e. μ({p}) = 0 for all points p in S.
the union of a collection of strictly fewer than |S| sets of measure 0 again has measure 0.

Without the ‘uncountable’ constraint, $\aleph_0$ would be measurable because this is equivalent to the definition of a non-principal ultrafilter.

If such a measurable cardinal exists, then it follows that every analytic set (continuous image of a Borel set) is determined, as is every coanalytic set (complement of an analytic set). A proof of this is here; I first encountered it in a 2015 graduate course on Descriptive Set Theory by Adrian Mathias.

Analytic and coanalytic sets together form the 1st level of the projective hierarchy; the 2nd level consists of projections of coanalytic sets and complements thereof; and so forth. (The Borel sets can be viewed as the 0th level of the projective hierarchy.)

If there are n Woodin cardinals with a measurable cardinal above them, then every set in the (n+1)th level of the projective hierarchy is determined. If there are infinitely many Woodin cardinals, then this holds for every n, and therefore every projective set is determined. This was proved in a paper by Martin and Steel.

Finally, if there’s a measurable cardinal above this infinite sequence of Woodin cardinals, then $L(\mathbb{R})$ (the constructible closure of the reals) satisfies the axiom of determinacy.

Consequences of determinacy

Determinacy has been formulated in terms of infinite games, but it is also of interest in real analysis because it implies various regularity properties about sets of reals. In particular, if a pointclass (family of sets) $\mathcal{A}$ is closed under continuous preimages, such as those we have just considered, then every set in $\mathcal{A}$ being determined also implies that they:

are Lebesgue measurable;
satisfy the property of Baire;
satisfy the perfect set property;

For example, if the axiom of determinacy holds in $L(\mathbb{R})$ , then all three of these regularity properties hold for every set in $\mathbb{P}(\mathbb{R}) \cap L(\mathbb{R})$ .

In Strong Axioms of Infinity and the Search for V (definitely worth reading), W. Hugh Woodin makes a strong case in favour of projective determinacy: projective sets are precisely the relations that can be formulated in second-order arithmetic, and assuming projective determinacy allows one to settle most natural questions in second-order arithmetic.