In the study of the arithmetic degrees the $\omega \text {-REA}$ sets play a role analogous to the role the r.e. degrees play in the study of the Turing degrees. However, much less is known about the arithmetic degrees and the role of the $\omega \text {-REA}$ sets in that structure than about the Turing degrees. Indeed, even basic questions such as the existence of an $\omega \text {-REA}$ set of minimal arithmetic degree are open. This paper makes progress on this question by demonstrating that some promising approaches inspired by the analogy with the r.e. sets fail to show that no $\omega \text {-REA}$ set is arithmetically minimal. Finally, it constructs a $\prod ^0_{2}$ singleton of minimal arithmetic degree. Not only is this a result of considerable interest in its own right, constructions of $\prod ^0_{2}$ singletons often pave the way for constructions of $\omega \text {-REA}$ sets with similar properties. Along the way, a number of interesting results relating arithmetic reducibility and rates of growth are established.

Goodstein’s principle is arguably the first purely number-theoretic statement known to be independent of Peano arithmetic. It involves sequences of natural numbers which at first appear to diverge, but eventually decrease to zero. These sequences are defined relative to a notation system based on exponentiation for the natural numbers. In this article, we provide a self-contained and modern analysis of Goodstein’s principle, obtaining some variations and improvements. We explore notions of optimality for notation systems and apply them to the classical Goodstein process and to a weaker variant based on multiplication rather than exponentiation. In particular, we introduce the notion of base-change maximality, and show how it leads to far-reaching extensions of Goodstein’s result. We moreover show that by varying the initial base of the Goodstein process, one readily obtains independence results for each of the fragments $\mathsf {I}\Sigma _n$ of Peano arithmetic.

Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of interest in descriptive set theory. In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals.

It is shown that the determinacy of $G_{\delta \sigma }$ games of length $\omega ^2$ is equivalent to the existence of a transitive model of ${\mathsf {KP}} + {\mathsf {AD}} + \Pi _1\textrm {-MI}_{\mathbb {R}}$ containing $\mathbb {R}$ . Here, $\Pi _1\textrm {-MI}_{\mathbb {R}}$ is the axiom asserting that every monotone $\Pi _1$ operator on the real numbers has an inductive fixpoint.

Extending Aanderaa’s classical result that $\pi ^{1}_{1} < \sigma ^{1}_{1}$ , we determine the order between any two patterns of iterated $\Sigma ^{1}_{1}$ - and $\Pi ^{1}_{1}$ -reflection on ordinals. We show that this order of linear reflection is a prewellordering of length $\omega ^{\omega }$ . This requires considering the relationship between linear and some non-linear reflection patterns, such as $\sigma \wedge \pi $ , the pattern of simultaneous $\Sigma ^{1}_{1}$ - and $\Pi ^{1}_{1}$ -reflection. The proofs involve linking the lengths of $\alpha $ -recursive wellorderings to various forms of stability and reflection properties satisfied by ordinals $\alpha $ within standard and non-standard models of set theory.

We characterize the determinacy of $F_\sigma $ games of length $\omega ^2$ in terms of determinacy assertions for short games. Specifically, we show that $F_\sigma $ games of length $\omega ^2$ are determined if, and only if, there is a transitive model of ${\mathsf {KP}}+{\mathsf {AD}}$ containing $\mathbb {R}$ and reflecting $\Pi _1$ facts about the next admissible set.

As a consequence, one obtains that, over the base theory ${\mathsf {KP}} + {\mathsf {DC}} + ``\mathbb {R}$ exists,” determinacy for $F_\sigma $ games of length $\omega ^2$ is stronger than ${\mathsf {AD}}$ , but weaker than ${\mathsf {AD}} + \Sigma _1$ -separation.

In a recent paper by M. Rathjen and the present author it has been shown that the statement “every normal function has a derivative” is equivalent to $\Pi ^1_1$ -bar induction. The equivalence was proved over $\mathbf {ACA_0}$ , for a suitable representation of normal functions in terms of dilators. In the present paper, we show that the statement “every normal function has at least one fixed point” is equivalent to $\Pi ^1_1$ -induction along the natural numbers.

