Daniel Donado – Metric spaces on omega_1 under determinacy

August 24, 2014

Daniel was my first masters student, completing his M.S. in June 2010. I co-advised him together with my friend and colleague Ramiro de la Vega, at the Universidad de los Andes, in Bogota. The following picture is from his Facebook profile.

Daniel Donado


Daniel’s thesis, Metric spaces on \omega_1 under the axiom of determinacy (in Spanish), is part of a vastly unexplored field: general topology in the absence of choice.

Work on this area has been mostly about highlighting pathologies, illustrating how vastly different results can be when we keep standard definitions but work in setting where the axiom of choice fails badly. Even in the setting of the real numbers with the standard topology, things may not work as expected: Every set of reals may be Borel (in fact F_{\sigma\sigma}), there may be Borel infinite Dedekind-finite sets, etc. In his PhD thesis at UC Berkeley, Apollo Hogan showed that, instead, we can carry out a systematic and detailed study of general topology if instead of dealing with arbitrary models with absurd failures of choice, we concentrate on settings where the absence of choice is compensated by a rich combinatorial structure. Specifically, Apollo (who was a student at Berkeley at the same time I was there) considered topology under the axiom of determinacy. Daniel’s thesis is a survey of some of the results discovered by Apollo.

Daniel begins by reviewing some of the basic consequences of \mathsf{AD}, the axiom of determinacy. To state \mathsf{AD}, we need to consider certain ideal games between two players, that I will just call I and II. In all these games the format is the same: players I and II alternate with I playing first. In each turn, the corresponding player picks a natural number, repetitions being allowed, and both players having knowledge of all the moves both have made previously. They play for infinitely many rounds. At the end, a sequence of natural numbers \langle n_0,n_1,n_2,\dots\rangle has been produced, with n_0,n_2,n_4,\dots being the numbers picked by player I, and n_1,n_3,\dots being the ones picked by II. We have one of these games for each set A\subseteq\mathbb N^{\mathbb N}, where \mathbb N^{\mathbb N} is the set of all infinite sequences of natural numbers. In the game associated to such an A, player I wins iff the sequence \langle n_0,n_1,n_2,\dots\rangle is in A. Otherwise, player II is the winner.

A strategy \sigma for player I is a function that tells player I what to play each time. Formally, this is just a function from the set of finite sequences of numbers to \mathbb N. A strategy for II is defined similarly. We say that a strategy for I is winning if and only if player I wins the game whenever they play following the strategy. That is, in any such game we have  n_0=\sigma(\langle\rangle), n_2=\sigma(\langle n_1\rangle), n_4=\sigma(\langle n_1,n_3\rangle), etc, and at the end we have that \langle n_0,n_1,n_2,\dots\rangle\in A. Winning strategies for player II are defined similarly. We say that A is determined iff one of the players has a winning strategy.

It is easy to give examples of determined sets A. Using the axiom of choice, we can give examples of undetermined sets, but deep theorems in descriptive set theory indicate that no undetermined set can be particularly simple. For instance, it is a celebrated theorem of Martin that all Borel sets are determined. Here, \mathbb N^{\mathbb N} is made into a topological space by taking the product topology of countably many copies of the discrete set \mathbb N.

The axiom of determinacy is the statement that all A\subseteq \mathbb N^{\mathbb N} are determined. In particular, this statement contradicts the axiom of choice. See here for slides of a talk I gave a few years ago containing a quick introduction to the subject.

The short remainder of this post (after the fold) is by necessity more technical.

Read the rest of this entry »

On strong measure zero sets

December 6, 2013

I meant to write a longer blog entry on strong measure zero sets (on the real line \mathbb R), but it is getting too long, so it may take me more than I expected. For now, let me record here an argument showing the following:

Theorem. If X is a strong measure zero set and F is a closed measure zero set, then X+F has measure zero.

The argument is similar to the one in

Janusz Pawlikowski. A characterization of strong measure zero sets, Israel J. Math., 93 (1), (1996), 171-183. MR1380640 (97f:28003),

where the result is shown for strong measure zero subsets of \{0,1\}^{\mathbb N}. This is actually the easy direction of Pawlikowski’s result, showing that this condition actually characterizes strong measure zero sets, that is, if X+F is measure zero for all closed measure zero sets F, then X is strong measure zero. (Since this was intended for my analysis course, and I do not see how to prove Pawlikowski’s argument without some appeal to results in measure theory, I am only including here the easy direction.) Pawlikowski’s argument actually generalizes an earlier key result of Galvin, Mycielski, and Solovay, who proved that a set X has strong measure zero iff it can be made disjoint from any given meager set by translation, that is, iff for any G meager there is a real r with X+r disjoint from G.

I proceed with the (short) proof after the fold.

Read the rest of this entry »

580 -Partition calculus (3)

April 6, 2009

1. Infinitary Jónsson algebras

Once again, assume choice throughout. Last lecture, we showed that {\kappa\not\rightarrow(\kappa)^{\aleph_0}} for any {\kappa.} The results below strengthen this fact in several ways.

Definition 1 Let {x} be a set. A function {f:[x]^{\aleph_0}\rightarrow x} is {\omega}-Jónsson for {x} iff for all {y\subseteq x,} if {|y|=|x|,} then {f''[y]^{\aleph_0}=x.}

Actually, for {x=\lambda} a cardinal, the examples to follow usually satisfy the stronger requirement that {f''[y]^\omega=\lambda.} In the notation from Definition 16 from last lecture, {\lambda\not\rightarrow[\lambda]^\omega_\lambda.}

The following result was originally proved in 1966 with a significantly more elaborate argument. The proof below, from 1976, is due to Galvin and Prikry.

Theorem 2 (Erdös-Hajnal) For any infinite {x,} there is an {\omega}-Jónsson function for {x.}

Read the rest of this entry »

580 -Cardinal arithmetic (11)

March 12, 2009

4. Strongly compact cardinals and {{sf SCH}}


Definition 1 A cardinal {kappa} is strongly compact iff it is uncountable, and any {kappa}-complete filter (over any set {I}) can be extended to a {kappa}-complete ultrafilter over {I.}


The notion of strong compactness has its origin in infinitary logic, and was formulated by Tarski as a natural generalization of the compactness of first order logic. Many distinct characterizations have been found.

Read the rest of this entry »