Recursively saturated and rather classless

2017 Sep 25

The exact strength of the class forcing theorem

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

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

Leave a comment

2017 Sep 15

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.

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

ClassForcing

Leave a comment

2017 Sep 14

On the length of iterated full satisfaction classes

This will be a talk at the Warsaw Workshop on Formal Truth Theories on 2017 Sept 29.

In second-order arithmetic, the principle of arithmetical transfinite recursion $\mathsf{ATR}$ asserts that every arithmetical recursive definition iterated transfinitely has a solution. One particular recursive definition of interest is Tarski’s definition of a truth predicate. This definition is carried out over a well-founded tree of rank $\omega$ . We can go further, defining truth about truth via an arithmetical recursion of rank $\omega + \omega$ , truth about truth about truth via an arithmetical recursion of rank $\omega \cdot 3$ , and so on. In general, $\mathsf{ATR}$ implies the existence of an iterated truth predicate of length $\alpha$ for any ordinal $\alpha$ , by way of a recursion over a tree of rank $\omega \cdot \alpha$ .

Consider now a nonstandard model $(M,\mathcal X)$ of $\mathsf{ATR}_0$ (= $\mathsf{ACA}_0 + \mathsf{ATR}$ ). Since $M$ is nonstandard $\mathcal X$ cannot contain the real truth predicate for $M$ , as from it $(M,\mathcal X)$ could define the standard cut of $M$ . Instead, the object which $(M,\mathcal X)$ thinks is the truth predicate for $M$ is an inductive full satisfaction class. This full satisfaction class is not confined to the real formulae as seen from outside, but also decides the truth or falsity of all formulae (in $M$ ) of nonstandard length. More generally, for any $\Gamma \in \mathcal X$ which $(M,\mathcal X)$ thinks is a well-order, $\mathcal X$ contains an inductive $\Gamma$ -iterated full satisfaction class.

$(M,\mathcal X)$ thinks that its full satisfaction class is {\em the} unique truth predicate for $M$ . Given two would-be truth predicates $(M,\mathcal X)$ can inductively show that they agree at each level and thus are the same. Similarly, $(M,\mathcal X)$ thinks its $\Gamma$ -iterated full satisfaction class is the unique $\Gamma$ -iterated truth predicate.

Externally to $(M,\mathcal X)$ , however, we know that full satisfaction classes, not even inductive full satisfaction classes, have to be unique. Indeed, as Krajewski showed, no countable (nonstandard) $M$ has a unique inductive full satisfaction class. Analogous questions can be asked about iterated full satisfaction classes. It is easy to see they will not be unique for countable models; if $S$ is an inductive full satisfaction class for countable $M$ then a version of Krajewski’s proof applies to $(M,S)$ to show that $M$ admits continuum many $2$ -iterated full satisfaction classes which extend $S$ . (With some mild assumptions on $M$ and $S$ we can get continuum many inductive $2$ -iterated full satisfaction classes extending $S$ .)

Uniqueness is out of the question, but we might hope some invariant can be found. If $S$ is an inductive full satisfaction class for $M$ , we can possibly extend it to an inductive $2$ -iterated full satisfaction class, then an inductive $3$ -iterated full satisfaction class, and so on until we reach a point that the iterated full satisfaction class is no longer inductive. If $S$ and $S'$ are inductive full satisfaction classes for $M$ , is the length we can iterate them the same? For that matter, is this length well-defined?

The answer to both questions is no.

Theorem: Suppose that countable nonstandard $M \models \mathsf{PA}$ satisfies the $\mathcal L_{\mathsf{PA}}$ -consequences of $\mathsf{PA}$ + “there is an inductive $2$ -iterated truth predicate”. If $M$ admits an inductive full satisfaction class, then there are $S$ and $S'$ inductive full satisfaction classes for $M$ so that $S$ can be iterated one step further to get an inductive $2$ -iterated full satisfaction class while $S'$ cannot.

More generally, the iteration length can be anything at all.

Consider countable nonstandard $M \models \mathsf{PA}$ and $a < b \in M$ . Suppose that $M$ satisfies the $\mathcal L_\mathsf{PA}$ -consequences of $\mathsf{PA}$ + “there is an inductive $b$ -iterated truth predicate”. Then, if $M$ admits an inductive $a$ -iterated truth predicate, there are $S_a$ and $S_a'$ inductive $a$ -iterated full satisfaction classes for $M$ so that $S_a$ can be iterated one step further to an inductive $(a+1)$ -iterated full satisfaction class while $S_a'$ cannot.

My original motivation for investigating these questions was in the context of models of set theory, where similar results apply. Suppose $M \models \mathsf{ZF}$ is countable and $\omega$ -nonstandard and satisfies the $\mathcal L_\mathsf{ZF}$ -consequences of $\mathsf{ZF}$ + “there is a strongly amenable $2$ -iterated truth predicate”. (Being strongly amenable is the set theoretic analogue of being inductive.) Then, if $M$ admits a strongly amenable full satisfaction class, there are $S$ and $S'$ strongly amenable full satisfaction classes for $M$ so that $S$ can be extended to a strongly amenable $2$ -iterated full satisfaction class while $S'$ cannot. Similar to the arithmetic case, this generalizes to longer iteration lengths.

As a consequence of this, plus the fact that having solutions to any transfinite recursion is equivalent to having solutions for the recursions to construct iterated truth predicates, strongly separating weak fragments of $\mathsf{ETR}$ is only possible with $\omega$ -standard models. Here, $\mathsf{ETR}$ (Elementary Transfinite Recursion) is a set theoretic analogue of $\mathsf{ATR}$ , introduced by Fujimoto. Say that $M \models \mathsf{ZF}$ strongly separates second-order set theories $T$ and $S$ if $M$ satisfies the first-order consequences of $S$ and of $T$ and there is $\mathcal T \subseteq \mathcal P(M)$ so that $(M,\mathcal T) \models T$ but no $\mathcal S \subseteq \mathcal P(M)$ so that $(M,\mathcal S) \models S$ . Intuitively, $M$ strongly separates $S$ and $T$ if $M$ can be made a model of $S$ but cannot be made a model of $T$ , and this is due to something inherently second-order rather than due to some first-order property of $M$ .

For an ordinal $\alpha$ , let $\mathsf{ETR}_\alpha$ denote the principle that elementary transfinite recursions of rank $\le \alpha$ have solutions. If $\beta \gg \alpha$ then $\mathsf{ETR}_\beta$ and $\mathsf{ETR}_\alpha$ can be separated, simply because $\mathsf{ETR}_\beta$ implies $\mathrm{Con}(\mathsf{ETR}_\alpha)$ (over Gödel–Bernays set theory). This separation can be witnessed by an $\omega$ -nonstandard model. However, if countable $M$ strongly separates $\mathsf{ETR}_\beta$ and $\mathsf{ETR}_\alpha$ then $M$ must be $\omega$ -standard. Indeed, $\mathsf{ETR}_\beta$ and $\mathsf{ETR}_\alpha$ are strongly separated by a transitive model of $\mathsf{ZF}$ .

No such phenomenon occurs in arithmetic, as there is only one standard model of arithmetic. We cannot strongly separate the existence of iterated truth predicates of different length with countable models.

Leave a comment

