1 Uncountable computability
Computability is often used to study the relationships between properties, to determine whether one property is more “complex” than another; the general strategy is to establish that the set of indices for structures with one property is reducible (Turing-reducible, m-reducible,
$1$
-reducible, or any of a number of other notions of reducibility) to the set of indices for structures with the other property, thereby showing that the latter property is at least as complex as the former. This technique has met considerable success in topics such as group theory and graph theory, settings in which countable structures are of key interest.
In descriptive set theory, however, the properties of interest are of sets of reals rather than sets of natural numbers. Because classical computability is predicated on
$\omega $
, it is difficult to apply its techniques to descriptive set-theoretic notions. For this reason, we turn to
$\alpha $
-recursion, a notion of computability built by replacing
$\omega $
with a larger ordinal
$\alpha $
.
For a full treatment of
$\alpha $
-recursion in the general case, see [Reference Chong1]; in this document, we will be largely concerned with
$\omega _1$
-recursion in particular. Further details on
$\omega _1$
-recursion may be found in [Reference Greenberg and Knight5]. To ensure that
$\omega _1$
-recursion will be sufficient to consider the objects of interest, we will operate under the premise that
$V = L$
.
The fundamental definitions of
$\omega _1$
-recursion will be provided at the beginning of the next section. Over the course of this paper, however, we will rely on an uncountable analogue of the Church-Turing Thesis: anything intuitively computable by a machine capable of manipulating countably infinite objects in memory and running for any countable number of stages is
$\omega _1$
-computable.
The work in this paper lies at the intersection of uncountable computability theory and descriptive set theory. Classical descriptive set theory studies the topological complexity of subsets of the set of real numbers
$\mathbb {R}$
in terms of their place in the Borel and projective hierarchies. Under the axiom of constructibility, every subset of
$\mathbb {R}$
, and more generally, any collection of Borel or projective subsets of
$\mathbb {R}$
can be coded as a subset of
${L}_{{\omega }_{1}}$
or of
${\omega }_{1}$
. It is then natural to investigate the connection between topological or descriptive complexity and algorithmic complexity in the context of the theory of computability on
${L}_{{\omega }_{1}}$
outlined above.
In this paper, the perfect set property, determinacy, the Baire property, and Lebesgue measurability of some point classes in the projective hierarchy will be investigated from the perspective of uncountable computability theory. Recall that a set A of real numbers is called analytic if it is the continuous image of some Borel subset of
$\mathbb {R}$
. It is a classical theorem that every uncountable analytic set contains a perfect set, which is a non-empty closed set with no isolated points. However under the axiom of constructibility, this fails to hold for complements of analytic sets, which are called co-analytic sets. In fact, a well-known result of Solovay (see Kanamori [Reference Kanamori6]) says that all uncountable co-analytic sets contain a perfect set if and only if for every real a,
${\omega }^{L[a]}_{1} < {\omega }_{1}$
. In particular, if every uncountable co-analytic set contains a perfect set, then
${\omega }_{1}$
is an inaccessible cardinal in L. We first investigate the algorithmic complexity of the (code for the) collection of all uncountable co-analytic sets of real numbers that contain perfect sets. It is shown that this set is
${\Sigma }^{0}_{1}$
-complete.
Another central theme in classical descriptive set theory is the determinacy of two player games of perfect information where the payoff set is Borel or projective. For any set A of real numbers, one can define a two player game
$\Game (A)$
as follows. Two players, call them In and Out, take turns choosing natural numbers, with the convention that In makes the initial move. At the end of play In and Out have jointly constructed a sequence
$\langle {a}_{n}: n \in \omega \rangle $
of natural numbers, where
${a}_{2n}$
has been played by In and
${a}_{2n + 1}$
was chosen by Out in response, for every
$n \in \omega $
. Now this sequence
$\langle {a}_{n}: n \in \omega \rangle $
codes a real number and In wins this particular play of the game
$\Game (A)$
if and only if the real number coded by
$\langle {a}_{n}: n \in \omega \rangle $
belongs to the set A. The set A is said to be determined if either In or Out has a winning strategy in
$\Game (A)$
. A major theorem is that every Borel subset of
$\mathbb {R}$
is determined (see [Reference Kechris8]). However under the axiom of constructibility, not all analytic sets are determined. The collection of all (codes for) analytic subsets of
$\mathbb {R}$
that are determined under the axiom of constructibility is shown to be
${\Sigma }^{0}_{2}$
-complete in Theorem 2.10.
These two results nicely tie-in with some well-known results from descriptive set theory. The statement “every uncountable co-analytic subset of
$\mathbb {R}$
contains a perfect set” and the statement “every analytic subset of
$\mathbb {R}$
is determined” are both consistent relative to large cardinals, and indeed they are both consequences of the existence of large cardinals (see [Reference Kanamori6]). However the consistency strength of the second of these statements is significantly greater than that of the first. The statement that every uncountable co-analytic subset of
$\mathbb {R}$
contains a perfect set is known to be equiconsistent with the existence of a strongly inaccessible cardinal, while the statement that every analytic subset of
$\mathbb {R}$
is determined requires at least the consistency of the much more powerful
${0}^{\sharp }$
. Extrapolating from this to the context of the axiom of constructibility, one might expect the collection of all analytic subsets of
$\mathbb {R}$
that are determined to be algorithmically strictly more complicated than the collection of all uncountable co-analytic subsets of
$\mathbb {R}$
that contain perfect sets. Our results bear out this intuition.
The Baire property and Lebesgue measurability of
${\boldsymbol {\Sigma }}^{1}_{2}$
sets is considered next. Here the concurrence with classical results in set theory is less straightforward. It is shown in Theorem 2.13 that the collection of all (codes for)
${\boldsymbol {\Sigma }}^{1}_{2}$
sets that have Baire property is Turing equivalent to the collection of all (codes for)
${\boldsymbol {\Sigma }}^{1}_{2}$
sets that are Lebesgue measurable. In terms of consistency strength, the statement that all
${\boldsymbol {\Sigma }}^{1}_{2}$
sets have the Baire property and the statement that all
${\boldsymbol {\Sigma }}^{1}_{2}$
sets are Lebesgue measurable are equally weak. They are both equiconsistent with
$\mathrm {ZFC}$
—Martin and Solovay showed that they are both consequences of
${\mathrm {MA}}_{{\aleph }_{1}}$
. However an asymmetry between the Baire property and Lebesgue measurability already appears at the level of
${\boldsymbol {\Sigma }}^{1}_{2}$
sets: Raisonnier and Stern showed that if all
${\boldsymbol {\Sigma }}^{1}_{2}$
sets are measurable, then all
${\boldsymbol {\Sigma }}^{1}_{2}$
sets have the Baire property, while Judah produced a model of
$\mathrm {ZFC}$
where all
${\boldsymbol {\Sigma }}^{1}_{2}$
sets have the Baire property and yet there is even a
${\boldsymbol {\Delta }}^{1}_{2}$
set that fails to be Lebesgue measurable (see [Reference Tomek and Judah13] for more details). It is well-known that a major asymmetry in consistency strength appears one level higher at
${\boldsymbol {\Sigma }}^{1}_{3}$
sets. The statement that all
${\boldsymbol {\Sigma }}^{1}_{3}$
sets have the Baire property is equiconsistent with
$\mathrm {ZFC}$
, while the statement that all
${\boldsymbol {\Sigma }}^{1}_{3}$
sets are measurable requires the consistency of a strongly inaccessible cardinal. Hence it would be of interest to investigate whether an asymmetry in Turing complexity also appears between the collection of all
${\boldsymbol {\Sigma }}^{1}_{3}$
sets that have the Baire property and the collection of all
${\boldsymbol {\Sigma }}^{1}_{3}$
sets that are measurable.
2 Index sets of descriptive set-theoretic notions
The following definitions are essentially due to Kripke [Reference Kripke10].
Definition 2.1. A set is hereditarily countable if it is countable and all of its elements are hereditarily countable. Note that, under the assumption
$V = L$
,
$L_{\omega _1}$
is precisely the set of hereditarily countable sets.
We develop the Lévy hierarchy of formulas as usual: a formula
$\varphi $
is
$\Sigma ^0_1$
if it has the form
$\exists x\psi $
, where
$\psi $
is a formula with only bounded quantification. A formula
$\varphi $
is
$\Pi ^0_n$
if it is the negation of a
$\Sigma ^0_n$
formula, and is
$\Sigma ^0_{n+1}$
if it has the form
$\exists x\psi $
, where
$\psi $
is a
$\Sigma ^0_n$
formula.
A subset
$X \subset L_{\omega _1}$
is said to be
$\omega _1$
-
$\Sigma ^0_n$
if there exists a
$\Sigma ^0_n$
formula
$\varphi $
and a parameter
$c \in L_{\omega _1}$
so that for each
$x \in L_{\omega _1}$
,
$x \in X$
iff
$L_{\omega _1}\models \varphi (x,c)$
. X is
$\omega _1$
-computable if both it and its complement are
$\omega _1$
-
$\Sigma ^0_1$
.
As usual, we say that a function is
$\omega _1$
-computable if its graph is
$\omega _1$
-
$\Sigma ^0_1$
.
For ease of notation, we will use “computable” in place of “
$\omega _1$
-computable” (and likewise
$\Sigma ^0_n$
for
$\omega _1$
-
$\Sigma ^0_n$
) except when ambiguity would arise. In general, if a notion is intended in the classical sense, it will be referred to as “
$\omega $
-computable” or “in the standard setting.” Boldface symbols are intended in the descriptive set-theoretic sense, detailed below.
We begin with a few well-known elementary facts regarding
$\omega _1$
-recursion.
Fact 2.2.
-
(i) The map
$\alpha \to L_{\alpha }$
taking each countable ordinal to the corresponding level of the constructible hierarchy is a computable function. -
(ii) The canonical well-ordering
$<_L$
, restricted to
$L_{\omega _1}$
, is a computable relation, which orders
$L_{\omega _1}$
with order-type
$\omega _1$
.
Further, the traditional definitions of many key topics of classical computability carry forward in a natural way to the uncountable setting. The example which is relevant to this paper is the definition of
$\emptyset '$
.
Definition 2.3. Let
$\emptyset '$
be the set of (indices for) true
$\Sigma ^0_1$
formulas with parameters in
$L_{\omega _1}$
.
With these definitions in place, we now turn our attention to descriptive set theory.
Definition 2.4. A code for a
$\boldsymbol {\Pi ^1_1}$
set is a tree
$T \subseteq (\omega \times \omega )^{<\omega }$
; the set coded by a tree T is
$X = \{g \in \omega ^{\omega } \mid (\forall f \in \omega ^{\omega })(\exists n)\langle f\upharpoonright n, g\upharpoonright n\rangle \notin T\}$
.
Let
$C_{\Pi }$
be the set of codes for uncountable, co-uncountable
$\boldsymbol {\Pi ^1_1}$
sets of reals.
Proposition 2.5.
$\boldsymbol {\Pi ^1_1}$
sets (equivalently,
$\boldsymbol {\Sigma ^1_1}$
sets) are
$\omega _1$
-computable.
Proof. Given a tree T coding a
$\boldsymbol {\Pi ^1_1}$
set X,
$g \in X$
iff
$g \in \omega ^{\omega }$
and
$(\forall f \in \omega ^{\omega })(\exists n \in \omega )\langle f\upharpoonright n, g\upharpoonright n\rangle \notin T$
. This is a
$\Pi ^0_1$
property by inspection—note that, while the quantifier
$\exists n \in \omega $
would be considered an unbounded quantifier within the context of classical computability,
$\omega $
is itself an
$\omega _1$
-finite object, and the quantifier is hence bounded from the standpoint of
$\omega _1$
-computability.
On the other hand, it is also the case that
$g \in X$
iff there exists an map F from the subtree
$\{\langle \sigma ,\tau \rangle \in T \mid \tau \prec g\}$
into the countable ordinals so that
$F(\langle \sigma _1, \tau _1\rangle ) < F(\langle \sigma _2,\tau _2\rangle )$
whenever
$\sigma _1 \succcurlyeq \sigma _2$
and
$\tau _1 \succcurlyeq \tau _2$
. Because this map, if it exists, is hereditarily countable and hence a member of
$L_{\omega _1}$
, the statement that such a map exists is
$\Sigma ^0_1$
.⊣
Proposition 2.6. The set of codes for
$\boldsymbol {\Pi ^1_1}$
sets having the perfect set property is
$\Sigma ^0_1$
.
Proof. X has the perfect set property iff
$$ \begin{align*} (\exists f:2^{<\omega} \to \omega^{<\omega})(\forall Y \in 2^\omega)f[Y] \in X. \end{align*} $$
Because X is
$\boldsymbol {\Pi ^1_1}$
, the statement
$f[Y] \in X$
is
$\Pi ^1_1[r]$
for some real r. So the statement
$$ \begin{align*} (\forall Y \in 2^\omega)f[Y] \in X \end{align*} $$
is also a
$\Pi ^1_1[r]$
statement. By Proposition 2.5, it is computable; so the full formula is
$\Sigma ^0_1$
.⊣
Definition 2.7. For
$X \subseteq \omega ^{\omega }$
, the Gale-Stewart game
$G_X$
is the following two-player game.
Players I and II alternate turns playing natural numbers, I going first. In this manner, they construct an infinite sequence x of natural numbers. Player I wins if
$x \in X$
; Player II wins if
$x \notin X$
.
A strategy is a function
$f:\omega ^{<\omega } \to \omega $
. A player may play according to f by playing on each turn
$f(\sigma )$
, where
$\sigma $
is the sequence of numbers chosen at previous turns. The strategy f is a winning strategy for a given player if playing according to that strategy always results in a win for that player, regardless of the other player’s moves.
A set X is determined if the game
$G_X$
has a winning strategy for either player.
For more information on Gale-Stewart games, see [Reference Kanamori6], [Reference Kechris8], or [Reference Soare12].
It is well-known that all Borel sets are determined (see Kechris [Reference Kechris8]). However, not all
$\boldsymbol {\Sigma ^1_1}$
and
$\boldsymbol {\Pi ^1_1}$
sets in L are determined.
Proposition 2.8. The set of codes for determined
$\boldsymbol {\Pi ^1_1}$
sets is
$\Sigma ^0_2$
.
Proof. X is determined if there is a winning strategy:
$$ \begin{align*} X \textrm{ is determined} \iff \exists f\forall g(\textrm{the play resulting from } f \textrm{ and } g \textrm{ is in } X). \end{align*} $$
Since membership in X is computable, this is
$\Sigma ^0_2$
.⊣
Theorem 2.9 (
$V = L$
).
The set of codes for
$\boldsymbol {\Pi ^1_1}$
sets having the perfect set property is
$\Sigma ^0_1$
-complete. In fact,
$\emptyset ' \equiv _m (P, C_{\Pi } \setminus P)$
, where P is the set of codes in
$C_{\Pi }$
coding a
$\boldsymbol {\Pi ^1_1}$
set that contains a perfect set.
Proof. For the other direction, we use a construction used extensively in [Reference Miller11] to construct a code for an uncountable, co-uncountable
$\boldsymbol {\Pi ^1_1}$
set which contains a perfect set iff a given
$\Sigma ^0_1$
formula is true. The basic idea of this method for constructing
$\boldsymbol {\Pi ^1_1}$
sets with special combinatorial properties under the axiom of constructibility goes back to the work of Erdős et al. [Reference Erdös, Kunen and Mauldin3], and it has found several other applications recently, for instance in [Reference Fischer and Törnquist4, Reference Kastermans7].
Say that
$L_{\alpha }$
is point-definable iff the Skolem-hull of
$(L_{\alpha },\in )$
under the typical Skolem functions for
$V = L$
is isomorphic to
$(L_{\alpha },\in )$
. It is known that there are unboundedly many point-definable
$L_{\alpha }$
for
$\alpha < \omega _1^L$
; see [Reference van Engelen, Miller and Steel2] for details. Let
$\langle L_{\beta _s}\rangle _{s < \omega _1}$
enumerate (in order) the point-definable
$L_{\beta }$
.
Fix a
$\Sigma ^0_1$
formula
$\exists x\varphi (x)$
for
$\varphi \in \Delta ^0_0$
. We construct a set
$S_{\varphi }$
together with an auxiliary sequence
$\mathbf{x} = \langle x_s\rangle $
as follows:
Stage
$0$
: Let
$\mathbf{x}$
be the empty sequence, and
$S_{\varphi }$
the empty set.
Stage
$s > 0$
: Suppose
$L_{\beta _s} \models \neg \exists x\varphi (x)$
. Let
$P_s$
be the
$<_L$
-least code in
$L_{\beta _s}$
for a perfect set P so that
$L_{\beta _s} \models \neg (\exists y \in P, t < s)y = x_t$
, and put
$x_s$
the
$<_L$
-least such y. Let
$z_s$
be the
$<_L$
-least
$z \in L_{\beta _s + \omega }$
so that
$z \neq x_t$
for
$t \leq s$
and there is a presentation of
$L_{\beta _s}$
recursive in z, and include
$z_s$
in
$S_{\varphi }$
.
If
$L_{\beta _s} \models \exists x\varphi (x)$
, then put z in
$S_{\varphi }$
for every z so that
$z \neq x_t$
for
$t \leq s$
and z computes some presentation of
$L_{\beta _s}$
, and halt construction.
Because
$L_{\beta _s}$
is point-definable and L has Skolem functions, there is a presentation of
$L_{\beta _s}$
computable in the first-order theory of
$L_{\beta _s}$
. Because the first-order theory appears shortly afterward in the constructible hierarchy, this presentation appears by
$L_{\beta _s + n}$
for a finite n (the precise value of n is unimportant). As a result,
$L_{\beta _s + \omega }$
is a sufficiently high level of the constructible hierarchy to run the construction up through stage s; there is certainly a
$z \in L_{\beta _s + \omega }$
which computes a presentation of
$L_{\beta _s}$
, and determining whether a given z does requires at most three additional levels of definability (one to quantify over sets computable from z, one to determine whether the necessary Skolem functions are realized in a given candidate presentation, and one to determine whether all elements of the candidate are part of the Skolem hull).
Since
$L_{\beta _s+\omega }$
is sufficient to perform this construction through stage s,
$z \in S_{\varphi }$
iff
$z = z_s$
for some s iff
$L_{\beta _s + \omega } \models z = z_s$
for some s. But this holds only if z computes some presentation of
$L_{\beta _s}$
, in which case there is a presentation of
$L_{\beta _s + \omega }$
hyperarithmetic in z. So
$z \in S_{\varphi }$
iff
$(\exists x \in \Delta ^1_1(z))\,x $
is a presentation of some
$L_{\alpha } \wedge L_{\alpha }\models z \in S_{\varphi }$
. Determining whether a given x is a presentation of some
$L_{\alpha }$
is a
$\Pi ^1_1$
task, because it requires checking for well-foundedness. By a result of Kleene [Reference Kleene9], the existential quantifier over
$\Delta ^1_1(z)$
does not add further complexity; therefore,
$S_{\varphi }$
is
$\boldsymbol {\Pi ^1_1}$
.
It is evident that
$S_{\varphi }$
contains a perfect set iff
$L_{\omega _1} \models \exists x\varphi (x)$
; if no witness is ever found, then at every step we place one member of the next perfect set into our sequence
$\mathbf{x}$
, to be withheld from
$S_{\varphi }$
. If a witness is eventually found, then the entirety of
$\{z \mid z \geq _T L_{\beta _s}\}$
(minus a countable set) is immediately included in
$S_{\varphi }$
; this is Borel and not countable, and therefore contains a perfect set.
It is also evident that
$S_{\varphi }$
is never countable or co-countable. If no witness to
$\varphi $
is ever found, then one real is added to
$S_{\varphi }$
at every stage and one withheld. If a witness is eventually found, then
$S_{\varphi }$
is only countably different from
$\{z \mid z \geq _T L_{\beta _s}\}$
for the appropriate s, which is clearly an uncountable and co-uncountable set.
Thus the function f taking
$\varphi $
to this canonical code for
$S_{\varphi }$
is the desired m-reduction.⊣
Theorem 2.10 (
$V = L$
).
The set of codes for determined
$\boldsymbol {\Pi ^1_1}$
sets is
$\Sigma ^0_2$
-complete. In fact,
$S \equiv _m (D, C_{\Pi } \setminus D)$
, where S is the set of true
$\Sigma ^0_2(L_{\omega _1})$
formulas and D is the set of codes in
$C_{\Pi }$
for determined
$\boldsymbol {\Pi ^1_1}$
sets.
Proof. To show the other direction, we perform a construction similar to before. Fix a
$\Sigma ^0_2(L_{\omega _1})$
formula
$\varphi = (\exists x)(\forall y)\psi (x,y)$
. Again we construct a set of reals
$S_{\varphi }$
and an auxiliary sequence of reals
$\langle x_s\rangle $
; we will ensure that
$S_{\varphi }$
is
$\boldsymbol {\Pi ^1_1}$
by way of an index uniform in
$\varphi $
. Again let
$\langle L_{\beta _s}\rangle _{s < \omega _1}$
enumerate the countable ordinals
$\beta $
so that
$L_{\beta }$
is point-definable and
$\beta = \alpha + \omega $
for some
$\alpha $
.
Stage
$0$
: Take
$S_{\varphi } = \emptyset $
,
$\langle x_s\rangle $
the empty sequence.
Stage
$s> 0$
: If
$L_{\beta _s} \models (\exists y)\neg \psi (x,y)$
for the first value of x for which this was not true at a previous stage, then let
$(f,i)$
be the
$<_L$
-least pair of a strategy in
$L_{\beta _s}$
and a player (I or II) that has not yet been considered, if any exists. Fix the
$<_L$
-least two reals
$z_1,z_2$
so that the following holds:
-
(i)
$z_1 \neq z_2$
; -
(ii) Each is the result of the player i playing according to f;
-
(iii) Neither are in
$S_{\varphi }$
or the sequence
$\langle x_t\rangle _{t < s}$
; -
(iv)
$z_2 \in L_{\beta _s}$
; and -
(v)
$z_1$
computes a presentation of
$L_{\beta _s}$
.
Observe that such a pair
$z_1,z_2$
does exist; this is because the opposing player may play any sequence of naturals, regardless of the restrictions on the player i. Since at any countable stage both
$S_{\varphi }$
and
$\langle x_t\rangle _{t < s}$
consist only of reals present in
$L_{\beta _t}$
for
$t < s$
, to satisfy condition (iii) it is sufficient that the sequence of plays by the opposing player be a real not in any such
$L_{\beta _t}$
. As noted in the previous proof, since
$L_{\beta _t}$
is point-definable there is a presentation of
$L_{\beta _t}$
in
$L_{\beta _t+\omega }$
(in fact, there is a presentation of
$L_{\beta _t + 1}$
, which cannot be in
$L_{\beta _t}$
). By the choice of the sequence,
$\beta _t \geq \sup _{u < t}\beta _u + \omega $
for all t, and therefore
$L_{\beta _s}$
includes reals not in any previous
$L_{\beta _t}$
. By taking one of these reals as the opposing plays, we have a
$z_2 \in L_{\beta _s}$
satisfying (ii) through (iv). By taking a sufficiently complicated presentation of
$L_{\beta _s}$
(e.g., one found only in
$L_{\beta _s + 3}$
) and using this for the opposing plays, we obtain a
$z_1$
satisfying (i) through (v).
Put
$z_1 \in S_{\varphi }$
and set
$x_s = z_2$
. Note that, as long as the members of
$\langle x_s\rangle $
are withheld from
$S_{\varphi }$
, f cannot be a winning strategy for either player.
If, on the other hand,
$L_{\beta _s} \models (\forall y)\psi (x,y)$
for the first value of x for which this was true until this stage, then let
$z_s$
be the
$<_L$
-least real so that
$z_s \neq x_t$
for
$t < s$
and
$z_s$
is a presentation of
$L_{\beta _s}$
. Put
$z_s \in S_{\varphi }$
. This completes the construction.
Note that
$S_{\varphi }$
is
$\boldsymbol {\Pi ^1_1}$
for the same reason as before:
$L_{\beta _s + \omega }$
is enough to run the construction up through stage s.
If we fall in the first case only boundedly often, then
$S_{\varphi }$
is (up to a countable set) a set of reals coding well-founded relations; there is then clearly a strategy that avoids
$S_{\varphi }$
, and
$S_{\varphi }$
is therefore determined. If we visit the first case unboundedly often, on the other hand, then each possible strategy is eventually encountered and diagonalized against, so
$S_{\varphi }$
is not determined. And clearly we visit the first case unboundedly often if and only if
$L_{\omega _1} \models \neg \varphi $
. This completes the proof.⊣
Definition 2.11. A
$\boldsymbol {\Sigma ^1_2}$
code or a code for a
$\boldsymbol {\Sigma ^1_2}$
set is a pair
$(\varphi (x,b),a)$
where
$\varphi (x,b)$
is a formula of the form
$(\exists y \in \omega ^{\omega })(\forall z \in \omega ^{\omega })\psi (x,y,z,b)$
and
$a \in \omega ^{\omega }$
. The set X coded by a
$\boldsymbol {\Sigma ^1_2}$
code
$(\varphi (x,b),a)$
is
$\{x \in \omega ^{\omega } \mid \varphi (x,a)\}$
.
Definition 2.12. Let
$\mathrm {Borel}_2$
denote the set of codes for
$\boldsymbol {\Sigma ^1_2}$
sets which are Borel. Let
$\mathrm {Baire}_2$
denote the set of
$\boldsymbol {\Sigma ^1_2}$
codes for
$\boldsymbol {\Sigma ^1_2}$
sets with the Baire property, and let
$\mathrm {Lebesgue}_2$
denote the set of
$\boldsymbol {\Sigma ^1_2}$
codes for Lebesgue-measurable
$\boldsymbol {\Sigma ^1_2}$
sets.
The remainder of this section will consist of the proof of the following theorem.
Theorem 2.13. Under the assumption
$V = L$
, the sets
$\mathrm {Borel}_2$
,
$\mathrm {Baire}_2$
, and
$\mathrm {Lebesgue}_2$
are pairwise m-equivalent. In particular, they have the same Turing degree.
The following lemma is straightforward, but essential to the proofs that follow.
Lemma 2.14 (
$V = L$
).
A set of reals is
$\boldsymbol {\Sigma ^1_2}$
in the classical sense if and only if it is
$\Sigma ^0_1$
(c.e.) in the sense of
$\omega _1$
.
Proof. (
$\Rightarrow $
): Let X be a
$\boldsymbol {\Sigma ^1_2}$
set of reals. Then there exists an arithmetic formula
$\varphi $
and a parameter
$a \subseteq \omega $
such that
$$ \begin{align*} x \in X \iff (\exists y \subseteq \omega)(\forall z \subseteq \omega)\varphi(a, x, y, z) \end{align*} $$
for all reals x. The formula
$(\forall z \subseteq \omega )\varphi (a,x,y,z)$
is
$\Pi ^1_1$
, hence
$\omega _1$
-computable; the full statement is therefore
$\omega _1$
-computably-enumerable.
(
$\Leftarrow $
): Let X be a c.e. set of reals. By definition, X is
$\Sigma ^0_1$
-definable over
$L_{\omega _1}$
, so there exists a formula
$\varphi $
and a parameter
$a \in L_{\omega _1}$
such that
$$ \begin{align*} x \in X \iff (\exists y \in L_{\omega_1})\varphi(a,x,y). \end{align*} $$
By replacing hereditarily countable sets with subsets of
$\omega $
encoding them, we may replace this with the following:
$$ \begin{align*} x \in X \iff (\exists y \subseteq \omega)(WF(y) \wedge \varphi^*(a,x,y)), \end{align*} $$
where
$WF(y)$
is the formula “the structure coded by y is well-founded” and
$\varphi ^*$
is
$\varphi $
modified to decode y.
$WF(y)$
is a
$\Pi ^1_1$
formula; the rest is Borel, so this is a
$\boldsymbol {\Sigma ^1_2}$
definition of X.⊣
As a consequence of the lemma, we will often transition freely between c.e. sets of reals and
$\boldsymbol {\Sigma ^1_2}$
sets of reals.
Theorem 2.13 is an immediate consequence of Theorems 2.15, 2.21, and 2.26. The proofs of these three results have very similar structure, so before we begin we outline some of the commonalities.
The general aim of each proof is to, given a c.e. set of reals X, produce a c.e. set of reals A. Alongside this, an additional c.e. set, usually called B, is constructed as well; B may be considered as a set of elements that are prohibited from entering A except by actions of sufficiently high priority.
In each proof, we also maintain a collection
$\mathcal {S}$
of promises of the form
$(s, i, Y)$
, where s is a countable ordinal, i is either
$0$
or
$1$
, and Y is (some representation of) a set of reals. Intuitively, a promise of the form
$(s, 0, Y)$
promises to include the next available element of Y in A, while a promise of the form
$(s, 1, Y)$
promises to include it in B. The first component, s, is a priority; lower values have higher priority. Promises are ordered in the natural way: lexicographically, using
$<_L$
to order each component. At every stage, the first promise that is satisfiable will be satisfied by adding a real to either A or B, and then will be removed from
$\mathcal {S}$
; the precise notion of satisfiability will vary slightly between the proofs.
Theorem 2.15. Under the assumption that
$V = L$
,
$\mathrm {Borel}_2 \geq _m \mathrm {Baire}_2$
.
Proof. Given a code for a
$\boldsymbol {\Sigma ^1_2}$
set X, we construct a code for another
$\boldsymbol {\Sigma ^1_2}$
set A. Recall that a set has the Baire property iff there is an open set with which its symmetric difference is meager; we therefore require a means of referring to open and meager sets within the construction.
Definition 2.16. An open code is a countable subset of
$\omega ^{<\omega }$
. If U is an open code, the set coded by U is the set
$\{x \in \omega ^{\omega } \mid (\exists \sigma \in U) \sigma \prec x\}$
.
A nowhere-dense code is a set
$X \subseteq \omega ^{<\omega }$
so that
$(\forall \sigma \in 2^{<\omega })(\exists \tau \in X)(\tau \preccurlyeq \sigma \vee \sigma \preccurlyeq \tau )$
. If N is a nowhere-dense code, the set coded by N is the set
$\{x \in \omega ^{\omega } \mid \neg (\exists \sigma \in N)\sigma \prec x\}$
.
A meager code is an
$\omega $
-sequence of nowhere-dense codes. If M is a meager code, the set coded by M is the union of the sets coded by its members.
Note that every open set has an open code, and while not every nowhere-dense set or meager set has a nowhere-dense or meager code, it is the case that every nowhere-dense set is covered by a nowhere-dense set that does, and likewise for meager sets.
It is also worth noting that every closed nowhere-dense set has a nowhere-dense code, so the closure of a given nowhere-dense set is an example of a nowhere-dense set with a nowhere-dense code that covers it.
A Borel code is a well-founded tree
$T \subseteq \omega ^{<\omega }$
equipped with a function f so that
$f(\sigma ) \in \omega ^{<\omega }$
whenever
$\sigma $
is a leaf node of T and
$f(\sigma ) \in \{\cup , \cap \}$
otherwise. When
$B = (T,f)$
is a Borel code, the set coded by B is defined inductively: let
$S_{\sigma } = \{x \in \omega ^{\omega } \mid f(\sigma ) \prec x\}$
for
$\sigma $
a leaf node of T; let
$S_{\sigma } = \bigcup _{i \in \omega }S_{\sigma i}$
if
$f(\sigma ) = \cup $
; and let
$S_{\sigma } = \bigcap _{i \in \omega }S_{\sigma i}$
otherwise. The set coded by B is
$S_{\langle \rangle }$
.
The set of open codes, the set of nowhere-dense codes, the set of meager codes, and the set of Borel codes are all
$\omega _1$
-computable (henceforth “computable”); note that since
$2^{<\omega }$
is hereditarily countable, quantification over it is bounded quantification. Likewise, the set coded by a code of any sort is computable uniformly in the code.
We now begin the construction. Given a code for a
$\boldsymbol {\Sigma ^1_2}$
set X, we will construct a code for a
$\boldsymbol {\Sigma ^1_2}$
set A so that A will be Borel iff X has the Baire property. We factor through the equivalence of
$\boldsymbol {\Sigma ^1_2}$
sets of reals and c.e. sets of reals from Lemma 2.14, and for clarity we do not distinguish between an open or meager code and the set it codes. Finally, we arrange that all c.e. sets enumerate at most one element per stage.
During the construction, we will maintain two structures. First, we will be constructing the c.e. set A, and alongside it an auxiliary c.e. set B. Second, we maintain a collection
$\mathcal {S}$
of promises of the form
$(s, i, Y)$
, where
$s \in \omega _1$
,
$i = 0$
or
$1$
, and Y is a (code for a) set. Intuitively,
$(s,0,Y)$
promises that the
$<_L$
-least element of Y will enter A, and
$(s,1,Y)$
that it will enter B, with priority s. We will ensure that elements that are enumerated into B on behalf of a promise
$(s,1,Y)$
have not previously been enumerated into A and will not be enumerated into A except on behalf of a promise of the form
$(t,0,Z)$
with
$t < s$
.
Fix an effective enumeration
$(U_e,M_e)$
of pairs of open codes and meager codes. These are the candidate witnesses to the Baire property for X. At any stage s, some of these pairs may have been invalidated: an x has been enumerated into X so that
$x \notin U_e \cup M_e$
. When this occurs, it is no longer possible that the symmetric difference of X and
$U_e$
might be covered by
$M_e$
, so we disregard the pair; we will consider only valid pairs (pairs which have not been invalidated). For ease of notation, we call an index e valid if the pair
$(U_e,M_e)$
is valid.
Let
$V_{e,s}$
denote the intersection of the
$U_i$
for
$i < e$
that are valid at stage s.
Let
$x_s$
be the real enumerated into X at stage s, if any. Suppose that there exists
$e < s$
such that the following conditions hold:
-
(i) e remains valid;
-
(ii)
$x_s$
is the
$<_L$
-least element of
$U_e \setminus M_e$
not already enumerated into X; and -
(iii) for every valid
$i < e$
,
$x_s \in U_i$
.
In such a situation, we say that e triggers an action. For the least e which triggers an action at stage s, add the promise
$(e, 0, V_{e,s})$
to
$\mathcal {S}$
.
Otherwise, let D be the first Borel set not yet considered. Add the promises
$(s, 1, D)$
and
$(s, 0, D)$
to
$\mathcal {S}$
.
Finally, we consider the contents of
$\mathcal {S}$
. Say that a promise
$(t, i, Y)$
is satisfiable if one of the following holds:
-
(i)
$i = 0$
,
$L_s \cap Y \cap V_{t,s} \setminus A$
is nonempty, and the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus A$
is either not in B or was enumerated into B on behalf of a promise of the form
$(u, 1, Z)$
with
$u> t$
or -
(ii)
$i = 1$
and
$L_s \cap Y \cap V_{t,s} \setminus (A \cup B)$
is nonempty.
If there is a satisfiable promise in
$\mathcal {S}$
, let
$(t,i,Y)$
be the first (
$<_L$
-least) one. If
$i = 0$
, we enumerate the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus A$
into A; if this element was already in B, return to
$\mathcal {S}$
the promise of the form
$(u,1,Z)$
on behalf of which that element was enumerated into B. If
$i = 1$
, we enumerate the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus (A \cup B)$
into B. In either case, we declare
$(t,i,Y)$
satisfied and remove it from
$\mathcal {S}$
.
Claim 2.17. Every promise eventually ceases to be satisfiable.
Proof. Let
$(t,i,Y)$
be a promise in
$\mathcal {S}$
, and suppose by induction that all promises that are
$<_L$
-below it eventually cease to be satisfiable. Let
$s_0> t$
be a stage at which this has happened. If
$(t,i,Y)$
is never satisfiable after stage
$s_0$
, then of course it has already ceased to be satisfiable. On the other hand, if it is satisfiable at some later stage u, then it must be the
$<_L$
-least promise satisfiable at that stage, which means it will be satisfied.
If
$i = 0$
, then by construction, once satisfied the promise will never be returned to
$\mathcal {S}$
, and hence will never be satisfiable again.
If
$i = 1$
, then the only circumstance in which
$(t,i,Y)$
would be returned to
$\mathcal {S}$
would be if a higher-priority promise of the form
$(s,0,Z)$
enumerated into A the element which was used to satisfy
$(t,i,Y)$
. However, this would only happen if
$(s,0,Z)$
became satisfiable, which by induction does not happen after stage u.⊣
Claim 2.18. If X is meager, then A is countable.
Proof. Suppose that X is meager. Then there is a meager code for a meager set that covers it. Let e be least so that
$U_e$
is empty and
$M_e \supseteq X$
. Clearly
$(U_e,M_e)$
is never invalidated.
For each
$i < e$
, the symmetric difference of X and
$U_i$
is not contained in
$M_i$
. Thus there is some
$y_i$
so that one of the following holds:
-
(i)
$y_i \in X \setminus U_i$
and
$y_i \notin M_i$
or -
(ii)
$y_i \in U_i \setminus X$
and
$y_i \notin M_i$
.
For a given i, if the first possibility holds, then as soon as
$y_i$
is enumerated into X the pair
$(U_i,M_i)$
will be invalidated. Let
$s_0$
be a stage large enough that every
$(U_i,M_i)$
for
$i < e$
that will ever be invalidated has been.
If the second possibility holds instead, then after a certain stage the
$<_L$
-least element of
$U_i \setminus (M_i \cup X)$
will be a witnessing
$y_i$
and will never be enumerated into X. After this point, i will never trigger an action. Let
$s_1> s_0$
be a stage large enough that this has occurred for every
$i < e$
for which it will ever occur.
After this stage, at most e elements will be enumerated into A: if no action is triggered at a stage before e, an element of a Borel set might be promised. Any promises made after stage e will never be satisfied, because by construction the elements added would have to be members of
$U_e$
, which is empty. So A is countable.⊣
Claim 2.19. If X has the Baire property, then A is Borel.
Proof. By Claim 2.18, we may suppose without loss of generality that X is nonmeager.
Suppose that X has the Baire property. Then there is an open set U and a meager set M so that the symmetric difference of X and U is M; since X is nonmeager, U is nonempty. There therefore exists some e such that
$U_e$
is a code for U and
$M_e$
codes a meager set covering M. Fix the least such e.
For each
$i < e$
, the symmetric difference of X and
$U_i$
is not contained in
$M_i$
. Thus there is some
$y_i$
such that one of the following holds:
-
(i)
$y_i \in X \setminus U_i$
and
$y_i \notin M_i$
or -
(ii)
$y_i \in U_i \setminus X$
and
$y_i \notin M_i$
.
If the first possibility holds for a particular i, then as soon as
$y_i$
is enumerated into X the pair
$(U_i,M_i)$
will be invalidated. Let
$s_0$
be a stage large enough that every
$i < e$
that will ever be invalidated has been.
If the second possibility holds instead, then after a certain stage the
$<_L$
-least element of
$U_i\setminus M_i$
will be the witnessing
$y_i$
and will never be enumerated into X; after this point, i will never trigger an action. Let
$s_1> s_0$
be a stage large enough that this has occurred for every
$i < e$
for which it will ever occur.
Let
$V = V_{e,s_1} = \bigcap _{i < e \textrm { valid}}U_i$
at stage
$s_1$
. Note that V is the intersection of at most countably many open sets, and so is
$G_{\delta }$
. Every element of
$U_e \setminus M_e$
will eventually be enumerated into X, so e will trigger an action uncountably often after stage
$s_1$
. So uncountably many promises of the form
$(e, 0, V)$
will be made, while only countably many promises of the form
$(i, 1, Y)$
with
$i < e$
(which could potentially cause elements of V to be enumerated into B and prohibited from A) will be made; so all but countably many members of V will be enumerated into A.
Likewise, after stage
$s_1$
every element enumerated into A will be in V; if an action is triggered by some
$j> e$
at a later s, any elements enumerated into A as a result will be required to be in
$V_{j,s} \subseteq V$
. So
$A \setminus V$
consists only of the countably many points enumerated before stage
$s_1$
.
Therefore A differs only countably from a
$G_{\delta }$
set; in particular, A is Borel.⊣
Claim 2.20. If X does not have the Baire property, then A is not Borel.
Proof. Suppose that X does not have the Baire property. As noted in the proof of Claim 2.19, for every pair
$(U_e,M_e)$
there is some stage
$s_e$
after which e will never again trigger an action (whether because it has been invalidated or because the necessary element is simply never enumerated into X). The function
$\alpha \mapsto \sup _{\beta < \alpha }s_{\beta }$
is continuous, and therefore has a closed and unbounded set of fixed points. At each such fixed point s, no
$e < s$
triggers an action and so no action is triggered. Thus each Borel set D is eventually addressed under the final clause of the construction.
Let D be a Borel set, and let t be the first stage at which no action is triggered and D is addressed. At stage t, the promises
$(t,0,D)$
and
$(t,1,D)$
are entered into
$\mathcal {S}$
. Likewise, let
$\overline {D}$
be the complement of D, and let
$\hat {t}$
be the first stage at which no action is triggered and
$\overline {D}$
is addressed; at stage
$\hat {t}$
, the promises
$(\hat {t},0,\overline {D})$
and
$(\hat {t},1,\overline {D})$
are entered into
$\mathcal {S}$
. By possibly exchanging the roles of D and
$\overline {D}$
, let
$t> \hat {t}$
.
Let
$s_0$
be a stage large enough that every
$i < t$
that will ever be invalidated has been. Note that for
$s> s_0$
,
$V_{t,s} = V_{t,s_0}$
; call this V. Note that V must be nonempty, because otherwise any member of X that lies in any
$U_i$
for valid
$i < t$
would have to be absent from some
$U_j$
for valid
$j < t$
; it would then have to be in
$M_j$
. Therefore, if V were empty, X would be covered by the (countably many) meager sets
$M_i$
for
$i < t$
, and would therefore itself be meager (and would hence have the Baire property). Likewise, if V were countable, X would be covered by the
$M_i$
and V; thus V must be uncountable.
Suppose
$D \cap V$
is uncountable. Then there are uncountably many stages at which there is an opportunity to satisfy the promises
$(t,0,D)$
and
$(t,1,D)$
(i.e., a new
$y \in D \cap V$
has appeared in L). The only circumstance under which neither is satisfied is when there is a promise of higher priority that is satisfied instead. But there are only countably many promises of higher priority, and by Claim 2.17 these promises eventually cease to be satisfiable; so eventually
$(t,0,D)$
and
$(t,1,D)$
will both be satisfied by enumerating an element of
$D \cap V$
into A and B respectively, such that the member of B enumerated on behalf of
$(t,1,D)$
will not enter A. Therefore, at least one member of D will never be enumerated into A, and hence
$A \neq D$
.
Suppose instead that
$D \cap V$
is countable. Then
$\overline {D} \cap V$
is uncountable. By the symmetric argument to the above, at least one member of
$\overline {D}$
will be enumerated into A; thus
$A \neq D$
.
In either case,
$A \neq D$
; since D was an arbitrary Borel set, A cannot be Borel.⊣
This completes the proof of Theorem 2.15.⊣
Theorem 2.21. Under the assumption that
$V = L$
,
$\mathrm {Baire}_2 \geq _m \mathrm {Lebesgue}_2$
.
Proof. This proof will be very similar to the previous one. Given an index for a
$\boldsymbol {\Sigma ^1_2}$
set X, we aim to construct a
$\boldsymbol {\Sigma ^1_2}$
set A so that X is Lebesgue-measurable iff A has the Baire property. Recall that a set X is Lebesgue-measurable iff there is a
$G_{\delta }$
set G and a null set N so that
$X = G \setminus N$
.
Definition 2.22. Recall the definition of an open code from the proof of Theorem 2.15. A
$G_{\delta }$
code is an
$\omega $
-sequence of open codes. If
$G = \langle G_i\rangle _{i<\omega }$
is a
$G_{\delta }$
code, the set coded by G is
$\bigcap _iA_i$
, where
$A_i$
is the set coded by
$G_i$
.
A null code is a sequence
$\langle N_n\rangle _{n < \omega }$
of (possibly infinite) subsets of
$2^{<\omega }$
so that
$$ \begin{align*} \lim_{n \to \omega}\sum_{\sigma \in N_n}2^{-|\sigma|} = 0. \end{align*} $$
If
$N = \langle N_n\rangle _{n < \omega }$
is a null code, the set coded by N is
$\{x \in 2^{\omega } \mid (\forall n) (\exists \sigma \in N_n)\sigma \prec x\}$
.
Observe that the set of
$G_{\delta }$
codes and the set of null codes are both computable sets (recalling that the definition of the limit requires only quantification over the rationals, which is bounded for the purposes of
$\omega _1$
-computability) and that the map from a code of either sort to the set it codes is uniformly computable.
Note that while not every null set is coded by a null code, it is the case that every null set is covered by a null set that is.
We now begin the construction. Given a code for a
$\boldsymbol {\Sigma ^1_2}$
set X, we will construct a code for a
$\Sigma ^1_2$
set A so that A will have the Baire property iff X is Lebesgue-measurable. We again factor through the equivalence of
$\boldsymbol {\Sigma ^1_2}$
sets of reals and c.e. sets of reals, and for clarity we do not distinguish between a
$G_{\delta }$
or null code and the set it codes. Finally, we arrange that all c.e. sets enumerate at most one element per stage.
As in the previous proof, we will maintain two structures. First, we will construct a c.e. set A, together with an auxiliary c.e. set B. Second, we maintain a collection
$\mathcal {S}$
of promises of the form
$(s, i, Y)$
, where
$s \in \omega _1$
,
$i = 0$
or
$1$
, and Y is a (code for a) set.
$(s,i,Y)$
may be thought of as a “promise” to enumerate an element of Y into A (if
$i = 0$
) or B (if
$i = 1$
), made with priority s. We will ensure that elements that are enumerated into B on behalf of a promise
$(s,1,Y)$
have not previously been enumerated into A and will not be enumerated into A except on behalf of a promise of the form
$(t,0,Z)$
with
$t < s$
.
Fix an effective enumeration
$(G_e,N_e)$
of pairs of
$G_{\delta }$
codes and null codes. These are the candidate witnesses to X being Lebesgue-measurable. At any stage s, some of these pairs may have been invalidated: an x has been enumerated into X so that
$x \notin G_e$
. When this occurs, it is no longer possible that
$X = G_e \setminus N$
for a null set covered by
$N_e$
, so we disregard the pair; we will consider only valid pairs (pairs which have not been invalidated). For ease of notation, we again call an index e valid if
$(G_e,N_e)$
is valid.
Also fix an effective enumeration
$(U_i,M_i)$
, as before, of pairs of open codes and meager codes; these are the candidate witnesses to A having the property of Baire.
For each i, let
$G_i^* = \{z \in G_i \mid (\exists y \leq _L z)y \in G_i \setminus N_i\}$
; note that if
$G_i\setminus N_i$
is nonempty then
$G_i^*$
is only countably different from
$G_i$
, but if
$G_i\setminus N_i$
is empty then so is
$G_i^*$
. Let
$V_{e,s}$
denote the intersection of
$G_i^*$
for all
$i < e$
that remain valid at stage s.
Let
$x_s$
be the real enumerated into X at stage s, if any. Suppose that there exists
$e < s$
so that the following conditions hold:
-
(i) e remains valid and
-
(ii)
$x_s$
is the
$<_L$
-least element of
$G_e\setminus N_e$
not already enumerated into X.
In such a situation, we say that e triggers an action.
If any action is triggered, let e be the least index that triggers an action. Enumerate
$(e, 0, V_{e,s})$
into
$\mathcal {S}$
.
Otherwise, let
$(U_j,M_j)$
be the first pair of an open code and a meager code not yet considered. Enumerate into
$\mathcal {S}$
the promises
$(s, 1, U_j \setminus M_j)$
and
$(s, 0, \omega ^{\omega } \setminus (U_j \cup M_j))$
.
Finally, we handle promises in the same manner as in the previous proof. Say that a promise
$(t, i, Y)$
is satisfiable if one of the following holds:
-
(i)
$i = 0$
,
$L_s \cap Y \cap V_{t,s} \setminus A$
is nonempty, and the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus A$
is either not in B or was enumerated into B on behalf of a promise of the form
$(u, 1, Z)$
with
$u> t$
or -
(ii)
$i = 1$
and
$L_s \cap Y \cap V_{t,s} \setminus (A \cup B)$
is nonempty.
If there is a satisfiable promise in
$\mathcal {S}$
, let
$(t,i,Y)$
be the first (
$<_L$
-least) one. If
$i = 0$
, we enumerate the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus A$
into A; if this element was already in B, return to
$\mathcal {S}$
the promise of the form
$(u,1,Z)$
on behalf of which that element was enumerated into B. If
$i = 1$
, we enumerate the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus (A \cup B)$
into B. In either case, we declare
$(t,i,Y)$
satisfied and remove it from
$\mathcal {S}$
.
Claim 2.23. Every promise eventually ceases to be satisfiable.
Proof. Because the relevant details of the construction are the same, the proof is identical to that of Claim 2.17.⊣
Claim 2.24. If X is Lebesgue-measurable, then A has the property of Baire.
Proof. Suppose that X is Lebesgue-measurable. Then there exists a
$G_{\delta }$
set G and a null set N such that
$G \setminus N = X$
; call e a code point for X if
$G_e$
is a
$G_{\delta }$
code for such a G and
$N_e$
is a code for a null set that covers the corresponding N. Note that such an e will never be invalidated.
Let e be the least code point for X so that
$G_e \setminus N_e$
is either empty or uncountable. If X is null, there is a code point e for which
$G_e \setminus N_e$
is empty; if X has positive measure, then every code point e has
$G_e \setminus N_e$
uncountable.
Let
$s_0$
be a stage late enough that every
$i < e$
that will ever be invalidated has been. Note that, after stage
$s_0$
, every
$i < e$
that remains valid must eventually cease to trigger actions; otherwise it would be the case that
$G_i \supseteq X \supseteq G_i \setminus N_i$
and uncountably many elements would have been enumerated into
$G_i \setminus N_i$
, in which case i would have been our chosen e. Let
$s_1> s_0$
be a stage large enough that every
$i < e$
has ceased to trigger actions.
Suppose now that
$G_e \setminus N_e$
is empty. Then
$G_e^*$
is empty, so no elements will be enumerated into A on behalf of promises
$(t,i,Y)$
with
$t> e$
. If A were uncountable, then, there would have to be some
$i < e$
that triggers an action uncountably often; by the above observation that cannot be the case. Therefore, if
$G_e \setminus N_e$
is empty, then A is countable.
Finally, suppose instead that
$G_e \setminus N_e$
is uncountable. Because
$X \supseteq G_e \setminus N_e$
, every element of
$G_e \setminus N_e$
is eventually enumerated into X; so e triggers an action uncountably often. By the argument above, e is the least index which triggers an action uncountably often, so
$(e,0,V_{e,s})$
is enumerated into
$\mathcal {S}$
for unboundedly many s.
For
$t> s_1$
,
$V_{e,t} = V_{e,s_1}$
; call this set V. All promises made after stage
$s_1$
will enumerate only elements of V into A, so
$A \setminus V$
is countable. Uncountably many promises
$(e,0,V)$
are eventually made, and eventually all promises
$(t,i,Y)$
with
$t < e$
that will ever be satisfied have been; after this point, all members of V that have not been placed into B will be enumerated into A. Thus A will differ from V by only a countable set. Since V is
$G_{\delta }$
, A has the property of Baire.⊣
Claim 2.25. If X is not Lebesgue-measurable, then A does not have the property of Baire.
Proof. Suppose that X is not Lebesgue-measurable. Then, as noted in the proof of Claim 2.24, for every pair
$(G_e,N_e)$
there is some stage
$s_e$
after which e will never again trigger an action (whether because it has been invalidated or because the necessary element is simply never enumerated into X). The function
$\alpha \mapsto \sup _{\beta < \alpha }s_{\beta }$
is a continuous function on the countable ordinals, and hence has a closed and unbounded set of fixed points; at each such fixed point s, no
$e < s$
can trigger an action, so no action is triggered. Thus each pair
$(U_j,M_j)$
is eventually addressed under the final clause of the construction.
Fix
$(U_j,M_j)$
, and let s be the stage at which it is addressed. At that stage, the promises
$(s, 1, U_j \setminus M_j)$
and
$(s, 0, \omega ^{\omega } \setminus (U_j \cup M_j))$
are enumerated into
$\mathcal {S}$
.
By some countable stage
$s_0$
, all promises in
$\mathcal {S}$
prior to
$(s,1,U_j\setminus M_j)$
that will ever be satisfied have been. By some stage
$s_1> s_0$
, all
$e < s$
that will ever be invalidated have been; for
$t> s_1$
,
$V_{s,t} = V_{s,s_1}$
. Call this V.
Suppose
$(U_j \setminus M_j) \cap V$
is uncountable. Then there exists some stage
$t> s_1$
at which there is a new element
$y \in L_t \cap (U_j \setminus M_j) \cap V$
that is not already in A. At this stage,
$(s, 1, U_j \setminus M_j)$
is satisfiable. Since
$t> s_1 > s_0$
, no prior promise is satisfiable, so
$(s,1,U_j\setminus M_j)$
is satisfied by enumerating such a y into B. Since by construction this element could only be enumerated into A on behalf of a higher-priority promise, all of which have ceased to be satisfiable by this stage, this will not be in A, so
$U_j \setminus M_j \nsubseteq A$
. Therefore the symmetric difference of A and
$U_j$
is not contained in
$M_j$
.
Suppose instead that
$(U_j \setminus M_j) \cap V$
is countable. Then
$V \setminus (U_j \setminus M_j)$
is not (otherwise X would be a null set and hence measurable). Then, by a symmetric argument to the above, the promise
$(s, 0, \omega ^{\omega } \setminus (U_j \cup M_j))$
is eventually satisfied, so
$A \setminus U_j$
includes an element not in
$M_j$
.
In either case, the symmetric difference of A and
$U_j$
is not contained in
$M_j$
. Since
$U_j$
was an arbitrary open code and
$M_j$
an arbitrary meager code, A does not have the property of Baire.⊣
This completes the proof of Theorem 2.21.⊣
Theorem 2.26. Under the assumption that
$V = L$
,
$\mathrm {Lebesgue}_2 \geq _m \mathrm {Borel}_2$
.
Proof. The proof is again very similar. Given an index for a
$\boldsymbol {\Sigma ^1_2}$
set X, we aim to construct a
$\boldsymbol {\Sigma ^1_2}$
set A so that X is Borel iff A is Lebesgue-measurable.
Recall the definitions of open codes and Borel codes from the proof of Theorem 2.15, and the definition of null codes from the proof of Theorem 2.21.
We will factor again through the equivalence of
$\boldsymbol {\Sigma ^1_2}$
sets of reals and c.e. sets of reals, and we do not distinguish between a code and the set it codes. As before, we arrange that all c.e. sets enumerate at most one element per stage.
Fix an effective enumeration of Borel codes
$\langle B_e\rangle _{e < \omega _1}$
, and an effective enumeration
$(G_e,N_e)$
of pairs of
$G_{\delta }$
codes and null codes. The
$B_e$
will be the candidates for X; the
$(G_e,N_e)$
will be candidates for witnesses that A is measurable. At any stage s, we will consider the codes
$B_e$
for
$e < s$
. Some of these may have been invalidated; that is, an x has been enumerated into X so that
$x \notin B_e$
. We only consider valid pairs (pairs which have not been invalidated). Let
$V_{e,s}$
be the intersection of
$B_i$
for the
$i < e$
that remain valid at stage s.
We will maintain our usual two structures throughout the construction. First, the c.e. set A and an auxiliary c.e. set C (a departure from the B of the previous proofs in order to distinguish it from the Borel sets). Second, a set
$\mathcal {S}$
of promises of the form
$(t,i,Y)$
for
$t \in \omega _1$
,
$i = 0$
or
$1$
, and Y a (code for a) set of reals. Intuitively,
$(t,0,Y)$
promises to include the
$<_L$
-least element of Y in A with priority t, while
$(t,1,Y)$
promises to include it in C.
We now begin the construction. Let
$x_s$
be the real enumerated into X at stage s, if any. Suppose that there exists
$e < s$
so that the following holds:
-
(i) e remains valid and
-
(ii)
$x_s$
is the
$<_L$
-least element of
$B_e$
not already enumerated into X.
In such a situation, we say that e triggers an action.
If an action is triggered at stage s, let e be the least index which triggers an action. Enumerate into
$\mathcal {S}$
the promise
$(e,0,V_{e,s})$
.
Otherwise, let
$(G_j,N_j)$
be the first pair of a
$G_{\delta }$
code and a null code not yet diagonalized against. Then enumerate into
$\mathcal {S}$
the promises
$(s,1,G_j\setminus N_j)$
and
$(s,0,\omega ^{\omega } \setminus G_j)$
.
We handle the satisfaction of promises in the same manner as in the proofs of Theorems 2.15 and 2.21. Say that a promise
$(t, i, Y)$
is satisfiable if one of the following holds:
-
(i)
$i = 0$
,
$L_s \cap Y \cap V_{t,s} \setminus A$
is nonempty, and the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus A$
is either not in C or was enumerated into C on behalf of a promise of the form
$(u, 1, Z)$
with
$u> t$
or -
(ii)
$i = 1$
and
$L_s \cap Y \cap V_{t,s} \setminus (A \cup C)$
is nonempty.
If there is a satisfiable promise in
$\mathcal {S}$
, let
$(t,i,Y)$
be the first (
$<_L$
-least) one. If
$i = 0$
, we enumerate the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus A$
into A; if this element was already in C, return to
$\mathcal {S}$
the promise of the form
$(u,1,Z)$
on behalf of which that element was enumerated into B. If
$i = 1$
, we enumerate the
$<_L$
-least member of
$Y \cap V_{t,s} \setminus (A \cup C)$
into C. In either case, we declare
$(t,i,Y)$
satisfied and remove it from
$\mathcal {S}$
.
Claim 2.27. Every promise eventually ceases to be satisfiable.
Proof. Because the relevant details of the construction are the same, the proof is identical to that of Claim 2.17.⊣
Claim 2.28. If X is countable, then A is countable.
Proof. If X is countable, then it is Borel. Let
$B_e$
be the first Borel code for X. Then, for any
$t> e$
and any s,
$V_{t,s} \subseteq X$
, and in particular
$V_{t,s}$
is countable. Therefore, only countably many elements enter A on behalf of promises of the form
$(t,i,Y)$
for
$t> s$
.
The only other promises are those added to
$\mathcal {S}$
by the triggering of an action; but an action is triggered at most once for each element of X, which means only countably many such promises are made, and therefore only countably many elements enter A on their behalf.⊣
Claim 2.29. If X is Borel, then A is Lebesgue-measurable.
Proof. By Claim 2.28, we may suppose without loss of generality that X is uncountable. Suppose X is Borel; then there is an e so that
$B_e$
is a code for X. Fix the least such e.
For each
$i < e$
,
$B_i \neq X$
. Thus for some
$y_i$
, one of the following holds:
-
(i)
$y_i \in X \setminus B_i$
or -
(ii)
$y_i \in B_i \setminus X$
.
If the first possibility holds for some particular i, then as soon as
$y_i$
is enumerated into X,
$B_i$
will be invalidated. Fix a stage
$s_0$
large enough that every
$i < e$
that will ever be invalidated has been.
If the second possibility holds for some particular i, then after a certain stage the
$<_L$
-least element of
$B_i\setminus X$
will be such a
$y_i$
, and will never be enumerated into X; after this point, i will never trigger an action. Fix
$s_1> s_0$
large enough that this has occurred for every
$i < e$
for which it will ever occur.
Let
$V = V_{e,s_1}$
. As a countable intersection of Borel sets, V is itself Borel. After stage
$s_1$
, e will trigger an action uncountably often, because every member of
$B_e$
will eventually be enumerated into X. So every element of V except those promised to C with priority
$<e$
will eventually be enumerated into A, and there are only countably many such promises. So
$V \setminus A$
will be countable. Likewise, after stage
$s_1$
, every new element enumerated into A will be in V. So
$A \setminus V$
consists only of elements promised to or enumerated into A before stage
$s_1$
, of which there are only countably many. Thus A differs only countably from a Borel set, and is hence Borel (and therefore Lebesgue-measurable).⊣
Claim 2.30. If X is not Borel, then A is not Lebesgue-measurable.
Proof. Suppose that X is not Borel. Then, as noted in the previous argument, for every code
$B_e$
there is some stage
$s_e$
after which e will never again trigger an action (whether because it has been invalidated or because the necessary element is simply never enumerated into X). The function
$\alpha \mapsto \sup _{\beta < \alpha }s_{\beta }$
is a continuous function on the countable ordinals, and therefore has a closed and unbounded set of fixed points. At each such fixed point s, no
$e < s$
can trigger an action, so no action is triggered. Thus each pair
$(G_j,N_j)$
is eventually addressed under the final clause of the construction.
Let
$(G_j,N_j)$
be an arbitrary pair of a
$G_{\delta }$
code and a null code, and let s be the stage at which it is addressed. At that stage, the promises
$(s,1,G_j\setminus N_j)$
and
$(s,0,\omega ^{\omega }\setminus G_j)$
are enumerated into
$\mathcal {S}$
.
By some countable stage
$s_0$
, all promises in
$\mathcal {S}$
prior to
$(s,1,G_j\setminus N_j)$
that will ever be satisfied have been. By some stage
$s_1> s_0$
, all
$e < s$
that will ever be invalidated have been; for
$t> s_1$
,
$V_{s,t} = V_{s,s_1}$
. Call this V.
Suppose that
$(G_j \setminus N_j) \cap V$
is uncountable. Then there will come a stage
$t> s_1$
at which a new
$y \in (G_j \setminus N_j) \cap V$
has appeared, which gives an opportunity to satisfy the promise
$(s,1,G_j\setminus N_j)$
. Since all prior promises that will ever be satisfied have been already, this is the promise that is satisfied at stage t; so an element of
$G_j\setminus N_j$
is enumerated into C (and consequently never enters A). Therefore
$A \nsupseteq G_j \setminus N_j$
.
Suppose instead that
$(G_j \setminus N_j) \cap V$
is countable. Then
$V \setminus G_j$
is not (otherwise X would be Borel). By a symmetric argument to the above, the promise
$(s,0,V\setminus G_j)$
is eventually satisfied, so A includes at least one element not in
$G_j$
; hence
$A \nsubseteq G_j$
.
In either case, it is not the case that
$G_j \supseteq A \supseteq G_j \setminus N_j$
; since
$(G_j,N_j)$
was chosen arbitrarily, A cannot be the difference of a
$G_{\delta }$
set and a null set. Therefore A is not Lebesgue-measurable.⊣
This completes the proof of Theorem 2.26.⊣
We are now able to complete the proof of Theorem 2.13.
Proof of Theorem 2.13. By Theorem 2.15,
$\mathrm {Borel}_2 \geq _m \mathrm {Baire}_2$
. By Theorem 2.21,
$\mathrm {Baire}_2 \geq _m \mathrm {Lebesgue}_2$
. By Theorem 2.26,
$\mathrm {Lebesgue}_2 \geq _m \mathrm {Borel}_2$
. Combining these, we have
$$ \begin{align*} \mathrm{Borel}_2 \geq_m \mathrm{Baire}_2 \geq_m \mathrm{Lebesgue}_2 \geq_m \mathrm{Borel}_2. \end{align*} $$
So in fact
$\mathrm {Borel}_2 \equiv _m \mathrm {Baire}_2 \equiv _m \mathrm {Lebesgue}_2$
.⊣
Acknowledgements
The authors wish to thank the anonymous referee for pointing out some significant errors in an earlier version of this paper. Raghavan was partially supported by the Singapore Ministry of Education’s research grant number MOE2017-T2-2-125.
