In this thesis, we explore connections between computability theory and set theory. We investigate an extension of reverse mathematics to a higher-order context, focusing in particular on determinacy principles, and an extension of computable structure theory to uncountable structures via set-theoretic forcing. We also look at computability-theoretic operations induced by ultrafilters, and the classical computable structure theory of ordinals as clarified by set-theoretic results.

It is a well-known empirical phenomenon that natural axiomatic theories are pre-well-ordered by proof-theoretic strength. However, without a precise definition of ``natural,'' it is not clear how to explain this observation in a strictly mathematical way. One expression of the pre-well-ordering phenomenon comes from ordinal analysis, a research program wherein ordinals are assigned to natural theories; these ordinals are commonly understood as measuring the ``strength'' of the theories to which they are assigned. Our goal in this dissertation is to formulate and prove statements that provide insight into the pre-well-ordering phenomenon.

Part I contains an investigation of the pre-well-ordering phenomenon in the setting of first-order arithmetic. One method for determining the proof-theoretic ordinal of a theory $T$ involves showing that $T$ can be conservatively approximated by iterating consistency statements over a weak base theory. This technique yields informative results only for natural theories. Why can natural theories be conservatively approximated by iterating consistency statements? Our explanation is that the consistency operator and its iterates into the effective transfinite are canonical as functions on theories. To this end, we prove that any recursive monotone function on finitely axiomatized theories that is everywhere bounded by an iterate of the consistency operator must coincide somewhere with some iterate of the consistency operator. We also prove that any recursive monotone function on finitely axiomatized theories must be either as weak as the identity operator in the limit or as strong as the consistency operator in the limit.

Part II contains an investigation of the pre-well-ordering phenomenon in the setting of second-order arithmetic. In second-order arithmetic it is possible to formalize $\Pi^1_1$ reflection, which provides a more robust measurement of proof-theoretic strength than consistency strength. We prove that the behavior exhibited by natural theories with respect to consistency strength is exhibited in general with respect to $\Pi^1_1$ strength in the following sense: there is no sequence $(T_n)_{n<\omega}$ of $\Pi^1_1$ sound extensions of $\mathsf{ACA}_0$ such that, for each $n$, $T_n$ proves the $\Pi^1_1$ soundness of $T_{n+1}$. This means that it is possible to rank the $\Pi^1_1$ sound extensions of $\mathsf{ACA}_0$ by proof-theoretic strength. We prove that for every $\Pi^1_1$ sound extension $T$ of $\mathsf{ACA}_0^+$ the rank of $T$ is exactly the proof-theoretic ordinal of $T$; this vindicates the common wisdom that ordinal analysis measures the proof-theoretic strength of natural theories. Along the way we prove two far-reaching conservation theorems. First, $\alpha$ iterated $\Pi^1_1$ reflection of $\mathsf{ACA}_0$ is $\Pi^1_1(\Pi^0_3)$ conservative over $\varepsilon_\alpha$ iterated $\Pi^1_1(\Pi^0_3)$ reflection of $\mathsf{RCA}_0$. Second, for any $\Pi^1_2$ axiomatizable $T$, every set is contained in an $\omega$ model if and only if, for every well order $\alpha$, $\alpha$ iterated $\Pi^1_1$ reflection for $T$ is $\Pi^1_1$ sound. Finally, we use the techniques introduced to prove these results to provide a purely proof-theoretic demonstration of a classical theorem of recursion theory: there is no sequence $(A_n)_{n<\omega}$ such that, for each $n$, $ \mathcal{O}^{A_{n+1}} \leq_H A_n $. This engenders a well-founded ranking of the real numbers; we prove for almost all reals $A$, the rank of $A$ is $\omega_1^A$. These results strengthen the analogy between the pre-well-ordering of natural theories by proof-theoretic strength in proof theory and the pre-well-ordering of reals under descriptive complexity.

Part III contains reflections on foundational issues. The main foundational applications of ordinal analysis to date are in Hilbert's program and modifications thereof. Instead, I emphasize the \emph{explanatory} value of ordinal-theoretic consistency proofs over their \emph{justificatory} value. Whether, for instance, Gentzen's consistency proof convinces us \emph{that} arithmetic is consistent, it explains \emph{why} arithmetic is consistent. On this basis, I argue against certain restrictive norms on mathematical practice. For instance, I argue against the norm that consistency proofs ought to be carried out using only constructive methods. Though this restriction is reasonable if one is attempting to convince a constructivist skeptic, it loses force when one instead seeks a combinatorial explanation of a theory's consistency.

We prove various results about the complexity of countable structures, both computable and arbitrary.

We begin by investigating descriptions of countable structures in the infinitary logic L_ω1ω. Given a countable structure A, we can find a sentence ϕ, a Scott sentence for A, which describes A up to isomorphism in the sense that A is the unique countable model of ϕ. We can assign a complexity, the Scott rank of A, to A; this is the quantifier complexity of the simplest Scott sentence. We investigate the Scott ranks of the models of a theory; we produce several new computable models of high Scott rank; we construct a computable group with no d-Σ₂ Scott sentence; and we produce a first-order theory of Ulm type.

Next, we look at computable structures on a cone. If A is a natural structure—by which we mean an informal notion of a structure that might show up in the normal course of mathematics, and which was not constructed explicitly as a computability-theoretic counterexample—then arguments about A will generally relativize. So we can study natural structures by studying arbitrary structures relativized "on a cone". This gives us a way of making precise statements about the imprecise notion of a natural structure. We give a complete classification of the degrees of categoricity on a cone, and prove a number of results about degree spectra of relation on a cone.

Third, we investigate the deep connections between infinitary interpretations and functors. An interpretation of one structure A in another structure B induces a functor which produces copies of A from copies of B. Moreover, the interpretation induces a homomorphism from the automorphism group of B to the automorphism group of A. We show that this reverses: given a functor from B to A, or a homomorphism from the automorphism group of B to A, we can recover an interpretation. We consider the effective version of this, as well as the corresponding results for bi-interpretations.

Finally, we look at a number of different algebraic structures. We study the effectivization of extending automorphisms of fields to their algebraic closure, extending valuations to a field extension, and embedding valued fields into algebraically closed valued fields. We give a metatheorem for finding computable copies of various algebraic structures with an independence relation, such as differentially closed fields with δ-independence, with a computable basis. We show that there is a computable left-orderable group with no computable copy with a computable ordering.