2017 Sep 12

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/}, }

Leave a comment

2017 Jul 13

The exact strength of the class forcing theorem

V. Gitman, J. D. Hamkins, P. Holy, P. Schlicht, and K. Williams, “The exact strength of the class forcing theorem”. (under review) arXiv bibTeX

Abstract The class forcing theorem, which asserts that every class forcing notion $\mathbb P$ admits a forcing relation $\Vdash_{\mathbb P}$ , that is, a relation satisfying the forcing relation recursion—it follows that statements true in the corresponding forcing extensions are forced and forced statements are true—is equivalent over Gödel-Bernays set theory $\mathsf{GBC}$ to the principle of elementary transfinite recursion $\mathsf{ETR}_{\mathrm{Ord}}$ for class recursions of length $\mathrm{Ord}$ . It is also equivalent to the existence of truth predicates for the infinitary languages $\mathcal{L}_{\mathrm{Ord},\omega}(\in,A)$ , allowing any class parameter $A$ ; to the existence of truth predicates for the language $\mathcal{L}_{\mathrm{Ord},\mathrm{Ord}}(\in,A)$ ; to the existence of $\mathrm{Ord}$ -iterated truth predicates for first-order set theory $\mathcal{L}_{\omega,\omega}(\in,A)$ ; to the assertion that every separative class partial order $\mathbb P$ has a set-complete class Boolean completion; to a class-join separation principle; and to the principle of determinacy for clopen class games of rank at most $\mathrm{Ord}+1$ . Unlike set forcing, if every class forcing notion $\mathbb P$ has a forcing relation merely for atomic formulas, then every such $\mathbb P$ has a uniform forcing relation applicable simultaneously to all formulas. Our results situate the class forcing theorem in the rich hierarchy of theories between $\mathsf{GBC}$ and Kelley-Morse set theory $\mathsf{KM}$ .

We shall characterize the exact strength of the class forcing theorem, which asserts that every class forcing notion $\mathbb{P}$ has a corresponding forcing relation $\Vdash_\mathbb{P}$ , a relation satisfying the forcing relation recursion. When there is such a forcing relation, then statements true in any corresponding forcing extension are forced and forced statements are true in those extensions.

Unlike set forcing, for which one may prove in $\mathsf{ZFC}$ that every set forcing notion has corresponding forcing relations, with class forcing it is consistent with Gödel-Bernays set theory $\mathsf{GBC}$ that there is a proper class forcing notion lacking a corresponding forcing relation, even merely for the atomic formulas. For certain forcing notions, the existence of an atomic forcing relation implies $\mathrm{Con}(\mathsf{ZFC})$ and much more, and so the consistency strength of the class forcing theorem strictly exceeds $\mathsf{GBC}$ , if this theory is consistent. Nevertheless, the class forcing theorem is provable in stronger theories, such as Kelley-Morse set theory. What is the exact strength of the class forcing theorem?

Our project here is to identify the strength of the class forcing theorem by situating it in the rich hierarchy of theories between $\mathsf{GBC}$ and $\mathsf{KM}$ . It turns out that the class forcing theorem is equivalent over $\mathsf{GBC}$ to an attractive collection of several other natural set-theoretic assertions; it is a robust axiomatic principle.

The main theorem is naturally part of the emerging subject we call the reverse mathematics of second-order set theory, a higher analogue of the perhaps more familiar reverse mathematics of second-order arithmetic. In this new research area, we are concerned with the hierarchy of second-order set theories between $\mathsf{GBC}$ and $\mathsf{KM}$ and beyond, analyzing the strength of various assertions in second-order set theory, such as the principle $\mathsf{ETR}$ of elementary transfinite recursion, the principle of $\Pi^1_1$ -comprehension or the principle of determinacy for clopen class games. We fit these set-theoretic principles into the hierarchy of theories over the base theory $\mathsf{GBC}$ . The main theorem of this article does exactly this with the class forcing theorem by finding its exact strength in relation to nearby theories in this hierarchy.

Main Theorem

The following are equivalent over Gödel-Bernays set theory.

The atomic class forcing theorem: every class forcing notion admits forcing relations for atomic formulae $p\Vdash\sigma=\tau$ and $p\Vdash\sigma\in\tau.$

The class forcing theorem schema: for each first-order formula $\varphi$ in the forcing language, with finitely many class names $\dot \Gamma_i$ , there is a forcing relation applicable to this formula and its subformulae $p\Vdash\varphi(\vec \tau,\dot\Gamma_0,\ldots,\dot\Gamma_m).$

The uniform first-order class forcing theorem: every class forcing notion $\mathbb{P}$ admits a uniform forcing relation $p\Vdash\varphi(\vec \tau,\dot\Gamma_0,\ldots,\dot\Gamma_m)$ applicable to all assertions $\varphi\in\mathcal{L}_{\omega,\omega}(\in,V^\mathbb{P},\dot\Gamma_0,\ldots,\dot\Gamma_m)$ in the first-order forcing language with finitely many class names.

The uniform infinitary class forcing theorem: every class forcing notion $\mathbb{P}$ admits a uniform forcing relation $p\Vdash\varphi(\vec \tau,\dot\Gamma_0,\ldots,\dot\Gamma_m)$ applicable to all assertions $\varphi\in\mathcal{L}_{\mathrm{Ord},\mathrm{Ord}}(\in,V^\mathbb{P},\dot\Gamma_0,\ldots,\dot\Gamma_m)$ in the infinitary forcing language with finitely many class names.

Names for truth predicates: every class forcing notion $\mathbb{P}$ has a class name $\dot T$ and a forcing relation for which $\mathbf{1}\Vdash\dot T$ is a truth-predicate for the first-order forcing language with finitely many class names $\mathcal{L}_{\omega,\omega}(\in,V^\mathbb{P},\dot\Gamma_0,\ldots,\dot\Gamma_m)$ .

Boolean completions: Every class forcing notion $\mathbb{P}$ , that is, every separative class partial order, admits a Boolean completion $\mathbb B$ , a set-complete class Boolean algebra into which $\mathbb{P}$ densely embeds.

The class-join separation principle plus $\mathsf{ETR}_{\mathrm{Ord}}$ -foundation.

For every class $A$ , there is a truth predicate for $\mathcal{L}_{\mathrm{Ord},\omega}(\in,A)$ .

For every class $A$ , there is a truth predicate for $\mathcal{L}_{\mathrm{Ord},\mathrm{Ord}}(\in,A)$ .

For every class $A$ , there is an $\mathrm{Ord}$ -iterated truth predicate for $\mathcal{L}_{\omega,\omega}(\in,A)$ .

The principle of determinacy for clopen class games of rank at most $\mathrm{Ord}+1$ .

The principle $\mathsf{ETR}_{\mathrm{Ord}}$ of elementary transfinite recursion for $\mathrm{Ord}$ -length recursions of first-order properties, using any class parameter.

Bibtex

