Categoricty theorems for second-order set theory without powersets
In 1904, Oswald Veblen defined that a theory is categorical if it has a unique model up to isomorphism. Categoricty quickly proved to be unattainable in the first-order setting. The upward Löwenheim–Skolem theorem showed that any first-order theory with a model of some infinite cardinality $\kappa$ has models of cardinality at least $\gamma$ for every $\gamma\geq\kappa$. The question becomes more meaningful if we ask for $\kappa$-categorical theories, those having a unique up to isomorphism model of cardinality $\kappa$. Morley famously showed that a theory is either (1) $\omega$-categorical, (2) categorical for all uncountable cardinals but not $\omega$-categorial, or (3) categorical for all infinite cardinals [1]. After a century of working in first-order logic, it surprises no one that it is bad at categorizing things. So what about the much more powerful second-order logic?
The massive difference between the two logics is how much of the set-theoretic universe they have access to. Even first-order logic does not exist entirely outside of the set-theoretic universe because it requires recursion for Tarsky's definition of truth, but it cannot detect most of its set-theoretic background. As we saw from Morley's theorem even though it might in certain instances be able to tell the difference between the countable and uncountable, it cannot recognize its own cardinality. Even more basically, a first-order model of arithmetic or set theory can easily miss its own ill-foundedness. Second-order logic is a very different story. The logic has additional (second-order) quantifiers ranging over all relations on the model. (For theories with coding such as arithmetic or set theory, we will think of the second-order quantifiers as ranging over the subsets of the model, which we refer to as the model's classes.) Now this is where a bit of confusion comes in for many people because there are two types of models in second-order logic, the (true) models and the Henkin models. In a model of second-order logic, we are allowed to quantify over all relations on the model that the underlying set-theoretic universe has, giving the model full access to its powerset. A Henkin model comes with a possibly restricted collection of relations on the model and the second-order quantifiers then only have access to this collection. Henkin models are camouflaged first-order structures because we can interpret their two sorts, the domain and the relations over the domain in a contorted, but first-order way. In contemporary set theory when we talk about 'second-order' set theory or set theory with classes, we are always dealing with Henkin models. People just don't look at second-order models anymore (caveat: unless they are studying abstract logics) because they are too powerful. But in this post, I will be dealing with the actual second-order models of set theory because I want to discuss the categoricity results available in this setting.
Given how much the (non-Henkin) models of second-order set theory know about their powerset, it should not be surprising that strong categoricity results can be obtained for them. Let ${\rm ZFC}_2$ denote the second-order ${\rm ZFC}$-axioms consisting of the usual axioms, but with Replacement having access to ALL functions on the model. How much do these models 'know'? Well, they have to be well-founded because if there was an infinitely descending membership chain, then the model would see it using the second-order Replacement axiom. So we can assume without loss of generality that they are $\in$-models. They have to be correct about cardinals and cofinalities because they likewise see all available functions on the ordinals. Given a set, they also have to have its full powerset. In other words, a set model of ${\rm ZFC}_2$ is a $V_\kappa$ and $\kappa$ must be inaccessible. In particular, any two models of ${\rm ZFC}_2$ with the same ordinals must be isomorphic. This is Zermelo's Categority Theorem for ${\rm ZFC}_2$. Beau Madison Mount recently asked me if there is a corresponding categoricty theorem for ${\rm ZFC}^-_2$ the second-order version of set theory without powersets, where we extend the Replacement axiom to all functions (note that the Collection scheme follows from second-order Replacement). The answer is yes and it is easy to see that models of ${\rm ZFC}^-_2$ are precisely the structures $H_\beta$ (the collection of all sets whose transitive closure has cardinality less than $\beta$). So here also it is the case that any two models with the same ordinals are going to be isomorphic. Let's fix a model $M$ of ${\rm ZFC}^-_2$ and see why. As before because the models are correct about well-foundedness, we can assume that $M$ is an $\in$-model. Also, as before $M$ is correct about cardinals and if it has a cardinal $\delta$, then $P(\delta)\subseteq M$ (not necessarily an element though because of the failure of powerset). Since every element of $H_{\delta^+}$ can be coded by a subset of $\delta$, it follows that $H_{\delta^+}\subseteq M$. First, suppose that $M$ has the largest cardinal $\delta$. Then as we already argued $H_{\delta^+}\subseteq M$. Now given a set $A\in M$, $M$ thinks that $A$ has size at most $\delta$ and it is correct about this. Thus, since $M$ is transitive, it is contained in $H_{\delta^+}$, and hence $M=H_{\delta^+}$. Otherwise, let $\beta$ be the supremum of the cardinals in $M$, and show similarly that $M=H_\beta$.
Väänänen has a more refined concept of categoricity which tries to limit the access of the models to the full powerset, a condition, as we have seen, under which categoricity results are too easily obtained. His concept of internal categoricity puts two models of, say ${\rm ZFC}$, into a Henkin model of second-order logic satisfying that only (relatively low complexity) definable relations over the model are required to exist [2]. The overarching Henkin model then views these ${\rm ZFC}$ models as models of ${\rm ZFC}_2$ from its own perspective, that is the models see only the classes that are available in the Henkin model containing them both. Can such a Henkin model recognize that two models of ${\rm ZFC}$ are isomorphic? What about ${\rm ZFC}^-$?
Let's first give a more precise definition of internal categoricity. Our language consists of two unary predicates $M$ and $N$, which are going to split the domain into the models $M$ and $N$, and binary predicates $E^M$ and $E^N$, which are going to be the membership relations on $M$ and $N$ respectively. Our second-order theory is going to say that (1) $\Pi^1_1$-comprehension holds (the model has every relation defined by a formula with a single universal second-order quantifier followed by a first-order formula of any complexity), (2) $M$ together with $E^M$ is a model of ${\rm ZFC}_2$ (with the respect to the sets available in the Henkin model), (3) similarly $N$ together with $E^N$ is a ${\rm ZFC}_2$ model, and finally (4) there is an isomorphism $F$ between the ordinals of $M$ and the ordinals of $N$. The reason we use $\Pi^1_1$-comprehension is that it suffices for the existence of solutions to recursions on (second-order) relations along the ordinals (either of $M$ or $N$ since they are isomorphic). Via a recursion on the rank of the elements we can define an isomorphism between $M$ and $N$: given that we already have an isomorphism on all sets of rank less than some $\alpha$, we extend it in the obvious fashion to an isomorphism on all elements of rank $\alpha$. Actually, much less than $\Pi^1_1$-comprehension is supposed to suffice for building the isomorphism. The point of internal categoricity is that you don't need the entire set theoretic background to verify that two models are isomorphic, you only need a Henkin model having some very concretely definable relations.
Can we extend the same internal categoricity result to models of ${\rm ZFC}^-$? Yes, the same argument using a recursion on rank will work, but I don't know in this case whether we can weaken the comprehension assumption. In the ${\rm ZFC}$ case the elements of the recursion are actually elements of the model (they are sets in $M$ or $N$) and not second-order objects and so $\Pi^1_1$-comprehension is overkill for the existence of a solution. But since a model of ${\rm ZFC}^-$ can have class many elements of a certain rank, our recursion in this case definitely has second-order initial segments.
References
- M. Morley, “Categoricity in power,” Trans. Amer. Math. Soc., vol. 114, pp. 514–538, 1965. Available at: https://doi.org/10.2307/1994188
- J. Väänänen, “Tracing internal categoricity,” Theoria, vol. 87, no. 4, pp. 986–1000, 2021. Available at: https://doi.org/10.1111/theo.12237