This dissertation investigates several questions concerning complexity in the context of countable Borel equivalence relations (CBERs) and topological Ramsey spaces. Chapter 2 presents relevant background material about topological Ramsey spaces. Also discussed are several examples of such spaces, including the Milliken space of strong subtrees and the Carlson–Simpson space of infinite partitions of $\omega $.

Chapter 3, which is joint work with Aristotelis Panagiotopoulos, studies CBERs on the Carlson–Simpson space. Ramsey-theoretic methods cannot distinguish CBERs beyond hyperfiniteness. More specifically, Mathias showed that every CBER on $[\omega ]^\omega $ is hyperfinite on a non-empty Ellentuck cube, and Bursics and Vidnyánszky recently extended this result to all topological Ramsey spaces. An even stronger result holds in some topological Ramsey spaces. For example, Kanovei, Sabok, and Zapletal showed that every CBER on the Milliken space of strong subtrees of $2^{<\omega }$ is smooth on a non-empty Ellentuck cube; in fact, the same holds true for any analytic equivalence relation on this space. The main result of this chapter is that every CBER on the Carlson–Simpson space is smooth on a non-empty Ellentuck cube, but that this statement fails for arbitrary analytic equivalence relations.

Chapter 4 examines the complexity of a set arising naturally from notions in topological Ramsey theory. Sabok proved that the set of codes for the $G_\delta $ Ramsey positive sets in $[\omega ]^\omega $ is $\Sigma ^1_2$-complete, and that the same holds for analytic Ramsey positive sets. A natural question is whether the same results hold in other topological Ramsey spaces. In this chapter, it is shown that the analogous sets of codes in other topological Ramsey spaces are $\Sigma ^1_2$. Moreover, additional assumptions under which these sets are also $\Sigma ^1_2$-hard, hence $\Sigma ^1_2$-complete, are identified. These additional assumptions are not too onerous, and indeed are verified in many common examples of topological Ramsey spaces.

Finally, a class of compactly graphable CBERs is exhibited in Chapter 5. Frisch, Kechris, Shinko, and Vidnyánszky introduced the study of topological realizations of CBERs, establishing many results about the topological properties of CBERs up to Borel isomorphism. One of these properties is compact graphability, that is, being expressible as the connectedness relation of a compact graph on a Polish space. Frisch, Kechris, Shinko, and Vidnyánszky proved that every aperiodic CBER that is hyperfinite or compressible has a compactly graphable realization and asked whether every aperiodic CBER has this property. The main result of this chapter is a partial positive answer to this question. In particular, the orbit equivalence relation of any continuous, free, minimal action of a countable group on the Cantor space is compactly graphable.

Clinton T. Conley (transcribed with superficial edits from Section 1.3 of the doctoral thesis written by Allison Y. Wang).

E-mail: ayw@math.ucla.edu.

This thesis investigates the inner model ${C({\texttt{aa}}^+)} $ obtained from the ${\texttt{aa}}^+ $-quantifier, which is a variant of the ${\texttt{aa}} $-quantifier of stationary logic. The intuitive meaning of the ${\texttt{aa}}^+ $-quantifier is that there is a closed unbounded set of countable subsets of the model such that a given property holds in the next admissible set built from the model and any one of the subsets in the closed unbounded set.

The research presented in the thesis belongs to the framework of extended constructibility, which is a research program that studies inner models obtained by replacing first-order logic by a stronger logic in the definition of Gödel’s constructible hierarchy. The most extensively studied model within the program has been the model ${C({\texttt{aa}})} $, obtained from stationary logic, which forms the immediate background for the research developed here.

After an introductory chapter, we give the definition of the ${\texttt{aa}}^+ $-quantifier and discuss some of the basic properties of the logic ${\mathcal{L}({\texttt{aa}}^+)} $ and the model ${C({\texttt{aa}}^+)} $. We show that the logic ${\mathcal{L}({\texttt{aa}}^+)} $ is strictly more expressive than the stationary logic ${\mathcal{L}({\texttt{aa}})} $, and that the previously known ${C({\texttt{aa}})} $-proof of the key notion of Club Determinacy from large cardinals also works for ${C({\texttt{aa}}^+)} $ with a minor modification.