@ARTICLE{GitmanHamkinsHolySchlichtWilliams:The-exact-strength-of-the-class-forcing-theorem, author = {Victoria Gitman and Joel David Hamkins and Peter Holy and Philipp Schlicht and Kameryn Williams}, title = {The exact strength of the class forcing theorem}, journal = {}, year = {}, volume = {}, number = {}, pages = {}, month = {}, note = {manuscript under review}, abstract = {}, keywords = {}, source = {}, doi = {}, eprint = {1707.03700}, archivePrefix = {arXiv}, primaryClass = {math.LO}, url = {http://jdh.hamkins.org/class-forcing-theorem}, }

3 Comments

2017 May 15

Weak fragments of ETR have least transitive models

Everyone who’s anyone knows the Shepardson-Cohen result that there is a least transitive model of $\mathsf{ZFC}$ . Of course, we can ask a similar question about other set theories: given a set theory $T$ , is there is a smallest transitive model of $T$ ? This question makes sense even when $T$ is a second-order theory, such as $\mathsf{GBC}$ or $\mathsf{KM}$ . A second-order model $(M,\mathcal X)$ is transitive when its set-set and set-class elementhood relations are the true $\in$ .

Theorem (Shepardson). There is a least transitive model of $\mathsf{GBC}$ .

Namely, the least transitive model of $\mathsf{GBC}$ is $(L_\alpha, L_{\alpha+1})$ , where $L_\alpha$ is the least transitive model of $\mathsf{ZFC}$ .

However, if we ask the same question for second-order set theories much stronger than $\mathsf{GBC}$ we get a negative answer.

Theorem (W., not yet published). There is no transitive model of $\mathsf{KM}$ which is contained in all transitive models of $\mathsf{KM}$ .

What happens if we weaken $\mathsf{KM}$ ? If we weaken it all the way down to $\mathsf{GBC}$ , then we get the phenomenon of minimal models. If we only weaken it a little bit, say to $\Pi^1_k\text{-}\mathsf{CA}$ for $k \ge 2$ , then we still do not have least transitive models.

What if we weaken it a lot, but not all the way down to $\mathsf{GBC}$ ? Or, starting from the other direction, how much can we strengthen $\mathsf{GBC}$ and retain the existence of minimal models?

Of course, this question must be made more precise. We can come up with silly strengthenings of $\mathsf{GBC}$ which do not have least transitive models. Consider the theory consisting of $\mathsf{GBC}$ plus the assertion that there is no definable global well-order. This theory does not have a least transitive model. (A proof of this can be found in my forthcoming paper which also has a proof for the above theorem.)

I don’t want to muck about too much with making this question precise, so for now I will wave my hands and say the word “natural”. Which natural theories intermediate between $\mathsf{GBC}$ and $\mathsf{KM}$ have minimal models?

One natural theory is $\mathsf{ETR}$ , a strengthening of $\mathsf{GBC}$ which also asserts that any transfinite recursion of a first-order property along a well-founded class relation has a solution. ( $\mathsf{ETR}$ stands for “elementary transfinite recursion”, à la the arithmetical transfinite recursion axiom from arithmetic.) This theory sits between $\mathsf{GBC}$ and $\mathsf{KM}$ in strength. It’s stronger than $\mathsf{GBC}$ as it proves, for instance, the existence of a truth predicate for first-order formulae. It’s weaker than $\mathsf{KM}$ as it is provable from $\Pi^1_1\text{-}\mathsf{CA}$ .

(For more on $\mathsf{ETR}$ , see Fujimoto’s “Classes and truth in set theory” or Gitman and Hamkins’s “Open determinacy for class games“.)

Is there a least transitive model of $\mathsf{ETR}$ ? While I do not have an answer for this, I do have an answer for some fragments of $\mathsf{ETR}$ .

We can weaker $\mathsf{ETR}$ by only requiring that we have solutions for recursions along relations of low rank. If $\alpha$ is an ordinal then $\mathsf{ETR}_\alpha$ asserts that we have solutions for recursions of rank $\le \alpha$ . Similarly, $\mathsf{ETR}_\mathrm{Ord}$ asserts that we have solutions for recursions of rank $\le \mathrm{Ord}$ .

Proposition. If $\alpha = \mathrm{Ord}$ or $\alpha < \mathrm{Ord}$ so that $\alpha = \omega \cdot \alpha$ , then there is a least transitive model of $\mathsf{ETR}_\alpha$ .

In the remainder of this post I want to prove this proposition.

The first step is to reduce $\mathsf{ETR}$ to having solutions just for certain recursions. Gitman and Hamkins showed that $\mathsf{ETR}$ is equivalent to having, for any class well-order $\Gamma$ and any class $Z$ , an iterated truth predicate along $\Gamma$ relative to the class $Z$ . (See their Theorem 8.) Staring at their proof for a few moments, one sees that they showed that whenever $\alpha = \omega \cdot \alpha$ that $\mathsf{ETR}_\alpha$ is equivalent to having iterated truth predicates along $\alpha$ relative to any class $Z$ .

Thus, we can build models of $\mathsf{ETR}_\alpha$ just by ensuring that we have enough iterated truth predicates.

Lemma. Suppose that $(M,\mathcal X) \models \mathsf{ETR}_\alpha$ is transitive and has a global well-order which is first-order definable without any class parameters, where $\alpha = \omega \cdot \alpha$ or $\alpha = \mathrm{Ord}$ . Then $M$ has a smallest $\mathsf{ETR}_\alpha$ -realization. That is, there is $\mathcal Y \subseteq \mathcal P(M)$ so that $(M,\mathcal Y) \models \mathsf{ETR}_\alpha$ and whenever $(M,\mathcal Z) \models \mathsf{ETR}_\alpha$ we have $\mathcal Y \subseteq \mathcal Z$ .

Proof: Let $\mathcal Y_0 = \mathrm{Def}(M)$ . Then, $(M, \mathcal Y_0) \models \mathsf{GBC}$ , because $M$ has a definable global well-order. However, $(M, \mathcal Y_0) \not \models \mathsf{ETR}_\alpha$ as it doesn’t even have a truth predicate. Let $T_0$ be the $\alpha$ -iterated truth predicate for $M$ relative to $\emptyset$ . Then, because $T_0 \in \mathcal X$ , if we set $\mathcal Y_1 = \mathrm{Def}(M,T_0)$ we have $(M, \mathcal Y_1) \models \mathsf{GBC}$ . We still do not have a model of $\mathsf{ETR}_\alpha$ , because $\mathcal Y_1$ doesn’t contain the $\alpha$ -iterated truth predicate relative to $T_0$ . So let $T_1$ be this truth predicate and set $\mathcal Y_2 = \mathrm{Def}(M,T_1)$ .

Keep going on in this manner. Having defined $T_{n-1}$ and $\mathcal Y_n = \mathrm{Def}(M,T_{n-1})$ , next let $T_n$ be the $\alpha$ -iterated truth predicate relative to $T_{n-1}$ and set $\mathcal Y_{n+1} = \mathrm{Def}(M,T_n)$ .

After $\omega$ steps, set $\mathcal Y = \bigcup_n \mathcal Y_n$ . We get that $(M,\mathcal Y) \models \mathsf{GBC}$ because it is the union of an increasing chain of models of $\mathsf{GBC}$ . More, for any class $A \in \mathcal Y$ we have $A \in \mathcal Y_n$ for some $n$ . Hence, $\mathcal Y_{n+1}$ will contain the $\alpha$ -iterated truth predicate for $M$ relative to $A$ . Altogether, this gives that $(M,\mathcal Y) \models \mathsf{ETR}_\alpha$ .

It remains only to see that $\mathcal Y$ is contained in every $\mathsf{ETR}_\alpha$ -realization for $M$ . But this is simply because any $(M,\mathcal Z) \models \mathsf{ETR}_\alpha$ must contain $T_n$ for every $n$ . Since $\mathcal Y$ is the smallest $\mathsf{GBC}$ -realization for $M$ containing all of the $T_n$ , it must be contained within $\mathcal Z$ . ∎

Note that we could have built $\mathcal Y$ in a single step as $\mathcal Y = \mathrm{Def}(M; \mathrm{Tr}_\Gamma : \Gamma < \alpha \cdot \omega)$ , i.e. the smallest $\mathsf{GBC}$ -realization for $M$ which contains the $\Gamma$ -iterated truth predicate for $M$ for all $\Gamma < \alpha \cdot \omega$ .

This argument needs that truth predicates for $M$ are unique, which is true for transitive $M$ . On the other hand, $\omega$ -nonstandard models can admit mutually incompatible full satisfaction classes which decide the ‘truth’ of nonstandard formulae in different ways.

This lemma gets us most of the way towards proving the above proposition.

Proof of proposition: Let $\eta$ be the least ordinal $\eta'$ so that $L_{\eta'}$ is $\mathsf{ETR}_\alpha$ -realizable. By the above lemma, $L_\eta$ has a least $\mathsf{ETR}_\alpha$ -realization $\mathcal Y$ . I claim that $(L_\eta, \mathcal Y)$ is the least transitive model of $\mathsf{ETR}_\alpha$ .

To see this, take transitive $(M,\mathcal X) \models \mathsf{ETR}_\alpha$ . There are two cases to consider. The first is if $\mathrm{Ord}^M = \eta$ . We need to see that $\mathrm{Tr}^{L_\eta}_\Gamma \in \mathcal X$ for each $\Gamma < \alpha \cdot \omega$ . This can be seen by noticing that $\mathrm{Tr}^{L_\eta}_\Gamma = \{ \phi : \phi^L \in \mathrm{Tr}^M_\Gamma \}$ and using that $\mathrm{Tr}^M_\Gamma \in \mathcal X$ whenever $\Gamma < \alpha \cdot \omega$ . The second case is if $\mathrm{Ord}^M > \eta$ . In this case, $L_\eta \in M$ , so $\mathrm{Tr}^{L_\eta}_\Gamma \in M$ for $\Gamma < \alpha \cdot \omega$ and thus $\mathcal Y \in M$ . ∎

What if we want to go beyond $\mathrm{Ord}$ ? If we are dealing with iterated truth predicates whose length is set-sized, then we have a canonical choice for its length, namely the von Neumann ordinal. But when we look at class-sized well-orders we have to contend with the fact that being well-founded is not absolute for transitive models of second-order set theories. There are transitive models of, say, $\mathsf{KM}$ or $\mathsf{ETR}$ which contain class relations the model wrongly thinks is well-founded. In such a context the above reasoning falls apart as we cannot reason externally to the model to construct iterated truth predicates. (See this previous blog post of mine for a taste of the pitfalls in considering iterated truth predicates when nonstandardness rears its head.)

However, this issue is avoided so long as we don’t try to fly too high. It was safe to reason about $\mathsf{ETR}_\mathrm{Ord}$ because $\mathrm{Ord} \times \omega$ , ordered lexicographically, is well-founded in any model of $\mathsf{GBC}$ . In general, if $\mathtt{t}$ is a term for a class well-order which is well-founded in any model of $\mathsf{GBC}$ then $\mathtt{t} \cdot \omega$ will always be well-founded and so it is meaningful to talk about the least $\eta$ so that the $\mathtt{t} \cdot n$ -iterated truth predicate is strongly amenable over $L_\eta$ (for all $n < \omega$ ). This yields minimal models of stronger fragments than $\mathsf{ETR}_\mathrm{Ord}$ —for example, $\mathsf{ETR}_{\mathrm{Ord}^2}$ or $\mathsf{ETR}_{\mathrm{Ord}^\mathrm{Ord}}$ —but how high does this get us? Can we get as high as all the first-order definable class well-orders?

Question. If $\mathsf{GBC}$ proves that the class defined by $\varphi(x,y)$ doesn’t contain an infinite descending sequence, where $\varphi$ is a first-order formula with no class parameters, then must it be that $(M,\mathcal X) \models \mathsf{GBC}$ being transitive implies $\varphi[M]$ truly is well-founded? Asked in the negative, is it possible to have a transitive model of $\mathsf{GBC}$ which wrongly believes that the class defined by $\varphi$ is well-founded?

Leave a comment

2017 Apr 04

Usually well-behaved class forcings can behave quite badly in the absence of choice

I recently stumbled upon yet another example of how class forcing can be wilder than set forcing. A class forcing can be well-behaved under the assumption that the ground model satisfies the axiom of choice while being destructive if choice fails in the ground model. (Thank you to Joel David Hamkins for a helpful conversation and for noticing the key fact I had missed.)

Proposition: There is a (definable) class forcing $\mathbb G$ so that:

If $(M,\mathcal X) \models \mathsf{GB} + \mathsf{AC}$ then forcing with $\mathbb G^M$ over $(M,\mathcal X)$ preserves $\mathsf{GB} + \mathsf{AC}$ .

If $(M,\mathcal X) \models \mathsf{GB} + \neg \mathsf{AC}$ then forcing with $\mathbb G^M$ over $(M,\mathcal X)$ does not preserve Replacement.

Proof: This forcing $\mathbb G$ is the forcing to add a global choice function. Specifically, conditions in $\mathbb G$ are functions $g : \alpha \to V$ whose domains are ordinals. The order is the natural one, namely $g \le h$ if $g$ extends $h$ . (Observe that this definition only depends upon the first-order part of our model of set theory, justifying the use of $\mathbb G^M$ above instead of $\mathbb G^{(M,\mathcal X)}$ .)

An easy density argument shows that for any $a \in V$ it is dense to get $a$ in the range of a condition. Therefore, forcing with $\mathbb G$ adds a surjection $G : \mathrm{Ord} \to V$ , from which we can easily define a global choice function. Note that this doesn’t require the ground model to satisfy any fragment of choice. While we will see that forcing with $\mathbb G$ over a model without choice kills Replacement, at least we get Global Choice as a consolation prize.

We also have that $\mathbb G$ is $\mathord<\mathrm{Ord}$ -closed, meaning that any set-sized decreasing sequence of conditions has a lower bound. Given a descending sequence $\langle g_\xi : \xi < \alpha \rangle$ of conditions from $\mathbb G$ , they have $\bigcup_{\xi < \alpha} g_\xi$ as a lower bound. Therefore, forcing with $\mathbb G$ does not add any new sets. In particular, if we start with a model of $\mathsf{AC}$ , then choice is preserved.

To finish the argument for (1) of the Proposition we need to see that $\mathsf{GB}$ is preserved. For that, I will be lazy and link to a pair [1, 2] of blog posts by Victoria Gitman who was kind enough to write up the gritty details. Let’s check, however, where Vika’s argument uses that choice holds in the ground model. Consider her argument that Replacement is preserved, i.e. that if $F$ is a class (in the forcing extension) and $a$ is a set then $F \upharpoonright a$ is a set. Vika does this by contradiction, assuming some $g$ in the generic forces $\dot F \upharpoonright \check a$ . She then finds a stronger condition which decides $\dot F \upharpoonright \check a$ , leading to the desired contradiction. To do this, she uses a well-order of $a$ . Of course, if choice fails, then we can find $a$ with no well-order, so her argument won’t work in that context.

Now let’s see (2) of the Proposition. Suppose we have a ground model set which lacks a well-order. Call this set $b$ . As we saw above, if $G$ is the generic function $\mathrm{Ord} \to V$ added by forcing with $\mathbb G$ , then every element of $b$ appears in the range of $G$ . However, it cannot be that they all appear by some bounded stage. If it were that $b \subseteq \mathrm{ran}(G \upharpoonright \alpha)$ for some ordinal $\alpha$ , then since $G \upharpoonright \alpha$ is a set from the ground model, we would have a well-order of $b$ in the ground model, contrary to our assumption.

This gives a failure of Replacement. Namely, consider the function $F$ taking $a \in V$ to the least $\alpha$ so that $G(\alpha) = a$ . By the above paragraph, we get that $F '' b \subseteq_{\mathsf{cof}} \mathrm{Ord}$ is not a set. ∎

The following corollary can be extracted from the above argument.

Corollary: In the absence of Replacement, Global Choice does not imply (Set) Choice. In other words, in the absence of Replacement the existence of a (class) function which picks elements from every nonempty set does not imply the existence of a set function which picks elements from every nonempty subset of a set $b$ .

I view this corollary as (yet more) evidence of the importance of Replacement. It is necessary to prove the ‘obvious fact’ that Global Choice implies (Set) Choice.

Leave a comment

2017 Mar 14

Non-hyperfinite countable equivalence relations

This will be a talk at the CUNY Models of Peano Arithmetic seminar on Wednesday, March 15th 2017. (Added later: the talk overspilled into the next two weeks of the MoPA seminar.)

I will present an argument of the Slaman–Steel theorem that the equivalence relation $E_\infty$ is not hyperfinite. Time permitting, I will explain a potential connection between this argument and the classification problem for models of arithmetic.

Leave a comment

2017 Mar 08

The truth about incommensurable truths: iterated truth predicates in a nonstandard world

If $M$ is a transitive model of $\mathsf{ZFC}$ , then either $M$ admits a strongly amenable iterated truth predicate of length $\mathrm{Ord}^M$ or else there is a unique $\xi < \mathrm{Ord}^M$ so that $M$ admits a strongly amenable iterated truth predicate of length $\xi$ but not one of length $\xi + 1$ . (We can go beyond $\mathrm{Ord}^M$ , but this starts getting into subtleties I want to avoid in a paragraph introducing another topic.) However, if $M$ has ill-founded $\omega$ , this is no longer the case. We can find different full satisfaction classes for $M$ which can be iterated different lengths. Indeed, any reasonable length is possible.

In my previous post, I gave an application of iterated truth predicates. The only structures dealt with there were transitive. In a transitive world, things are simple. It is easy to check that the truth predicate for a structure is unique. Since transitive structures have the correct $\omega$ , they are correct about what formulae are. Thus, the only class which can be added to a transitive structure which looks like its truth predicate is its actual truth predicate.

For nonstandard structures, things are not so nice. If we want to be able to use a class $A$ for much, then we want the expanded structure $(M,A)$ to satisfy the axiom schemata of our theory—Separation and Collection for set theory, Induction for arithmetic—with a predicate symbol added for the class. When this happens, we say that $A$ is, in the case of set theory, strongly amenable or, in the case of arithmetic, inductive.

Hereon, I’ll focus on models of arithmetic, but similar things can be said about models of set theory.

It’s easy to see that the actual truth predicate, which consists only of standard-length formulae, for a nonstandard model can never be inductive. Otherwise, apply the instance of induction for the property “there is a $\Sigma_x$ -formula in the truth predicate”, which is true for $0$ and closed under successor, to get that the model must be the standard model, a contradiction. As such, if we want to do much we need something that looks like a truth predicate but includes formulae of all length, even nonstandard length.

The notion used by model theorists of arithmetic is that of a full satisfaction class. A satisfaction class for a model $M$ is a class which satisfies the recursive Tarskian definition of truth. For instance, $\exists x \varphi(x)$ is in the satisfaction class only if there is $a \in M$ so that $\varphi(a)$ is in the satisfaction class. It is full when it decides every formula, i.e. either $\varphi$ is in the satisfaction class or else $\neg \varphi$ is in, even for nonstandard $\varphi$ .

Full satisfaction classes are well studied; see, for example, this survey article by Kotlarski. One important fact is that if a model admits a full satisfaction class (even a non-inductive one) then it must be recursively saturated. If the model is countable, then the converse also holds.

Another important fact is that full satisfaction classes are far from satisfying the uniqueness property from the standard world; Krajewski constructed countable models of arithmetic with continuum many different full satisfaction classes. Even if we restrict to inductive full satisfaction classes, things are no better. We cannot even guarantee that different full satisfaction classes give the same theory in the expanded language.

Proposition: There is $M \models \mathsf{PA}$ and $U, I \subseteq M$ inductive full satisfaction classes so that $\mathrm{Th}(M,U) \ne \mathrm{Th}(M,I)$ .

(I do not know who first observed this fact. I learned of it from Joel David Hamkins. In a joint paper with Ruizhi Yang he attributes a stronger form of this proposition to Jim Schmerl—see page 30. It is more-or-less his argument I now sketch.)

Proof sketch: Consider the theory $T$ consisting of $\mathsf{TA}$ plus the assertion, formalized as an axiom schema, that $S$ is an inductive full satisfaction class. (To be clear, the language for this theory is the language of arithmetic augmented with an extra predicate symbol for $S$ .) While the reduct of this theory to the language of arithmetic is complete, $T$ is not itself complete. This is just a version of Tarski’s theorem on the undefinability of truth. Now let $T_1$ and $T_2$ be two consistent but incompatible extensions of $T$ . By a standard resplendency argument, find a model $M \models T$ and $U, I \subseteq M$ so that $(M,U) \models T_1$ and $(M,I) \models T_2$ . ∎

It must be that $U$ and $I$ agree about standard formulae. Specifically, restricted to standard formulae they are both $\mathrm{Th}(M)$ . Their disagreement can only occur for nonstandard formulae— $I$ may think that nonstandard $\varphi$ is true while $U$ know better and think that $\varphi$ is false.

The above proposition shows, however, that if we are interested not in truth but rather in truth about truth then disagreement can happen at a standard level. Any full satisfaction class for the structure $(M,S)$ must have $\mathrm{Th}(M,S)$ as an initial segment. As such, if we want inductive iterated full satisfaction classes starting with $U$ and $I$ —say we only want to iterate one step to get $U_2$ and $I_2$ respectively—then there is no longer any guarantee that they line up if we restrict to looking only at standard truths.

We have no hope that the theory we get from iterating truth is independent of our choice of satisfaction class, but perhaps we can find other invariants. In my previous post, I showed how to construct transitive models of set theory which admit a strongly amenable iterated truth predicate of length $\xi$ but one of length $\xi + 1$ . As we’ve seen, for nonstandard models we have a choice of satisfaction class. But we might hope that how far out we can iterate a satisfaction class (where we have to make a choice at each level how to proceed) is an invariant.

Put differently, we can think of the inductive iterated satisfaction classes as forming a tree. The root is simply the empty set. Given a node in the tree, i.e. an iterated inductive full satisfaction class $S_a$ of length $a$ , its children are all the $(a+1)$ -iterated inductive full satisfaction classes which extend $S_a$ . Is it the case that all branches through this tree have the same length?

The answer is no.

Before seeing why, let’s fix some notation. Let $\mathsf{CT}$ be the theory consisting of the axioms of $\mathsf{PA}$ plus the assertions that $S$ is an inductive full satisfaction class. (This theory is in the language of arithmetic augmented with a symbol for $S$ .) Note that this theory is computably enumerable; it is a single sentence to say that $S$ is a full satisfaction class and a computable schema to say that $S$ is inductive. ( $\mathsf{CT}$ stands for “compositional truth”; cf. this SEP article.)

Next, let $\mathsf{PAT}$ be all theorems of $\mathsf{CT}$ which are in the language of arithmetic. That is, $\mathsf{PAT}$ consists of all theorems of $\mathsf{CT}$ which don’t make reference to truth. It is not hard to see that $\mathsf{PAT}$ is a proper extension of $\mathsf{PA}$ . For instance, $\mathrm{Con}(\mathsf{PA})$ is a theorem of $\mathsf{PAT}$ but, by a famous theorem of Gödel, is not a theorem of $\mathsf{PA}$ .

As a warm-up, let’s prove the following.

Proposition: Let $M \models \mathsf{PAT}$ be countable and recursively saturated. Then, there is $S \subseteq M$ so that $(M,S) \models \mathsf{CT}$ . Moreover, $S$ can be chosen so that $(M,S)$ is also recursively saturated.

In informal language, the only thing that could possibly stop a countable, recursively saturated model from admitting an inductive full satisfaction class is its theory.

Proof: This is a standard argument by resplendency. For the sake of the reader unfamiliar with this kind of argument (and because I’d feel a little silly giving a one sentence argument :/) I’ll provide a more detailed argument.

The first step is to note that $M$ contains nonstandard $t$ which codes the theory of $M$ . This is a fun exercise in writing down the correct recursive type. Next, let $(\varphi_n : n \in \omega)$ be an effective enumeration of the theorems of $\mathsf{PAT}$ . Finally, let $\tau(x)$ be the formula expressing $\mathrm{Con}(T_x)$ , where $T_x$ is $t \upharpoonright x + \bigwedge_{i < x} \varphi_i$ .

Observe that $M \models \tau(n)$ for all standard $n$ . By overspill, we can pick nonstandard $a \in M$ so that $M \models \tau(a)$ . Working inside $M$ , apply the arithmetized completeness theorem to $T_a$ . This gives a definable class of $M$ which codes a model $(N,\bar S)$ of $T_a$ . (Of course, $T_a$ is an ersatz theory which consists of real, standard formulae as well as nonstandard formulae, so the preceding sentence is a bit of nonsense. What is really meant is that $M$ has a definable class which codes what it thinks is the satisfaction predicate of $(N,\bar S)$ and that this satisfaction predicate includes $T_a$ .) Restricting to the standard formulae, we get that $(N,\bar S) \models \mathsf{CT} + \mathrm{Th}(M)$ .

Further, we get that $N$ end-extends $M$ . This is because $M$ thinks it is the standard model and that it embeds into any model of arithmetic. This is sufficiently absolute that if $M$ thinks it then it really is true. As a consequence, we get that $M$ and $N$ have the same standard system. But then, $M$ and $N$ are isomorphic. (This is a consequence of the more general fact that countable recursively saturated $M,N \models \mathsf{PA}$ are isomorphic if they have the same theory and the same standard system.) Letting $S$ be the image of $\bar S$ under the isomorphism we get that $(M,S) \models \mathsf{CT}$ , as desired.

The “moreover” part of the proposition is because for countable models, recursive saturation implies resplendency implies chronic resplendency. ∎

Similar to the definitions of $\mathsf{CT}$ and $\mathsf{PAT}$ , we can define $\mathsf{CT}_2$ and $\mathsf{PAT}_2$ for truth about truth instead of just truth. That is, $\mathsf{CT}$ consists of $\mathsf{PA}$ plus the assertions that $S_2$ is a $2$ -iterated inductive full satisfaction class while $\mathsf{PAT}_2$ consists of the theorems of $\mathsf{CT}_2$ in the language of arithmetic.

Proposition: Suppose $M \models \mathsf{PAT}_2$ is countable and recursively saturated. Then, there are $S,S' \subseteq M$ inductive full satisfaction classes so that $S$ can be iterated one step further to get a $2$ -iterated inductive full satisfaction class while $S'$ cannot.

Proof: Constructing $S$ is very similar to what we have already done. The easiest way to go about it is to first find $S_2$ a $2$ -iterated inductive full satisfaction class for $M$ by essentially the same argument as above. Then, restrict $S_2$ to the first stage to get a $1$ -iterated inductive full satisfaction class $S$ , i.e. an inductive full satisfaction class.

To construct $S'$ yet again apply the same argument from above. To ensure that it cannot be iterated further to produce an inductive $2$ -iterated full satisfaction class, it suffices to work with a theory $T \supseteq \mathsf{CT}$ which is incompatible with $\mathsf{PAT}_2$ . This can be done because, by a version of Tarski’s theorem on the undefinability of truth, $\mathsf{PAT}_2$ is independent over $\mathsf{CT}$ . This gives us $(M,S') \models \mathsf{CT}$ which cannot be extended to a model of $\mathsf{CT}_2$ . ∎

