Hostname: page-component-5cf477f64f-zrtmk Total loading time: 0 Render date: 2025-03-31T15:08:00.343Z Has data issue: false hasContentIssue false

A ONE-PAGE PROOF OF A THEOREM OF BELEZNAY

Published online by Cambridge University Press:  18 March 2025

JUAN P. AGUILERA
Affiliation:
DEPARTMENT OF DISCRETE MATHEMATICS AND GEOMETRY TU WIEN WIEDNER HAUPTSTR 8–10, 1040 VIENNA AUSTRIA E-mail: [email protected] E-mail: [email protected]
MARTINA IANNELLA
Affiliation:
DEPARTMENT OF DISCRETE MATHEMATICS AND GEOMETRY TU WIEN WIEDNER HAUPTSTR 8–10, 1040 VIENNA AUSTRIA E-mail: [email protected] E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

We give a short proof of a theorem of Beleznay asserting that the set $L2$ of reals coding linear orders of the form $I + I$ is complete analytic.

Type
Article
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

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$ .

References

Becker, H., Descriptive set theoretic phenomena in analysis and topology , Set Theory of the Continuum (Judah, H., Just, W., and Woodin, H., editors), Springer-Verlag, New York, 1992, pp. 125.Google Scholar
Beleznay, F., The complexity of the collection of countable linear orders of the form $I+I$ . Journal of Symbolic Logic , vol. 64 (1999), pp. 15191526.CrossRefGoogle Scholar
Harrison, J., Recursive pseudo-well-orderings . Transactions of the American Mathematical Society , vol. 131 (1968), pp. 526543.CrossRefGoogle Scholar
Humke, P. D. and Laczkovich, M., The Borel structure of iterates of continuous functions . Proceedings of the Edinburgh Mathematical Society , vol. 32 (1989), pp. 483494.CrossRefGoogle Scholar
Kechris, A. S., Classical Descriptive Set Theory , Springer-Verlag, New York, 1994.Google Scholar
Marcone, A. and Montalbán, A., The Veblen function for computability theorists . Journal of Symbolic Logic , 76 (2011), pp. 575602.CrossRefGoogle Scholar
Montalbán, A., Computable Structure Theory II: Beyond the Arithmetic . Book draft.Google Scholar