In studying functions of the form
$g \circ g$
, Humke and Laczkovich [Reference Humke and Laczkovich4] proved that
$L2$
is not Borel and Beleznay [Reference Beleznay2] improved this to the result in the abstract. Combined with [Reference Humke and Laczkovich4, Lemma 3], this solved a problem of Becker [Reference Becker, Judah, Just and Woodin1, p. 4] and Kechris [Reference Kechris5, p. 215]. We give a one-page proof. Let
$A\subset \mathbb {R}$
be
$\Sigma ^1_1$
. Thus to each
$x\in \mathbb {R}$
one can effectively associate a tree
$T_x$
on
$\mathbb {N}$
such that
$T_x$
is well-founded if and only if
$x\not \in A$
. Uniformly in x (see, e.g., [Reference Montalbán7, Section VI.1.1]), one can find an ill-founded tree
$K_x$
recursive in x with no infinite branch in
$\Delta ^1_1(x)$
. Let
$S_x$
be the tree of pairs
$(l,m) \in T_x \times K_x$
of the same length ordered by
$(l,m) <_{S_x} (l',m')$
if
$l <_{T_x} l'$
and
$m <_{K_x} m'$
.
Observe that
$S_x$
is ill-founded if
$T_x$
is. Conversely, from any branch through
$S_x$
we can compute branches through both
$T_x$
and
$K_x$
. Let
$L_x = \omega ^{\mathsf {KB}(S_x)}$
, where
$\mathsf {KB}(S_x)$
denotes the Kleene–Brouwer ordering on
$S_x$
and
$\omega ^{\mathsf {KB}(S_x)}$
is the natural order on formal Cantor normal forms
$\omega ^{x_1}\cdot m_1 + \omega ^{x_2}\cdot m_2 + \dots + \omega ^{x_k}\cdot m_k$
, where
$x_1> \dots > x_k$
are elements of
$\mathsf {KB}(S_x)$
. Note that if
$x\not \in A$
, then
$L_x$
is well-ordered and additively indecomposable, so
$L_x \not \in L2$
.
In contrast, if
$x \in A$
, then
$S_x$
is ill-founded but has no branch which is
$\Delta ^1_1(x)$
, so
$\mathsf {KB}(S_x)$
has no
$\Delta ^1_1(x)$
infinite descending sequence; neither does
$L_x = \omega ^{\mathsf {KB}(S_x)}$
, by a result of Girard and Hirst (see [Reference Marcone and Montalbán6, Theorem 1.3]). By a result of Harrison [Reference Harrison3],
$\mathsf {KB}(S_x)$
and
$L_x$
are respectively of the form
$\omega _1^x\cdot (1+\mathbb {Q}) + \alpha $
and
$\omega _1^x\cdot (1+\mathbb {Q}) + \alpha _0$
for some
$\alpha ,\alpha _0 < \omega _1^x$
(smallest non-x-recursive ordinal). However,
$\omega ^{\omega _1^x\cdot (1 + \mathbb {Q}) + \alpha }$
contains arbitrarily large copies of
$\mathbb {Q}$
and thus
$\alpha _0 = 0$
. Since
$\mathbb {Q}\cong \mathbb {Q} + 1 + \mathbb {Q}$
, we have
$L_x = \omega _1^x\cdot (1 + \mathbb {Q}) \cong \omega _1^x\cdot (1 + \mathbb {Q})\cdot 2 \in L2$
.