The main part of the thesis consists of a development of the theory of ${\texttt{aa}}^+ $-mice and ${\texttt{aa}}^+ $-ultrapowers. We prove that the ${\texttt{aa}}^+ $-mice have the same central properties as the ${\texttt{aa}} $-mice developed earlier to investigate the model ${C({\texttt{aa}})} $. In particular, we show that one gets a level of the model ${C({\texttt{aa}}^+)} $ by forming the iterated ${\texttt{aa}}^+ $-ultrapower of length $\omega _1$ of a countable ${\texttt{aa}}^+ $-mouse. This allows us to show that ${C({\texttt{aa}}^+)} $ satisfies, assuming Club Determinacy, the combinatorial principles that have been previously shown for ${C({\texttt{aa}})} $. In particular, we show how the Continuum Hypothesis, the Ultrapower Axiom, and the Generalized Continuum Hypothesis follow from the properties of the iterated ${\texttt{aa}}^+ $-ultrapowers.

Abstract prepared by Otto Rajala. The abstract is taken directly from the thesis.

Current address: Śniadeckich 8, 00-656 Warszawa, Poland

E-mail: orajala@impan.pl

URL: http://hdl.handle.net/10138/600440

The dissertation concerns the intended interpretation of mathematical theories. Reasonably straightforward results in model theory show that the axioms of our mathematical theories fail to determine their own intended interpretation, even up to isomorphism. Quite generally, any first-order mathematical theory purporting to describe a particular subject matter will have unintended, non-isomorphic models of its axioms. These unintended interpretations satisfy not only the axioms of the theory but indeed the complete set of truths concerning the domain. As a result, axiomatic theories cannot uniquely determine their mathematical content. However, this raises a worrying question. Simply put, if the relevant axioms could not determine the subject matter of a theory, what possibly could? In the dissertation, I explore this problem. To do so, I begin in chapter one by situating the project with respect to the broader philosophical literature, and utilise some basic techniques for the construction of non-standard models to introduce the general challenge with which the dissertation is concerned. In my second chapter, I show that model-theoretic underdetermination can entail a skeptical conclusion about mathematics which presents a substantial challenge for philosophers. In doing so I explore three prominent anti-skeptical arguments, and show that they are each subject to significant structural defects. I therefore conclude that the problem of unintended interpretations remains a significant problem for the philosophy of mathematics. In the third chapter, I draw attention to an important presupposition that has been widely overlooked throughout the debate: the presupposition of classical mathematics. In doing so, I utilise theorems of intuitionistic mathematics to show that intuitionistic arithmetic and set theory do not face the same problems as their classical counterparts. As a result I argue that, contrary to received wisdom, there is a stable view which can be maintained in light of the skeptical challenge which can also be seen as providing an independent argument for intuitionism. In my final chapter, I develop a novel proposal for a purely algebraic conception of mathematics which seeks to reframe the problem of unintended interpretations as a beneficial feature of modern axiomatic systems, rather than a defect. In doing so I argue that no mathematical theory possesses only a single uniquely correct interpretation. Rather, there are a plurality of structures corresponding to our theories, each of which should be regarded as legitimate. The dissertation concludes that there is significant value to be had both mathematically and philosophically from investigating unintended interpretations, and urges further research into the intersection of philosophy and model theory.

Abstract prepared by Owain Griffin.

Current address: 350 University Hall, 230 North Oval Mall, USA.

E-mail: griffin.862@osu.edu.

URL: https://etd.ohiolink.edu/acprod/odb_etd/r/etd/search/1?clear=0,1,5,10,20,21,1001.

We recently found a kind of orbit equivalence relations, denoted by $E(G)$, which can well describe structures and properties of Polish groups from the perspective of Borel reducibility. Given a Polish group G, let $E(G)$ be the right coset equivalence relation $G^\omega /c(G)$, where $c(G)$ is the group of all convergent sequences in G. We list some main results.

Let G and H be two Polish groups. (1) G is a discrete countable group containing at least two elements iff $E(G)\sim _BE_0$; (2) G is non-archimedean iff $E(G)\le _B=^+$; (3) if H is CLI but G is not, then $E(G)\not \le _BE_H^Y$ for any Polish H-space Y; (4) if H is a non-archimedean Polish group but G is not, then $E(G)\not \le _BE_H^Y$ for any Polish H-space Y; (5) if H is TSI but G is not, then $E(G)\not \le _BE(H)$; (6) G is TSI non-archimedean iff $E(G)\leq _B E_0^\omega $ iff $E(G)\leq _B {\mathbb {R}}^\omega /c_0$; in particular, $E(G)\sim _B E_0^\omega $ iff G is TSI uncountable non-archimedean.

The notion of $\alpha $-l.m.-unbalanced Polish group for $\alpha <\omega _1$ is introduced. Let $G,H$ be Polish groups, $0<\alpha <\omega _1$. If G is $\alpha $-l.m.-unbalanced but H is not, then $E(G)\not \le _B E(H)$.

