Beta-models of GBC can satisfy very little transfinite recursion

by kamerynwilliams

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!