This gives us that the length a full satisfaction class be iterated to produce inductive iterated full satisfaction classes is not invariant under choice of satisfaction class. We can push this a little bit further and get that the length can be anything we desire.

WordPress is telling me that I’m nearly at two thousand words, so let me skimp on details. Similar to how we can write down a theory $\mathsf{CT}_2$ for having a $2$ -iterated inductive full satisfaction class, we can do the same for any $n$ and get $\mathsf{CT}_n$ . Indeed, if we work over a fixed $M$ we can talk about $\mathsf{CT}_a$ for any $a \in M$ . We also get $\mathsf{PAT}_a$ , the theorems of $\mathsf{CT}_a$ in the language of arithmetic. By considering a theory $T_a$ extending $\mathsf{CT}_a$ but incompatible with $\mathsf{PAT}_{a+1}$ we can get $S_a$ , an $a$ -iterated inductive full satisfaction class which cannot be iterated any further. Therefore, any possible length can be achieved.

Proposition: Let $M \models \mathsf{PA}$ be countable and recursively saturated and fix $b \in M$ . Suppose that $M \models \mathsf{PAT}_b$ . Then, for any $a \le b$ in $M$ , there is $S_a \subseteq M$ so that $(M,S_a) \models \mathsf{CT}_a$ but $S_a$ cannot be iterated one step further to an $(a+1)$ -iterated inductive full satisfaction class. ∎