For TSI Polish groups, we proved a Pre-rigid Theorem: the existence of Borel reduction is transformed into the existence of a well-behaved continuous mapping between topological groups. As its applications, we proved several rigid theorems for locally compact Polish groups, separable Banach spaces, and separable Fréchet spaces, respectively. In particular, we obtained a complete answer for abelian connected Lie groups: for $b_0,e_0,b_1,e_1\in {\mathbb {N}}$, $E({\mathbb {R}}^{b_0}\times {\mathbb {T}}^{e_0})\le _BE({\mathbb {R}}^{b_1}\times {\mathbb {T}}^{e_1})$ iff $e_0\le e_1$ and $b_0+e_0\le b_1+e_1$. In addition, we also proved that, the partially ordered set $P(\omega )/\text {Fin}$ can be embedded into Borel equivalence relations between $E({\mathbb {R}}^n)$ and $E({\mathbb {T}}^n)$.

We study expansions of Hilbert spaces with a bounded normal operator T. We axiomatize this theory in a natural language and identify all of its completions. We prove the definability of the adjoint $T^*$ and prove quantifier elimination for every completion after adding $T^*$ to the language. We identify types with measures on the spectrum of the operator and show that the logic topology on the type space corresponds to the weak*-topology on the space of measures. We also give a precise formula for the metric on the space of $1$-types. We prove all completions are stable and characterize the stability spectrum of the theory in terms of the spectrum of the operator. We also show all completions, regardless of their spectrum, are $\omega $-stable up to perturbations.

Higman’s lemma and Kruskal’s theorem are two of the most celebrated results in the theory of well quasi-orders. In his seminal paper G. Higman obtained what is known as Higman’s lemma as a corollary of a more general theorem, dubbed here as Higman’s theorem. While the lemma deals with finite sequences over a well quasi-order, the theorem is about abstract operations of arbitrarily high arity.

J. B. Kruskal was fully aware of this broader framework: in his seminal paper, he not only applied Higman’s lemma at crucial points of his proof but also followed Higman’s proof schema. At the conclusion of the article, Kruskal noted that Higman’s theorem is a special case—restricted to trees of finite degree—of his own tree theorem. Although he provided no formal reduction, he included a glossary translating concepts between the tree and algebraic settings. The equivalence between these versions was later clarified by D. Schmidt and M. Pouzet. In this work, we revisit that equivalence to illuminate the proof-theoretical relationships between the two theorems within the base system RCA$_0$ of reverse mathematics.

Moreover, some independence results over first- and second-order theories are treated. In particular, tree-like structures, involving either Ackermannian terms or exponential expressions, are studied unveiling well-foundedness properties that are independent from Peano arithmetic and relevant fragments of second-order arithmetic.

We study the well-quasi-order (wqo) consisting of the set of finite trees with leaf labels coming from an arbitrary wqo Q, ordered by tree homomorphisms which respect the order on the labels. This is a variant of the usual Kruskal tree ordering without infima preservation. We calculate the precise maximal order types of this class of wqos as a function of the maximal order type of the labels Q. In the process, we sharpen some recent results of Friedman and Weiermann [7]. Furthermore, we show a correspondence with indecomposable transfinite sequences with finite range, over elements of the wqo Q, of length less than $\omega ^\omega $. Nash-Williams proved that arbitrary transfinite sequences with finite range are also well-quasi-ordered [17], but there are no known methods to extract bounds on the maximal order type from the proof. More concrete proofs for sequences of length less than $\alpha $ for some $\alpha < \omega ^\omega $ were given by Erdös and Rado [5]. Using the correspondence, we obtain precise bounds for the entire collection of transfinite sequences with finite range of length less than $\omega ^\omega $.

Approximation Theory uses nicely-behaved subcategories to understand entire categories, just as projective modules are used to approximate arbitrary modules in classical homological algebra. We use set-theoretic elementary submodel arguments to give new, short proofs of well-known theorems in approximation theory, sometimes with stronger results.

The thesis is thematically divided into three parts. Part I investigates the following conjecture of John Steel from “The Core Model Iterability Problem”:Conjecture(ZFC).

Let $\Omega $ be a measurable cardinal and $\mathcal {R}$ and $\mathcal {W}$ be premice such that $\mathrm {OR}^{\mathcal {R}} = \mathrm {OR}^{\mathcal {W}} = \Omega $ and both are $(0,\Omega +1)$-iterable. Then the following are equivalent$:$

