Recursively saturated and rather classless

A mathematics blog by Kameryn Williams

Category: Transfinite Recursion

The structure of models of second-order set theories

This is my PhD dissertation.

[PDF] [arXiv] [CUNY Academic Works (forthcoming)] [bibTeX]

Abstract. This dissertation is a contribution to the project of second-order set theory, which has seen a revival in recent years. The approach is to understand second-order set theory by studying the structure of models of second-order set theories. The main results are the following, organized by chapter. First, I investigate the poset of T-realizations of a fixed countable model of ZFC, where T is a reasonable second-order set theory such as GBC or KM, showing that it has a rich structure. In particular, every countable partial order embeds into this structure. Moreover, we can arrange so that these embedding preserve the existence/nonexistence of upper bounds, at least for finite partial orders. Second I generalize some constructions of Marek and Mostowski from KM to weaker theories. They showed that every model of KM plus the Class Collection schema “unrolls” to a model of ZFC with a largest cardinal. I calculate the theories of the unrolling for a variety of second-order set theories, going as weak as GBC + ETR. I also show that being T-realizable goes down to submodels for a broad selection of second-order set theories T. Third, I show that there is a hierarchy of transfinite recursion principles ranging in strength from GBC to KM. This hierarchy is ordered first by the complexity of the properties allowed in the recursions and second by the allowed heights of the recursions. Fourth, I investigate the question of which second-order set theories have least models. I show that strong theories—such as KM or \Pi^1_1-CA—do not have least transitive models, while weaker theories—from GBC to GBC + ETROrd—do have least transitive models.

fig4.4


Bibtex