This completely determines what can happen for iterated inductive full satisfaction classes of $M$ -finite length. But, at least in some circumstances, we can go further. For instance, $\mathsf{ATR}_0$ proves the existence of iterated truth predicates of transfinite length. (Naturally, any $A$ in the second-order part of a model of $\mathsf{ATR}_0 \supseteq \mathsf{ACA}_0$ must be inductive over the first-order part.) Thus, starting with a model $(M, \mathcal X)$ of $\mathsf{ATR}_0$ we can find, say, $S_\omega \subseteq M$ which is an $\omega^M$ -iterated inductive full satisfaction class for $M$ . What can be said in general about iterated inductive full satisfaction classes of transfinite length?

1 Comment

2017 Jan 13

Just how big is the smallest inaccessible cardinal anyway?

I’ve been playing around with iterated truth predicates recently and found a cute application. Namely, iterated truth predicates can be used to show that there is a lot of structure going on below inaccessible cardinals. While we usually think of inaccessible cardinals as being relatively small objects, from their own perspective they are quite large. They sit at the top of a tower of towers of towers of … of worldly cardinals. (A cardinal $\lambda$ is worldly if $V_\lambda \models \mathsf{ZFC}$ .) Looking downward from the least inaccessible cardinal, we see a dizzying stack of transitive models of $\mathsf{ZFC}$ below.