1. 1. $\mathcal {W} \leq ^* \mathcal {R}$, where $\leq ^*$ denotes the mouse-order, and

2. 2. there is a club $C \subseteq \Omega $ such that for all $\alpha \in C$, if $\alpha $ is regular, then $(\alpha ^+)^{\mathcal {W}} \leq (\alpha ^+)^{\mathcal {R}}$.

Under the large cardinal assumption that there is a $(0,\omega _1+1)$-iterable and sound premouse which is a model of , we construct a counterexample to the conjecture. However, we show that under the anti-large cardinal assumption that there is no transitive model of $\mathsf {KP} + \exists \delta ("\delta \text { is Woodin}")$, the conjecture holds. In the construction of the counterexample, we show the following forcing theorem for admissible premice which seems to be of independent interest: If $M$ is a premouse which is a model of $\mathsf {KP}$ with a largest, regular, uncountable cardinal $\delta $, and $\mathbb {P} \in M$ is a forcing poset such that $M \models "\mathbb {P} \text { has the } \delta -c.c."$, and $g \subseteq \mathbb {P}$ is $M$-generic, then $M[g] \models \mathsf {KP}$.

In Part II, we adapt the $\mathrm {HOD}$-analysis of $L[x,G]$ to an admissible context. More specifically, assume that there is a Woodin cardinal and for $x \in \mathbb {R}$ let $\alpha _x$ be the least ordinal $\beta $ such that

$$\begin{align*}L_\beta[x] \models \Sigma_n\text{-}\mathsf{KP} + \exists \kappa ("\kappa \text{ is inaccessible and }\kappa^+ \text{ exists}"). \end{align*}$$

$x$

$\mathcal {M}^{n\text {-}\mathrm {ad}}$

$H \subseteq L_\alpha [x,G]$

$\mathrm {HOD}^{L[x,G]}$

$H = M_\infty [\Sigma _0]$

$M_\infty $

$\mathcal {M}^{n\text {-}\mathrm {ad}}$

$\Sigma _0$

$M_\infty [\Sigma _0]$

$M_\infty [\Sigma _0]$

$L_\alpha [x,G]$

In Part III, we investigate the consistency strength of infinitely many Woodin cardinals in a fragment of $\mathsf {KP}$. More specifically, let $\mathsf{KP}^{-}$ be the theory obtained from $\mathsf {KP}$ by replacing the axiom scheme of class foundation with the axiom of set foundation. Let $\Pi _1\text {-}\mathsf {Foundation~at~}\omega $ be the axiom scheme of $\Pi _1\text {-}\mathsf {Foundation}$ relativized to the set $\omega $. We show that if there is a model of $\mathsf{KP}^{-} + \Pi _1\text {-}\mathsf {Foundation~at~}\omega $ which models

$$\begin{align*}"V_\lambda \text{ exists, and } \lambda \text{ is a limit of Woodin cardinals}", \end{align*}$$

$\mathsf{KP}^{-} + \Pi _1\text {-}\mathsf {Foundation~at~}\omega $

1. 1. $"\mathcal {P}(V_\omega ) \text { exists}"$,

2. 2. $V = L(\mathcal {P}(V_\omega ))$,

3. 3. “all length $\omega $ games on $\omega $ are determined”, that is, $\mathsf {AD}$, and

4. 4. “$\exists \alpha \in \mathrm {OR}$ such that $(L_\alpha (\mathcal {P}(V_\omega )),\mathcal {P}(V_\omega )) \prec _{\Sigma _1} (L(\mathcal {P}(V_\omega )),\mathcal {P}(V_\omega ))"$.

The construction of the determinacy model resembles Woodin’s derived model construction. However, it is carried out “in the codes”.

Abstract prepared by Jan Kruschewski

Current address: Institut für Diskrete Mathematik und Geometrie,

TU Wien, Wiedner Hauptstrasse 8-10, Austria.

E-mail: jan.kruschewski@tuwien.ac.at.

We investigate the relationship between various versions of Ramsey’s theorem and bounding schemes in a model $\mathcal {N}$ of a fragment of arithmetic $F$. Our primary objective is to recast and extend the seminal results of Hirst [15] (see Theorem 1) through the modern lens of Weihrauch reducibility. By extracting explicit Weihrauch reductions from classical proofs, we expose the uniform computational content underlying these combinatorial principles, yielding a deeper and more refined understanding of their reverse mathematical strength.

