For ordinals
$\alpha , \beta , \gamma , \delta $
in 1956 Erdős and Rado introduced the shorthand
$\alpha \longrightarrow (\beta )^{\gamma }_{\delta }$
to mean that for any partition P of
$[\alpha ]^{\gamma }$
—where
$[\alpha ]^{\gamma }$
denotes the subsets of
$\alpha $
having order-type
$\gamma $
—into
$\delta $
classes there is a
$B \in [\alpha ]^\beta $
such that
$[B]^{\gamma }$
lies wholly within one part of P. Complementarily,
$\alpha \mspace {7mu}\not \mspace {-7mu}\longrightarrow (\beta )^{\gamma }_{\delta }$
denotes this statement’s negation. These relations between
$\alpha $
,
$\beta $
,
$\gamma ,$
and
$\delta $
are often referred to as partition properties or partition relations and the notation as Hungarian notation or arrow notation.
In the following years Erdős and Rado were joined by Hajnal and others in proving several theorems establishing or refuting partition properties, always assuming the Axiom of Choice and quite often the Generalised Continuum Hypothesis as well. This body of work constitutes a substantial part of set theory developed in the period between the major results of Gödel and Cohen. Later, partition properties played a role in the elucidation of large cardinal properties, among them, weakly compact cardinals, ineffable cardinals, Erdős cardinals, Jónsson cardinals, and Rowbottom cardinals.
The notation was only introduced after results in what is now called Ramsey theory had been attained. Ramsey had shown that
$\omega \longrightarrow (\omega )^m_n$
for all natural numbers m and n and Klein and Szekeres had shown in 1935 that among any five points in general position in the Euclidean plane there are four which are the corners of a convex quadrilateral. But more importantly for our discussion, in 1952, using the Axiom of Choice (
$\mathsf {AC}$
) Erdős and Rado had shown the relation
$\alpha \mspace {7mu}\not \mspace {-7mu}\longrightarrow (\omega )^\omega _2$
for any ordinal
$\alpha $
. Hence partition relations with infinite exponents as above only have content in absence of full
$\mathsf {AC}$
.
The Axiom of Determinacy (
$\mathsf {AD}$
) was introduced by Mycielski and Steinhaus in 1962. It states that in every zero-sum game without gradations (such as draws, for example) lasting
$\omega $
rounds between two participants playing natural numbers, one player has a winning strategy. The Axiom of Real Determinacy (
$\mathsf {AD}_{\mathbb {R}}$
) is the analogue where the participants play real numbers. The authors noted that
$\mathsf {AD}$
implies two regularity properties for all sets of reals, Lebesgue measurability and the Baire property. Davis shortly thereafter derived the perfect set property from the Axiom and Mycielski, Scott, and Świerczkowski proved that
$\mathsf {AD}$
implies the Axiom of Choice for countable families of sets of reals. Some years later, more consequences of
$\mathsf {AD}$
were established. Solovay showed that
$\mathsf {AD}$
implies both
$\aleph _1$
and
$\aleph _2$
to be measurable, in 1966 and 1968, respectively. In 1970, Martin showed that the existence of a measurable cardinal requires
$\bf {\Pi }^1_1$
-sets to be determined and that for all
$n \in \omega \setminus 2$
, the cardinal
$\aleph _n$
has cofinality
$\omega _2$
. Together with Paris he went on to show that
$\omega _2 \mspace {7mu}\not \mspace {-7mu}\longrightarrow (\omega _2)^ {\omega _2}_2$
. Kleinberg showed that for regular
$\kappa $
and
$\lambda> \kappa $
, if
$\lambda \longrightarrow (\lambda )^{\kappa 2}_2$
, then
$\lambda $
is measurable. In 1973, Martin proved
$\omega _1 \longrightarrow (\omega _1)^{\omega _1}_2$
from
$\mathsf {AD}$
and in 1976, Prikry showed that
$\mathsf {AD}_{\mathbb {R}}$
implies all sets of reals having Ramsey’s property or, equivalently, that it implies
$\omega \longrightarrow (\omega )^\omega $
. In 1977, Kleinberg wrote “Infinite Combinatorics and the Axiom of Determinateness” summarizing the state of the art.
Since then, beside the work on
$\mathsf {AD}$
in
$L(\mathbb {R})$
and equiconsistency results, there have been numerous articles investigating the combinatorics of
$\mathsf {AD}$
. Coming immediately to my mind are some whose sets of authors are subsets of
$\{$
Apter, Henle, Jackson, Löwe, Mathias
$\}$
. However the closest approximations to introductions to the subject written since then seem to be Chapter 6 of Kanamori’s 1994 book “The Higher Infinite” and Jackson’s article “Structural Consequences of
$\mathsf {AD}$
” in the 2010 handbook of set theory. In light of this the paper under review does not appear too early.
In the following discussion
$\mathsf {ZF} + \mathsf {AD}$
is assumed throughout. For example any claim that an axiom
$\mathsf {X}$
implies a certain statement should be understood to say that this statement is derivable in the theory
$\mathsf {ZF} + \mathsf {AD} + \mathsf {X}$
. For the discussion the article will be quartered roughly into parts consisting of consecutive sections each which slightly deviates from the disection the author proposes; according to him, the whole article (minus its introduction) is divided in two parts, Sections 2–6 of the paper being concerned with the subject matter proper alluded to in the title whereas the penultimate and final section deal with
$\infty $
-Borel-codes in
$L(\mathbb {R})$
and results on the Vopénka-forcing by Woodin.
Roughly, a background in elementary set theory, descriptive set theory and some knowledge of constructibility is sufficient to digest the first part of the paper whereas the second one requires a broader metamathematical background; this is nothing less than what the author announces in Section 1, the introduction. In Section 2, the Hungarian notation is recalled and the notion of correct type is defined. A function whose range is included in its domain which is ordinal is of the correct type if it is of uniform cofinality
$\omega $
and everywhere discontinuous. Then the notation
$\kappa \longrightarrow _* (\kappa )^\lambda _\gamma $
is defined as a modification of the traditional arrow notation in which on the one hand the witnessing set is only homogeneous for subsets whose enumerations are of the correct type but on the other can be assumed to be club. The close connection between the two arrows is established when the author continues to show that for an ordinal
$\kappa $
and a
$\lambda < \kappa $
, the relation
$\kappa \longrightarrow _* (\kappa )^\lambda _2$
implies
$\kappa \longrightarrow (\kappa )^\lambda _2$
while
$\kappa \longrightarrow (\kappa )^{\omega \lambda }_2$
implies
$\kappa \longrightarrow _* (\kappa )^\lambda _2$
. After that some further basic combinatorial facts are established.
Another way of saying that
$\kappa \longrightarrow (\kappa )^\kappa _2$
(or, equivalently,
$\kappa \longrightarrow (\kappa )^\kappa _{\mathbb {R}}$
) holds for a certain cardinal
$\kappa $
is to say that
$\kappa $
has the strong partition property. That
$\omega _1$
has it is established in Section 4. In Section 3 the author defines the notion of good coding system for
${{}}^{\lambda } \kappa $
and proves the following theorem:
Theorem. Suppose
$\lambda , \kappa $
are ordinals such that
$\omega \lambda \leqslant \kappa $
. Suppose there is a good coding system for
${{}}^{\omega \lambda } \kappa $
. Then
$\kappa \longrightarrow _* (\kappa )^ \lambda _2$
holds.
Here a good coding system consists of a pointclass
$\Gamma $
closed under both projection and continuous substitution and a decoding function d assigning to every real a subset of
$\lambda \times \kappa $
and succeeding in decoding every function from
$\lambda $
to
$\kappa $
from some real. Moreover, letting
$\Delta := \{X \subset \mathbb {R} | \{X, \mathbb {R} \setminus X\} \subset \Gamma \}$
, the following shall be satisfied: If
$\beta < \lambda $
and A is the projection of a set in
$\Delta $
all whose elements decode to a subset which looks like a function at
$\beta $
(i.e., for all
$x \in A$
, there is a unique
$\gamma < \kappa $
with
$\langle \beta , \gamma \rangle \in d(x)$
), then these
$\gamma $
’s are bounded in
$\kappa $
, i.e., there is a
$\delta < \kappa $
such that for all
$x \in A$
and all
$\xi \in \kappa \setminus \delta $
we have
$\langle \beta , \xi \rangle \notin d(x)$
.
It then follows that
$\Delta $
is closed under wellordered unions of length smaller than
$\kappa $
. The paradigmatic case for this definition is the one in which
$\Gamma $
consists of all analytic sets while
$\Delta $
consists of all Borel sets.
Given a colouring
$P : [\kappa ]^ \lambda $
, the Theorem above is then proved using a game in which Player 1 wins in one of two cases: Either his play codes a subset of
$\lambda \times \kappa $
for which the smallest ordinal below
$\lambda $
at which it fails to behave functionally is larger than the respective ordinal for the decoded play of Player 2. Alternatively, if the plays of both players happen to code functions from
$\lambda $
to
$\kappa $
, Player 1 wins if
$P(h) = 0$
where h is the function mapping an ordinal
$\beta < \lambda $
to the maximum of the two suprema of the
$\beta $
th
$\omega $
-blocks of the functions coded by the plays of each Player.
In Section 4, it just remains to show that there is a good coding system for
${{}}^{\omega _1} \omega _1$
The author even provides two proofs of this, one going back to Martin, the other to Kechris. This setup has the benefit of enabling a reader to discern commonalities and differences between Martin’s proof of the strong partition property of
$\omega _1$
and the one by Kechris. There are two other proofs of the strong partition relation, one due to Jackson, the other a derivation of the former due to Jackson and May. The author mentions the former and the fact that in contrast to the proofs he presents it relies on the principle of dependent choices (
$\mathsf {DC}$
).
In the penultimate part, the author analyses ultrapowers
${{}}^{\kappa } \kappa /\mu $
for a normal
$\kappa $
-complete measure
$\mu $
on a strong partition cardinal
$\kappa $
. He establishes that these ultrapowers, if well-founded, are regular cardinals. The paradigmatic case is
$\kappa = \omega _1$
where the ultrapower is
$\omega _2$
. This result is then employed to establish that, while the strong partition property does not hold for
$\omega _2$
, one does have
$\omega _2 \longrightarrow (\omega _2)^\alpha $
for all
$\alpha < \omega _2$
. Also, it is shown that there are exactly two
$\omega _2$
-complete normal ultrafilters on
$\omega _2$
, the one of
$\omega $
-closed unbounded sets and the one of
$\omega _1$
-closed unbounded sets. Another fact pointed out is that the set of ordinals below
$\omega _2$
of cofinality
$\omega _1$
does not belong to the ultrapower obtained from the club filter on
$\omega _1$
. Via Kechris’s result that
$L(\mathbb {R}) \models \mathsf {DC}$
this implies the failure of Łos’s Theorem for the club filter on
$\omega _1$
.
In the last part,
$\infty $
-Borel codes are defined. Given a set of ordinals S and a set-theoretic formula
$\varphi $
, the pair
$\langle S, \varphi \rangle $
is an
$\infty $
-Borel code for a set if there is a natural number n such that the set can be defined to consist of exactly those n-tuples of reals x for which
$L[S, x] \models \varphi (S, x)$
. It is established that
$V = L(\mathbb {R})$
implies that every set has an
$\infty $
-Borel code and that
$\mathsf {DC}_{\mathbb {R}}$
implies that the class of sets having an
$\infty $
-Borel code is closed under real quantification.
Furthermore, the Vopénka forcing and a subforcing of it used in later proofs are defined. Some basic forcing facts are recalled. The author defines both the set of Turing degrees
$\mathcal {D}$
as well as the filter
$\mu _{\mathcal {D}}$
on it generated by Turing cones. He goes on to prove Martin’s result, that
$\mu _{\mathcal {D}}$
is a countably complete ultrafilter. Finally, Woodin’s Theorem of countable section uniformization is proved and under the additional assumption that
$V = L(\mathbb {R})$
the same is done for his perfect set dichotomy, i.e., that for any equivalence relation E, either
$\mathbb {R} / E$
is well-orderable or
$\mathbb {R}$
can be embedded in
$\mathbb {R} / E$
. On his way the author establishes many other results originally due to Woodin.
Generally, what is done in the paper, is done well. The level of detail, from my point of view, is in the Goldilocks zone, arguments left out are restricted to proofs of well-definedness or similar matters. One could argue that the level of formality, especially at the beginning, is surprisingly high. Nevertheless, the author’s choice of style does seem appropriate as many potential readers may be very experienced in arguing informally…in
$\mathsf {ZFC}$
. Just being done with throwing in “uniformly” here and there may have failed to make matters clearer.
One might wish for the article to also contain more information about the historical development of the subject and its open problems but, arguably, this would be asking for too much. With respect to the subject’s history, excellent accounts of it already exist, for example P. Larson’s article in the Handbook of the History of Logic and Chapter 6 of Kanamori’s “The Higher Infinite”. At the end of the day, a survey paper cannot replace a book and an analogue of Kleinberg’s book for the twenty-first century is still missing.
The author mentioned in the introduction that one purpose of the article was to serve as background for results of Jackson, Trang, and himself. I believe that beyond that it probably is the best text currently available to serve the purpose indicated in its title. For the cognoscenti this paper might only offer few new facts. To everybody else interested even slightly in its subject matter, I recommend its reading.