Recursively saturated and rather classless

A mathematics blog by Kameryn Williams

Non-hyperfinite countable equivalence relations

This will be a talk at the CUNY Models of Peano Arithmetic seminar on Wednesday, March 15th 2017.

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.

Observation.

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.

Models of arithmetic with two expansions to ACA_0

This was a pair of talks for CUNY’s MoPA seminar on 5 Oct and 26 Oct 2016.

First talk: In this talk and its sequel I will construct models of arithmetic with exactly two expansions to a model of \mathsf{ACA}_0. To do so, I will use a modified version of Keisler’s construction of a rather-classless model. This talk will focus on this construction, while in Part 2 I will show how to use this construction to get the result.

Second talk: In this talk and its prequel I construct models of arithmetic with exactly two expansions to a model of \mathsf{ACA}_0. Last time, we saw how to build models of arithmetic which are A-rather classless for some class A of the model. In this talk, I will use a kind of forcing argument to show how to pick this A so that the resulting model has exactly two expansions to \mathsf{ACA}_0. Time permitting, I will explain the difficulties in moving from two to three.

Unfortunately, Roman Kossak spotted an error in the second talk which I have since been unable to fix. To my knowledge it is currently open whether there is a model of \mathsf{PA} with precisely two \mathsf{ACA}_0-realizations.

Yet more forcing in arithmetic: life in a second-order world

This was a talk in CUNY’s MoPA seminar.

In previous semesters of this seminar, I have talked about how the technique of forcing, originally developed by Cohen for building models of set theory, can be used to produce models of arithmetic with various properties. In this talk, I will present a forcing proof of Harrington’s theorem on the conservativity of \mathsf{WKL}_0 over \mathsf{RCA}_0. More formally, any countable model of \mathsf{RCA}_0 can be extended to a model of \mathsf{WKL}_0 with the same first-order part. As an immediate corollary, we get that any \Pi^1_1 sentence provable by \mathsf{WKL}_0 is already provable by \mathsf{RCA}_0.