Our results, informally stated in our terminology and established inside $\mathcal {N}$, are as follows: The following are equivalent: $\mathrm {B}\Sigma ^0_2$, the statement that the finite union of finite c.e. sets is finite, and the Infinite Pigeonhole Principle (see Theorem 3). We also discuss the Weihrauch relations between these logically equivalent principles (see Section 4). The Infinite Pigeonhole Principle is Weihrauch reducible to $\mathrm {RT}^2_2$ (see Theorem 4). There is also another principle logically equivalent to $\mathrm {B}\Sigma ^0_2$ which is Weihrauch reducible to $\mathrm {SRT}^2_2$ (see Theorem 5). We show that there is a principle which is equivalent to $\mathrm {B}\Sigma ^0_3$ (see Theorem 6) and Weihrauch reducible to $\mathrm {SRT}^2_{<\infty }$ (Theorem 7). We discuss some equivalences with $\mathrm {B}\Sigma ^0_{n}$ (see Section 6.1) and end with a problem Weihrauch reducible to $\mathrm {RT}^{n+1}_{2}$ (Section 6.2).

Since we work within the model $\mathcal {N}$, many standard definitions must be adjusted. Due to the expository nature of this article, these definitions are introduced throughout the text as needed. Reading the article from start to finish will provide a better understanding of the ideas involved than focusing only on individual theorems.

This thesis investigates combinatorial principles from order theory and Ramsey theory with a focus on foundational aspects within the framework of reverse mathematics and computability theory. The first part focuses on order dimension theory, a classical topic at the intersection of order theory and combinatorics. Intuitively, the dimension measures how “far” a poset is from being linearly ordered. We are interested in statements that give an upper bound to the dimension of a poset in terms of the dimension of its subposets, obtained by removing one or more points. We analyze these bounding theorems, calibrating their logical strength within subsystems of second-order arithmetic. The second part examines the notion of strong indivisibility, a particular Ramsey-like property. We focus on countable structures, with particular emphasis on Cameron’s classification theorem of strongly indivisible graphs. We study this classification from the perspectives of reverse mathematics and computable combinatorics, investigating the role of induction axioms and effective constructions. In the final part, we study a very general finite Ramsey theorem, where both the sets being colored and the homogeneous set must satisfy some largeness notion. Historically, largeness notions were associated with countable ordinals and systems of fundamental sequences. To extend this approach, we develop a more flexible framework using blocks and barriers. Since the complexity of barriers can be measured by countable ordinals, we define and study Ramsey ordinals, a generalization of the well-known Ramsey numbers of classical finite Ramsey theory.

Andrea Volpi

E-mail: andreavolpi207801@gmail.com

URL: https://andreasdfghj.github.io/andreavolpi/PhD_Thesis.pdf

The abstract was taken directly from the thesis.

In this article, we deal with the classification complexity of continuous (Devaney) chaotic systems in dimensions $0,1,$ and $\infty $ using the framework of invariant descriptive set theory. We identify the complexity in dimensions $0$ and $\infty $, while in dimension $1$ we get some partial results.

More precisely, we prove the topological conjugacy relation of invertible chaotic systems on the Hilbert cube (resp. on all compact metric spaces) has the same complexity as (i.e., is Borel bireducible with) the universal orbit relation induced by a Polish group. As a consequence, this answers a recent question asked by L. Ding. We also prove that the topological conjugacy relation of invertible chaotic systems on the Cantor space has the same complexity as the universal relation induced by the group $S_\infty $. This answers a recent question by M. Foreman. Some non-trivial bounds on the classification complexity of chaotic systems on the interval and on the circle are also obtained. Namely, the lower bound is the Vitali equivalence relation, and the upper bound is the equality of countable sets of reals. This especially implies that the relation is Borel. However, the exact complexity remains unknown.

In The Emperor’s New Mind [7], Roger Penrose proves a variant of the halting problem, and uses it to argue that humans have cognitive capacities beyond the computable. In this short note, I explicate his argument, and show how it fails, via a corollary of his result. My response to Penrose is in fact of a kind with a number of prior responses: he assumes human powers, that (as the corollary shows) no computer could have. However, as far as I am aware, no one has previously addressed this specific form of the argument, in the direct way that I will.

We introduce finite support iterations of symmetric systems, and use them to provide a strongly modernized proof of David Pincus’ classical result that the axiom of dependent choice is independent over $\operatorname {\mathrm {ZF}}$ with the ordering principle together with a failure of the axiom of choice.

This article examines the results of [6] in a purely tree-theoretic context. We show how this rephrased Chase–Freitag Lemma is sufficient to prove the Sauer–Shelah and Bhaskar Lemmas. We also use this approach to expand these two lemmas to the context of arbitrary finite label sets.