Let $\kappa$ be the smallest inaccessible cardinal. Then because $\kappa$ is in particular regular, $(V_\kappa, V_{\kappa+1})$ is a model of $\mathsf{KM}$ . Recall that Kelley-Morse set theory $\mathsf{KM}$ allows comprehension for all formulae, including those that include class quantifiers. This allows $\mathsf{KM}$ to prove that recursive constructions can be carried out along well-founded relations, even if the relations are proper classes. For simplicity, let’s confine ourselves for the moment to looking at class well-orders. Let $\Gamma$ be a class well-order and let $\phi$ be some definition we want to recursively carry out along $\Gamma$ . By comprehension, we can form the class of all counterexamples to $\phi$ in $\Gamma$ , i.e.

$\{ g \in \mathrm{dom}\, \Gamma : \neg \exists F \text{ such that } F \text{ is a partial solution to } \phi \text{ up to } g \}$ .

Once we have the class of counterexamples, we can find the least counterexample, assuming any exist. Thus, if $\phi$ really is a recursive definition, meaning that having a solution to $\phi$ up to $g'$ for all $g' \mathbin{\Gamma} g$ implies having a solution to $\phi$ up to $g$ , there must be no counterexamples. Otherwise, letting $g$ be the least counterexample we would get a solution up to $g$ , a contradiction. Thus, we can carry out the recursive definition all the way along $\Gamma$ .

