This is a talk at the Warsaw Workshop on Formal Truth Theories on 29 Sept 2017. For a writeup of the material in this talk, see chapter 3 of my dissertation.

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 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.

Theorem 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.