Scott analysis
Foundational theories and related topics

It is a fact about mathematical practice that some theories are treated algebraically—that is, with the aim of describing all their models—while others are approached non-algebraically, with the aim of describing a specific (intended) model. After reviewing selected philosophical and mathematical approaches to the problem of individuating intended structures, I will focus on the notion of the simplest model property, which I introduced to investigate whether the problem of individuation can be understood as optimization of descriptive complexity (in particular, Scott rank) of models of a given theory. As an example, I will consider the interaction between the simplest model property and weak set theories, which can be viewed as aiming to describe the canonical model of hereditarily finite sets. The talk will cover some preliminary/partial results in this direction.

The chain-antichain principle (CAC) says that for every partial order on ℕ there exists an infinite chain or antichain with respect to this order. It is one of the well-known consequences of Ramsey's theorem for pairs and two colours (RT²₂) that are studied extensively in reverse mathematics.

Recently, the strength of RT²₂, CAC, and a few related combinatorial principles was studied over the weak base theory RCA^*₀, which is obtained from the usual base theory for reverse mathematics, RCA₀, by replacing the Σ⁰₁-induction scheme with Δ⁰₁-induction. Both RT²₂ and CAC are Π⁰₃-conservative over RCA^*₀. Such conservation results usually lead to questions about lengths of proofs. Kołodziejczyk, Wong and Yokoyama showed that RT²₂ has non-elementary speedup over RCA^*₀ for proofs of Σ₁ sentences. We show that the behaviour of CAC is the opposite: it can be polynomially simulated by RCA^*₀ with respect to Π⁰₃ sentences. For the proof, we use the method of forcing interpretations and syntactically simulate a two-step model-theoretic argument, which involves construction of a restricted definable ultrapower, followed by a generic cut satisfying CAC.

In the setting of generalized descriptive set theory at singular cardinals of countable cofinality, we code coarse mice, in particular those from the Dodd-Jensen core model. We then derive a lower bound on the consistency strength for every (lightface) λ-Π¹₁ subset of the generalized Cantor space having the λ-perfect set property.

Intuitively speaking, a theory is sequential if it can uniformly encode finite sequences of arbitrary objects from its domain as its objects. Virtually any theory with foundational flavour is sequential (with one prominent exception: as shown by Visser, Robinson's Arithmetic Q is not). Sequential theories include all extensions of PA⁻, such as PA and its canonical fragments IΣ_n, as well as every subsystem of Second Order Arithmetic studied in Reverse Mathematics.

During the talk we outline a fairly detailed sketch of a recent result that for every sequential theory T, the isomorphism problem for the models of T is Borel complete in the sense of Friedman–Stanley. In particular, for a fixed sequential theory T, there is a Borel function F from the class of countable linear orders to the class of countable models of T such that for all linear orders L, L′: L ≃ L′ ⟺ F(L) ≃ F(L′). Our proof rests crucially on an earlier result due to Kossak and Coskey, and simultaneously generalises results for completions of PA and for T = ZFC.

Trees are fundamental combinatorial objects, with important applications in logic and computer science. Kruskal proved that finite trees form a well-quasi-order under homeomorphic embeddings. In fact, this remains true even when we consider trees with labels in an arbitrary well-quasi-order. Kruskal's theorem is of particular interest in light of the unprovability results obtained by Friedman, one of the earliest successes of the reverse mathematics program. Moreover, Nash-Williams introduced a natural strengthening of the notion of well-quasi-order, called better-quasi-order, and used it to extend Kruskal's result to infinite trees. We work in reverse mathematics and discuss the strength of certain restricted versions of Nash-Williams' better-quasi-ordering theorem for trees with respect to the usual 'big five' systems of second-order arithmetic, as well as to more recently introduced systems of partial impredicativity.

Scott analysis of Peano Arithmetic (PA) has already given us insight into the dependence of the complexity of the structure on various model- or computability-theoretic properties such as homogeneity, recursive saturation and being finitely generated. Methods used so far oftenmost exploit PA in its full strength, deeming them hard to adjust to different settings. We will take a look at fragments of PA in which induction and collection schemes – canonically describing PA – are restricted to a smaller class of formulas and compare them to the already known case of PA, hoping to generalize some of the methods to other and especially much weaker theories such as IOpen, where induction is assumed to hold only for quantifier-free formulas.

During the talk we will show some results of Scott analysis of fragments of PA of the form IΣ_n or BΣ_n — induction and collection schemes restricted to Σ_n formulas. In particular we will show that theories BΣ_n + ¬IΣ_n and IΣ_n + ¬BΣ_n+1 have no models of Scott rank below n+1 and that rank n+1 is indeed achievable. We will then turn to the methods we have used and elaborate on how we can adjust them in contexts outside of the scope of arithmetical theories extending IΔ₀ + exp, or indicate the crucial use of properties of these theories.

Apart from the famous result of Solovay about the arithmetical completeness of GL, in the same paper he shows that GL.3 is the logic of transitive models of ZFC, i.e. □-formulas are interpreted by "…holds in every transitive model of ZFC". Later, Aguilera and Pakhomov produced a polymodal version of this logic GLP.3 that stratifies ZFC models by the amount of correctness they carry, i.e. "…holds in every Σ_n-correct model of ZFC". In the talk I make an overview of my recent results regarding completeness of GL.3 and GLP.3 with respect to topological spaces based on ordinals. Joint work with Juan Aguilera.