One recursion of interest is Tarski’s recursive definition of truth for a structure. Given a structure $\mathfrak{A}$ , we can define truth for $\mathfrak{A}$ by recursion along the tree of formulae in the language of $\mathfrak{A}$ , allowing parameters. If $\mathfrak{A}$ is $(V,\in)$ , this gives us, in $\mathsf{KM}$ , a truth predicate for first-order truth for the universe of sets. (And thus, by a famous theorem of Tarski, $\mathsf{KM}$ is not conservative over $\mathsf{ZFC}$ .)

Back to our $(V_\kappa, V_{\kappa+1})$ . This structure has a truth predicate $T$ for $(V_\kappa,\in)$ . Even better, we can use this class as a parameter when applying the Lévy-Montague reflection principle. By reflection, we can find $\alpha < \kappa$ so that $\phi[a] \in T \upharpoonright V_\alpha$ iff $\phi[a] \in T$ . Translated into more natural language, this says that $(V_\alpha,\in)$ is an elementary substructure of $(V_\kappa,\in)$ . In fact, we get a club of such $\alpha$ . That is, $V_\kappa$ is the union of an elementary chain $\langle V_\alpha : \alpha \in C \rangle$ where $C \subseteq \kappa$ is club. Because $V_\alpha$ is a model of $\mathsf{ZFC}$ , so are each of the $V_\alpha$ . So our smallest inaccessible cardinal sits atop a tower of worldly cardinals. Actually, the $V_\alpha$ are a bit more than just worldly. Because they are elementary in $V_\kappa$ which thinks there is a club class of worldly cardinals, each $V_\alpha$ is itself the union of a club of worldly cardinals.

Let’s call this a $2$ –tower, as it is a tower of towers. In general, say that a $1$ –tower is a sequence $\langle V_\alpha : \alpha \in C \subseteq_{\mathsf{club}} \beta \rangle$ where each $V_\alpha$ is a model of $\mathsf{ZFC}$ . And a $(\xi + 1)$ –tower is a sequence $\langle V_\alpha : \alpha \in C \subseteq_{\mathsf{club}} \beta \rangle$ where each $V_\alpha$ is itself the union of of a $\xi$ -tower. Finally, if $\gamma$ is a limit ordinal, then a $\gamma$ –tower is a sequence $\langle V_\alpha : \alpha \in C \subseteq_{\mathsf{club}} \beta \rangle$ so that each $V_\alpha$ is the union of a $\xi$ -tower for all $\xi < \gamma$ .

We have already seen that the smallest inaccessible cardinal sits at the top of a $2$ -tower. But we can say more by using iterated truth predicates, rather than just ordinary truth predicates. Given a model of set theory, we can often expand the structure by adding in a predicate symbol for truth about the model. For example, if $\kappa$ is inaccessible then $(V_\kappa,\in,T) \models \mathsf{ZFC}(T)$ , where by $\mathsf{ZFC}(T)$ I mean the theory gotten by having the separation and collection schemata allow formulae which make reference to $T$ . (For ease of notation, let’s say that $T$ is strongly amenable over $V_\kappa$ to refer to this.) We can then ask about truth of this expanded structure, expanding it yet further with a predicate for truth about truth. We can continue this process to get truth about truth about truth, and so on.

Let’s step back a moment and note that this definition isn’t trivial. There are transitive models of $\mathsf{ZFC}$ which don’t admit strongly amenable truth predicates. For instance, suppose that $M \models \mathsf{ZFC}$ is pointwise-definable, meaning that every element of $M$ is definable. (For an example, the least transitive model of $\mathsf{ZFC}$ is pointwise-definable.) Then, $M$ cannot admit a strongly amenable truth predicate. If it did, then by replacement we could define the map which sends $\phi$ to the element of $M$ defined by $\phi$ and get a definable surjective map $\omega \to M$ , which of course is impossible.

Back to iterated truth predicates. How do we construct them? By recursion. First, we carry out the Tarskian recursion to define truth $T_1$ . Then we carry out another instance of the Tarskian recursion to define truth about truth $T_2$ . We can keep going, defining $T_3$ (truth about truth about truth), $T_4$ (truth about truth about truth about truth), and so on. Rather than thinking about this as a series of recursive definitions, we can fold this all into a single recursive definition, carried out along a tree of higher rank; we define $T_1$ by a recursion of rank $\omega$ and $T_2$ by a recursion of rank $\omega \cdot 2$ . Because $\mathsf{KM}$ proves that solutions to these recursions exist, we get iterated truth predicates for the universe of sets. And we can continue this process transfinitely, using a recursion of rank $\omega \cdot \alpha$ to get the $\alpha$ -iterate of truth $T_\alpha$ for any ordinal $\alpha$ .

