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

by kamerynwilliams

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?