@PHDTHESIS{Williams:dissertation,
author = {Kameryn J Williams},
title = {The structure of models of second-order set theories},
school = {The Graduate Center, The City University of New York},
year = {2018},
eprint = {1804.09526},
archivePrefix ={arXiv},
primaryClass = {math.LO},
url = {https://kamerynblog.wordpress.com/2018/04/25/the-structure-of-models-of-second-order-set-theories},
}

Advertisements

Beta-models of ATR_0

This will be a talk for the CUNY MoPA seminar on Wednesday, November 29.

Recall that \mathsf{ATR}_0 is the subsystem of second-order arithmetic axiomatized by (basic axioms plus) arithmetical comprehension plus arithmetical transfinite recursion. Also recall that a beta-model of arithmetic is a model (\omega,\mathcal{X}) of second-order arithmetic which is correct about which of its set relations are well-founded. I will present a theorem, due to Simpson, that the intersection of all beta-models of \mathsf{ATR}_0 is the omega-model whose sets are the hyperarithmetical sets.

The exact strength of the class forcing theorem

This will be a talk at CUNY Set Theory Seminar on Friday, October 13.

Slides.

Gödel–Bernays set theory \mathsf{GBC} proves that sufficiently nice (i.e. pretame) class forcings satisfy the forcing theorem—that is, these forcing relations \mathbb P admit forcing relations \Vdash_\mathbb{P} satisfying the recursive definition of the forcing relation. It follows that statements true in the corresponding forcing extensions are forced and forced statements are true. But there are class forcings for which having their forcing relation exceeds \mathsf{GBC} in consistency strength. So \mathsf{GBC} does not prove the forcing theorem for all class forcings. This is in contrast to the well-known case of set forcing, where \mathsf{ZFC} proves the forcing theorem for all set forcings. On the other hand, stronger second-order set theories such as Kelley–Morse set theory \mathsf{KM} prove the forcing theorem for all class forcings, providing an upper bound. What is the exact strength of the class forcing theorem?

I will show that, over \mathsf{GBC}, the forcing theorem for all class forcings is equivalent to \mathsf{ETR}_\mathrm{Ord} the principle of elementary transfinite recursion for recursions of height \mathrm{Ord}. This is equivalent to the existence of \mathrm{Ord}-iterated truth predicates for first-order truth relative to any class parameter; which is in turn equivalent to the existence of truth predicates for the infinitary languages \mathcal L_{\mathrm{Ord}, \omega}(\in, A) allowing any class parameter A. This situates the class forcing theorem precisely in the hierarchy of theories between \mathsf{GBC} and \mathsf{KM}.

This is joint work with Victoria Gitman, Joel Hamkins, Peter Holy, and Philipp Schlict from our paper of the same name.

ClassForcing

The exact strength of the class forcing theorem

This will be a talk at the Kurt Gödel Research Center Research Seminar on Tuesday, September 26. See also their page for the talk. Slides here.

Gödel–Bernays set theory \mathsf{GBC} proves that sufficiently nice (i.e. pretame) class forcings satisfy the forcing theorem—that is, these forcing relations \mathbb P admit forcing relations \Vdash_\mathbb{P} satisfying the recursive definition of the forcing relation. It follows that statements true in the corresponding forcing extensions are forced and forced statements are true. But there are class forcings for which having their forcing relation exceeds \mathsf{GBC} in consistency strength. So \mathsf{GBC} does not prove the forcing theorem for all class forcings. This is in contrast to the well-known case of set forcing, where \mathsf{ZFC} proves the forcing theorem for all set forcings. On the other hand, stronger second-order set theories such as Kelley–Morse set theory \mathsf{KM} prove the forcing theorem for all class forcings, providing an upper bound. What is the exact strength of the class forcing theorem?

I will show that, over \mathsf{GBC}, the forcing theorem for all class forcings is equivalent to \mathsf{ETR}_\mathrm{Ord} the principle of elementary transfinite recursion for recursions of height \mathrm{Ord}. This is equivalent to the existence of \mathrm{Ord}-iterated truth predicates for first-order truth relative to any class parameter; which is in turn equivalent to the existence of truth predicates for the infinitary languages \mathcal L_{\mathrm{Ord}, \omega}(\in, A) allowing any class parameter A. This situates the class forcing theorem precisely in the hierarchy of theories between \mathsf{GBC} and \mathsf{KM}.

This is joint work with Victoria Gitman, Joel Hamkins, Peter Holy, and Philipp Schlict from our paper of the same name.

ClassForcing

Least models of second-order set theories

K. Williams “Least models of second-order set theories” (under review) arXiv PDF bibTeX

Abstract The main theorems of this paper are (1) there is no least transitive model of Kelley–Morse set theory \mathsf{KM} and (2) there is a least \beta-model—that is, a transitive model which is correct about which of its classes are well-founded—of Gödel–Bernays set theory \mathsf{GBC} + Elementary Transfinite Recursion. Along the way I characterize when a countable model of \mathsf{ZFC} has a least \mathsf{GBC}-realization and show that no countable model of \mathsf{ZFC} has a least \mathsf{KM}-realization. I also show that fragments of Elementary Transfinite Recursion have least \beta-models and, for sufficiently weak fragments, least transitive models. These fragments can be separated from each other and from the full principle of Elementary Transfinite Recursion by consistency strength.
The main question left unanswered by this article is whether there is a least transitive model of \mathsf{GBC} + Elementary Transfinite Recursion.

Every set theorist knows there is a least transitive model of \mathsf{ZFC}. What if we want to ask the same question about second-order set theories? Which second-order set theories, if any, have least transitive models? The answer for \mathsf{GBC} follows immediately from the existence of a least transitive model of \mathsf{ZFC}: the least transitive model of \mathsf{GBC} is (L_\alpha, \mathrm{Def}(L_\alpha)) where L_\alpha is the least transitive model of \mathsf{ZFC}. (Indeed, Shepherdson formulated his original argument in terms of \mathsf{GB} (i.e. without Global Choice), rather than in terms of \mathsf{ZFC}.) But this easy argument won’t work for second-order set theories that assert the existence of more classes.

Indeed, no argument will work for sufficiently strong second-order set theories. Take \mathsf{KM}. Allowing for the existence of impredicatively-defined classes means that models of \mathsf{KM} have enough “meta-ordinals” that tools from admissible set theory can be applied. Starting from a model of \mathsf{KM} we can build another model of \mathsf{KM} whose first-order part is the same but whose second-order part sits off to the side, so to speak.

friedman-things

So no (countable) model of \mathsf{ZFC} has a least \mathsf{KM}-realization and thus there cannot be a smallest transitive model of \mathsf{KM}. (Of course, see the actual paper for more than a brief sketch of the argument.)

But \mathsf{KM} is much stronger than \mathsf{GBC} and there are natural theories in the middle. What about those? For \Pi^1_k\text{-}\mathsf{CA} more or less the same argument as the \mathsf{KM} case goes through, getting that they don’t have least transitive models. (But I don’t give a proof of such in this paper; see my forthcoming dissertation for full details.)

So let’s go lower, to the theory \mathsf{ETR}, which is \mathsf{GBC} augmented with the principle of Elementary Transfinite Recursion. Then \mathsf{ETR} is stronger than \mathsf{GBC} because, say, we can construct the Tarskian satisfaction class for first-order formulae via a class recursion of height \omega. But \mathsf{ETR} is strictly weaker than \Pi^1_1\text{-}\mathsf{CA}.

I don’t actually know whether there is a least transitive model of \mathsf{ETR}. (This is the main open question from my paper.) However, I do show that there is a least \beta-model of \mathsf{ETR}. As well, sufficiently weak fragments of \mathsf{ETR}—such as \mathsf{ETR}_{\mathrm{Ord}} which only asserts that elementary transfinite recursions of height \le \mathrm{Ord} have solutions—do have least transitive models. Combined with the results from my joint paper with Gitman, Hamkins, Holy, and Schlict this gives that there is a smallest transitive model of \mathsf{GBC} which satisfies the forcing theorem for all class forcings. I think that’s neat.


Bibtex

@ARTICLE{Williams:least-models,
author = {Kameryn Williams},
title = {Least models of second-order set theories},
journal = {},
year = {},
volume = {},
number = {},
pages = {},
month = {},
note = {manuscript under review},
abstract = {},
keywords = {},
source = {},
doi = {},
eprint = {1709.03955},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {https://kamerynblog.wordpress.com/2017/09/12/least-models-of-second-order-set-theories/},
}