Much like there are transitive models of $\mathsf{ZFC}$ which don’t admit strongly amenable truth predicates, there are models of $\mathsf{ZFC}$ which don’t admit strongly amenable iterated truth predicates. Indeed, if $M \models \mathsf{ZFC}$ admits a strongly amenable $\xi$ -iterated truth predicate then there is $N \prec M$ which admits a strongly amenable $\xi$ -iterated truth predicate but doesn’t admit a strongly amenable $(\xi+1)$ -iterated truth predicate. Namely, take $N$ to be the Skolem hull of the empty set in $M$ using the $\xi$ -iterated truth predicate as a parameter. Then $N$ will be pointwise-definable from its $\xi$ -iterated truth predicate. This rules out the possibility of $N$ having a $(\xi+1)$ -iterated truth predicate, similar to the argument above.

In our case of $(V_\kappa,V_{\kappa+1})$ , we have that for for any $\alpha < \kappa$ we have that $T_\alpha \in V_{\kappa+1}$ , the $\alpha$ th iterated truth, is strongly amenable. Consequently, $V_\kappa$ is the union of a tower of towers of towers of towers of towers of towers of towers of towers of …

Proposition: Suppose $V_\kappa$ is a transitive model of $\mathsf{ZFC}$ and that $T_\eta$ is the $\eta$ th iterate of truth for $V_\kappa$ . If $T_\eta$ is strongly amenable, then $V_\kappa$ is the union of an $\eta$ -tower.

Proof: By an easy induction. The base case is essentially the argument above that inaccessibles sit atop a $1$ -tower. For the successor step in the argument, you can use reflection to show that a $(\xi+1)$ -iterated truth predicate for $V_\kappa$ can be reflected down to give, for a club of $\alpha < \kappa$ , that $V_\alpha$ has a strongly amenable $\xi$ -iterated truth predicate. Similarly for the limit step.

Corollary: If $\kappa$ is inaccessible, then $V_\kappa$ is the union of an $\eta$ -tower for all $\eta < \kappa$ .

Looking down from $\kappa$ , we can see a lot of rich transitive models of $\mathsf{ZFC}$ . But we get more. Why should we stop with iterating truth along well-orders shorter than $\kappa$ ? In $V_{\kappa+1}$ we can find well-orders of length much greater than $\kappa$ and $\mathsf{KM}$ lets us recursively define iterated truth along these long well-orders.

Let’s start by looking at $\mathrm{Ord} + 1$ . We can find $T_{\mathrm{Ord}+1} \in V_{\kappa + 1}$ which is strongly amenable over $V_\kappa$ . By reflection, we find $\alpha < \kappa$ so that $V_\alpha$ has a strongly amenable $\mathrm{Ord}$ th iteration of truth.

It’s worth stepping back a moment to clarify what this means. When we looked at $T_\xi$ for $\xi < \kappa$ , it was easy to see what happened when we reflected down to $V_\alpha$ . We have a lot of room between $\xi$ and $\kappa$ to find appropriate $\alpha$ , so we never had to worry about iterating truth over a proper class. This no longer works if we want to iterate $\mathrm{Ord}$ many times. What we get is that $(T_{\mathrm{Ord}})^{V_\alpha}$ is truth iterated out $\alpha$ many times and $(T_{\mathrm{Ord} + 1})^{V_\kappa}$ is truth iterated out $\kappa + 1$ many times. In other words, $\mathrm{Ord}$ here is acting as a parameter giving the height of the model.

Never the less, it’s still sensible to talk about $\mathrm{Ord}$ -towers or $(\mathrm{Ord} + 1)$ -towers, and so on. It’s perhaps helpful to first take a new perspective on the “short” towers we have already seen. I’ll borrow some ideas from the dissertation of Erin Carmody, my academic elder sister. As part of section 2 of her dissertation, she looked at degrees of inaccessibility. For instance, a cardinal is $2$ -inaccessible if it is an inaccessible limit of inaccessibles. It’s easy to keep going and define $\alpha$ -inaccessibility for ordinals $\alpha$ , but Erin went further. She gave definitions of $t$ -inaccessibility, where $t$ is a formal arithmetic term in $\mathrm{Ord}$ , e.g. $(\mathrm{Ord}^\omega \cdot \omega_1 + \mathrm{Ord}^5 \cdot 3 + \mathrm{Ord} \cdot \omega_7 + \omega_2)$ -inaccessibility.

Let $W$ be the class of worldly cardinals and let $\mathcal T$ be the tower operation, i.e. if $A \subseteq \mathrm{Ord}$ then $\mathcal T(A) = \{ \alpha \in \mathrm{Ord} : A \cap \alpha \subseteq_{\mathsf{club}} \alpha \}$ . By the terminology above, $\mathcal T(W)$ is the class of cardinals which are the union of $1$ -towers. By iterating the application of $\mathcal T$ we can get the cardinals sitting atop $\xi$ -towers as being exactly $\mathcal T^\xi(W)$ . Phrasing one of the above results in this language, if $\kappa$ is inaccessible then $\kappa \in \mathcal T^\eta(W)$ for all $\eta < \kappa$ .

How do we make sense of $\mathrm{Ord}$ -towers from this perspective? We want to say that $\alpha$ sits atop an $\mathrm{Ord}$ -tower if it sits atop a $\xi$ -tower for all $\xi < \alpha$ . This is exactly asking that $\alpha$ be in the diagonal intersection of the $\mathcal T^\xi(W)$ s.

Now we can go beyond $\mathrm{Ord}$ . For instance, a $(\mathrm{Ord} + 1)$ -tower is a sequence of a club of $V_\alpha$ s which are themselves unions of $\mathrm{Ord}$ -towers. We keep going as before until we get to $\mathrm{Ord} \cdot 2$ , where we again take a diagonal intersection. We can keep going up to any arithmetic term in $\mathrm{Ord}$ . For example, we can talk about $(\mathrm{Ord}^{\omega_1^{\mathsf{CK}}} + \mathrm{Ord}^{\omega \cdot 3} \cdot \omega_1 + \mathrm{Ord}^\omega \cdot \omega_{91} + \omega_\omega + 1)$ -towers, i.e. sequences of clubs of $V_\alpha$ s which are themselves unions of $(\mathrm{Ord}^{\omega_1^{\mathsf{CK}}} + \mathrm{Ord}^{\omega \cdot 3} \cdot \omega_1 + \mathrm{Ord}^\omega \cdot \omega_{91} + \omega_\omega)$ -towers

By roughly the same argument as above, we get that inaccessible cardinals sit atop towers of ‘meta-ordinal’ height for any meta-ordinal we can write down. The key fact used is that if $t$ is an arithmetic term in $\mathrm{Ord}$ , then $V_\kappa$ has a strongly amenable $(t+1)$ -iterated truth predicate which can be reflected down to get that $V_\kappa$ is the union of an elementary chain of $V_\alpha$ s which themselves have $t$ -iterated truth predicates.

Proposition: Let $t$ be an arithmetic term in $\mathrm{Ord}$ . Then, if $\kappa$ is inaccessible, $V_\kappa$ is the union of a $t$ -tower of worldly cardinals.

5 Comments