We study genericity and randomness with respect to ITTMs, continuing the work initiated by Carl and Schlicht. To do so, we develop a framework to study randomness in the constructible hierarchy. We then answer several of Carl and Schlicht’s question. We also ask a new question one the equality of two classes of randoms. Although the natural intuition would dictate that the two classes are distinct, we show that things are not as simple as they seem. In particular we show that the categorical analogues of these two classes coincide, in contradiction with the natural intuition. Even though we are not able to answer the question for randomness in this article, we delineate and sharpen its contour and outline.

We prove the following two basis theorems for ${\rm{\Sigma }}_2^1$-sets of reals:

1. (1) Every nonthin ${\rm{\Sigma }}_2^1$-set has a perfect ${\rm{\Delta }}_2^1$-subset if and only if it has a nonthin ${\rm{\Delta }}_2^1$-subset, and this is equivalent to the statement that there is a nonconstructible real.

2. (2) Every uncountable ${\rm{\Sigma }}_2^1$-set has an uncountable ${\rm{\Delta }}_2^1$-subset if and only if either every real is constructible or $\omega _1^L$ is countable.

We also apply the method that proves (2) to show that if there is a nonconstructible real, then there is a perfect ${\rm{\Pi }}_2^1$-set with no nonempty ${\rm{\Pi }}_2^1$-thin subset, strengthening a result of Harrington [4].

We study randomness beyond ${\rm{\Pi }}_1^1$-randomness and its Martin-Löf type variant, which was introduced in [16] and further studied in [3]. Here we focus on a class strictly between ${\rm{\Pi }}_1^1$ and ${\rm{\Sigma }}_2^1$ that is given by the infinite time Turing machines (ITTMs) introduced by Hamkins and Kidder. The main results show that the randomness notions associated with this class have several desirable properties, which resemble those of classical random notions such as Martin-Löf randomness and randomness notions defined via effective descriptive set theory such as ${\rm{\Pi }}_1^1$-randomness. For instance, mutual randoms do not share information and a version of van Lambalgen’s theorem holds.

Towards these results, we prove the following analogue to a theorem of Sacks. If a real is infinite time Turing computable relative to all reals in some given set of reals with positive Lebesgue measure, then it is already infinite time Turing computable. As a technical tool towards this result, we prove facts of independent interest about random forcing over increasing unions of admissible sets, which allow efficient proofs of some classical results about hyperarithmetic sets.

We investigate the class of bipartite Borel graphs organized by the order of Borel homomorphism. We show that this class is unbounded by finding a jump operator for Borel graphs analogous to a jump operator of Louveau for Borel equivalence relations. The proof relies on a nonseparation result for iterated Fréchet ideals and filters due to Debs and Saint Raymond. We give a new proof of this fact using effective descriptive set theory. We also investigate an analogue of the Friedman-Stanley jump for Borel graphs. This analogue does not yield a jump operator for bipartite Borel graphs. However, we use it to answer a question of Kechris and Marks by showing that there is a Borel graph with no Borel homomorphism to a locally countable Borel graph, but each of whose connected components has a countable Borel coloring.

Exploring further the properties of ITRM-recognizable reals started in [1], we provide a detailed analysis of recognizable reals and their distribution in Gödels constructible universe L. In particular, we show that new unrecognizable reals are generated at every index $\gamma \, \ge \,\omega _\omega ^{CK}$. We give a machine-independent characterization of recognizability by proving that a real r is recognizable if and only if it is ${\Sigma _1}$-definable over ${L_{\omega _\omega ^{CK,\,r}}}$ and that $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ for every recognizable real r and show that either every or no r with $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ generated over an index stage ${L_\gamma }$ is recognizable. Finally, the techniques developed along the way allow us to prove that the halting number for ITRMs is recognizable and that the set of ITRM-computable reals is not ITRM-decidable.