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 is worldly if .) Looking downward from the least inaccessible cardinal, we see a dizzying stack of transitive models of below.
Let be the smallest inaccessible cardinal. Then because is in particular regular, is a model of . Recall that Kelley-Morse set theory allows comprehension for all formulae, including those that include class quantifiers. This allows 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 be a class well-order and let be some definition we want to recursively carry out along . By comprehension, we can form the class of all counterexamples to in , i.e.
Once we have the class of counterexamples, we can find the least counterexample, assuming any exist. Thus, if really is a recursive definition, meaning that having a solution to up to for all implies having a solution to up to , there must be no counterexamples. Otherwise, letting be the least counterexample we would get a solution up to , a contradiction. Thus, we can carry out the recursive definition all the way along .
One recursion of interest is Tarski’s recursive definition of truth for a structure. Given a structure , we can define truth for by recursion along the tree of formulae in the language of , allowing parameters. If is , this gives us, in , a truth predicate for first-order truth for the universe of sets. (And thus, by a famous theorem of Tarski, is not conservative over .)
Back to our . This structure has a truth predicate for . Even better, we can use this class as a parameter when applying the Lévy-Montague reflection principle. By reflection, we can find so that iff . Translated into more natural language, this says that is an elementary substructure of . In fact, we get a club of such . That is, is the union of an elementary chain where is club. Because is a model of , so are each of the . So our smallest inaccessible cardinal sits atop a tower of worldly cardinals. Actually, the are a bit more than just worldly. Because they are elementary in which thinks there is a club class of worldly cardinals, each is itself the union of a club of worldly cardinals.
Let’s call this a –tower, as it is a tower of towers. In general, say that a –tower is a sequence where each is a model of . And a –tower is a sequence where each is itself the union of of a -tower. Finally, if is a limit ordinal, then a –tower is a sequence so that each is the union of a -tower for all .
We have already seen that the smallest inaccessible cardinal sits at the top of a -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 is inaccessible then , where by I mean the theory gotten by having the separation and collection schemata allow formulae which make reference to . (For ease of notation, let’s say that is strongly amenable over 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 which don’t admit strongly amenable truth predicates. For instance, suppose that is pointwise-definable, meaning that every element of is definable. (For an example, the least transitive model of is pointwise-definable.) Then, cannot admit a strongly amenable truth predicate. If it did, then by replacement we could define the map which sends to the element of defined by and get a definable surjective map , 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 . Then we carry out another instance of the Tarskian recursion to define truth about truth . We can keep going, defining (truth about truth about truth), (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 by a recursion of rank and by a recursion of rank . Because 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 to get the -iterate of truth for any ordinal .
Much like there are transitive models of which don’t admit strongly amenable truth predicates, there are models of which don’t admit strongly amenable iterated truth predicates. Indeed, if admits a strongly amenable -iterated truth predicate then there is which admits a strongly amenable -iterated truth predicate but doesn’t admit a strongly amenable -iterated truth predicate. Namely, take to be the Skolem hull of the empty set in using the -iterated truth predicate as a parameter. Then will be pointwise-definable from its -iterated truth predicate. This rules out the possibility of having a -iterated truth predicate, similar to the argument above.
In our case of , we have that for for any we have that , the th iterated truth, is strongly amenable. Consequently, is the union of a tower of towers of towers of towers of towers of towers of towers of towers of …
Proposition: Suppose is a transitive model of and that is the th iterate of truth for . If is strongly amenable, then is the union of an -tower.
Proof: By an easy induction. The base case is essentially the argument above that inaccessibles sit atop a -tower. For the successor step in the argument, you can use reflection to show that a -iterated truth predicate for can be reflected down to give, for a club of , that has a strongly amenable -iterated truth predicate. Similarly for the limit step.
Corollary: If is inaccessible, then is the union of an -tower for all .
Looking down from , we can see a lot of rich transitive models of . But we get more. Why should we stop with iterating truth along well-orders shorter than ? In we can find well-orders of length much greater than and lets us recursively define iterated truth along these long well-orders.
Let’s start by looking at . We can find which is strongly amenable over . By reflection, we find so that has a strongly amenable th iteration of truth.
It’s worth stepping back a moment to clarify what this means. When we looked at for , it was easy to see what happened when we reflected down to . We have a lot of room between and to find appropriate , so we never had to worry about iterating truth over a proper class. This no longer works if we want to iterate many times. What we get is that is truth iterated out many times and is truth iterated out many times. In other words, here is acting as a parameter giving the height of the model.
Never the less, it’s still sensible to talk about -towers or -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 -inaccessible if it is an inaccessible limit of inaccessibles. It’s easy to keep going and define -inaccessibility for ordinals , but Erin went further. She gave definitions of -inaccessibility, where is a formal arithmetic term in , e.g. -inaccessibility.
Let be the class of worldly cardinals and let be the tower operation, i.e. if then . By the terminology above, is the class of cardinals which are the union of -towers. By iterating the application of we can get the cardinals sitting atop -towers as being exactly . Phrasing one of the above results in this language, if is inaccessible then for all .
How do we make sense of -towers from this perspective? We want to say that sits atop an -tower if it sits atop a -tower for all . This is exactly asking that be in the diagonal intersection of the s.
Now we can go beyond . For instance, a -tower is a sequence of a club of s which are themselves unions of -towers. We keep going as before until we get to , where we again take a diagonal intersection. We can keep going up to any arithmetic term in . For example, we can talk about -towers, i.e. sequences of clubs of s which are themselves unions of -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 is an arithmetic term in , then has a strongly amenable -iterated truth predicate which can be reflected down to get that is the union of an elementary chain of s which themselves have -iterated truth predicates.
Proposition: Let be an arithmetic term in . Then, if is inaccessible, is the union of a -tower of worldly cardinals.