Recursively saturated and rather classless

A mathematics blog by Kameryn Williams

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?

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:

  1. If (M,\mathcal X) \models \mathsf{GB} + \mathsf{AC} then forcing with \mathbb G^M over (M,\mathcal X) preserves \mathsf{GB} + \mathsf{AC}.
  2. 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.

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.

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 Schmerlsee 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 formulaeI 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 Isay we only want to iterate one step to get U_2 and I_2 respectivelythen 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?

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 2tower, as it is a tower of towers. In general, say that a 1tower 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 \gammatower 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 \alphath 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 \etath 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_\alphas 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_\alphas 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_\alphas 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.


Beta-models of GBC can satisfy very little transfinite recursion

The reason that the fact mentioned in the title is interesting is because this gives us another place where the analogy between arithmetic and set theory fails. (Or, perhaps more accurately, this is another facet of an already-known disanalogy.)

Say that a two-sorted structure (M,\mathfrak X), either a model of second-order arithmetic or of a second order set theory, is a beta-model if it is correct about well-foundedness. Naturally, this implies that M must be transitive, in the case of set theory, or, in the case of arithmetic, M = \omega. For models of arithmetic, being a beta-model implies quite a bit more. Let’s say that (M, \mathfrak X) is a model of arithmetical comprehension, for concreteness. (Weaker requirements are enough, but let’s not worry about how low we can go.) Then, if (M, \mathfrak X) is a beta-model, it automatically satisfies transfinite-recursion for first-order properties. That is, if R \in \mathfrak X is a well-founded relation then recursion for first-order properties can be iterated along it to get a solution in \mathfrak X. If you’re familiar with the big five theories, what I’ve just said is that every beta-model of \mathsf{ACA}_0 is a model of the stronger theory \mathsf{ATR}_0.

This is actually pretty easy to see, taking as given the  following fact: for models of arithmetical comprehension, the formula “X is a well-order” is \Pi^1_1-universal. Thus, being a beta-model is equivalent to having \omega as your first-order part plus being correct about \Sigma^1_1 assertions. Note that a recursion for a first-order property having a solution is itself a \Sigma^1_1 assertion. Since a solution exists in the ambient universe, because R really is well-founded, we thus get that a beta-model must also see the solution.

This argument does not generalize to models of set theory. In this context, “X is a well-order” does not have a hope of being \Pi^1_1-universal. Indeed, the obstacle here is exactly what will give us the fact from the title. The following observation encapsulates what’s happening here.


If (M,\mathfrak X) is a beta-model of a second-order set theory and \mathfrak Y \subseteq \mathfrak X is so that (M,\mathfrak Y) is also a model of set theory, then (M,\mathfrak Y) is a beta-model.

Proof: Suppose that R \in \mathfrak Y so that (M,\mathfrak Y) thinks R is ill-founded. Then, there is a set r \in M which is an infinite descending sequence in R. But then (M,\mathfrak X) thinks R is ill-founded, so by betaness R really is ill-founded. Thus (M,\mathfrak Y) is correct about well-foundedness.

As an immediate consequence of this observation we get lots and lots of beta-models of set theory which don’t satisfy transfinite recursion for first-order properties. Indeed, we can get beta-models whose second-order part is as small as possible. For example, take (M, \mathfrak X) a beta-model of KM (or some other theory which proves transfinite recursion for first-order properties). More, assume that M has a definable global well-order. Then, we get that (M, \mathrm{Def}(M)) is a model of GBC. By the observation, it is a beta-model. Yet it will fail to have solutions to many transfinite recursions. This even happens for transfinite recursions whose rank is as low as \omega, such as the transfinite recursion to define a truth predicate in the Tarskian manner!

Separating class determinacy

This was a talk at the CUNY Set Theory Seminar.

In his dissertation, Steel showed that both open determinacy and clopen determinacy have a reverse math strength of \mathsf{ATR}_0. In particular, this implies that clopen determinacy is equivalent to open determinacy (over a weak base theory). Gitman and Hamkins in recent work explored determinacy for class-sized games in the context of second-order set theory. They asked whether the analogue of Steel’s result holds: over \mathsf{GBC}, is open determinacy for class games equivalent to clopen determinacy for class games?

The answer, perhaps surprisingly, is no. In this talk I will present some recent results by Hachtman which answer the question of Gitman and Hamkins. We will see how to construct a transitive model of \mathsf{GBC} which satisfies clopen class determinacy but does not satisfy open class determinacy.