We thank Ali Enayat and Farmer Schlutzenberg for helpful comments and correspondence, especially concerning the results on theories of bounded-complexity consequences.
Contents
Background definitions 4
K P KP K P is neither solid nor tight 5
2.1. Solidity failure 5
2.2. Tightness failure 13
2.3. Some generalizations 16
Quantifier bounded theories generally aren’t tight 19
The Definable Countable Enumeration Lemma 21
4.1. Tableau proof systems: building models by approximation 22
4.2. Modifying the tableaux 24
4.3. Building models 29
4.4. Main proof 37
Geology with little hammers 37
5.1. Ground model definability in a weak set theory 39
5.2. A uniquely definable ground theorem 43
Applications 49
6.1. Large cardinals beyond L L L and other extensions 49
6.2. The inexpressibility of V = H O D V = HOD V = H O D in quantifier bounded set theories 54
6.3. Solidity and the ground axiom 54
References 58
It’s well known that no theory with an infinite model that is articulated in first order logic can be categorical: compactness says there will always be a bigger model. However, in recent years logicians have studied a number of properties that a theory can possess which appear to, in some sense, approximate categoricity [8 ] . As a rule of thumb, the kinds of theories that have categoricity proofs in second order logic tend to satisfy these properties when they are converted into first order theories using schematic techniques. For example, the second-order versions of P A \mathit{PA} PA and Z F C \mathit{ZFC} ZFC are respectively categorical and quasi-categorical,1 and both P A \mathit{PA} PA and Z F C \mathit{ZFC} ZFC possess these new properties [35 , 7 ] .
Our broad goal in this paper is to investigate set theories that only use bounded versions of the Separation, Collection and Replacement schemas while remaining fully inductive in the sense that they satisfy the Full Set Induction schema; i.e., any definable nonempty class has an ∈ \in ∈ -minimal element. The main upshot of this paper is that these approximate categoricity properties fail for broad classes of such theories. This places our results in the program of identifying natural set and class theories that fail to be tight or solid. Freire and Hamkins [2020] showed that Zermelo set theory and Z F C \mathit{ZFC} ZFC without Powerset are not tight. Freire and Williams [2025] established corresponding failures for fragments of Kelley-Morse set theory and second-order arithmetic.
This paper extends results of Enayat and Lelyk [2024]. In particular, they show that for any n ∈ ω n \in\omega n ∈ ω , the Π n \Pi_n Π n -consequences of Z F \mathit{ZF} ZF are neither solid nor tight .2 The results of this paper improve this in two directions. First, we include Full Set Induction in our theories. Second, we do not limit ourselves to sub-theories of Z F \mathit{ZF} ZF , but rather, show that an open ended collection of theories extending a weak base theory are neither solid nor tight. In particular, we will show that for a natural class of these theories, solidity implies that the theory proves a version of the Ground Axiom.
Aside from the main results, this paper makes use of a couple of strange techniques that are worth discussing. First, we show that some models of these bounded theories are capable of defining generics over their posets and the generic extensions based on those generics.3 This runs counter to the orthodox pedagogy of set theory where one learns that generic sets must exist outside their models and thus, generic extensions are not within the purview of relative interpretation. The key to this counterintuitive approach is the ability to find models of these bounded theories that are able to see that they are countable, in the sense that they can define a surjection from the natural numbers onto their entire domain. For sub-theories of Z F \mathit{ZF} ZF , we can exploit well known fine-structural results to obtain such enumerations in models of V = L V=L V = L using the natural well-ordering of L L L .4 But for theories incompatible with L L L this technique is not available. As such, we prove a very general lemma showing that our bounded theories are always consistent with the existence of a definable countable enumeration of the universe. This is the most novel result of the paper and, as such, it takes up the most space.
The paper is divided up as follows. In the next section we give proper definitions of our target properties and explain why they are interesting. In Section 2, we show that K P \mathit{KP} KP satisfies neither of these properties. To achieve this, we develop the theory of definable forcing over L ω 1 C K L_{\omega_1^{CK}} L ω 1 C K and then generalize this further. Aside from the fact that K P KP K P is a theory of obvious foundational interest, this setting provides a convenient location to explain the underlying ideas of the paper in a setting that is likely to be familiar to its readers. Section 3 then provides the framework for a substantial generalization of these results to theories that are bounded extensions of a weak sub-theory of Z F C ZFC Z F C that includes Full Set Induction. This gives us a theorem template (Theorem 31) that allows us to show that when such theories possess a crucial property (Definition 29) they can never be tight. The theorem template is then demonstrated on the basis of a lemma that we prove in the following section. The Definable Countable Enumeration Lemma (Lemma 30) is then proved in Section 4. This is the most original and unusual contribution of the paper. In order to set up for applications of this template, we need tools from set-theoretic geology. Section 5 starts from Schlutzenberg’s ground-model definability theorem over the weak theory M O S T MOST M O S T [Schlutzenberg, 2022].5 We adapt it to use a smaller parameter and then code that parameter into the continuum function, so that the ground can be recovered without parameters. The small-parameter argument works over M O S T MOST M O S T ; the coding construction is carried out over Z F C Π 3 ZFC\Pi_3 Z F C Π 3 . Finally, in Section 6, we bring these results to bear on a variety of natural examples.
Background definitions
Let us start by introducing the property of tightness.
Definition 1. [7 ] Say that a theory T T T is tight if any pair of bi-interpretable extensions of T T T are the same theory (in the sense that they have the same deductive closure).
Informally, a theory is tight if it cannot be extended in distinct, but equivalent ways. To get more of a feel for this, let’s contrast a non-tight theory with a tight one. For a non-tight theory, let Empty be the empty theory of binary relations articulated in L E m p t y = { R } \mathcal{L}_{Empty}=\{R\} L E m pt y = { R } . Now consider the extensions S 0 S_0 S 0 and S 1 S_1 S 1 of Empty that say that R R R is, respectively, reflexive and irreflexive. S 0 S_0 S 0 and S 1 S_1 S 1 are clearly bi-interpretable, indeed, they are definitionally equivalent. From a graph theoretic perspective, we add loops in one direction and remove the loops in the other direction. But they are not the same theory. We might say that Empty is, unsurprisingly, insufficiently specific to be tight.
For a contrast, we observe that P A PA P A is tight [35 ] . So P A PA P A appears to be more specific than Empty . To make more sense of this, let’s try to pull on some intuitions. We know that P A PA P A has an intended model, N = ⟨ ω , 0 , s , + , × ⟩ \mathbb{N}=\langle\omega,0,s,+,\times\rangle N = ⟨ ω , 0 , s , + , × ⟩ , and we also know that P A PA P A is incomplete, so P A ⊈ T h ( N ) PA\nsubseteq Th(\mathbb{N}) P A ⊈ T h ( N ) . Now imagine, for a moment, that P A PA P A was not tight and that this was witnessed by another theory S ⊇ P A S\supseteq PA S ⊇ P A that was bi-interpretable with T h ( N ) Th(\mathbb{N}) T h ( N ) . This would be a strange situation. Since S S S would be distinct from T h ( N ) Th(\mathbb{N}) T h ( N ) , we’d have another way of understanding 0 , s , + , × 0,s,+,\times 0 , s , + , × that was distinct from the standard interpretation and yet still satisfied the axioms of P A PA P A . There would, thus, be an arithmetic sentence true in one interpretation and false in the other; and little, if any, good reason to choose between them. Such a situation would attest to a different kind of incompleteness in P A PA P A . Fortunately, we know this cannot occur. Indeed, we don’t need to go as far as the true theory of arithmetic. Any pair of bi-interpretable extensions of P A PA P A , true or not, must determine the same theory.
Solidity is a more technical notion that was uncovered by Enayat in an effort to identify the model theoretic core of tightness.
Definition 2. [7 ] A theory T T T is solid if for all models M 0 , N \mathcal{M}_0,\mathcal{N} M 0 , N and M 1 \mathcal{M}_1 M 1 of T T T , whenever we have
M 0 ▹ p a r N ▹ p a r M 1 \mathcal{M}_0 \triangleright_{\mathrm{par}} \mathcal{N} \triangleright_{\mathrm{par}} \mathcal{M}_1 M 0 ▹ par N ▹ par M 1 and an isomorphism f : M 0 ≅ M 1 f:\mathcal{M}_0 \cong\mathcal{M}_1 f : M 0 ≅ M 1 that is (parametrically) definable over M 0 \mathcal{M}_0 M 0 , then there is another isomorphism g : M 0 ≅ N g:\mathcal{M}_0 \cong\mathcal{N} g : M 0 ≅ N that is (parametrically) definable over M 0 \mathcal{M}_0 M 0 .
It is not difficult to show that a solid theory must be tight.6 Indeed, proving solidity is the main pathway to establishing the tightness of a theory. However, the definition can also be given a more familiar mathematical gloss. The definition above is nicely understood as taking place in the class, mod ( T ) \operatorname{mod}(T) mod ( T ) , of models of T T T . The antecedent clauses of the definition require that M 0 \mathcal{M}_0 M 0 and M 1 \mathcal{M}_1 M 1 are “visibly” isomorphic to each other. Given this, we might as well treat them as “identical.” The arrangement of M 0 , N \mathcal{M}_0,\mathcal{N} M 0 , N and M 1 \mathcal{M}_1 M 1 then tells us that there is a way of interpreting a model N \mathcal{N} N in M 0 \mathcal{M}_0 M 0 from which we can then interpret M 0 \mathcal{M}_0 M 0 (up to isomorphism) again. We thus, have a kind of structure preserving map, known as a retraction, from M 0 \mathcal{M}_0 M 0 to N \mathcal{N} N . It preserves structure in the sense that M 0 \mathcal{M}_0 M 0 can still be recovered from N \mathcal{N} N (up to isomorphism). Solidity then addresses whether such maps can be non-trivial ; i.e., is the output, N \mathcal{N} N , distinct from the input, M 0 \mathcal{M}_0 M 0 (up to isomorphism). If we can find an arrangement of models of T T T where the output is distinct (up to isomorphism), T T T is not solid. Thus, intuitively speaking, solidity tells us that mod ( T ) \operatorname{mod}(T) mod ( T ) has no non-trivial structure preserving self-interpretations.
KP is neither solid nor tight
Let’s move to our first batch of results. Let K P KP K P be the Kripke-Platek set theory using Full Set Induction.7 Our target theorem is the following.
Theorem 3. K P KP K P is neither solid nor tight.
Since solidity implies tightness, it would suffice for us to merely show that K P KP K P is not tight. However, given that the techniques used below are a little unorthodox, we have opted to give a detailed proof that K P KP K P is not solid first. Then we adapt that proof to the more general claim that K P KP K P is not tight. We think this will be helpful as the proof that K P KP K P is not solid takes place in the familiar world of the hyperarithmetic sets. By taking our time here and building some intuitions, we believe this will make things much easier for the rest of the paper. There are also techniques developed here that will be useful for the investigation of solidity (independent of tightness).
Solidity failure
We start by sketching the idea of the proof. Recall that L ω 1 C K L_{\omega_1^{CK}} L ω 1 C K is the smallest model of K P KP K P in the sense that it is the intersection of all ω \omega ω -models of that theory. To save a little clutter, let’s write N N N instead of L ω 1 C K L_{\omega_1^{CK}} L ω 1 C K . We plan to show that N N N can define a sufficiently generic Cohen real c c c and, using that, a version of the corresponding generic extension, N [ c ] N[c] N [ c ] . Thus, it can be seen that we have
N ▹ N [ c ] ▹ L N [ c ] . N \triangleright N[c] \triangleright L^{N[c]}. N ▹ N [ c ] ▹ L N [ c ] .
Moreover, we shall ensure that N N N is able to define an isomorphism η : N ≅ L N [ c ] \eta: N \cong L^{N[c]} η : N ≅ L N [ c ] , while, of course, N ≇ N [ c ] N \not\cong N[c] N ≅ N [ c ] . Thus, we shall see that K P KP K P is not solid.
This ability to define a generic is a little unusual and warrants some discussion about what that means and how it will be done. First, observe that c ⊆ ω c \subseteq\omega c ⊆ ω must be defined as a proper class over N N N rather than a set. Otherwise, we’d fall into the standard contradiction where the complement of the generic filter associated with c c c is a dense set missed by the filter. Second, we note that in order to ensure this, the complexity of the definition of c c c must be greater than that of the underlying Separation Axiom. To see this, note that in the presence of the full axiom of Separation, if c c c is definable then it can be separated as a subset of ω \omega ω . Fortunately, we only have Δ 1 \Delta_1 Δ 1 -Separation available in N N N . Thirdly, in order to obtain a generic we wish to follow the standard Baire-Category strategy. As such, we want the dense sets of A d d ( ω , 1 ) Add(\omega,1) A dd ( ω , 1 ) to be definably countable so that we can run a version of the standard inductive argument. This rules out theories that satisfy full Replacement. Fortunately, we only have Σ 1 \Sigma_1 Σ 1 -Collection in N N N . Fourth and finally, note that in order for N [ c ] N[c] N [ c ] to satisfy K P KP K P , and in particular, Σ 1 \Sigma_1 Σ 1 -Collection, an ordinary generic filter meeting all dense subsets of A d d ( ω , 1 ) Add(\omega,1) A dd ( ω , 1 ) that are elements of N N N will not suffice.8 We shall thus introduce a stronger notion of genericity.
With the sketch complete, let us fix our convention for measuring the complexity of formulae. We use prenex formulae: all quantifiers are at the front, followed by a quantifier-free formula. We count alternating blocks of quantifiers, bounded or unbounded, as far as the last unbounded quantifier; any bounded quantifiers after it do not contribute to the count. Thus ∀ x ∃ y ∈ z ∀ w ψ \forall x\exists y \in z\forall w\ \psi ∀ x ∃ y ∈ z ∀ w ψ , with ψ \psi ψ bounded, is Π 3 \Pi_3 Π 3 . A formula with only bounded quantifiers is Δ 0 \Delta_0 Δ 0 . When obtaining a prenex formula, we first expand bounded quantifiers with their usual restrictions as necessary and then use ordinary logical equivalences. This respects empty bounds and requires no Collection. The classes Σ k \Sigma_k Σ k and Π k \Pi_k Π k below use this convention, with harmless padding by unused quantifiers allowed.
Let us say that a formula is B Σ k B\Sigma_k B Σ k if it is a finite Boolean combination of Σ k \Sigma_k Σ k formulae. A subset of N N N is B Σ k B\Sigma_k B Σ k if it is definable by such a formula, possibly using parameters from N N N . Since this paper is focused on interpretability and thus on definability without parameters, whenever we say that an object is definable, we mean definable without parameters; we shall always say when parameters are required.
Definition 4. Let P \mathbb{P} P be a poset. We say that G ⊆ P G \subseteq\mathbb{P} G ⊆ P is B Σ k B\Sigma_k B Σ k -generic over N N N if G G G is a filter on P \mathbb{P} P and for all B Σ k B\Sigma_k B Σ k dense subsets D D D of P \mathbb{P} P , G ∩ D ≠ ∅ G \cap D \ne\varnothing G ∩ D = ∅ .
We adopt the common assumption that forcing posets have a greatest condition, which we denote as 1 1 1 . We assume that ⊩ \Vdash ⊩ is the syntactic forcing relation used in [21 ] . Note that we cannot uniformly define the forcing relation for arbitrary formulae, since this would contradict Tarski’s theorem. For bounded formulae, forcing is uniformly Δ 1 \Delta_1 Δ 1 -definable over K P KP K P . For higher formulae, we shall use a uniform finite bound. For k ∈ ω k \in\omega k ∈ ω , let
b ( k ) = 2 k + 3. b(k)=2k+3. b ( k ) = 2 k + 3.
For each fixed k k k , forcing for B Σ k B\Sigma_k B Σ k formulae is uniformly Δ b ( k ) \Delta_{b(k)} Δ b ( k ) -definable over K P KP K P . The definition is uniform in the formula code, the tuple of names, the condition and the forcing poset. We prove this bound below, after recalling the density lemma. The bound is chosen for convenience; we do not claim that it is optimal.
Using a suitably generic G ⊆ P G \subseteq\mathbb{P} G ⊆ P , we can then define a generic extension of the ground model. However, given that our eventual goal is to use a definable generic and interpret the generic extension, we cannot use the familiar V a l Val V a l function since that construction would try (and fail) to collapse the generic extension in the ground model. As such, we shall use something like an ultrapower construction that interprets our generic extension as a pre-structure. Thus, we have a structure where the identity relation symbol, = = = , is interpreted as the congruence relation ≈ ∗ \approx^{*} ≈ ∗ .
Definition 5. For G ⊆ P G \subseteq\mathbb{P} G ⊆ P , let N P / G = ⟨ N ∗ , ∈ ∗ , ≈ ∗ ⟩ \mathbb{N}^{\mathbb{P}}/G = \langle N^{*}, \in^{*}, \approx^{*}\rangle N P / G = ⟨ N ∗ , ∈ ∗ , ≈ ∗ ⟩ where:
N ∗ = N P N^{*} = N^{\mathbb{P}} N ∗ = N P ;
x ˙ ∈ ∗ y ˙ \dot{x} \in^{*} \dot{y} x ˙ ∈ ∗ y ˙ iff ∃ p ∈ G p ⊩ x ˙ ∈ y ˙ \exists p \in G\ p \Vdash\dot{x} \in\dot{y} ∃ p ∈ G p ⊩ x ˙ ∈ y ˙ , for all x ˙ , y ˙ ∈ N P \dot{x},\dot{y} \in N^{\mathbb{P}} x ˙ , y ˙ ∈ N P ; and
x ˙ ≈ ∗ y ˙ \dot{x} \approx^{*} \dot{y} x ˙ ≈ ∗ y ˙ iff ∃ p ∈ G p ⊩ x ˙ = y ˙ \exists p \in G\ p \Vdash\dot{x} = \dot{y} ∃ p ∈ G p ⊩ x ˙ = y ˙ , for all x ˙ , y ˙ ∈ N P \dot{x},\dot{y} \in N^{\mathbb{P}} x ˙ , y ˙ ∈ N P .
Note that ≈ ∗ \approx^{*} ≈ ∗ is an equivalence relation that is a congruence for ∈ ∗ \in^{*} ∈ ∗ .
Given that N N N satisfies V = L V = L V = L , we could also define this as a genuine structure by using L L L -least witnesses. However, for our purposes this is more trouble than it’s worth. Observe that if we have such a G G G definable over N N N without parameters, then N ∗ N^{*} N ∗ , ∈ ∗ \in^{*} ∈ ∗ and ≈ ∗ \approx^{*} ≈ ∗ are also all definable without parameters over N N N . We may then prove a version of the truth lemma for B Σ k B\Sigma_k B Σ k formulae using a B Σ b ( k ) B\Sigma_{b(k)} B Σ b ( k ) -generic filter. First we recall a standard, but very useful, fact about syntactic forcing.
Fact 6. Let φ \varphi φ be a fixed formula for which the syntactic forcing relation has been defined. Then K P KP K P proves, for every forcing poset P \mathbb{P} P and every p ∈ P p \in\mathbb{P} p ∈ P , that the following are equivalent: 9
p ⊩ φ p \Vdash\varphi p ⊩ φ ; and
{ q ∈ P ∣ q ⊩ φ } \{q \in\mathbb{P} \mid q \Vdash\varphi\} { q ∈ P ∣ q ⊩ φ } is dense below p p p .
Lemma 7. (Uniform forcing bound.) For each fixed k ∈ ω k \in\omega k ∈ ω , forcing for B Σ k B\Sigma_k B Σ k formulae is uniformly Δ b ( k ) \Delta_{b(k)} Δ b ( k ) -definable over K P KP K P . For bounded formulae alone, the uniform bound is Δ 1 \Delta_1 Δ 1 .
Proof. We first consider prenex formulae with at most r r r alternating blocks before the final bounded formula. We show, by induction on r r r , that their forcing relation has both Σ 2 r + 1 \Sigma_{2r+1} Σ 2 r + 1 and Π 2 r + 1 \Pi_{2r+1} Π 2 r + 1 definitions, uniformly in the formula code and the other arguments. When r = 0 r = 0 r = 0 , this is the usual uniform Δ 1 \Delta_1 Δ 1 definition of bounded forcing.
Suppose the assertion holds for r r r , and let h = 2 r + 1 h = 2r + 1 h = 2 r + 1 . For a universal block we have
p ⊩ ∀ x ˉ ψ ( x ˉ , τ ˉ ) ⟺ ∀ σ ˉ p ⊩ ψ ( σ ˉ , τ ˉ ) , p \Vdash\forall\bar{x}\,\psi(\bar{x},\bar{\tau}) \quad\Longleftrightarrow\quad\forall\bar{\sigma}\ p \Vdash\psi(\bar{\sigma},\bar{\tau}), p ⊩ ∀ x ˉ ψ ( x ˉ , τ ˉ ) ⟺ ∀ σ ˉ p ⊩ ψ ( σ ˉ , τ ˉ ) ,
where σ ˉ \bar{\sigma} σ ˉ ranges over tuples of names of the required length. Using the Π h \Pi_h Π h definition of forcing for ψ \psi ψ , the right-hand side is Π h \Pi_h Π h .
For an existential block we use density once for the entire block:
p ⊩ ∃ x ˉ ψ ( x ˉ , τ ˉ ) ⟺ ∀ q ≤ p ∃ u ˉ ≤ q ∃ σ ˉ u ⊩ ψ ( σ ˉ , τ ˉ ) . p \Vdash\exists\bar{x}\,\psi(\bar{x},\bar{\tau}) \quad\Longleftrightarrow\quad\forall q \leq p\ \exists\bar{u} \leq q\ \exists\bar{\sigma}\ u \Vdash\psi(\bar{\sigma},\bar{\tau}). p ⊩ ∃ x ˉ ψ ( x ˉ , τ ˉ ) ⟺ ∀ q ≤ p ∃ u ˉ ≤ q ∃ σ ˉ u ⊩ ψ ( σ ˉ , τ ˉ ) .
This is equivalent to the successive existential forcing clauses. Given a condition below p p p , refine it successively to obtain the finitely many witnessing names. Conversely, a condition forcing ψ \psi ψ with those names forces the existential sentence, so the density lemma applies. A tuple of names is coded by one set. Full Set Induction proves the existence of the required finite sequences, including when their length is internally finite in a nonstandard model.
Using the Σ h \Sigma_h Σ h definition of forcing for ψ \psi ψ , everything after ∀ q ≤ p \forall q \leq p ∀ q ≤ p has a Σ h \Sigma_h Σ h definition. Under our counting convention the whole expression is therefore Π h + 1 \Pi_{h+1} Π h + 1 . By adding an unused quantifier, it has both Σ h + 2 \Sigma_{h+2} Σ h + 2 and Π h + 2 \Pi_{h+2} Π h + 2 definitions. These bounds also cover the universal case. The tests for formula codes and tuples of names are Δ 1 \Delta_1 Δ 1 and can be written in the appropriate form without increasing the bound. This proves the induction.
Finally, a finite Boolean combination of Σ k \Sigma_k Σ k formulae can be put into prenex form with at most k + 1 k+1 k + 1 alternating blocks before a bounded formula. Move negations inward, rename bound variables, and pad the formulae to a common alternating pattern before joining their quantifier blocks. This is an effective logical manipulation, not an application of Collection. Applying the preceding induction with r = k + 1 r=k+1 r = k + 1 gives
2 ( k + 1 ) + 1 = b ( k ) . 2(k+1)+1=b(k). 2 ( k + 1 ) + 1 = b ( k ) .
The ordinary logical laws for syntactic forcing identify forcing for the original formula with forcing for this prenex presentation. The resulting definition is uniform in its code. Correctness is asserted for each standard formula; accepting internal formula codes as arguments does not assert an external truth relation for nonstandard formulae. □ \square □
Lemma 8. ( B Σ k B\Sigma_k B Σ k -truth lemma.) Suppose k ≥ 1 k \geq1 k ≥ 1 and G G G is B Σ b ( k ) B\Sigma_{b(k)} B Σ b ( k ) -generic over N N N . Then, for every B Σ k B\Sigma_k B Σ k formula φ \varphi φ and every appropriate tuple τ ˉ \bar{\tau} τ ˉ of names from N N N ,
N P / G ⊨ φ ( τ ˉ ) ⟺ ∃ p ∈ G ( p ⊩ φ ( τ ˉ ) ) N . N^{P}/G \models\varphi(\bar{\tau}) \quad\Longleftrightarrow\quad\exists p \in G\ (p \Vdash\varphi(\bar{\tau}))^{N}. N P / G ⊨ φ ( τ ˉ ) ⟺ ∃ p ∈ G ( p ⊩ φ ( τ ˉ ) ) N . For bounded formulae, B Σ 1 B\Sigma_1 B Σ 1 -genericity suffices.
Proof. Proceed by simultaneous induction on formulae and their negations. For Δ 0 \Delta_0 Δ 0 formulae, the atomic cases are immediate from the definitions of ∈ ∗ \in^{*} ∈ ∗ and ≈ ∗ \approx^{*} ≈ ∗ . Conjunction follows from directedness of G G G . For negation, use the dense deciding class
D ψ = { q ∈ P : q ⊩ ψ or q ⊩ ¬ ψ } . D_{\psi}=\{q\in P:q\Vdash\psi\mathbin{\text{ or }}q\Vdash\neg\psi\}. D ψ = { q ∈ P : q ⊩ ψ or q ⊩ ¬ ψ } .
Since forcing for bounded formulae is Δ 1 \Delta_1 Δ 1 -definable, D ψ D_{\psi} D ψ is met by G G G , and the usual compatibility argument gives the negation clause.
The bounded-universal case uses the analogous deciding-class argument. We let
D 0 = { q : q ⊩ ∀ y ∈ z ˇ ψ ( y ˙ ) } and D 1 = { q : ∃ y ˙ q ⊩ ¬ ( y ˙ ∈ z ˇ → ψ ( y ˙ ) ) } . D_0=\{q:q\Vdash\forall y\in\check{z}\,\psi(\dot{y})\}\text{ and }D_1=\{q:\exists\dot{y}\ q\Vdash\neg(\dot{y}\in\check{z}\to\psi(\dot{y}))\}. D 0 = { q : q ⊩ ∀ y ∈ z ˇ ψ ( y ˙ )} and D 1 = { q : ∃ y ˙ q ⊩ ¬ ( y ˙ ∈ z ˇ → ψ ( y ˙ ))} .
The union is dense and Σ 1 \Sigma_1 Σ 1 -definable. If the bounded universal is true in the quotient, the inductive hypothesis excludes the second alternative, so some condition in G G G forces the bounded universal. Conversely, if a condition in G G G forces it, the forcing clauses and the inductive hypothesis show that it holds of every member of z ˇ \check{z} z ˇ in the quotient. This establishes the bounded case.
For the higher levels, use the prenex presentations from the uniform forcing-bound lemma. All the forcing relations needed in the induction have both Σ b ( k ) \Sigma_{\mathrm{b}(k)} Σ b ( k ) and Π b ( k ) \Pi_{\mathrm{b}(k)} Π b ( k ) definitions. In the negation case the same deciding class D ψ D_\psi D ψ is therefore Σ b ( k ) \Sigma_{\mathrm{b}(k)} Σ b ( k ) -definable, so it is met by G G G . For a universal formula, use
D 0 = { q : q ⊩ ∀ y ψ ( y ) } and D 1 = { q : ∃ y ˙ q ⊩ ¬ ψ ( y ˙ ) } . D_0=\{q:q\Vdash\forall y\ \psi(y)\}\text{ and }D_1=\{q:\exists\dot y\ q\Vdash\neg\psi(\dot y)\}. D 0 = { q : q ⊩ ∀ y ψ ( y )} and D 1 = { q : ∃ y ˙ q ⊩ ¬ ψ ( y ˙ )} .
Both classes have Σ b ( k ) \Sigma_{\mathrm{b}(k)} Σ b ( k ) definitions: for D 1 D_1 D 1 , use the Σ b ( k ) \Sigma_{\mathrm{b}(k)} Σ b ( k ) definition of forcing before adjoining the existential name quantifier. Their union is dense by the forcing clauses and the density lemma.
If the universal formula is true in the quotient, the inductive hypothesis rules out the second alternative. Genericity then supplies a condition in G G G forcing the universal formula. Conversely, suppose p ∈ G p\in G p ∈ G forces ∀ y ψ ( y ) \forall y\ \psi(y) ∀ y ψ ( y ) . Then p ⊩ ψ ( y ˙ ) p\Vdash\psi(\dot y) p ⊩ ψ ( y ˙ ) for every name y ˙ ∈ N \dot y\in N y ˙ ∈ N , so the inductive hypothesis shows that ψ \psi ψ holds of every element of the quotient. Existential quantification is handled by expressing ∃ y ψ \exists y\ \psi ∃ y ψ as ¬ ∀ y ¬ ψ \neg\forall y\ \neg\psi ¬∀ y ¬ ψ . Repeated quantifiers of the same kind are handled by induction on their finite length. This proves the equivalence for the prenex formulae under consideration; the propositional cases give finite Boolean combinations, and logical equivalence with the original formula completes the proof. □
Our next goal is to show that N P / G N^{\mathbb{P}}/G N P / G satisfies K P KP K P . We start by observing that standard arguments establish that K P KP K P can prove that all of its axioms are forced.
Lemma 9. For each fixed axiom instance φ \varphi φ of K P KP K P , K P KP K P proves that, for every forcing poset P \mathbb{P} P ,
1 ⊩ P φ . 1\Vdash_{\mathbb{P}}\varphi. 1 ⊩ P φ .
We leave the proof of this to the reader although they might like to consult [3 ] or [21 ] . As our next step toward showing N P / G N^{\mathbb{P}}/G N P / G satisfies K P KP K P , we first show that it satisfies Full Set Induction.
Lemma 10. For all P ∈ N P\in N P ∈ N and G G G that is B Σ 1 1 B\Sigma^1_1 B Σ 1 1 -generic over N N N , N P / G N^{\mathbb{P}}/G N P / G satisfies Full Set Induction.
Proof. It will suffice to show that N P / G N^{\mathbb{P}}/G N P / G is externally well-founded. We first record a consequence of the forcing clause for membership. Suppose that y ˙ ∈ ∗ x ˙ \dot y\in^*\dot x y ˙ ∈ ∗ x ˙ and choose p ∈ G p\in G p ∈ G such that p ⊩ y ˙ ∈ x ˙ p\Vdash\dot y\in\dot x p ⊩ y ˙ ∈ x ˙ . Let
D = { q ≤ p ∣ ∃ ⟨ z ˙ , r ⟩ ∈ x ˙ ( q ≤ r ∧ q ⊩ y ˙ = z ˙ ) } . D=\{q\leq p\mid\exists\langle\dot z,r\rangle\in\dot x\ (q\leq r\land q\Vdash\dot y=\dot z)\}. D = { q ≤ p ∣ ∃ ⟨ z ˙ , r ⟩ ∈ x ˙ ( q ≤ r ∧ q ⊩ y ˙ = z ˙ )} .
By the syntactic forcing clause for membership, D D D is dense below p p p . Moreover, since forcing for atomic equality is Δ 1 \Delta_1 Δ 1 -definable, D D D is Δ 1 \Delta_1 Δ 1 -definable over N N N with parameters. Since p ∈ G p\in G p ∈ G and D D D is dense below p p p , we may fix some q ∈ G ∩ D q\in G\cap D q ∈ G ∩ D and z ˙ ∈ dom ( x ˙ ) \dot z\in\operatorname{dom}(\dot x) z ˙ ∈ dom ( x ˙ ) such that q ⊩ y ˙ = z ˙ q\Vdash\dot y=\dot z q ⊩ y ˙ = z ˙ . Thus
y ˙ ∈ ∗ x ˙ ⟹ ∃ z ˙ ∈ dom ( x ˙ ) z ˙ ≈ ∗ y ˙ . \dot y\in^*\dot x\Longrightarrow\exists\dot z\in\operatorname{dom}(\dot x)\ \dot z\approx^*\dot y. y ˙ ∈ ∗ x ˙ ⟹ ∃ z ˙ ∈ dom ( x ˙ ) z ˙ ≈ ∗ y ˙ .
Now suppose toward a contradiction that there is an infinite descending sequence
x ˙ 0 ∋ ∗ x ˙ 1 ∋ ∗ x ˙ 2 ∋ ∗ ⋯ \dot x_0\ni^*\dot x_1\ni^*\dot x_2\ni^*\cdots x ˙ 0 ∋ ∗ x ˙ 1 ∋ ∗ x ˙ 2 ∋ ∗ ⋯
Recursively choose names y ˙ n \dot y_n y ˙ n such that y ˙ n ≈ ∗ x ˙ n \dot y_n\approx^*\dot x_n y ˙ n ≈ ∗ x ˙ n and
y ˙ n + 1 ∈ dom ( y ˙ n ) \dot y_{n+1}\in\operatorname{dom}(\dot y_n) y ˙ n + 1 ∈ dom ( y ˙ n )
for every n ∈ ω n \in\omega n ∈ ω . Start with y ˙ 0 = x ˙ 0 \dot{y}_0=\dot{x}_0 y ˙ 0 = x ˙ 0 . Given y ˙ n \dot{y}_n y ˙ n , the congruence of ≈ ∗ \mathrel{\approx^*} ≈ ∗ gives x ˙ n + 1 ∈ ∗ y ˙ n \dot{x}_{n+1}\in{}^*\dot{y}_n x ˙ n + 1 ∈ ∗ y ˙ n , so the preceding observation supplies the required y ˙ n + 1 \dot{y}_{n+1} y ˙ n + 1 . Consequently,
rank N ( y ˙ n + 1 ) < rank N ( y ˙ n ) \operatorname{rank}^{N}(\dot{y}_{n+1})<\operatorname{rank}^{N}(\dot{y}_n) rank N ( y ˙ n + 1 ) < rank N ( y ˙ n )
for every n ∈ ω n \in\omega n ∈ ω . Since N = L ω 1 C K N=L_{\omega_1^{CK}} N = L ω 1 C K is well-founded, these are genuine ordinals, giving an impossible infinite descending sequence of ordinals. Therefore N P / G N^{\mathbb{P}}/G N P / G is well-founded and hence satisfies Full Set Induction. □
It is then easy to verify that N P / G N^{\mathbb{P}}/G N P / G satisfies K P KP K P when G G G is sufficiently generic.
Lemma 11. For all P ∈ N \mathbb{P}\in N P ∈ N and all G ⊆ P G\subseteq\mathbb{P} G ⊆ P that are B Σ b ( 3 ) B\Sigma_{\mathsf{b}(3)} B Σ b ( 3 ) -generic over N N N , the quotient N P / G N^{\mathbb{P}}/G N P / G satisfies K P KP K P .
Proof. By Lemma 9, every fixed axiom instance of K P KP K P is forced by P \mathbb{P} P . The basic axioms and the instances of Δ 0 \Delta_0 Δ 0 -Separation have complexity below Π 3 \Pi_3 Π 3 . The relevant point is Δ 0 \Delta_0 Δ 0 -Collection: its instances can be expressed as Π 3 \Pi_3 Π 3 sentences. Thus every axiom instance other than Full Set Induction is a Boolean combination of Σ 3 \Sigma_3 Σ 3 sentences. Since b ( 3 ) = 9 \mathsf{b}(3)=9 b ( 3 ) = 9 , the revised truth lemma transfers all these forced axioms to N P / G N^{\mathbb{P}}/G N P / G . Finally, B Σ b ( 3 ) B\Sigma_{\mathsf{b}(3)} B Σ b ( 3 ) -genericity implies B Σ 1 B\Sigma_1 B Σ 1 -genericity, so Lemma 10 applies. Therefore N P / G ⊨ K P N^{\mathbb{P}}/G\models KP N P / G ⊨ K P . □
Next we obtain a countable enumeration of the universe of N N N that is definable over N N N .
Lemma 12. There is a parameter-free B Σ 1 B\Sigma_1 B Σ 1 -definable, and hence Δ 2 \Delta_2 Δ 2 -definable, class function f : ω ↠ N f:\omega\twoheadrightarrow N f : ω ↠ N .
Proof. Working in N N N , fix the standard partial Σ 1 \Sigma_1 Σ 1 parametrization n ↦ E n n\mapsto E_n n ↦ E n of hyperarithmetic binary relations on ω \omega ω , each with a distinguished root, using numerical indices for witnessed hyperarithmetic computations.10 Call n n n good if E n E_n E n is defined and below its root, it is extensional and well-founded in the sense that there is a strictly order preserving map in N N N between the segment below its root and the ordinals of N N N . Let Val ( n , x ) \operatorname{Val}(n,x) Val ( n , x ) assert n n n is good and that the transitive collapse of E n E_n E n sends the root to x x x . By standard arguments, we see that Val ( n , x ) \operatorname{Val}(n,x) Val ( n , x ) is Σ 1 \Sigma_1 Σ 1 and functional. Let
f ( n ) = { the unique x such that Val ( n , x ) , if n is good , ∅ , otherwise . f(n)=
\begin{cases}
\text{the unique }x\text{ such that }\operatorname{Val}(n,x), & \text{if }n\text{ is good},\\
\varnothing, & \text{otherwise}.
\end{cases} f ( n ) = { the unique x such that Val ( n , x ) , ∅ , if n is good , otherwise .
It should be clear then that f : ω → N f:\omega\to N f : ω → N . The graph of f f f is defined by
F ( n , x ) ↔ n ∈ ω ∧ ( Val ( n , x ) ∨ ( ¬ Good ( n ) ∧ x = ∅ ) ) . F(n,x)\leftrightarrow n\in\omega\land\bigl(\operatorname{Val}(n,x)\lor(\neg\operatorname{Good}(n)\land x=\varnothing)\bigr). F ( n , x ) ↔ n ∈ ω ∧ ( Val ( n , x ) ∨ ( ¬ Good ( n ) ∧ x = ∅ ) ) .
This is a Boolean combination of Σ 1 \Sigma_1 Σ 1 formulae and hence Δ 2 \Delta_2 Δ 2 . Finally, f f f is surjective by the well-known fact that every set in N N N admits a rooted hyperarithmetic code of the kind described above. □
We then use this enumeration to define suitably generic sets.
Lemma 13. For all k ∈ ω k \in\omega k ∈ ω and P ∈ N \mathbb{P} \in N P ∈ N , there is some G ⊆ P G \subseteq\mathbb{P} G ⊆ P that is definable over N N N without parameters and is B Σ k B\Sigma_k B Σ k -generic over N N N . For k ≥ 1 k \ge1 k ≥ 1 , G G G may be chosen Δ k + 2 \Delta_{k+2} Δ k + 2 -definable; for k = 0 k = 0 k = 0 it may be chosen Δ 2 \Delta_2 Δ 2 -definable.
Proof. Fix k ∈ ω k \in\omega k ∈ ω and P ∈ N \mathbb{P} \in N P ∈ N . Since N ⊨ V = L N \models V = L N ⊨ V = L , fix the canonical parameter-free definable well-order < L <_{L} < L of N N N . Let f : ω ↠ N f : \omega\twoheadrightarrow N f : ω ↠ N be as in Lemma 12. Choose m ∈ ω m \in\omega m ∈ ω with f ( m ) = P f(m) = \mathbb{P} f ( m ) = P . Since m m m is a fixed natural number, it can be represented by its numeral in the defining formula. Thus the construction below does not use P \mathbb{P} P as a parameter. Fix an effective enumeration
⟨ Φ i ( x , y ) ∣ i ∈ ω ⟩ \langle\Phi_i(x,y) \mid i \in\omega\rangle ⟨ Φ i ( x , y ) ∣ i ∈ ω ⟩ of the B Σ k B\Sigma_k B Σ k formulae with one object variable and one parameter variable. Using a recursive pairing function, define
e ( ⟨ i , j ⟩ ) = ⟨ i , f ( j ) ⟩ . e(\langle i,j\rangle)=\langle i,f(j)\rangle. e (⟨ i , j ⟩) = ⟨ i , f ( j )⟩ . Thus every pair consisting of a B Σ k B\Sigma_k B Σ k formula and a parameter from N N N occurs in the range of e e e . Let Sat B Σ k \operatorname{Sat}_{B\Sigma_k} Sat B Σ k be the uniform satisfaction predicate for these formulae. Thus
N ⊨ Φ i ( q , b ) ⟺ N ⊨ Sat B Σ k ( i , q , b ) . N \models\Phi_i(q,b) \Longleftrightarrow N \models\operatorname{Sat}_{B\Sigma_k}(i,q,b). N ⊨ Φ i ( q , b ) ⟺ N ⊨ Sat B Σ k ( i , q , b ) . We now give our modification of the standard Baire category argument. Thus, we recursively define a descending sequence
⟨ p n ∣ n ∈ ω ⟩ \langle p_n \mid n \in\omega\rangle ⟨ p n ∣ n ∈ ω ⟩ in P \mathbb{P} P that hits every dense B Σ k B\Sigma_k B Σ k subset of P \mathbb{P} P . Let p 0 p_0 p 0 be the top element of P \mathbb{P} P . Then suppose p n p_n p n has been defined and e ( n ) = ⟨ i , b ⟩ e(n)=\langle i,b\rangle e ( n ) = ⟨ i , b ⟩ . If there is q ≤ p n q \le p_n q ≤ p n such that
N ⊨ Sat B Σ k ( i , q , b ) , N \models\operatorname{Sat}_{B\Sigma_k}(i,q,b), N ⊨ Sat B Σ k ( i , q , b ) , let p n + 1 p_{n+1} p n + 1 be the < L <_{L} < L -least such q q q ; otherwise let p n + 1 = p n p_{n+1}=p_n p n + 1 = p n . This is enough to ensure that every dense B Σ k B\Sigma_k B Σ k subset of P \mathbb{P} P is hit by some p n p_n p n . Finally let
G = { q ∈ P ∣ ∃ n ∈ ω ( p n ≤ q ) } G=\{q\in\mathbb{P}\mid\exists n\in\omega\ (p_n\le q)\} G = { q ∈ P ∣ ∃ n ∈ ω ( p n ≤ q )} which clearly satisfies the requirements of the lemma.
For the complexity calculation, first suppose k ≥ 1 k \ge1 k ≥ 1 . Use the uniform partial truth predicates for the prenex Σ k \Sigma_k Σ k and Π k \Pi_k Π k formulae under our counting convention. Evaluating a finite Boolean combination gives Σ k + 1 \Sigma_{k+1} Σ k + 1 definitions of both its truth and its falsity: record the finite truth-value assignment and verify its positive and negative constituents. Hence Sat B Σ k \operatorname{Sat}_{B\Sigma_k} Sat B Σ k is Δ k + 1 \Delta_{k+1} Δ k + 1 . The relation saying that q q q is the selected successor of p p p is Π k + 1 \Pi_{k+1} Π k + 1 : use the Π k + 1 \Pi_{k+1} Π k + 1 presentations to verify that q q q qualifies, that no earlier condition qualifies, or that no condition qualifies and q = p q=p q = p . The enumeration values can be specified universally using the total B Σ 1 B\Sigma_1 B Σ 1 graph of f f f . Consequently, checking that a finite sequence begins with p 0 p_0 p 0 and follows the recursion is a Π k + 1 \Pi_{k+1} Π k + 1 condition, so asserting the existence of such a sequence of length n + 1 n+1 n + 1 ending in p p p gives a Σ k + 2 \Sigma_{k+2} Σ k + 2 definition of p = p n p=p_n p = p n . For k = 0 k=0 k = 0 , bounded truth and < L <_{L} < L are Δ 1 \Delta_1 Δ 1 ; recording the finitely many enumeration values together with such a finite sequence instead gives a Σ 2 \Sigma_2 Σ 2 definition. The displayed definition of G G G therefore gives a Σ k + 2 \Sigma_{k+2} Σ k + 2 definition for k ≥ 1 k\ge1 k ≥ 1 , and a Σ 2 \Sigma_2 Σ 2 definition for k = 0 k=0 k = 0 . To obtain the complementary definition, for each q ∈ P q\in\mathbb{P} q ∈ P use the dense Δ 0 \Delta_0 Δ 0 class
D q = { p ∈ P : p ≤ q or p ⊥ q } . D_q=\{p\in\mathbb{P}:p\le q\text{ or }p\perp q\}. D q = { p ∈ P : p ≤ q or p ⊥ q } . Since the constructed filter meets D q D_q D q , we have q ∉ G q\notin G q ∈ / G iff some $p_n
is incompatible with q q q . This has the same complexity bound. Thus G G G is Δ k + 2 \Delta_{k+2} Δ k + 2 for k ≥ 1 k \ge1 k ≥ 1 and Δ 2 \Delta_2 Δ 2 for k = 0 k = 0 k = 0 . Finally, eliminate the parameter P P P using its fixed numeral index under f f f ; this does not increase these bounds.
Since G G G is definable over N N N , N N N can interpret N P / G N^P/G N P / G . We then observe that we may define the required isomorphism between N N N and the constructible universe of N P / G N^P/G N P / G . To make this a little more concrete, we use A d d ( ω , 1 ) Add(\omega,1) A dd ( ω , 1 ) .
Lemma 14. Let G ⊆ A d d ( ω , 1 ) G \subseteq Add(\omega,1) G ⊆ A dd ( ω , 1 ) be a parameter-free definable B Σ b ( 3 ) B\Sigma_{b(3)} B Σ b ( 3 ) -generic filter over N N N , supplied by the preceding generic-construction lemma. Then there is an isomorphism
η : N ≅ L N A d d ( ω , 1 ) / G \eta: N \cong L^{N^{Add(\omega,1)}/G} η : N ≅ L N A dd ( ω , 1 ) / G that is definable over N N N .
Proof. Let
M = N A d d ( ω , 1 ) / G . \mathcal{M} = N^{Add(\omega,1)}/G. M = N A dd ( ω , 1 ) / G .
We first identify the ordinals of M \mathcal{M} M directly. If y ˙ ∈ ∗ x ˙ \dot{y} \in^* \dot{x} y ˙ ∈ ∗ x ˙ , then the syntactic forcing clause for membership and B Σ 1 B\Sigma_1 B Σ 1 -genericity give some z ˙ ∈ dom ( x ˙ ) \dot{z} \in\operatorname{dom}(\dot{x}) z ˙ ∈ dom ( x ˙ ) such that z ˙ ≈ ∗ y ˙ \dot{z} \approx^* \dot{y} z ˙ ≈ ∗ y ˙ . Hence any external descending ∈ ∗ \in^* ∈ ∗ -chain can be represented by names of strictly decreasing N N N -rank.11 Since N = L ω 1 C K N = L_{\omega_1^{CK}} N = L ω 1 C K is well-founded, no such chain exists. Induction on the rank of names also shows that the well-founded rank of an element represented by x ˙ \dot{x} x ˙ is bounded by rank N ( x ˙ ) \operatorname{rank}^N(\dot{x}) rank N ( x ˙ ) . It follows that every ordinal of M \mathcal{M} M has order type below ω 1 C K \omega_1^{CK} ω 1 C K . Conversely, every α < ω 1 C K \alpha< \omega_1^{CK} α < ω 1 C K is represented by [ α ˇ ] G [\check{\alpha}]_G [ α ˇ ] G . Thus M \mathcal{M} M and N N N have the same ordinals. Define a relation E E E over N N N by
x E y ˙ ⟺ ∃ p ∈ G ( p ⊩ x ˇ = y ˙ ) . x E \dot{y} \Longleftrightarrow\exists p \in G\ (p \Vdash\check{x} = \dot{y}). x E y ˙ ⟺ ∃ p ∈ G ( p ⊩ x ˇ = y ˙ ) .
Because G G G and atomic forcing are definable over N N N , so is E E E . On equivalence classes it represents the action of a function such that
η ( x ) = [ x ˇ ] G . \eta(x) = [\check{x}]_G. η ( x ) = [ x ˇ ] G .
The atomic forcing facts for canonical names show that η \eta η is an ∈ \in ∈ -embedding of N N N into M \mathcal{M} M . For each common ordinal α \alpha α , let
C α = { [ x ˇ ] G ∣ x ∈ L α N } . C_\alpha= \{[\check{x}]_G \mid x \in L^N_\alpha\}. C α = {[ x ˇ ] G ∣ x ∈ L α N } .
We show by induction on α \alpha α that C α = L α M C_\alpha= L^\mathcal{M}_\alpha C α = L α M . The limit step is immediate. For the successor step, suppose C α = L α M C_\alpha= L^\mathcal{M}_\alpha C α = L α M . The restriction of η \eta η is an isomorphism between L α N L^N_\alpha L α N and L α M L^\mathcal{M}_\alpha L α M . Therefore the subsets of L α N L^N_\alpha L α N definable over that structure with parameters correspond exactly to the subsets of L α M L^\mathcal{M}_\alpha L α M definable there with the corresponding parameters. Hence, C α + 1 = L α + 1 M C_{\alpha+1} = L^\mathcal{M}_{\alpha+1} C α + 1 = L α + 1 M . Thus the induction holds for every common ordinal. Since N = L ω 1 C K N = L_{\omega_1^{CK}} N = L ω 1 C K and the two structures have the same ordinals, ran ( η ) = L M \operatorname{ran}(\eta) = L^\mathcal{M} ran ( η ) = L M . Consequently η : N ≅ L M \eta: N \cong L^\mathcal{M} η : N ≅ L M , and the relation E E E shows that the isomorphism is definable over N N N .
Finally, we can put all this together to get our first result.
Theorem 15. K P KP K P is not solid.
Proof. Let P = Add ( ω , 1 ) \mathbb{P}=\operatorname{Add}(\omega,1) P = Add ( ω , 1 ) , and let G ⊆ P G\subseteq\mathbb{P} G ⊆ P be the parameter-free definable B Σ b ( 3 ) B\Sigma_{b(3)} B Σ b ( 3 ) -generic filter supplied by Lemma 13. Let
M = N P / G . \mathcal{M}=\mathcal{N}^{\mathbb{P}}/G. M = N P / G .
Because G G G is definable over N \mathcal{N} N , we see that
N ▹ M ▹ L M . \mathcal{N}\triangleright\mathcal{M}\triangleright L^{\mathcal{M}}. N ▹ M ▹ L M .
where the final ▹ \triangleright ▹ follows since Lemma 11 tells us that M ⊨ K P \mathcal{M}\models KP M ⊨ K P and so it can define its version of L L L . Lemma 14 then gives an isomorphism
η : N ≅ L M \eta:\mathcal{N}\cong L^{\mathcal{M}} η : N ≅ L M
that is definable over N \mathcal{N} N . Finally, we see that N ≢ M \mathcal{N}\not\equiv\mathcal{M} N ≡ M since N \mathcal{N} N satisfies V = L V=L V = L while M \mathcal{M} M does not. Thus, N ≇ M \mathcal{N}\not\cong\mathcal{M} N ≅ M and so we see that K P KP K P is not solid. □
Tightness failure
Our next goal is to show that K P KP K P is not tight. The proof will build on the techniques of the previous subsection, but generalize them to the context of arbitrary models of a well-chosen theory, rather than a particular model. For this purpose, we let
S 0 = K P + V = L ω 1 C K . S_0=KP+V=L_{\omega_1^{CK}}. S 0 = K P + V = L ω 1 C K .
The additional axiom may equivalently be expressed as V = L V=L V = L along with the assertion that there are no admissible ordinals. We then define a second extension S 1 S_1 S 1 by saying that the universe is the canonically definable Cohen extension of its constructible universe. The next two lemmas isolate the uniformity required for this definition. First, we observe that arbitrary models of S 0 S_0 S 0 can produce a suitable version of a definable countable enumeration.
Lemma 16. There is a parameter-free formula F ( n , x ) F(n,x) F ( n , x ) such that every M ⊨ S 0 \mathcal{M}\models S_0 M ⊨ S 0 satisfies that F M F^{\mathcal{M}} F M is the graph of a surjective class function
f M : ω M ↠ M . f^{\mathcal{M}}:\omega^{\mathcal{M}}\twoheadrightarrow\mathcal{M}. f M : ω M ↠ M .
Proof. With the internal reading of V = L ω 1 C K V=L_{\omega_1^{CK}} V = L ω 1 C K fixed above, the proof of Lemma 12 formalizes in S 0 S_0 S 0 . The internal witnessed coding construction gives S 0 ⊢ ∀ x ∃ n ∈ ω Val ( n , x ) S_0\vdash\forall x\exists n\in\omega\ \operatorname{Val}(n,x) S 0 ⊢ ∀ x ∃ n ∈ ω Val ( n , x ) . Functionality and the default-value construction are provable in K P KP K P . Hence the same parameter-free formula F F F defines the required surjection in every M ⊨ S 0 \mathcal{M}\models S_0 M ⊨ S 0 . □
We then observe that the required generics can also be defined over models of S 0 S_0 S 0 .
Lemma 17. There is a parameter-free formula γ ( p ) \gamma(p) γ ( p ) such that, for every M ⊨ S 0 \mathcal{M}\models S_0 M ⊨ S 0 ,
G M = { p ∈ Add ( ω , 1 ) M : M ⊨ γ ( p ) } G^{\mathcal{M}}=\{p\in\operatorname{Add}(\omega,1)^{\mathcal{M}}:\mathcal{M}\models\gamma(p)\} G M = { p ∈ Add ( ω , 1 ) M : M ⊨ γ ( p )} is B Σ b ( 3 ) B\Sigma_{b(3)} B Σ b ( 3 ) -generic over M \mathcal{M} M .
Proof. Use the generic construction from Section 2.1, now with the uniform enumeration supplied by the preceding Lemma 16. Thus we enumerate the pairs of B Σ b ( 3 ) B\Sigma_{b(3)} B Σ b ( 3 ) formulae and parameters and recursively form a descending sequence of conditions. At the stage corresponding to a formula-parameter pair, if the class it defines contains an extension of the current condition, choose the < L <_{L} < L -least such extension; otherwise keep the current condition. Full Set Induction proves the existence of every internally finite initial sequence. The filter generated by this sequence meets every B Σ b ( 3 ) B\Sigma_{b(3)} B Σ b ( 3 ) -definable dense class. All parts of this construction are given by fixed formulae and are provable in S 0 S_0 S 0 , so the resulting definition γ \gamma γ is uniform over models of S 0 S_0 S 0 . □
Fix the formula γ \gamma γ from Lemma 17. Let Ψ γ \Psi_\gamma Ψ γ be the sentence asserting that there is a set g g g such that:
p ∈ g p \in g p ∈ g iff p ∈ Add ( ω , 1 ) L ∧ L ⊨ γ ( p ) p \in\operatorname{Add}(\omega,1)^L \land L \models\gamma(p) p ∈ Add ( ω , 1 ) L ∧ L ⊨ γ ( p ) ;
g g g is Add ( ω , 1 ) L \operatorname{Add}(\omega,1)^L Add ( ω , 1 ) L -generic over L L L ;
L L L has no admissible ordinals; and
V = L [ g ] V = L[g] V = L [ g ] .
Since γ \gamma γ is fixed, this is a single first-order sentence. Let
S 1 = K P + Ψ γ . S_1 = KP + \Psi_\gamma. S 1 = K P + Ψ γ .
The set g g g occurring in Ψ γ \Psi_\gamma Ψ γ is unique.
We now verify that the canonical generic extensions of models of S 0 S_0 S 0 satisfy K P KP K P . First we record the form of the truth lemma needed for arbitrary models.
Lemma 18. (Truth lemma for arbitrary models. ) Suppose M ⊨ K P \mathcal{M} \models KP M ⊨ K P , P ∈ M \mathbb{P} \in\mathcal{M} P ∈ M is a forcing poset, and k ≥ 1 k \ge1 k ≥ 1 is standard. If G G G is B Σ b ( k ) B\Sigma_{b(k)} B Σ b ( k ) -generic over M \mathcal{M} M , then, for every standard B Σ k B\Sigma_k B Σ k formula φ \varphi φ and every appropriate tuple τ ˉ \bar{\tau} τ ˉ of M \mathcal{M} M -names,
M P / G ⊨ φ ( τ ˉ ) ⟺ ∃ p ∈ G M ⊨ p ⊩ φ ( τ ˉ ) . \mathcal{M}^{\mathbb{P}}/G \models\varphi(\bar{\tau}) \quad\Longleftrightarrow\quad\exists p \in G\ \mathcal{M} \models p \Vdash\varphi(\bar{\tau}). M P / G ⊨ φ ( τ ˉ ) ⟺ ∃ p ∈ G M ⊨ p ⊩ φ ( τ ˉ ) . For bounded formulae, B Σ 1 B\Sigma_1 B Σ 1 -genericity suffices.
The proof is the same as in Section 2.1: the induction is external on standard formulae and uses only K P KP K P , the forcing clauses, the density lemma and the indicated genericity. It does not require the ground model to be externally well-founded.
As before, we treat Full Set Induction separately. Here definability of the generic is used to apply Full Set Induction in the ground model.
Lemma 19. Suppose M ⊨ K P \mathcal{M} \models KP M ⊨ K P , P ∈ M \mathbb{P} \in\mathcal{M} P ∈ M , and G ⊆ P G \subseteq\mathbb{P} G ⊆ P is definable over M \mathcal{M} M and B Σ 1 B\Sigma_1 B Σ 1 -generic over M \mathcal{M} M . Then M P / G \mathcal{M}^{\mathbb{P}}/G M P / G satisfies Full Set Induction.
Proof. Let N = M P / G \mathcal{N} = \mathcal{M}^{\mathbb{P}}/G N = M P / G and suppose some instance of Full Set Induction fails in N \mathcal{N} N . For a formula witnessing this failure, let C \mathcal{C} C be the class of names satisfying that formula in N \mathcal{N} N . Since G G G is definable over M \mathcal{M} M , the class C \mathcal{C} C is definable over M \mathcal{M} M . By Full Set Induction in M \mathcal{M} M , choose x ˙ ∈ C \dot{x} \in\mathcal{C} x ˙ ∈ C of minimal M \mathcal{M} M -rank. Failure of Set Induction gives y ˙ ∈ C \dot{y} \in\mathcal{C} y ˙ ∈ C with y ˙ ∈ ∗ x ˙ \dot{y} \in^{*} \dot{x} y ˙ ∈ ∗ x ˙ . Choose p ∈ G p \in G p ∈ G with p ⊩ y ˙ ∈ x ˙ p \Vdash\dot{y} \in\dot{x} p ⊩ y ˙ ∈ x ˙ . By the forcing clause for membership, the class of q ≤ p q \leq p q ≤ p for which there is some z ˙ ∈ dom ( x ˙ ) \dot{z} \in\operatorname{dom}(\dot{x}) z ˙ ∈ dom ( x ˙ ) with q ⊩ y ˙ = z ˙ q \Vdash\dot{y} = \dot{z} q ⊩ y ˙ = z ˙ is dense below p p p and Δ 1 \Delta_1 Δ 1 -definable. Hence G G G meets it. For the resulting z ˙ \dot{z} z ˙ , we have z ˙ ≈ ∗ y ˙ \dot{z} \approx^{*} \dot{y} z ˙ ≈ ∗ y ˙ and therefore z ˙ ∈ C \dot{z} \in\mathcal{C} z ˙ ∈ C , while
M ⊨ rank ( z ˙ ) < rank ( x ˙ ) . \mathcal{M} \models\operatorname{rank}(\dot{z}) < \operatorname{rank}(\dot{x}). M ⊨ rank ( z ˙ ) < rank ( x ˙ ) .
This contradicts the choice of x ˙ \dot{x} x ˙ . □
The verification of the rest of the axioms of K P KP K P then follows easily.
Corollary 20. If M ⊨ S 0 \mathcal{M} \models S_0 M ⊨ S 0 and G M G^{\mathcal{M}} G M is the canonical generic from Lemma 17 , then
M Add ( ω , 1 ) / G M ⊨ K P . \mathcal{M}^{\operatorname{Add}(\omega,1)}/G^{\mathcal{M}} \models KP. M Add ( ω , 1 ) / G M ⊨ K P .
Proof. The proof of K P KP K P -preservation in § 2.1 applies to all axioms other than Full Set Induction. Those axioms are forced and are B Σ 3 B\Sigma_3 B Σ 3 sentences. The canonical generic is B Σ ~ b ( 3 ) B\widetilde{\Sigma}_{b(3)} B Σ b ( 3 ) -generic, so the truth lemma for arbitrary models transfers them to the quotient. Full Set Induction is supplied by the preceding lemma. □
Next we show that one of the isomorphisms required to witness bi-interpretability is suitably definable.
Lemma 21. Let M ⊨ S 0 \mathcal{M} \models S_0 M ⊨ S 0 and let
Q = M Add ( ω , 1 ) / G M . Q = \mathcal{M}^{\operatorname{Add}(\omega,1)}/G^{\mathcal{M}}. Q = M Add ( ω , 1 ) / G M . There is an isomorphism
η M : M ≅ L Q \eta^{\mathcal{M}}:\mathcal{M}\cong L^Q η M : M ≅ L Q which is uniformly definable over M \mathcal{M} M .
Proof. We first show that every ordinal of Q Q Q is represented by a canonical ordinal name. Suppose Q ⊨ α ˙ ∈ O r d Q \models\dot{\alpha}\in Ord Q ⊨ α ˙ ∈ O r d . By the Δ 0 \Delta_0 Δ 0 truth lemma, choose p ∈ G M p\in G^{\mathcal{M}} p ∈ G M such that ( p ⊩ α ˙ ∈ O r d ) M (p\Vdash\dot{\alpha}\in Ord)^{\mathcal{M}} ( p ⊩ α ˙ ∈ O r d ) M . Working in M \mathcal{M} M , the usual rank-bounding argument for ordinal names12 gives some δ ∈ O r d M \delta\in Ord^{\mathcal{M}} δ ∈ O r d M with p ⊩ α ˙ ≤ δ ˇ p\Vdash\dot{\alpha}\leq\check{\delta} p ⊩ α ˙ ≤ δ ˇ . Hence p ⊩ α ˙ ∈ δ ˇ + 1 p\Vdash\dot{\alpha}\in\check{\delta}+1 p ⊩ α ˙ ∈ δ ˇ + 1 . By the syntactic forcing clause for membership,
D = { q ≤ p : ∃ β < δ + 1 q ⊩ α ˙ = β ˇ } D=\{q\leq p:\exists\beta<\delta+1\ q\Vdash\dot{\alpha}=\check{\beta}\} D = { q ≤ p : ∃ β < δ + 1 q ⊩ α ˙ = β ˇ } is dense below p p p . This class is Δ 1 \Delta_1 Δ 1 -definable over M \mathcal{M} M , so G M G^{\mathcal{M}} G M meets it. Thus every ordinal of Q Q Q is represented by β ˇ \check{\beta} β ˇ for some β ∈ O r d M \beta\in Ord^{\mathcal{M}} β ∈ O r d M . The converse is immediate, so the canonical-name map identifies the ordinals of M \mathcal{M} M and Q Q Q . Define η M \eta^{\mathcal{M}} η M by the relation
η M ( x ) = [ x ˇ ] G M . \eta^{\mathcal{M}}(x)=[\check{x}]_{G^{\mathcal{M}}}. η M ( x ) = [ x ˇ ] G M . Since G M G^{\mathcal{M}} G M is defined by the fixed formula γ \gamma γ , this relation is uniformly definable over M \mathcal{M} M . The atomic forcing facts show that it is an ∈ \in ∈ -embedding. Using the preceding identification of ordinals, Full Set Induction in M \mathcal{M} M gives, for every α ∈ O r d M \alpha\in Ord^{\mathcal{M}} α ∈ O r d M ,
η M [ L α M ] = L α Q . \eta^{\mathcal{M}}[L^{\mathcal{M}}_\alpha]=L^Q_\alpha. η M [ L α M ] = L α Q . The successor step follows because definable subsets are preserved under isomorphism, and the limit step is immediate. Since M ⊨ V = L \mathcal{M}\models V=L M ⊨ V = L and the two structures have the same ordinals, the range of η M \eta^{\mathcal{M}} η M is exactly L Q L^Q L Q . □
Then, analogously to the previous subsection, we see that models of S 0 S_0 S 0 can interpret models of S 1 S_1 S 1 .
Corollary 22. For every M ⊨ S 0 \mathcal{M} \models S_0 M ⊨ S 0 , the quotient
M Add ( ω , 1 ) / G M \mathcal{M}^{\operatorname{Add}(\omega,1)}/G^{\mathcal{M}} M Add ( ω , 1 ) / G M is a model of S 1 S_1 S 1 . Hence S 0 S_0 S 0 interprets S 1 S_1 S 1 .
Proof. Let Q Q Q be the quotient. By Corollary 20, Q ⊨ K P Q \models KP Q ⊨ K P . By Lemma 21, L Q L^Q L Q is isomorphic to M \mathcal{M} M and therefore has no admissible ordinals. Let g g g be the interpretation in Q Q Q of the standard name for the generic filter. Under the isomorphism η M \eta^{\mathcal{M}} η M , this is exactly the subset of Add ( ω , 1 ) L Q \operatorname{Add}(\omega,1)^{L^Q} Add ( ω , 1 ) L Q defined over L Q L^Q L Q by γ \gamma γ . It is generic over L Q L^Q L Q , and the standard valuation recursion gives
Q = L Q [ g ] . Q = L^Q[g]. Q = L Q [ g ] . Thus Q ⊨ Ψ γ Q \models\Psi_\gamma Q ⊨ Ψ γ . □ \square □
Finally, we show that the other isomorphism, required for the bi-interpretation, is suitably definable.
Lemma 23. If N ⊨ S 1 \mathcal{N} \models S_1 N ⊨ S 1 , then L N ⊨ S 0 L^{\mathcal{N}} \models S_0 L N ⊨ S 0 . Moreover, if g g g is the unique set specified by Ψ γ \Psi_\gamma Ψ γ , there is a uniformly definable isomorphism
ν N : ( L N ) Add ( ω , 1 ) / g ≅ N . \nu^{\mathcal{N}} : (L^{\mathcal{N}})^{\operatorname{Add}(\omega,1)}/g \cong\mathcal{N}. ν N : ( L N ) Add ( ω , 1 ) / g ≅ N . Proof. The constructible universe of a model of K P KP K P again satisfies K P KP K P . By Ψ γ \Psi_\gamma Ψ γ , L N L^{\mathcal{N}} L N has no admissible ordinals, and of course it satisfies V = L V = L V = L . Hence L N ⊨ S 0 L^{\mathcal{N}} \models S_0 L N ⊨ S 0 . The same axiom says that g g g is the canonical Add ( ω , 1 ) L N \operatorname{Add}(\omega,1)^{L^{\mathcal{N}}} Add ( ω , 1 ) L N -generic filter and that N = L N [ g ] \mathcal{N} = L^{\mathcal{N}}[g] N = L N [ g ] . Let ν N \nu^{\mathcal{N}} ν N be induced by the familiar valuation function:^13
ν N ( [ x ˙ ] g ) = val g ( x ˙ ) . \nu^{\mathcal{N}}([\dot{x}]_g) = \operatorname{val}_g(\dot{x}). ν N ([ x ˙ ] g ) = val g ( x ˙ ) . The forcing theorem gives that this is well-defined and preserves ∈ \in ∈ , and every element of L N [ g ] L^{\mathcal{N}}[g] L N [ g ] is the value of an L N L^{\mathcal{N}} L N -name. Thus ν N \nu^{\mathcal{N}} ν N is an isomorphism. Since g g g is defined without parameters from L N L^{\mathcal{N}} L N by the fixed formula γ \gamma γ , the valuation relation, and hence ν N \nu^{\mathcal{N}} ν N , is uniformly definable over N \mathcal{N} N . □ \square □
And now we have our second, more powerful, result.
Theorem 24. K P KP K P is not tight.
Proof. Let t t t be the interpretation of S 1 S_1 S 1 in S 0 S_0 S 0 supplied by Corollary 22, and let s s s be the interpretation of S 0 S_0 S 0 in S 1 S_1 S 1 given by the constructible universe. Lemma 21 gives a uniformly definable isomorphism from each M ⊨ S 0 \mathcal{M} \models S_0 M ⊨ S 0 to s ∘ t ( M ) s \circ t(\mathcal{M}) s ∘ t ( M ) , while Lemma 23 gives a uniformly definable isomorphism from t ∘ s ( N ) t \circ s(\mathcal{N}) t ∘ s ( N ) to each N ⊨ S 1 \mathcal{N} \models S_1 N ⊨ S 1 . Thus S 0 S_0 S 0 and S 1 S_1 S 1 are bi-interpretable. They are not the same theory. Indeed, S 0 ⊢ V = L S_0 \vdash V = L S 0 ⊢ V = L , whereas S 1 ⊢ V ≠ L S_1 \vdash V \ne L S 1 ⊢ V = L , since the set g g g asserted by Ψ γ \Psi_\gamma Ψ γ is Cohen generic over L L L . Hence K P KP K P is not tight. □ \square □
Some generalizations
Our goal now is to generalize these results to suitable theories that are consistent with V = L V = L V = L . The reader will have observed there are two crucial ingredients to the proofs above:
We need a definable countable enumeration of the universe in order to define generic filters and generic extensions.
(2) We need a ground model to generically extend from and which can be defined in the generic extension.
If we force out of a model of V = L V=L V = L , then (2) is easy to achieve. For theories consistent with V = L V=L V = L , (1) can also be obtained straightforwardly using elementary fine-structural techniques as long as we don’t have Full Separation and Collection. With that in mind, let us say that a set S S S of sentences from L ∈ \mathcal{L}_{\in} L ∈ is quantifier bounded if there is some k ∈ ω k \in\omega k ∈ ω such that every sentence φ ∈ S \varphi\in S φ ∈ S is Σ k \Sigma_k Σ k .
We then observe that whenever we extend K P KP K P by a quantifier bounded set of sentences, we have a theory that can be extended to say that the universe has a definable countable enumeration.
Lemma 25. Let T = U + K P T=U+KP T = U + K P be consistent with V = L V=L V = L , where U U U is quantifier bounded . Then there is a parameter-free formula θ ( n , x ) \theta(n,x) θ ( n , x ) such that
T + V = L + “ θ defines a class surjection from ω onto V ” T+V=L+\text{“}\theta\text{ defines a class surjection from }\omega\text{ onto }V\text{”} T + V = L + “ θ defines a class surjection from ω onto V ” is consistent.14
Proof. Our plan is to work in T + V = L T+V=L T + V = L and define a sufficiently strong Skolem function on the universe that will give us a hull upon which that function delivers our required enumeration. Working now in T + V = L T+V=L T + V = L , let m + 1 ≥ 3 m+1\ge3 m + 1 ≥ 3 be sufficiently large that the axioms of U U U and K P + V = L KP+V=L K P + V = L , except Full Set Induction, can be articulated as Π m + 1 \Pi_{m+1} Π m + 1 sentences. Let Sat Π m \operatorname{Sat}_{\Pi_m} Sat Π m be a satisfaction predicate for Π m \Pi_m Π m formulae with three free variables, so we have
Sat Π m ( ⌜ ψ ⌝ , ⟨ x , y , a ⟩ ) ⟺ ψ ( x , y , a ) . \operatorname{Sat}_{\Pi_m}(\ulcorner\psi\urcorner,\langle x,y,a\rangle)\Longleftrightarrow\psi(x,y,a). Sat Π m ( ┌ ψ ┐ , ⟨ x , y , a ⟩) ⟺ ψ ( x , y , a ) .
Note that Sat Π m \operatorname{Sat}_{\Pi_m} Sat Π m can be articulated as a Π m \Pi_m Π m formula. We assume that our Gödel coding is in bijection with ω \omega ω .
We now define a Σ m + 1 \Sigma_{m+1} Σ m + 1 -Skolem function in three steps. First, we let h 0 : ω × V ⇀ V × V h_0:\omega\times V\rightharpoonup V\times V h 0 : ω × V ⇀ V × V be such that h 0 ( ⌜ ψ ⌝ , a ) = ⟨ x , y ⟩ h_0(\ulcorner\psi\urcorner,a)=\langle x,y\rangle h 0 ( ┌ ψ ┐ , a ) = ⟨ x , y ⟩ iff
Sat Π m ( ⌜ ψ ⌝ , ⟨ x , y , a ⟩ ) ⏟ Π m ∧ ∀ u , v , w ( w = pr L ( ⟨ x , y ⟩ ) ∧ ⟨ u , v ⟩ ∈ w → ¬ Sat Π m ( ⌜ ψ ⌝ , ⟨ u , v , a ⟩ ) ) ⏟ Σ m \underbrace{\operatorname{Sat}_{\Pi_m}(\ulcorner\psi\urcorner,\langle x,y,a\rangle)}_{\Pi_m}\land\underbrace{\forall u,v,w\left(w=\operatorname{pr}_{L}(\langle x,y\rangle)\land\langle u,v\rangle\in w\rightarrow\neg\operatorname{Sat}_{\Pi_m}(\ulcorner\psi\urcorner,\langle u,v,a\rangle)\right)}_{\Sigma_m} Π m Sat Π m ( ┌ ψ ┐ , ⟨ x , y , a ⟩) ∧ Σ m ∀ u , v , w ( w = pr L (⟨ x , y ⟩) ∧ ⟨ u , v ⟩ ∈ w → ¬ Sat Π m ( ┌ ψ ┐ , ⟨ u , v , a ⟩) )
(the displayed conjunction is Π m + 1 ). \text{(the displayed conjunction is } \Pi_{m+1}\text{).} (the displayed conjunction is Π m + 1 ).
where pr L ( z ) \operatorname{pr}_{L}(z) pr L ( z ) is the Δ 1 \Delta_1 Δ 1 definable set of L L L -predecessors of z z z .15 h 0 h_0 h 0 takes the Gödel code of a Π m \Pi_m Π m -formula along with a parameter and returns the L L L -least pair satisfying it. Note that h 0 h_0 h 0 is Π m + 1 \Pi_{m+1} Π m + 1 definable.
Next we let h 1 : ω < ω ⇀ V < ω h_1:\omega^{<\omega}\rightharpoonup V^{<\omega} h 1 : ω < ω ⇀ V < ω be such that h 1 ( s ) = x h_1(s)=x h 1 ( s ) = x iff
x 0 = h 0 ( s 0 , ∅ ) ∧ ∀ i + 1 < lh ( s ) x i + 1 = h 0 ( s i + 1 , ⟨ π 0 ( x 0 ) , … , π 0 ( x i ) ⟩ ) x_0=h_0(s_0,\varnothing)\land\forall i+1<\operatorname{lh}(s)\;x_{i+1}=h_0\left(s_{i+1},\langle\pi_0(x_0),\ldots,\pi_0(x_i)\rangle\right) x 0 = h 0 ( s 0 , ∅ ) ∧ ∀ i + 1 < lh ( s ) x i + 1 = h 0 ( s i + 1 , ⟨ π 0 ( x 0 ) , … , π 0 ( x i )⟩ )
where π 0 \pi_0 π 0 gives us the first element of an ordered pair. This function takes a sequence of formulae and returns a sequence of sets that are inductively defined from using those formulae. This is intended to replicate the inductive steps in a standard argument for the downward Löwenheim-Skolem theorem. Finally, we let h ( s ) = y h(s)=y h ( s ) = y iff y y y is the first member of the final pair in h 1 ( s ) h_1(s) h 1 ( s ) .
A standard Tarski-Vaught argument then establishes that h [ ω < ω ] h[\omega^{<\omega}] h [ ω < ω ] is a Σ m + 1 \Sigma_{m+1} Σ m + 1 -Skolem hull of the universe. Moreover, since h 0 h_0 h 0 is Π m + 1 \Pi_{m+1} Π m + 1 definable over, it can then be seen that the formula defining h h h in V V V also defines h h h in h [ ω < ω ] h[\omega^{<\omega}] h [ ω < ω ] . Clearly then, h : ω → h [ ω < ω ] h:\omega\to h[\omega^{<\omega}] h : ω → h [ ω < ω ] is a partial surjection that is definable over h [ ω < ω ] h[\omega^{<\omega}] h [ ω < ω ] . It is then a simple matter to define a total surjection h ∗ : ω → h [ ω < ω ] h^*:\omega\to h[\omega^{<\omega}] h ∗ : ω → h [ ω < ω ] in h [ ω < ω ] h[\omega^{<\omega}] h [ ω < ω ] . To close things out, we then observe that h [ ω < ω ] h[\omega^{<\omega}] h [ ω < ω ] satisfies T + V = L T+V=L T + V = L since we chose m m m to be sufficiently large for all axioms with the exception of Full Set Induction, and the latter holds since h [ ω < ω ] h[\omega^{<\omega}] h [ ω < ω ] is a definable submodel of a universe satisfying Full Set Induction that shares its membership relation. □
We then note that if we follow the template suggested by the proof of Theorem 24 , we want to ensure that our theory is preserved when we move to a generic extension.
Definition 26. Let T T T be a theory extending K P KP K P and let P \mathbb{P} P be a forcing notion uniformly definable without parameters over models of T T T . We say that T T T is generically invariant with respect to P \mathbb{P} P if there is some k ∈ ω k\in\omega k ∈ ω such that whenever M ⊨ T \mathcal{M}\models T M ⊨ T and G ⊆ P M G\subseteq\mathbb{P}^{\mathcal{M}} G ⊆ P M is definable over M \mathcal{M} M and B Σ k B\Sigma_k B Σ k -generic over M \mathcal{M} M , then M P / G ⊨ T \mathcal{M}^{\mathbb{P}}/G\models T M P / G ⊨ T .
Now we may state a more general theorem.
Theorem 27. Let T = U + K P T=U+KP T = U + K P be consistent with V = L V=L V = L where U U U is quantifier bounded. Moreover suppose that T T T is generically invariant with respect to some nontrivial set forcing uniformly definable without parameters over T T T . Then T T T is not tight.16
Proof. Let k k k witness generic invariance. Enlarge k k k , if necessary, so that k ≥ b ( j ) k\geq b(j) k ≥ b ( j ) for a bound j j j on the fixed additional formulae used in the forcing and truth arguments below. By Lemma 25 , fix a parameter-free formula θ ( n , x ) \theta(n,x) θ ( n , x ) such that the theory
S 0 = T + V = L + “ θ defines a class surjection from ω onto V ” S_0=T+V=L+\text{“}\theta\text{ defines a class surjection from }\omega\text{ onto }V\text{”} S 0 = T + V = L + “ θ defines a class surjection from ω onto V ”
is consistent. Let γ \gamma γ be the fixed parameter-free formula obtained by applying the least-extension construction from the earlier tightness proof to P \mathbb{P} P using θ \theta θ . Thus, in every model of S 0 S_0 S 0 , γ \gamma γ defines a B Σ k B\Sigma_k B Σ k -generic filter G G G on P \mathbb{P} P . By generic invariance, the corresponding generic extension is again a model of T T T .
Let S 1 S_1 S 1 extend T T T by asserting that its constructible universe satisfies S 0 S_0 S 0 and that there is a set g g g such that
p ∈ g ⟺ L ⊨ γ ( p ) , p\in g\ \Longleftrightarrow\ L\models\gamma(p), p ∈ g ⟺ L ⊨ γ ( p ) ,
g g g is P L \mathbb{P}^L P L -generic over L L L , and V = L [ g ] V=L[g] V = L [ g ] . If M ⊨ S 0 \mathcal{M}\models S_0 M ⊨ S 0 and G G G is its canonical generic, then generic invariance gives
M P / G ⊨ T . \mathcal{M}^{\mathbb{P}}/G\models T. M P / G ⊨ T .
The same ordinal-recovery argument used in the earlier K P KP K P tightness proof identifies the constructible universe of this extension with M \mathcal{M} M , while the standard valuation recursion gives
M P / G = ( L [ G ] ) M P / G . \mathcal{M}^{\mathbb{P}}/G = (L[G])^{\mathcal{M}^{\mathbb{P}}/G}. M P / G = ( L [ G ] ) M P / G .
Hence S 0 S_0 S 0 interprets S 1 S_1 S 1 .
Conversely, if N ⊨ S 1 \mathcal{N} \models S_1 N ⊨ S 1 , then L N ⊨ S 0 L^{\mathcal{N}} \models S_0 L N ⊨ S 0 . Interpreting S 0 S_0 S 0 by L L L and then taking its canonical P \mathbb{P} P -generic extension recovers N \mathcal{N} N up to the usual definable valuation isomorphism. In the other direction, the constructible universe of the canonical generic extension of a model of S 0 S_0 S 0 is definably isomorphic to the original model, exactly as in the earlier proof. Thus S 0 S_0 S 0 and S 1 S_1 S 1 are bi-interpretable.
Finally, S 0 ⊢ V = L S_0 \vdash V = L S 0 ⊢ V = L , whereas S 1 ⊢ V ≠ L S_1 \vdash V \ne L S 1 ⊢ V = L . Indeed, the canonical g g g cannot belong to L L L : otherwise P L ∖ g \mathbb{P}^L \setminus g P L ∖ g would be a dense set in L L L disjoint from g g g , using the nontriviality of P L \mathbb{P}^L P L . Hence the two theories have different deductive closures. They are distinct bi-interpretable extensions of T T T , so T T T is not tight. □
Thus, to obtain theories that aren’t tight, we simply need to find quantifier bounded theories that are generically invariant and consistent with V = L V = L V = L . Here are some obvious examples.
Corollary 28. Let Φ \Phi Φ be any of the statements below. If K P + P o w e r s e t + Φ + V = L KP + \mathit{Powerset} + \Phi+ V = L K P + Powerset + Φ + V = L is consistent, then K P + P o w e r s e t + Φ KP + \mathit{Powerset} + \Phi K P + Powerset + Φ is not tight.
(1) There is an inaccessible cardinal;
(2) There is a Mahlo cardinal;
(3) There is a weakly compact cardinal, where weak compactness is formulated as inaccessibility together with the tree property.
Proof. Fix one of the displayed statements Φ \Phi Φ and let T = K P + P o w e r s e t + Φ T = KP + \mathit{Powerset} + \Phi T = K P + Powerset + Φ . By hypothesis, T + V = L T + V = L T + V = L is consistent. Let P = Add ( ω , 1 ) \mathbb{P} = \operatorname{Add}(\omega, 1) P = Add ( ω , 1 ) . This is a nontrivial forcing uniformly definable without parameters. If κ \kappa κ witnesses Φ \Phi Φ , then ∣ P ∣ < κ |\mathbb{P}| < \kappa ∣ P ∣ < κ . The standard small-forcing argument preserves inaccessibility and Mahloness; in the third case, the usual name-tree argument also preserves the tree property. The usual name-bound argument for Powerset, together with the preceding K P KP K P -preservation results and these small-forcing arguments, shows that the non-induction axioms of T T T are forced. Choose a fixed j j j bounding their complexity. The truth lemma for arbitrary models transfers them whenever the generic is B Σ b ( j ) B\Sigma_{\mathsf{b}(j)} B Σ b ( j ) -generic. For definable generics, the separate Full Set Induction lemma supplies the remaining axioms. Thus T T T is generically invariant with respect to P \mathbb{P} P , and the result now follows from Theorem 27 . □
Quantifier bounded theories generally aren’t tight
We now have a rich collection of theories compatible with V = L V = L V = L that fail to be tight. But what if we wanted to consider theories that countenance, say, the existence of a measurable cardinal or a proper class of extendible cardinals? These extensions are not consistent with V = L V = L V = L and thus, the techniques described above are of little use. Nonetheless, the underlying strategy can be adapted. In general, we are looking for theories of the appropriate form that:
are consistent with a countable definable enumeration; and
admit generic extensions where the ground model can be recovered by definition.
With regard to (2), we now identify a property of theories that makes them suitable for the anti-tightness arguments we are about to give. For this purpose, we make use of a simple extension of K P KP K P . In particular, we let K P C KP^{C} K P C be K P KP K P with the Axiom of Choice in the form: ∀ x ∃ f ∃ α f : x ↪ α \forall x\exists f\exists\alpha\ f:x\mathrel{\hookrightarrow}\alpha ∀ x ∃ f ∃ α f : x ↪ α .
Definition 29. Say that a theory T T T has the stable definable ground property if there is an inner model N of K P C KP^{C} K P C definable over T T T and a term P \mathbb{P} P defined over T T T by a formula relativized to N such that T T T proves
P ∈ N \mathbb{P}\in N P ∈ N is a non-trivial forcing poset;
“( ⊩ P ψ ) N (\Vdash_{\mathbb{P}}\psi)^{N} ( ⊩ P ψ ) N ” for all ψ ∈ T \psi\in T ψ ∈ T ;
∃ g ∈ g e n ( P , N ) V = N [ g ] \exists g\in gen(\mathbb{P},N)\ V=N[g] ∃ g ∈ g e n ( P , N ) V = N [ g ] ; and
( ⊩ P “ N G ˙ = V ˇ ” ) N (\Vdash_{\mathbb{P}}\ “N^{\dot G}=V^{\check{\,}}”)^{N} ( ⊩ P “ N G ˙ = V ˇ ” ) N .
The last clause deserves some explanation. We are saying that any P \mathbb{P} P -generic extension N [ h ] N[h] N [ h ] of the defined P \mathbb{P} P -ground N is such that N [ h ] N[h] N [ h ] ’s version of N is still N. This is why we call it stably definable.
In essence, theories with the stable definable ground property are theories whose models are generic extensions of inner models that are robustly definable from their generic extensions. For example, K P KP K P together with the assertion that the universe is a Cohen extension of L L L has the stable definable ground property, witnessed by N = L L L and P = A d d ( ω , 1 ) L \mathbb{P}=Add(\omega,1)^{L} P = A dd ( ω , 1 ) L .
Moving onto (1), we prove a very general lemma about theories obtained from extending a weak set theory with a quantifier bounded collection of sentences.
Lemma 30. If T = K P C + S T=KP^{C}+S T = K P C + S is consistent and S S S is quantifier bounded, then there is a parameter free formula θ ( n , x ) \theta(n,x) θ ( n , x ) such that
T + “ θ defines a class surjection from ω onto V ” T+\text{“}\theta\text{ defines a class surjection from }\omega\text{ onto }V\text{”} T + “ θ defines a class surjection from ω onto V ” is consistent. The same conclusion holds for a fixed finite expansion of the language by constant symbols.
Let’s call this the Definable Countable Enumeration Lemma . Its proof takes a little while and uses some unusual techniques. As such, we defer its proof to the next section and offer a simple demonstration of our main theorem template on the basis of this promise.
Theorem 31. Suppose T = K P C + U T=KP^{C}+U T = K P C + U is consistent where U U U is quantifier bounded and that T T T has the stable definable ground property. Then T T T is not tight.
Proof. Let R R R be K P C KP^{C} K P C together with the assertion that P \mathbb{P} P is non-trivial, the assertions $1_{\mathbb{P}}\Vdash\varphi$ for φ ∈ U \varphi\in U φ ∈ U , and the assertion that forcing with P \mathbb{P} P preserves the fixed definition of N in the sense of the last clause of Definition 29. A model of T T T together with its distinguished ground witnesses the consistency of R R R . Choose a fixed j j j such that the sentences in U U U , the non-induction axioms of K P C KP^{C} K P C , and the fixed sentence expressing stability of the ground definition are all Σ j \Sigma_{j} Σ j . By the uniform forcing-bound lemma, their forcing translations have a common bound Δ b ( j ) \Delta_{b(j)} Δ b ( j ) . The remaining assertion in R R R , that P \mathbb{P} P is nontrivial, also has fixed finite complexity. Thus R R R is of the form K P C + S KP^{C}+S K P C + S with S S S quantifier bounded. By the Definable Countable Enumeration Lemma (Lemma 30), we may then fix a parameter-free formula θ \theta θ and a model W ⊨ R W\models R W ⊨ R in which θ \theta θ defines a class surjection from ω \omega ω onto W W W . Choose $k\ge b ( j ) b(j) b ( j ) , enlarged as necessary for the usual product-forcing argument, and apply the least-extension construction to P × P \mathbb{P}\times\mathbb{P} P × P . At each stage, choose an eligible extension with the least index in the enumeration defined by θ \theta θ . This gives a canonical B Σ k B\Sigma_k B Σ k -generic pair ⟨ G 0 , G 1 ⟩ \langle G_0,G_1\rangle ⟨ G 0 , G 1 ⟩ over W W W , with each projection sufficiently generic for the formulae just listed. Let M i = W [ G i ] M_i=W[G_i] M i = W [ G i ] for i ∈ 2 i\in2 i ∈ 2 . Set forcing forces the non-induction axioms of K P C KPC K P C , and the forcing clauses in R R R give the members of U U U . The truth lemma for arbitrary models transfers these sentences to M i M_i M i , while definability of G i G_i G i gives Full Set Induction by the separate preservation lemma (Lemma 19). Hence M i ⊨ T M_i\models T M i ⊨ T . Stability gives N M i = W N^{M_i}=W N M i = W for each i ∈ 2 i\in2 i ∈ 2 . For i ∈ 2 i\in2 i ∈ 2 , let S i S_i S i extend T T T by saying that θ N \theta^N θ N enumerates N \mathbb{N} N and that the universe is the i t h i^{\mathrm{th}} i th coordinate of the canonical P × P \mathbb{P}\times\mathbb{P} P × P -generic pair thereby defined over N N N . The models M i M_i M i witness consistency. In any model of S i S_i S i , first recover N N N , then θ \theta θ , and hence the other coordinate extension. When we interpret back, the stability clause recovers the same N N N and therefore the same canonical pair, so the usual valuation map gives the required definable isomorphism. Thus S 0 S_0 S 0 and S 1 S_1 S 1 are bi-interpretable. Finally, we observe that S 0 ≠ S 1 S_0\ne S_1 S 0 = S 1 since S 0 S_0 S 0 says it’s formed from the 0 t h 0^{\mathrm{th}} 0 th projection while S 1 S_1 S 1 says it’s formed from the 1 s t 1^{\mathrm{st}} 1 st projection. This then suffices since the associated filters are mutually generic. Hence T T T is not tight. □
Thus, if we want to show that an extension of K P C KPC K P C , of the kind discussed above, fails to be tight, it will suffice for us to show that theory has a consistent extension with the stable definable ground property. In Section 6, we will show this for a wide variety of theories.
The Definable Countable Enumeration Lemma
Our goal now is to prove Lemma 30. This is the most original part of the paper and it takes the most time and effort to prove. The strategy is simple to sketch, but fussy to execute. The argument has three main steps. We start by working in an arbitrary model of a suitable theory T T T which we treat as the universe. Working in this context, we then describe a way of building a model of T T T by approximation using something like a tableau proof system, model existence game, inverted sequent, or analytic consistency property [33 , 27 , 1 ] (Väänänen 2011). Such models are countable as witnessed by the fact that they are defined from a countable set of constant symbols. The model we obtain can then be interpreted in our adopted universe and we call it M 0 \mathcal{M}_0 M 0 . We shall also make use of an ordinal side-condition that delivers a definable order-preserving map from M 0 \mathcal{M}_0 M 0 into the ordinals of this background universe. This is the sense in which the model is well-founded, and it ensures Full Set Induction. For the second step, we shall be very careful in setting up our model building process so that when we use the same process inside M 0 \mathcal{M}_0 M 0 , we define another model M 1 \mathcal{M}_1 M 1 with an isomorphism j : M 0 ≅ M 1 j:\mathcal{M}_0\cong\mathcal{M}_1 j : M 0 ≅ M 1 definable in the background universe. Thus, there is a sense in which our model building process is idempotent. This is the tricky part. For the final step, we use M 0 \mathcal{M}_0 M 0 ’s countable presentation of M 1 \mathcal{M}_1 M 1 to define, without parameters and inside M 0 \mathcal{M}_0 M 0 , a countable enumeration of itself. Obtaining this internal definition requires a further argument, supplied in Lemma 45. Thus, M 0 \mathcal{M}_0 M 0 witnesses the claim.
So much for the sketch. The rest of this section is divided up as follows. First, we recall some of the basics of tableau proof systems. Then we describe some modifications of this system that will fulfill the requirements of the sketch above. After that, we show that it does what we need it to do.
Tableau proof systems: building models by approximation
Tableau proof systems originated with Beth, Hintikka and Kanger [1955, 1955, 1957] as a means of providing a simple proof theory for first order logic whereby we take a sentence φ \varphi φ and search for a counterexample to it. This is done by taking ¬ φ \neg\varphi ¬ φ and systematically unpacking it to find out if it is satisfiable. If ⊢ φ \vdash\varphi ⊢ φ , then ¬ φ \neg\varphi ¬ φ is inconsistent, and the unpacking process applied to ¬ φ \neg\varphi ¬ φ eventually crashes revealing that ¬ φ \neg\varphi ¬ φ is unsatisfiable; i.e., ⊨ φ \models\varphi ⊨ φ . On the other hand, if ¬ φ \neg\varphi ¬ φ is consistent, the process never crashes and we end up defining a model in which ¬ φ \neg\varphi ¬ φ is satisfied; thus, ⊭ φ \not\models\varphi ⊨ φ . More generally, the unpacking process can be used to take a simple, countable set of sentences and ascertain whether it is satisfiable.17
Rules for FOL without identity
Let us now recall the process in a little more detail.18 Suppose we are given a sentence φ \varphi φ from some language L \mathcal{L} L without identity and we wish to figure out whether there is a model M \mathcal{M} M satisfying φ \varphi φ .19 The tableau for φ \varphi φ is a tree whose nodes are sentences of the language L ( C ) \mathcal{L}(C) L ( C ) , which is L \mathcal{L} L expanded with a countable set C = { c n } n ∈ ω C=\{c_n\}_{n\in\omega} C = { c n } n ∈ ω of new constant symbols. The tree grows downward and at the top (the root node) we find φ \varphi φ . The tableau is then produced by unpacking formulae that occur on the tree by following a set of rules that we give below.
( ∨ ) φ ∨ ψ ⟶ φ , ψ ( ¬ ∨ ) ¬ ( φ ∨ ψ ) ⟶ ¬ φ , ¬ ψ ( ¬ ¬ ) ¬ ¬ φ ⟶ φ ( ∃ ) ∃ x φ ( x ) ⟶ φ ( c ) ( ¬ ∃ ) ¬ ∃ x φ ( x ) ⟶ ¬ φ ( a ) \begin{aligned}
(\lor)\quad&\varphi\lor\psi&&\longrightarrow&&\varphi,\ \psi\\
(\neg\lor)\quad&\neg(\varphi\lor\psi) &&\longrightarrow&&\neg\varphi,\ \neg\psi\\
(\neg\neg)\quad&\neg\neg\varphi&&\longrightarrow&&\varphi\\
(\exists)\quad&\exists x\varphi(x) &&\longrightarrow&&\varphi(c) \\
(\neg\exists)\quad&\neg\exists x\varphi(x) &&\longrightarrow&&\neg\varphi(a)
\end{aligned} ( ∨ ) ( ¬ ∨ ) ( ¬¬ ) ( ∃ ) ( ¬∃ ) φ ∨ ψ ¬ ( φ ∨ ψ ) ¬¬ φ ∃ x φ ( x ) ¬∃ x φ ( x ) ⟶ ⟶ ⟶ ⟶ ⟶ φ , ψ ¬ φ , ¬ ψ φ φ ( c ) ¬ φ ( a )
For the ∃ \exists ∃ rule the constant symbol c c c must be new to the tree. For the ¬ ∃ \neg\exists ¬∃ rule the constant symbol a a a is arbitrary. To save some space, we shall assume that other connectives and quantifiers are defined in the usual way, and thus, can be given the obvious derived rules that we’ll often use below.
Next we describe what happens when the unpacking process crashes. If we ever end up in a situation where a branch in the tableau tree has both ψ \psi ψ and ¬ ψ \neg\psi ¬ ψ occurring upon it, we deem that branch to be closed and place a × \times × below the final sentence node to indicate that we are finished with that branch.
Suppose we have a tableau tree T T T for φ \varphi φ before us. We say that a branch b b b in T T T is complete if b b b is closed or every rule that can be applied to every formula occurring on b b b has been applied.20 We say that a branch is open if it is complete but not closed. We then say that the entire tableau tree is closed if all its branches are closed; and that it is open , if it has at least one open branch.
Soundness and completeness
We then obtain the following version of soundness and completeness.
Theorem 32. φ \varphi φ is satisfiable iff every completed tableau T \mathcal{T} T for φ \varphi φ is open.
We give a quick sketch of this as it provides a simple illustration of what we will be doing later.
Proof. ( → (\rightarrow ( → , soundness) Suppose φ \varphi φ is satisfied in M \mathcal{M} M and without loss of generality suppose that M \mathcal{M} M is countable. Our goal is to show that the tableau T \mathcal{T} T for φ \varphi φ has an open branch. To do this we use M \mathcal{M} M to guide us through T \mathcal{T} T . This is done by induction on the length of the branch. Thus, we suppose we have an incomplete branch b b b in T \mathcal{T} T of length n n n and that every sentence occurring on b b b is satisfiable in an expansion of M \mathcal{M} M that interprets the new constant symbols added via the ( ∃ ) (\exists) ( ∃ ) rule. We then show that the rule whose application gives a branch b ∗ b^* b ∗ in T \mathcal{T} T of length n + 1 n+1 n + 1 extending b b b is such that a possible further expansion of M \mathcal{M} M satisfies the new formula. The interesting cases are ( ∨ ) (\lor) ( ∨ ) (where we may need to use M \mathcal{M} M to make a choice) and ( ∃ ) (\exists) ( ∃ ) where we add new constant symbols. At the limit, this gives us a complete branch upon which every formula is satisfied in an expansion of M \mathcal{M} M .
( ← (\leftarrow ( ← , completeness) Suppose b b b is an open branch in the tableau T \mathcal{T} T for φ \varphi φ . We use this branch to define a model M = ⟨ M , R M ⟩ \mathcal{M}=\langle M,R^{\mathcal{M}}\rangle M = ⟨ M , R M ⟩ where, for simplicity, we suppose that L \mathcal{L} L just has one 2-place relation symbol. We let:
M M M be the set of constant symbols occurring in sentences on b b b ; and
R M R^{\mathcal{M}} R M be the set of pairs ⟨ c , d ⟩ \langle c,d\rangle ⟨ c , d ⟩ of constant symbols such that “R c d Rcd R c d ” occurs on b b b .
We then argue by induction on the (tableau) complexity of sentences that every sentence occurring on b b b is true in M \mathcal{M} M . Thus, for example, if ∀ x ψ ( x ) \forall x\psi(x) ∀ x ψ ( x ) occurs on b b b , we know that since b b b is complete that for all constant symbols c c c occurring on b b b , ψ ( c ) \psi(c) ψ ( c ) must occur on b b b . The induction hypothesis then tells us that M ⊨ ψ ( c ) \mathcal{M}\models\psi(c) M ⊨ ψ ( c ) for all c c c occurring on b b b ; and so M ⊨ ∀ x ψ ( x ) \mathcal{M}\models\forall x\psi(x) M ⊨ ∀ x ψ ( x ) as required. □
This gives us the completeness theorem for sentences of first order logic without identity.
Adding identity
To deal with identity relations, we add two new rules and a new closure condition. The new rules are set out below. The second new rule is essentially the indiscernibility of identicals:
d = d φ ( c ) d = c φ ( d ) \begin{aligned}
&\frac{}{d=d}
&&
\frac{\varphi(c)\quad d=c}{\varphi(d)}
\end{aligned} d = d φ ( d ) φ ( c ) d = c
The first of these rules uses an arbitrary constant symbol. It ensures that the identity relation is reflexive. The second rule is essentially the indiscernibility of identicals. For the purposes of this paper, we shall only allow use of atomic and negated atomic sentences in this rule; thus, φ ( c ) \varphi(c) φ ( c ) must be an atomic or negated atomic sentence.21
The new closure condition says that whenever c ≠ c c \ne c c = c occurs on a branch, then that branch is closed. The completeness proof is then modified by letting the domain be a set of equivalence classes of constant symbols determined by the identity statements occurring on the branch. The identity rules then ensure that this interpretation of identity is congruent with the interpretation of the rest of the non-logical vocabulary.
Modifying the tableaux
Our goal is to modify the tableau process described above to fit our target application. We have two main goals:
we should be able to build models of any quantifier bounded extension of K P C KPC K P C ; and
the model building process should be idempotent.
To address (1), we shall adjust our rules so that for any k ∈ ω k \in\omega k ∈ ω , we can build a well-founded model that has the same Σ k \Sigma_k Σ k theory as the background universe. This will allow us to absorb any quantifier bounded extension of K P C KPC K P C . To achieve this, we make use of the fact that Σ k \Sigma_k Σ k satisfaction is definable in K P KP K P and use this, like the model M \mathcal{M} M in the proof of Theorem 32 , to guide the construction of an open branch. In particular, we shall make sure that there is a bound on the complexity of sentences occurring in the tree.
Regarding (2), we need to control the theory of the model we construct so that when we repeat the construction inside this model, we get essentially the same branch that determined this model. For this purpose we introduce an unusual notion of satisfiability, that we will use to guide the definition of a model in a similar fashion to the soundness proof for Theorem 32 .
Definition 33. Let Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) be a finite set of sentences from L ∈ ( C ) \mathcal{L}_{\in}(C) L ∈ ( C ) where c ˉ = c 0 , … , c n \bar{c}=c_0,\ldots,c_n c ˉ = c 0 , … , c n and let s : { c ˉ } → O r d s:\{\bar{c}\}\to Ord s : { c ˉ } → O r d be an assignment of ordinals to the constant symbols occurring on Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) .
We say that Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is rank-satisfiable with s s s if there exists a ˉ = a 0 , … , a n \bar{a}=a_0,\ldots,a_n a ˉ = a 0 , … , a n from the universe, V V V , with rank ( a i ) = s ( c i ) \operatorname{rank}(a_i)=s(c_i) rank ( a i ) = s ( c i ) for all i ≤ n i\le n i ≤ n such that ⋀ Φ ( a ˉ ) \bigwedge\Phi(\bar{a}) ⋀ Φ ( a ˉ ) is true. We say that a ˉ \bar{a} a ˉ is a realizer of the rank-satisfiability of Φ \Phi Φ by s s s .
We say that Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is minimal-rank-satisfiable with s s s if Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is rank-satisfiable with s s s and there is no t : { c ˉ } → O r d t:\{\bar{c}\}\to Ord t : { c ˉ } → O r d lexicographically preceding s s s such that Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is rank-satisfiable with t t t .
Whenever assignments s , t : { c i 0 , … , c i m } → O r d s,t:\{c_{i_0},\ldots,c_{i_m}\}\to Ord s , t : { c i 0 , … , c i m } → O r d are compared lexicographically, we assume i 0 < ⋯ < i m i_0<\cdots<i_m i 0 < ⋯ < i m and compare the tuples ⟨ s ( c i 0 ) , … , s ( c i m ) ⟩ \langle s(c_{i_0}),\ldots,s(c_{i_m})\rangle ⟨ s ( c i 0 ) , … , s ( c i m )⟩ and ⟨ t ( c i 0 ) , … , t ( c i m ) ⟩ \langle t(c_{i_0}),\ldots,t(c_{i_m})\rangle ⟨ t ( c i 0 ) , … , t ( c i m )⟩ .
Less formally, Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is rank-satisfiable with some s : { c ˉ } → O r d s:\{\bar{c}\}\to Ord s : { c ˉ } → O r d if there is a way of assigning objects to the constant symbols occurring in sentences on Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) whose ranks correspond to s s s and which satisfies each sentence in Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) . Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is then minimal-rank-satisfiable if it cannot be rank-satisfied using an ordinal assignment that is lexicographically prior to s s s .
As before, we’ll construct our tableau using sentences from the language L ∈ ( C ) \mathcal{L}_{\in}(C) L ∈ ( C ) . Let us then note a few notational conventions. We adopt the convention of writing φ ( x ˉ , c ˉ ) \varphi(\bar{x},\bar{c}) φ ( x ˉ , c ˉ ) to mean that: φ \varphi φ has at most the variables x ˉ = x 0 , … , x n \bar{x}=x_0,\ldots,x_n x ˉ = x 0 , … , x n free; and that φ \varphi φ contains at most the constant symbols c ˉ = c 0 , … , c m \bar{c}=c_0,\ldots,c_m c ˉ = c 0 , … , c m . To save space and clutter on the page, we’ll avoid being too specific about how matters like substitution work leaving most of this to the reader’s imagination. However, at places where confusion seems likely to arise we’ll try to flag this and discuss how this might be resolved.
By y ˉ < r a n k - l e x d ˉ \bar{y} <_{\mathrm{rank\text{-}lex}} \bar{d} y ˉ < rank - lex d ˉ we mean that ⟨ rank ( y 0 ) , … , rank ( y n ) ⟩ \langle\operatorname{rank}(y_0), \ldots, \operatorname{rank}(y_n)\rangle ⟨ rank ( y 0 ) , … , rank ( y n )⟩ precedes ⟨ rank ( d 0 ) , … , rank ( d n ) ⟩ \langle\operatorname{rank}(d_0), \ldots, \operatorname{rank}(d_n)\rangle ⟨ rank ( d 0 ) , … , rank ( d n )⟩ in the lexicographic order. The natural adaptation of this definition also gives us ≤ r a n k - l e x \leq_{\mathrm{rank\text{-}lex}} ≤ rank - lex and = r a n k - l e x =_{\mathrm{rank\text{-}lex}} = rank - lex . Note that each of these is easily seen to be Δ 1 \Delta_1 Δ 1 in K P KP K P . While we are introducing this as a definition in our background theory, we shall also freely use this notation as a metalinguistic abbreviation in the sentences of L ∈ ( C ) \mathcal{L}_{\in}(C) L ∈ ( C ) occurring in the tableau. This will be helpful in ensuring idempotence. To save a little space on the page, we shall frequently write ∀ y ˉ < r a n k - l e x d ˉ φ ( y ˉ , c ˉ ) \forall\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\ \varphi(\bar{y},\bar{c}) ∀ y ˉ < rank - lex d ˉ φ ( y ˉ , c ˉ ) as a metalinguistic abbreviation for ∀ y ˉ ( y ˉ < r a n k - l e x d ˉ → φ ( y ˉ , c ˉ ) ) \forall\bar{y}(\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\to\varphi(\bar{y},\bar{c})) ∀ y ˉ ( y ˉ < rank - lex d ˉ → φ ( y ˉ , c ˉ )) .
We use the prenex and complexity conventions fixed in Section 2.1. Write φ p r e n e x \varphi^{\mathrm{prenex}} φ prenex for the result of applying a fixed computable procedure that expands bounded quantifiers with their restrictions as necessary and moves the quantifiers to the front by ordinary logical equivalences. Thus φ p r e n e x \varphi^{\mathrm{prenex}} φ prenex is logically equivalent to φ \varphi φ . Bounded quantifiers before the last unbounded quantifier contribute to the alternating-block count; no closure under arbitrary bounded quantification is assumed. We shall use this procedure on the sentences occurring in the tableau when calculating their complexity.
For our first modification, our new tableau will incorporate side conditions on the sentences occurring in the tree. Nodes on the tree will, thus, be of the form ⟨ φ ( c ˉ ) , s ⟩ \langle\varphi(\bar{c}),s\rangle ⟨ φ ( c ˉ ) , s ⟩ where φ \varphi φ is a sentence of L ∈ ( C ) \mathcal{L}_{\in}(C) L ∈ ( C ) using the constant symbols c ˉ = c i 0 , … , c i m \bar{c}=c_{i_0},\ldots,c_{i_m} c ˉ = c i 0 , … , c i m and s : { c i 0 , … , c i m } → Ord s:\{c_{i_0},\ldots,c_{i_m}\}\to\operatorname{Ord} s : { c i 0 , … , c i m } → Ord . We call s s s an ordinal assignment . The motivating idea here is that s s s will provide an assignment of ranks to the constant symbols from which we shall build our model. Among other things, this will ensure that the model is well-founded. When writing out the tableau, we shall, however, save some space and only notate ordinal assignments when we add new constant symbols to a branch, as in, say, an application of the ∃ \exists ∃ rule. We shall then speak of the accumulated ordinal assignment which is essentially the union of the ordinal assignments that have occurred up to the appearance of some sentence.
In order to ensure the idempotence property holds, we also need to modify the rules of our tableau. In particular, we shall introduce a new cut rule and change the ∨ \lor ∨ and ∃ \exists ∃ rules. These are rules that allow us to choose different ways of extending a branch. The modifications are intended to ensure that the theory of the model built from the tree is strong enough to ensure that we will get the same open branch if we repeat the process.
Modified rules
Next we describe how each of the modified rules works and make some observations that will assist us in applying them. First, we leave the ¬ ∨ \neg\lor ¬ ∨ , ¬ ¬ \neg\neg ¬¬ and identity rules unchanged. We modify the ¬ ∃ \neg\exists ¬∃ rule by demanding that if a negated block of ∃ \exists ∃ quantifiers occurs at the front of some sentence, we must apply the old ¬ ∃ \neg\exists ¬∃ rule repeatedly until there are no more negated ∃ \exists ∃ quantifiers at the front of the sentence.22 We call the rules we’ve discussed so far, ordinary rules . With regard to ∨ \lor ∨ and ∃ \exists ∃ a more complex modification is required, which we describe below. In addition to this, we shall add a modified cut rule to ensure that we can preserve truths from the background universe. We call the rules that aren’t ordinary, special rules .
In order to keep the complexity of sentences occurring on the tableau under control we introduce a technical definition that partitions sentences into major and minor sentences. Any output of one of the ordinary rules will give us a major sentence. However, the special rules below produce both major and minor sentences. In the construction that is described below, we shall see that minor sentences contain a kind of redundant information that somewhat obviously holds of the model in which we are building the tableau, but which we also wish to ensure holds in the model determined by the tableau.
Special Σ k \Sigma_k Σ k -cut. Let us fix some k > 1 k > 1 k > 1 . In a tableau system, the standard cut rule tells us that for any sentence φ \varphi φ we can extend a branch by splitting into two paths with φ \varphi φ on one side and ¬ φ \neg\varphi ¬ φ on the other.23 However, in our situation, we don’t want to consider arbitrary sentences but those below a specific complexity bound. Thus, we shall use what we might call a Σ k \Sigma_k Σ k -cut rule that considers arbitrary Σ k \Sigma_k Σ k sentences. This will allow us to use a definable bounded satisfaction relation to navigate the tableau.
Suppose we have a Σ k \Sigma_k Σ k sentence from L ∈ \mathcal{L}_{\in} L ∈ (so it contains no constant symbols from C C C ) of the form
∃ x ˉ φ ( x ˉ ) \exists\bar{x}\,\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ )
where φ ( x ˉ ) \varphi(\bar{x}) φ ( x ˉ ) is Π k − 1 \Pi_{k-1} Π k − 1 .
Then we may apply the following cut rule:
φ ( d ˉ ) , s ∀ x ˉ ¬ φ ( x ˉ ) [ ∀ y ˉ < r a n k - l e x d ˉ ¬ φ ( y ˉ ) ] p r e n e x \begin{aligned}
&\varphi(\bar{d}),s
&&\forall\bar{x}\neg\varphi(\bar{x})\\
&\left[\forall\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\ \neg\varphi(\bar{y})\right]^{\mathrm{prenex}}
\end{aligned} φ ( d ˉ ) , s [ ∀ y ˉ < rank - lex d ˉ ¬ φ ( y ˉ ) ] prenex ∀ x ˉ ¬ φ ( x ˉ )
where:
on the left, d ˉ = d 0 , … , d n \bar{d}=d_0,\ldots,d_n d ˉ = d 0 , … , d n must be the next constant symbols not already used on the branch; and
s : { d 0 , … , d n } → Ord s:\{d_0,\ldots,d_n\}\to\operatorname{Ord} s : { d 0 , … , d n } → Ord .
We say that φ ( d ˉ ) \varphi(\bar{d}) φ ( d ˉ ) is a major sentence and that [ ∀ y ˉ < r a n k - l e x d ˉ ¬ φ ( y ˉ ) ] p r e n e x \left[\forall\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\ \neg\varphi(\bar{y})\right]^{\mathrm{prenex}} [ ∀ y ˉ < rank - lex d ˉ ¬ φ ( y ˉ ) ] prenex and ∀ x ˉ ¬ φ ( x ˉ ) \forall\bar{x}\neg\varphi(\bar{x}) ∀ x ˉ ¬ φ ( x ˉ ) are minor sentences.
Observe that we are eliminating all of the existential quantifiers at the front of the sentence, not just the first one. Note that the diagram for the rule is also a little misleading in that it looks like there are just two choices. In fact, the left move is an abbreviation for a proper class of different options according to our choice of s : { d ˉ } → Ord s:\{\bar{d}\}\to\operatorname{Ord} s : { d ˉ } → Ord . Also observe that: φ ( d ˉ ) \varphi(\bar{d}) φ ( d ˉ ) is Π k − 1 \Pi_{k-1} Π k − 1 ; ∀ x ˉ ¬ φ ( x ˉ ) \forall\bar{x}\neg\varphi(\bar{x}) ∀ x ˉ ¬ φ ( x ˉ ) is Π k \Pi_k Π k and [ ∀ y ˉ < r a n k - l e x d ˉ ¬ φ ( y ˉ ) ] p r e n e x \left[\forall\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\ \neg\varphi(\bar{y})\right]^{\mathrm{prenex}} [ ∀ y ˉ < rank - lex d ˉ ¬ φ ( y ˉ ) ] prenex is Π k \Pi_k Π k . For the last of these, we rely on the fact that we have converted this entire sentence into prenex normal form.
The motivation behind the rule may be described as follows. In applying the rule, we are considering whether or not to add ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) . If we take the right move, then we are choosing not to make this sentence true. If we take one of the left moves, we are choosing to make it true and so we witness with a sequence d ˉ \bar{d} d ˉ of constant symbols and an ordinal assignment s s s of ranks to those constants. But more than that, we add a second sentence which says that there is no way of satisfying φ ( x ˉ ) \varphi(\bar{x}) φ ( x ˉ ) with a sequence of objects whose ranks preceded those of d ˉ \bar{d} d ˉ . This will help us to ensure that we get the same branch when we repeat the model building process.24
Special ∨ \lor ∨ . Next we consider a modification of the ∨ \lor ∨ rule.
φ ( c ˉ ) ∨ ψ ( c ˉ ) \varphi(\bar{c}) \lor\psi(\bar{c}) φ ( c ˉ ) ∨ ψ ( c ˉ )
φ ( c ˉ ) [ ∀ y ˉ < rank-lex d ˉ ¬ ( ψ ( y ˉ ) ∧ Ψ ( y ˉ ) ) ] prenex ψ ( c ˉ ) [ ∀ y ˉ ≤ rank-lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ ) ) ] prenex \begin{aligned}
\varphi(\bar{c}) \qquad& [\forall\bar{y} <_{\operatorname{rank\text{-}lex}} \bar{d}\ \neg(\psi(\bar{y}) \land\Psi(\bar{y}))]^{\operatorname{prenex}} \\
\psi(\bar{c}) \qquad& [\forall\bar{y} \le_{\operatorname{rank\text{-}lex}} \bar{d}\ \neg(\varphi(\bar{y}) \land\Psi(\bar{y}))]^{\operatorname{prenex}}
\end{aligned} φ ( c ˉ ) ψ ( c ˉ ) [ ∀ y ˉ < rank - lex d ˉ ¬ ( ψ ( y ˉ ) ∧ Ψ ( y ˉ )) ] prenex [ ∀ y ˉ ≤ rank - lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ )) ] prenex
where:
d ˉ = d 0 , … , d n \bar{d} = d_0, \ldots, d_n d ˉ = d 0 , … , d n are the constant symbols that have already occurred on the branch and which, thus, include c ˉ \bar{c} c ˉ ; and
Ψ ( d ˉ ) \Psi(\bar{d}) Ψ ( d ˉ ) is the set of major sentences already occurring on the branch.
We then say that φ ( c ˉ ) \varphi(\bar{c}) φ ( c ˉ ) and ψ ( c ˉ ) \psi(\bar{c}) ψ ( c ˉ ) are major sentences while [ ∀ y ˉ < rank-lex d ˉ ¬ ( ψ ( y ˉ ) ∧ Ψ ( y ˉ ) ) ] prenex [\forall\bar{y} <_{\operatorname{rank\text{-}lex}} \bar{d}\ \neg(\psi(\bar{y}) \land\Psi(\bar{y}))]^{\operatorname{prenex}} [ ∀ y ˉ < rank - lex d ˉ ¬ ( ψ ( y ˉ ) ∧ Ψ ( y ˉ )) ] prenex and [ ∀ y ˉ ≤ rank-lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ ) ) ] prenex [\forall\bar{y} \le_{\operatorname{rank\text{-}lex}} \bar{d}\ \neg(\varphi(\bar{y}) \land\Psi(\bar{y}))]^{\operatorname{prenex}} [ ∀ y ˉ ≤ rank - lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ )) ] prenex are minor sentences.
This is the same as the standard ∨ \lor ∨ rule except for the extra sentences below φ ( c ˉ ) \varphi(\bar{c}) φ ( c ˉ ) and ψ ( c ˉ ) \psi(\bar{c}) ψ ( c ˉ ) . The reader will also see that this rule is incredibly inefficient in that when we apply the rule, we are forcing ourselves to essentially repeat a lot of work that has already been done. Fortunately for our purposes, this kind of efficiency is not important.
The motivating idea is to ensure that:
when we turn left, there is no way to satisfy ψ ( y ˉ ) \psi(\bar{y}) ψ ( y ˉ ) with an assignment sequence whose ranks lexicographically precede those of the assignment for φ ( c ˉ ) \varphi(\bar{c}) φ ( c ˉ ) and the sentences already occurring on the branch; and
when we turn right, there is no way to satisfy φ ( y ˉ ) \varphi(\bar{y}) φ ( y ˉ ) with an assignment sequence whose ranks lexicographically precede or equal those of the assignment for ψ ( c ˉ ) \psi(\bar{c}) ψ ( c ˉ ) and the sentences already occurring on the branch.
Note that if φ ( x ˉ ) \varphi(\bar{x}) φ ( x ˉ ) and all the sentences occurring in Ψ ( y ˉ ) \Psi(\bar{y}) Ψ ( y ˉ ) (i.e., the major sentences already occurring on the branch) are Σ k \Sigma_k Σ k (or less), then [ ∀ y ˉ ≤ rank-lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ ) ) ] prenex [\forall\bar{y} \le_{\operatorname{rank\text{-}lex}} \bar{d}\ \neg(\varphi(\bar{y}) \land\Psi(\bar{y}))]^{\operatorname{prenex}} [ ∀ y ˉ ≤ rank - lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ )) ] prenex is Π k \Pi_k Π k .
Special ∃ \exists ∃ . Finally, we consider a modification of the ∃ \exists ∃ rule.
∃ x ˉ φ ( x ˉ , c ˉ ) \exists\bar{x}\ \varphi(\bar{x},\bar{c}) ∃ x ˉ φ ( x ˉ , c ˉ )
φ ( d ˉ , c ˉ ) , s [ ∀ y ˉ , z ˉ < rank-lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ Ψ ( y ˉ ) ) ] prenex \frac{\varphi(\bar{d},\bar{c}),s}{[\forall\bar{y},\bar{z} <_{\operatorname{rank\text{-}lex}} \bar{c},\bar{d}\ \neg(\varphi(\bar{z},\bar{y}) \land\Psi(\bar{y}))]^{\operatorname{prenex}}} [ ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ Ψ ( y ˉ )) ] prenex φ ( d ˉ , c ˉ ) , s
where:
c ˉ \bar{c} c ˉ are the constant symbols that have already occurred on the branch;25
Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) is the set of major sentences already occurring on the branch;
d ˉ \bar{d} d ˉ must be the next constant symbols not already used on the branch; and
s : { d ˉ } → O r d s:\{\bar{d}\}\to Ord s : { d ˉ } → O r d .
We say that φ ( d ˉ , c ˉ ) \varphi(\bar{d},\bar{c}) φ ( d ˉ , c ˉ ) is a major sentence and that
[ ∀ y ˉ , z ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) ] p r e n e x \left[\forall\bar{y},\bar{z}<_{\mathrm{rank\text{-}lex}}\bar{c},\bar{d}\ \neg\left(\varphi(\bar{z},\bar{y})\land\bigwedge\Psi(\bar{y})\right)\right]^{\mathrm{prenex}} [ ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) ] prenex
is a minor sentence. Again note that the diagram for the rule is a little misleading: there is a proper class of different options according to the different ordinal assignments s s s that go along with φ ( d ˉ , c ˉ ) \varphi(\bar{d},\bar{c}) φ ( d ˉ , c ˉ ) . Observe that this is the same as the ordinary ∃ \exists ∃ rule except that we add an extra sentence which is intended to ensure that there can be no sequence y ˉ , z ˉ \bar{y},\bar{z} y ˉ , z ˉ whose ranks precede those of c ˉ , d ˉ \bar{c},\bar{d} c ˉ , d ˉ that satisfies φ ( z ˉ , y ˉ ) \varphi(\bar{z},\bar{y}) φ ( z ˉ , y ˉ ) along with every major sentence already occurring on the branch. Note that if φ ( y ˉ , c ˉ ) \varphi(\bar{y},\bar{c}) φ ( y ˉ , c ˉ ) and every sentence in Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) are Σ k \Sigma_k Σ k (or less) then
[ ∀ y ˉ , z ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) ] p r e n e x \left[\forall\bar{y},\bar{z}<_{\mathrm{rank\text{-}lex}}\bar{c},\bar{d}\ \neg\left(\varphi(\bar{z},\bar{y})\land\bigwedge\Psi(\bar{y})\right)\right]^{\mathrm{prenex}} [ ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) ] prenex
is Π k \Pi_k Π k .
An important lemma
The following lemma establishes that we can put a quantifier bound on the complexity of sentences occurring in our tableau. This means that we can use a definable satisfaction predicate to guide the definition of an open branch.
Lemma 34. Suppose T T T is a (possibly incomplete) tableau produced using the system described above. Then every minor sentence on T T T is Π k \Pi_k Π k and every major sentence is Σ k \Sigma_k Σ k .
Proof. We proceed by induction on the length of branches to show that:
the complexity of any major sentence is Σ k \Sigma_k Σ k ; and
the complexity of every minor sentence is Π k \Pi_k Π k .
For the ¬ ∨ \neg\lor ¬ ∨ , ¬ ∃ \neg\exists ¬∃ and ¬ ¬ \neg\neg ¬¬ rules this is obvious: applying those rules always adds sentences of the same or lower complexity than the sentence to which those rules are applied. This suffices since it can be seen that every sentence on T T T is in prenex normal form and so we can only apply the ¬ ∨ \neg\lor ¬ ∨ and ¬ ¬ \neg\neg ¬¬ rules to Δ 0 \Delta_0 Δ 0 -sentences. The ¬ ∃ \neg\exists ¬∃ rule can apply to sentences more complex than Δ 0 \Delta_0 Δ 0 ; for instance a ¬ ∃ \neg\exists ¬∃ formula may result from taking the right move on a Special Σ k \Sigma_k Σ k -cut rule and thus, be Π k \Pi_k Π k . The sentence resulting will always be Σ k − 1 \Sigma_{k-1} Σ k − 1 which suffices. For the identity rules, note that we are only allowed to use them on atomic and negated atomic sentences. So we just need to consider the special rules described above.
(Special Σ k \Sigma_k Σ k -cut) Supposing we cut on ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) where φ ( x ˉ ) \varphi(\bar{x}) φ ( x ˉ ) is Π k − 1 \Pi_{k-1} Π k − 1 , we see that: the major sentence φ ( d ˉ ) \varphi(\bar{d}) φ ( d ˉ ) is Π k − 1 \Pi_{k-1} Π k − 1 and thus Σ k \Sigma_k Σ k ; the minor sentences ∀ x ˉ ¬ φ ( x ˉ ) \forall\bar{x}\neg\varphi(\bar{x}) ∀ x ˉ ¬ φ ( x ˉ ) and
[ ∀ y ˉ < r a n k - l e x d ˉ ¬ φ ( y ˉ ) ] p r e n e x \left[\forall\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\ \neg\varphi(\bar{y})\right]^{\mathrm{prenex}} [ ∀ y ˉ < rank - lex d ˉ ¬ φ ( y ˉ ) ] prenex
are both Π k \Pi_k Π k .
(Special ∨ \lor ∨ ) It is not difficult to see that our rules ensure that every sentence occurring in T T T is in prenex normal form. This means that the only way for a disjunction, φ ( c ˉ ) ∨ ψ ( c ˉ ) \varphi(\bar{c})\lor\psi(\bar{c}) φ ( c ˉ ) ∨ ψ ( c ˉ ) , to occur in T T T is if both φ ( c ˉ ) \varphi(\bar{c}) φ ( c ˉ ) and ψ ( c ˉ ) \psi(\bar{c}) ψ ( c ˉ ) are Δ 0 \Delta_0 Δ 0 . Thus, the major sentences are both Σ k \Sigma_k Σ k . Moreover, by the induction hypothesis, we see that the set Ψ ( d ˉ ) \Psi(\bar{d}) Ψ ( d ˉ ) of major sentences occurring on the branch so far is a conjunction of Σ k \Sigma_k Σ k sentences. Thus, the minor sentences can both be seen to be Π k \Pi_k Π k .
(Special ∃ \exists ∃ ) Similarly, since every sentence occurring in T T T is in prenex normal form, we see that the only way for a sentence of the form ∃ x ˉ φ ( x ˉ , c ˉ ) \exists\bar{x}\ \varphi(\bar{x},\bar{c}) ∃ x ˉ φ ( x ˉ , c ˉ ) to occur on T T T is if it is Σ k \Sigma_k Σ k . Using the induction hypothesis, we see that every sentence in Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) is Σ k \Sigma_k Σ k , and so the prenex normal form of
∀ y ˉ , z ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) \forall\bar{y},\bar{z}<_{\mathrm{rank\text{-}lex}}\bar{c},\bar{d}\ \neg\left(\varphi(\bar{z},\bar{y})\land\bigwedge\Psi(\bar{y})\right) ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) )
will be Π k \Pi_k Π k as required. □
:::
A standard process
Before we move on to describing the model-building process and establishing that it is idempotent, let us first suppose that we have fixed upon a particular order in the applications of our rules. The purpose of this is to give us a particular canonical tableau T \mathcal{T} T that we can refer to below. Similar processes can be found in many sources, so we content ourselves with a quick sketch [33 ] .
For one way of doing this, we essentially just work our way down a branch applying the next rule that needs to be applied. This works for rules that only require one application, like ¬ ∨ \neg\lor ¬ ∨ , Special ∨ \lor ∨ and Special ∃ \exists ∃ . However, for the Special ∃ \exists ∃ rule let us suppose that we always add the next sequence d ˉ = d 0 , … , d m \bar{d}=d_{0},\ldots,d_{m} d ˉ = d 0 , … , d m of elements from C C C to witness that ∃ x ˉ φ ( x ˉ , c ˉ ) \exists\bar{x}\,\varphi(\bar{x},\bar{c}) ∃ x ˉ φ ( x ˉ , c ˉ ) . Thus, if we’ve already used { c 0 , … , c n } \{c_{0},\ldots,c_{n}\} { c 0 , … , c n } on a particular branch, then we let d ˉ = c n + 1 , … , c n + m + 1 \bar{d}=c_{n+1},\ldots,c_{n+m+1} d ˉ = c n + 1 , … , c n + m + 1 .
For the identity and ¬ ∃ \neg\exists ¬∃ rules, we need to make infinitely many applications. So after every application of the other rules, we should go back to the beginning of the branch and do the next application of each identity and ¬ ∃ \neg\exists ¬∃ rule before moving on. In applications of the ¬ ∃ \neg\exists ¬∃ rule and the reflexive identity rule, we only allow the substitution of constant symbols that have already occurred on the branch; and we demand that every such constant symbol is eventually used.26 After doing that we still need to deal with Special Σ k \Sigma_{k} Σ k -cut. For this rule, we suppose we have a simple enumeration of the Σ k \Sigma_{k} Σ k sentences and so, after doing the next round of applications to each identity and ¬ ∃ \neg\exists ¬∃ rule, we then do the next Special Σ k \Sigma_{k} Σ k -cut. Finally, fix once and for all an initial branch (say the empty branch) and a primitive-recursive fair scheduling procedure which, from the code of a finite branch, determines the next pending ordinary-rule application, the next identity or ¬ ∃ \neg\exists ¬∃ instance, and the next Σ k \Sigma_{k} Σ k cut. The tableau generated using this fixed schedule will be called the canonical tableau that we shall denote as T \mathcal{T} T .
Building models
Let T T T be a theory as described in the statement of Lemma 30. Thus, we may fix some k > 3 k>3 k > 3 such that for all sentences φ ∈ T ∖ K P C \varphi\in T\setminus KPC φ ∈ T ∖ K P C , φ \varphi φ is Σ k \Sigma_{k} Σ k . For the remainder of this section, we work in the theory T T T unless stated otherwise. This means, for example, if we say that some relation is well-founded, it is well-founded according to T T T .27
Let T \mathcal{T} T be the canonical tableau using Special Σ k \Sigma_{k} Σ k -cut described above. Our goal is to use minimal-rank-satisfiability as a guide to defining an open branch through T \mathcal{T} T and then use that branch to interpret a well-founded model that is Σ k \Sigma_{k} Σ k elementary equivalent to our background universe.
Soundness
We are ready to describe a process for finding an open branch through T \mathcal{T} T . We start by making our lives a little easier with a sequence of three little claims showing that it will actually suffice to merely preserve rank-satisfiability (rather than minimal-rank-satisfiability). First, we observe that the truth of minor sentences only depends on the ranks of their constant symbols.
Proposition 35. Suppose χ ( c ˉ ) \chi(\bar{c}) χ ( c ˉ ) is of the form of one of the minor sentences. If a ˉ \bar{a} a ˉ and e ˉ \bar{e} e ˉ are such that rank ( a i ) = rank ( e i ) \operatorname{rank}(a_i)=\operatorname{rank}(e_i) rank ( a i ) = rank ( e i ) for all i < l h ( a ˉ ) i<lh(\bar{a}) i < l h ( a ˉ ) then
χ ( a ˉ ) ↔ χ ( e ˉ ) . \chi(\bar{a})\leftrightarrow\chi(\bar{e}). χ ( a ˉ ) ↔ χ ( e ˉ ) .
Proof. Observe that minor sentences are only concerned with the ranks of the constants they mention. For example,
∀ z ˉ , y ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) \forall\bar{z},\bar{y} <_{\mathrm{rank\text{-}lex}} \bar{c},\bar{d}\ \neg\left(\varphi(\bar{z},\bar{y}) \land\bigwedge\Psi(\bar{y})\right) ∀ z ˉ , y ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) )
is clearly satisfied by any interpretations a ˉ , e ˉ \bar{a},\bar{e} a ˉ , e ˉ for c ˉ , d ˉ \bar{c},\bar{d} c ˉ , d ˉ with the same rank. □
Now we shift our attention to branches in our tableau. We use the proposition above to show that if all the sentences on some branch are rank-satisfied with their accumulated ordinal assignment, then any realizer of its major sentences will also realize its minor sentences.
Proposition 36. Let b b b be a branch in T T T , Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) be the sentences occurring on b b b ; and Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) be the major sentences occurring on b b b . Suppose that Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is rank-satisfiable with s : { c ˉ } → O r d s:\{\bar{c}\}\to Ord s : { c ˉ } → O r d . Then every realizer a ˉ \bar{a} a ˉ for Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) being rank satisfiable with s s s is also a realizer for the rank-satisfiability of Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) with s s s .
Proof. Let e ˉ \bar{e} e ˉ be a realizer for the rank-satisfiability of Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) with s s s . Then suppose that a ˉ \bar{a} a ˉ is a realizer for the rank-satisfiability of Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) at s s s . We claim that a ˉ \bar{a} a ˉ is also a realizer for the satisfiability of Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) with s s s . To see this, let χ ( c ˉ ) \chi(\bar{c}) χ ( c ˉ ) be a minor sentence occurring on b b b . By our assumption, χ ( e ˉ ) \chi(\bar{e}) χ ( e ˉ ) is true and so Proposition 35 tells us that χ ( a ˉ ) \chi(\bar{a}) χ ( a ˉ ) is also true; and thus, we see that a ˉ \bar{a} a ˉ is a realizer for the rank-satisfiability of Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) with s s s . □
We then put this together to show that for branches in a tableau, rank-satisfiability implies minimal-rank-satisfiability.
Lemma 37. Suppose that b b b is a branch in T T T . Let Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) be the set of sentences occurring on b b b ; let Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) be the set of major sentences occurring on b b b ; and let s s s be the accumulated ordinal assignment. Suppose that Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is rank-satisfiable with s s s . Then
(1) Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) is minimal-rank-satisfiable with s s s ; and
(2) Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is minimal-rank-satisfiable with s s s .
Proof. We will prove (1) by induction on the length of branches. To see that (2) follows, fix using (1), a realizer a ˉ \bar{a} a ˉ for Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) being minimal-rank-satisfiable with s s s . Then by Proposition 36, we see that a ˉ \bar{a} a ˉ is also a realizer for Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) being rank-satisfiable. Then since a ˉ \bar{a} a ˉ is minimal for Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) with s s s and Ψ ( c ˉ ) ⊆ Φ ( c ˉ ) \Psi(\bar{c})\subseteq\Phi(\bar{c}) Ψ ( c ˉ ) ⊆ Φ ( c ˉ ) , it must also be minimal for Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) as required.
We proceed by induction on the length of branches. Suppose that we have established that (1) holds for b b b and wish to show that (1) still holds if we extend the branch to a new position b ∗ b^{*} b ∗ in T T T by following the rules.
Suppose first that the rule used to get to b ∗ b^{*} b ∗ from b b b was one that adds a formula that introduces no new constant symbols (i.e., an ordinary rule, Special ∨ \vee ∨ , or the right move in Special Σ k \Sigma_k Σ k -cut). Let Φ ∗ ( c ˉ ) \Phi^{*}(\bar{c}) Φ ∗ ( c ˉ ) and Ψ ∗ ( c ˉ ) \Psi^{*}(\bar{c}) Ψ ∗ ( c ˉ ) be respectively the sets of all and merely major sentences occurring on b ∗ b^{*} b ∗ ; and let Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) and Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) be the corresponding sets for b b b . Let s s s be the accumulated ordinal assignment for b b b and, thus, b ∗ b^{*} b ∗ too.
Then suppose that Φ ∗ ( c ˉ ) \Phi^{*}(\bar{c}) Φ ∗ ( c ˉ ) is rank-satisfiable with s s s . Then Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) is also rank-satisfiable with s ˉ \bar{s} s ˉ and so the induction hypothesis tells us that Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) is minimal-rank-satisfiable with s s s . But then since Ψ ∗ ( c ˉ ) ⊇ Ψ ( c ˉ ) \Psi^{*}(\bar{c})\supseteq\Psi(\bar{c}) Ψ ∗ ( c ˉ ) ⊇ Ψ ( c ˉ ) , we see that Ψ ∗ ( a ˉ ) \Psi^{*}(\bar{a}) Ψ ∗ ( a ˉ ) cannot be rank-satisfied by any s 0 s_0 s 0 preceding $s. Suppose next that the rule used to get from b b b to b ∗ b^* b ∗ does add new constant symbols. Thus, it must be the left move of Special Σ k \Sigma_k Σ k -cut or Special ∃ \exists ∃ . Let Φ ∗ ( c ˉ , d ˉ ) \Phi^*(\bar{c},\bar{d}) Φ ∗ ( c ˉ , d ˉ ) and Ψ ∗ ( c ˉ , d ˉ ) \Psi^*(\bar{c},\bar{d}) Ψ ∗ ( c ˉ , d ˉ ) be respectively the sets of all and merely major sentences occurring on b ∗ b^* b ∗ where d ˉ \bar{d} d ˉ are the new constant symbols; and let Φ ( c ˉ ) \Phi(\bar{c}) Φ ( c ˉ ) and Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) be the corresponding sets for b b b . Let s 0 s_0 s 0 be the accumulated ordinal assignment for b b b and s 0 ∪ s s_0 \cup s s 0 ∪ s be the accumulated ordinal assignment for b ∗ b^* b ∗ .
(Special Σ k \Sigma_k Σ k -cut, left move) Suppose that b ∗ b^* b ∗ is extended from b b b using
φ ( d ˉ ) , s \varphi(\bar{d}),s φ ( d ˉ ) , s
∀ y ˉ < r a n k - l e x d ˉ ¬ φ ( y ˉ ) . \forall\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\ \neg\varphi(\bar{y}). ∀ y ˉ < rank - lex d ˉ ¬ φ ( y ˉ ) .
Now suppose that Φ ∗ ( c ˉ , d ˉ ) \Phi^*(\bar{c},\bar{d}) Φ ∗ ( c ˉ , d ˉ ) is rank-satisfiable with s 0 ∪ s s_0 \cup s s 0 ∪ s as realized by a ˉ , e ˉ \bar{a},\bar{e} a ˉ , e ˉ . Suppose toward a contradiction that Ψ ∗ ( c ˉ , d ˉ ) \Psi^*(\bar{c},\bar{d}) Ψ ∗ ( c ˉ , d ˉ ) is not minimal-rank-satisfiable with s 0 ∪ s s_0 \cup s s 0 ∪ s . Then we may fix o ˉ , u ˉ < r a n k - l e x a ˉ , e ˉ \bar{o},\bar{u}<_{\mathrm{rank\text{-}lex}}\bar{a},\bar{e} o ˉ , u ˉ < rank - lex a ˉ , e ˉ such that Ψ ∗ ( o ˉ , u ˉ ) \Psi^*(\bar{o},\bar{u}) Ψ ∗ ( o ˉ , u ˉ ) is satisfiable. We break into two cases. First, if o ˉ < r a n k - l e x a ˉ \bar{o}<_{\mathrm{rank\text{-}lex}}\bar{a} o ˉ < rank - lex a ˉ then, Ψ ( o ˉ ) \Psi(\bar{o}) Ψ ( o ˉ ) is true, contradicting the induction hypothesis that told us Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) was minimal-rank-satisfiable with s 0 s_0 s 0 . Second, if o ˉ = r a n k - l e x a ˉ \bar{o}=_{\mathrm{rank\text{-}lex}}\bar{a} o ˉ = rank - lex a ˉ and u ˉ < r a n k - l e x e ˉ \bar{u}<_{\mathrm{rank\text{-}lex}}\bar{e} u ˉ < rank - lex e ˉ , then ∀ y ˉ < r a n k - l e x d ˉ ¬ φ ( y ˉ ) \forall\bar{y}<_{\mathrm{rank\text{-}lex}}\bar{d}\ \neg\varphi(\bar{y}) ∀ y ˉ < rank - lex d ˉ ¬ φ ( y ˉ ) is false, which contradicts our assumption that Φ ( c ˉ , d ˉ ) \Phi(\bar{c},\bar{d}) Φ ( c ˉ , d ˉ ) is rank-satisfiable with s 0 ∪ s s_0 \cup s s 0 ∪ s .
(Special ∃ \exists ∃ ) Suppose b b b is extended to b ∗ b^* b ∗ by adding
φ ( d ˉ , c ˉ ) , s \varphi(\bar{d},\bar{c}),s φ ( d ˉ , c ˉ ) , s
[ ∀ y ˉ , z ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) ] p r e n e x . \left[\forall\bar{y},\bar{z}<_{\mathrm{rank\text{-}lex}}\bar{c},\bar{d}\ \neg\bigl(\varphi(\bar{z},\bar{y})\wedge\bigwedge\Psi(\bar{y})\bigr)\right]^{\mathrm{prenex}}. [ ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) ] prenex .
Now suppose that Φ ∗ ( c ˉ , d ˉ ) \Phi^*(\bar{c},\bar{d}) Φ ∗ ( c ˉ , d ˉ ) is rank-satisfiable with s 0 ∪ s s_0 \cup s s 0 ∪ s as realized by a ˉ , e ˉ \bar{a},\bar{e} a ˉ , e ˉ . Then suppose toward a contradiction that Ψ ∗ ( c ˉ , d ˉ ) \Psi^*(\bar{c},\bar{d}) Ψ ∗ ( c ˉ , d ˉ ) is not minimal-rank-satisfiable with s 0 ∪ s s_0\cup s s 0 ∪ s . Then we may fix o ˉ , u ˉ < r a n k - l e x a ˉ , e ˉ \bar{o},\bar{u}<_{\mathrm{rank\text{-}lex}}\bar{a},\bar{e} o ˉ , u ˉ < rank - lex a ˉ , e ˉ such that Ψ ∗ ( o ˉ , u ˉ ) \Psi^*(\bar{o},\bar{u}) Ψ ∗ ( o ˉ , u ˉ ) is satisfiable. We break into two cases. First, if o ˉ < r a n k - l e x a ˉ \bar{o}<_{\mathrm{rank\text{-}lex}}\bar{a} o ˉ < rank - lex a ˉ then, Ψ ( o ˉ ) \Psi(\bar{o}) Ψ ( o ˉ ) is true, contradicting the induction hypothesis that told us Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) was minimal-rank-satisfiable with s 0 s_0 s 0 . Second, if o ˉ = r a n k - l e x a ˉ \bar{o}=_{\mathrm{rank\text{-}lex}}\bar{a} o ˉ = rank - lex a ˉ and u ˉ < r a n k - l e x e ˉ \bar{u}<_{\mathrm{rank\text{-}lex}}\bar{e} u ˉ < rank - lex e ˉ , then ∀ y ˉ , z ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) \forall\bar{y},\bar{z}<_{\mathrm{rank\text{-}lex}}\bar{c},\bar{d}\ \neg(\varphi(\bar{z},\bar{y})\wedge\bigwedge\Psi(\bar{y})) ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ )) is false, contradicting our assumption that Φ ∗ ( c ˉ , d ˉ ) \Phi^*(\bar{c},\bar{d}) Φ ∗ ( c ˉ , d ˉ ) is rank satisfiable with s 0 ∪ s s_0\cup s s 0 ∪ s . □
Finally, we are ready to build our open branch. Since the process is inductive, we focus first on the process of extending a particular branch. First a quick technical definition: let us say that a finite branch b b b in T T T is (minimal-)rank-satisfiable, if the sentences on b b b are (minimal-)rank-satisfiable with their accumulated rank-assignment.
Lemma 38. (Branch Extension ) Suppose b b b is a finite branch in T T T that is minimal rank-satisfiable. Then there is a way of selecting an extension b ∗ b^* b ∗ in T T T of b b b that is also minimal-rank-satisfiable. Moreover, b ∗ b^* b ∗ is uniformly Δ k + 1 \Delta_{k+1} Δ k + 1 definable from b b b .
Proof. We must consider what happens when each of the rules is applied. If b b b is extended with an application of an ordinary rule minimal-rank-satisfaction is obviously preserved. So we shall just consider: Special Σ k \Sigma_k Σ k -cut, Special ∀ \forall ∀ ; and Special ∃ \exists ∃ . We shall make use of a uniformly Δ k + 1 \Delta_{k+1} Δ k + 1 -definable satisfaction relation which is able to assess the truth of Boolean combinations of Σ k \Sigma_k Σ k -formulae. We also note that Lemma 37 makes our life easier by establishing that we only need to show that the extension of b b b is rank-satisfiable. (Special Σ k \Sigma_k Σ k -cut) Suppose b b b is extended to b ∗ b^* b ∗ by an application of the Special Σ k \Sigma_k Σ k -cut and that ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) is the cut-formula where φ ( x ˉ ) \varphi(\bar{x}) φ ( x ˉ ) is Π k − 1 \Pi_{k-1} Π k − 1 . If ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) is true, we extend b b b to b ∗ b^* b ∗ by taking the left move which adds
φ ( d ˉ ) , s \varphi(\bar{d}),s φ ( d ˉ ) , s
∀ y ˉ < r a n k − l e x d ˉ ¬ φ ( y ˉ ) \forall\bar{y}<_{\mathrm{rank-lex}}\bar{d}\ \neg\varphi(\bar{y}) ∀ y ˉ < rank − lex d ˉ ¬ φ ( y ˉ )
to b b b , where s : { d ˉ } → O r d s:\{\bar{d}\}\to Ord s : { d ˉ } → O r d is the lexicographically least assignment such that there is some a ˉ = a 0 , … , a n \bar{a}=a_0,\ldots,a_n a ˉ = a 0 , … , a n from V V V with rank ( a i ) = s ( d i ) \operatorname{rank}(a_i)=s(d_i) rank ( a i ) = s ( d i ) for i ≤ n i\leq n i ≤ n such that φ ( a ˉ ) \varphi(\bar{a}) φ ( a ˉ ) is true. The formula identifying such s s s is Δ k + 1 \Delta_{k+1} Δ k + 1 . Indeed, existence of a realizer with a prescribed rank profile is Σ k \Sigma_k Σ k , and taking the lexicographically least such profile is therefore Δ k + 1 \Delta_{k+1} Δ k + 1 . It is then clear that the extension of b b b with the major sentence φ ( d ˉ ) \varphi(\bar{d}) φ ( d ˉ ) is minimal-rank-satisfiable with s s s . Moreover, our choice of s s s for d ˉ \bar{d} d ˉ ensures that ∀ y ˉ < r a n k − l e x d ˉ ¬ φ ( y ˉ ) \forall\bar{y}<_{\mathrm{rank-lex}}\bar{d}\ \neg\varphi(\bar{y}) ∀ y ˉ < rank − lex d ˉ ¬ φ ( y ˉ ) is satisfied, which means that b ∗ b^* b ∗ is rank-satisfiable. If ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) is not true, we simply extend b b b to b ∗ b^* b ∗ by taking the right move.
(Special ∨ \lor ∨ ) Suppose b b b is extended by an application of the Special ∨ \lor ∨ rule to φ ( c ˉ ) ∨ ψ ( c ˉ ) \varphi(\bar{c})\lor\psi(\bar{c}) φ ( c ˉ ) ∨ ψ ( c ˉ ) . Then by our assumptions, we see that b b b is minimal-rank-satisfiable, as witnessed by an ordinal assignment s : { d ˉ } → O r d s:\{\bar{d}\}\to Ord s : { d ˉ } → O r d where d ˉ \bar{d} d ˉ are the constant symbols occurring in sentences on b b b . Let Ψ ( d ˉ ) \Psi(\bar{d}) Ψ ( d ˉ ) be the set of major sentences occurring on b b b and observe that the constant symbols c ˉ \bar{c} c ˉ are included in d ˉ \bar{d} d ˉ . Then clearly one of the extensions of b b b by φ ( c ˉ ) \varphi(\bar{c}) φ ( c ˉ ) or ψ ( c ˉ ) \psi(\bar{c}) ψ ( c ˉ ) is rank-satisfiable, as witnessed by s s s . Let b ∗ b^* b ∗ be the extension of b b b that adds the leftmost of those sentences.28 Our selection process then ensures that the minor sentence is satisfied by a sequence of objects whose ranks accord with the ordinal assignment for d ˉ \bar{d} d ˉ . If we turn left, the minor sentence follows from the minimality of major sentences in Ψ \Psi Ψ . Similarly, if we turn right, except that we have incorporated a tie-breaking condition.
(Special ∃ \exists ∃ ) Suppose b b b is extended by an application of the Special ∃ \exists ∃ rules to ∃ x ˉ φ ( x ˉ , c ˉ ) \exists\bar{x}\,\varphi(\bar{x},\bar{c}) ∃ x ˉ φ ( x ˉ , c ˉ ) . Suppose that s 0 : { c ˉ } → O r d s_0:\{\bar{c}\}\to Ord s 0 : { c ˉ } → O r d is the accumulated ordinal assignment for b b b . Then we extend b b b to b ∗ b^* b ∗ by adding
φ ( d ˉ , c ˉ ) , s 1 \varphi(\bar{d},\bar{c}),s_1 φ ( d ˉ , c ˉ ) , s 1
[ ∀ y ˉ , z ˉ < r a n k − l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ Ψ ( y ˉ ) ) ] p r e n e x \left[\forall\bar{y},\bar{z}<_{\mathrm{rank-lex}}\bar{c},\bar{d}\ \neg\left(\varphi(\bar{z},\bar{y})\land\Psi(\bar{y})\right)\right]^{\mathrm{prenex}} [ ∀ y ˉ , z ˉ < rank − lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ Ψ ( y ˉ ) ) ] prenex
below b b b where: Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) is the conjunction of the major sentences occurring on b b b ; and s 1 : { d ˉ } → O r d s_1:\{\bar{d}\}\to Ord s 1 : { d ˉ } → O r d is the lexicographically least assignment such that there exist a ˉ = a 0 , … , a n \bar{a}=a_0,\ldots,a_n a ˉ = a 0 , … , a n and e ˉ = e 0 , … , e m \bar{e}=e_0,\ldots,e_m e ˉ = e 0 , … , e m from V V V with rank ( a i ) = s 0 ( c i ) \operatorname{rank}(a_i)=s_0(c_i) rank ( a i ) = s 0 ( c i ) for all i ≤ n i\leq n i ≤ n and rank ( e i ) = s 1 ( d i ) \operatorname{rank}(e_i)=s_1(d_i) rank ( e i ) = s 1 ( d i ) for i ≤ m i\leq m i ≤ m such that
φ ( e ˉ , a ˉ ) ∧ ⋀ Ψ ( a ˉ ) \varphi(\bar{e},\bar{a})\land\bigwedge\Psi(\bar{a}) φ ( e ˉ , a ˉ ) ∧ ⋀ Ψ ( a ˉ )
is true. Proposition 36 ensures that the minor sentences on b b b are also satisfied by this assignment, so it should be clear that b ∪ { φ ( d ˉ , c ˉ ) } b\cup\{\varphi(\bar{d},\bar{c})\} b ∪ { φ ( d ˉ , c ˉ )} is rank-satisfiable with s ∪ s 1 s\cup s_1 s ∪ s 1 . Finally, it is clear from the induction hypothesis and the way we selected e ˉ , a ˉ \bar{e},\bar{a} e ˉ , a ˉ and s 1 s_1 s 1 that the minor sentence is also satisfied by a ˉ \bar{a} a ˉ and e ˉ \bar{e} e ˉ and thus, b ∗ b^* b ∗ is rank-satisfiable.
We may then repeatedly use this lemma to define an open branch.
Lemma 39. There is a Δ k + 1 \Delta_{k+1} Δ k + 1 definable open branch b 0 b_0 b 0 through T T T .
Proof. Define b 0 b_0 b 0 inductively using Lemma 38. At each stage use the next rule prescribed by Section 4.2.3 and the preferred extension supplied by Lemma 38. Every finite initial segment is rank-satisfiable, so the resulting branch is not closed; fairness of the schedule makes it complete, and hence open. This gives a Σ k + 1 \Sigma_{k+1} Σ k + 1 definition and since it is unique, it can also be given a Π k + 1 \Pi_{k+1} Π k + 1 definition. Note that b 0 b_0 b 0 is defined as a class, not a set. □
Let us call b 0 b_0 b 0 the canonical branch of T T T .
Completeness
We now describe how to use the canonical branch b 0 b_0 b 0 through T T T to define a model satisfying all the true Σ k \Sigma_k Σ k sentences of our background universe. The definition is essentially the same as that used to build models from tableaux for first order logic. However, we need to take a little more care since, in general, we are merely defining the model as a class (or interpretation) rather than a set. In particular, we shall work with pre-structures rather than genuine structures. Thus, we shall work with a defined congruence relation ≈ \approx ≈ rather than genuine identity.29
Lemma 40. If b 0 b_0 b 0 is the canonical branch through T T T , then we may define a well-founded L ∈ ( C ) \mathcal{L}_{\in}(C) L ∈ ( C ) -model M \mathcal{M} M from b 0 b_0 b 0 . Moreover, we see that for all sentences φ \varphi φ of L ∈ ( C ) \mathcal{L}_{\in}(C) L ∈ ( C )
φ occurs on b 0 ⇒ M ⊨ φ . \varphi\text{ occurs on }b_0 \Rightarrow\mathcal{M}\models\varphi. φ occurs on b 0 ⇒ M ⊨ φ .
Proof. We let M = ⟨ C , ≈ M , ∈ M , c i M ⟩ i ∈ ω \mathcal{M}=\langle C,\approx^\mathcal{M},\in^\mathcal{M},c_i^\mathcal{M}\rangle_{i\in\omega} M = ⟨ C , ≈ M , ∈ M , c i M ⟩ i ∈ ω so that:
≈ M = { ⟨ c i , c j ⟩ ∈ C × C ∣ ‘ ‘ c i = c j " occurs on b 0 } \approx^\mathcal{M}=\{\langle c_i,c_j\rangle\in C\times C\mid``c_i=c_j"\text{ occurs on }b_0\} ≈ M = {⟨ c i , c j ⟩ ∈ C × C ∣ ‘‘ c i = c j " occurs on b 0 } ;
∈ M = { ⟨ c i , c j ⟩ ∈ C × C ∣ ‘ ‘ c i ∈ c j " occurs on b 0 } \in^\mathcal{M}=\{\langle c_i,c_j\rangle\in C\times C\mid``c_i\in c_j"\text{ occurs on }b_0\} ∈ M = {⟨ c i , c j ⟩ ∈ C × C ∣ ‘‘ c i ∈ c j " occurs on b 0 } .
Observe that since there will be infinitely many true Σ k \Sigma_k Σ k -sentences: the process we described in Section 4.2.3 and Lemma 39, for building our canonical tableau, ensures that every constant symbol occurs on b 0 b_0 b 0 . Also note that M \mathcal{M} M is defined as a proper class and, as such, we cannot in general define the associated quotient.30 We leave it to the reader to show that the identity rules ensure that ≈ M \approx^\mathcal{M} ≈ M is a congruence relation with respect to ∈ M \in^\mathcal{M} ∈ M and c i M c_i^\mathcal{M} c i M for all $i\in\omega.31 $
We then proceed by induction on tableau complexity. This is a standard proof that can be found in many places, so we just highlight some representative cases.
(Base) Suppose c i = c j c_i=c_j c i = c j occurs on b 0 b_0 b 0 . Then ⟨ c i , c j ⟩ ∈ ≈ M \langle c_i,c_j\rangle\in\approx^\mathcal{M} ⟨ c i , c j ⟩ ∈ ≈ M and so M ⊨ c i = c j \mathcal{M}\models c_i=c_j M ⊨ c i = c j . The other cases are similar.
(Step) Suppose ∃ x ˉ φ ( x ˉ , c ˉ ) \exists\bar{x}\varphi(\bar{x},\bar{c}) ∃ x ˉ φ ( x ˉ , c ˉ ) occurs on b 0 b_0 b 0 . Then since b 0 b_0 b 0 is complete, the Special ∃ \exists ∃ rule guarantees that there is some d ˉ \bar{d} d ˉ from C C C such that φ ( d ˉ , c ˉ ) \varphi(\bar{d},\bar{c}) φ ( d ˉ , c ˉ ) occurs on b 0 b_0 b 0 . By the induction hypothesis, we see that M ⊨ φ ( d ˉ , c ˉ ) \mathcal{M}\models\varphi(\bar{d},\bar{c}) M ⊨ φ ( d ˉ , c ˉ ) and so M ⊨ ∃ x ˉ φ ( x ˉ , c ˉ ) \mathcal{M}\models\exists\bar{x}\varphi(\bar{x},\bar{c}) M ⊨ ∃ x ˉ φ ( x ˉ , c ˉ ) . We leave the other cases to the reader.
Finally, the well-foundedness of the model can be seen since the accumulation of the ordinal assignments gives an order preserving map from the interpreted model into the ordinals of our background universe.
In particular, observe that if s s s is the accumulated ordinal assignment determined by b 0 b_0 b 0 , then rank-satisfiability ensures that: c i ≈ M c j c_i \approx_M c_j c i ≈ M c j implies s ( c i ) = s ( c j ) s(c_i) = s(c_j) s ( c i ) = s ( c j ) ; and c i ∈ M c j c_i \in^M c_j c i ∈ M c j implies s ( c i ) < s ( c j ) s(c_i) < s(c_j) s ( c i ) < s ( c j ) for any c i , c j ∈ C c_i,c_j \in C c i , c j ∈ C . □
Let M 0 \mathcal{M}_0 M 0 be the model defined using the canonical branch b 0 b_0 b 0 through T T T . It is not then difficult to see that:
Corollary 41. M 0 ≡ Σ k V \mathcal{M}_0 \equiv_{\Sigma_k} V M 0 ≡ Σ k V ; i.e., M 0 \mathcal{M}_0 M 0 and V V V satisfy the same Σ k \Sigma_k Σ k sentences of L ∈ \mathcal{L}_{\in} L ∈ .
Proof. For any Σ k \Sigma_k Σ k sentence ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) of L ∈ \mathcal{L}_{\in} L ∈ , we see that:
if ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) is true then we take the left move on that cut and add φ ( d ˉ ) \varphi(\bar{d}) φ ( d ˉ ) ; and
if ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) is false, then we take the right move and add ∀ x ˉ ¬ φ ( x ˉ ) \forall\bar{x}\neg\varphi(\bar{x}) ∀ x ˉ ¬ φ ( x ˉ ) .
Then Lemma 40 tells us that
M 0 ⊨ ∃ x ˉ φ ( x ˉ ) ⇔ ∃ x ˉ φ ( x ˉ ) is true . \mathcal{M}_0 \models\exists\bar{x}\varphi(\bar{x}) \ \Leftrightarrow\ \exists\bar{x}\varphi(\bar{x})\text{ is true}. M 0 ⊨ ∃ x ˉ φ ( x ˉ ) ⇔ ∃ x ˉ φ ( x ˉ ) is true .
Thus, whenever k > 3 k > 3 k > 3 , we see that:
Proposition 42. M 0 ⊨ K P C \mathcal{M}_0 \models KPC M 0 ⊨ K P C .
Proof. By Corollary 41, we see that M 0 \mathcal{M}_0 M 0 satisfies every axiom of K P C KPC K P C with the possible exception of Full Set Induction, since they can all be articulated as Π 3 \Pi_3 Π 3 sentences. To see that Full Set Induction holds, we suppose toward a contradiction that ψ ( x , a ) \psi(x,a) ψ ( x , a ) with a ∈ M 0 a \in\mathcal{M}_0 a ∈ M 0 defines a nonempty subclass of M 0 \mathcal{M}_0 M 0 that has no ∈ M 0 \in^{\mathcal{M}_0} ∈ M 0 -minimal element. We shall use this to define an infinite decreasing chain of ordinals in the background universe.
First we define a ∈ M 0 \in^{\mathcal{M}_0} ∈ M 0 -descending (class) sequence ⟨ d n ⟩ n ∈ ω \langle d_n\rangle_{n\in\omega} ⟨ d n ⟩ n ∈ ω of elements of M 0 \mathcal{M}_0 M 0 . First, we let d 0 d_0 d 0 be c i c_i c i for the least i ∈ ω i \in\omega i ∈ ω such that ψ ( c i , a ) \psi(c_i,a) ψ ( c i , a ) is true. Then for each n ∈ ω n \in\omega n ∈ ω , let d n + 1 d_{n+1} d n + 1 be c i c_i c i for the least i ∈ ω i \in\omega i ∈ ω such that ψ ( c i , a ) \psi(c_i,a) ψ ( c i , a ) is true and c i ∈ M 0 d n c_i \in^{\mathcal{M}_0} d_n c i ∈ M 0 d n . Note that this is clearly definable as a class function. Now from Lemma 40, we see that there is a definable order preserving map π \pi π from M 0 \mathcal{M}_0 M 0 into the ordinals. So let ⟨ r n ⟩ n ∈ ω \langle r_n\rangle_{n\in\omega} ⟨ r n ⟩ n ∈ ω be such that for all n ∈ ω n \in\omega n ∈ ω , r n = π ( d n ) r_n = \pi(d_n) r n = π ( d n ) . Then we see that for all n ∈ ω n \in\omega n ∈ ω
r n + 1 ∈ r n r_{n+1} \in r_n r n + 1 ∈ r n which is impossible since we have Full Set Induction in the background universe. □
We have now constructed M 0 ⊨ K P C \mathcal{M}_0 \models KPC M 0 ⊨ K P C , with the same Σ k \Sigma_k Σ k theory as the background universe. We next repeat the construction inside M 0 \mathcal{M}_0 M 0 ; the goal of this repetition is to obtain an enumeration definable in M 0 \mathcal{M}_0 M 0 itself.
Idempotence
The following lemma establishes that if we take the canonical branch through M 0 \mathcal{M}_0 M 0 's version of T T T , we essentially get b 0 b_0 b 0 again. This gives us the idempotence property.
Lemma 43. Let T M 0 T^{\mathcal{M}_0} T M 0 be the Σ k \Sigma_k Σ k -tableau as we defined it above but now in M 0 \mathcal{M}_0 M 0 .
Then b 1 b_1 b 1 is the canonical branch through T M 0 \mathcal{T}^{\mathcal{M}_0} T M 0 .
Remark. Note that this proof is done from the perspective of our background universe, V V V .
Proof. We proceed by induction on the length of b 1 b_1 b 1 . First we avoid some notational clutter. Since M 0 \mathcal{M}_0 M 0 is well-founded from the perspective of the background universe, we can identify M 0 \mathcal{M}_0 M 0 ’s natural numbers with those of the background via their unique isomorphism. Analogously, we identify M 0 \mathcal{M}_0 M 0 and V V V ’s rendering of constant symbols and sentence codes. The syntactic process described in Section 4.2.3 is primitive recursive and thus, also behaves identically in M 0 \mathcal{M}_0 M 0 and V V V via this isomorphism.
Now suppose that we have verified that the canonical branch b ∗ b^* b ∗ through T M 0 \mathcal{T}^{\mathcal{M}_0} T M 0 is such that up to length n n n , b ∗ b^* b ∗ uses the same sentences as b 0 b_0 b 0 and the ordinal assignments sending c i c_i c i to rank ( c i ) M 0 \operatorname{rank}(c_i)^{\mathcal{M}_0} rank ( c i ) M 0 for all c i c_i c i occurring in sentences so far. We wish to show that this also holds at length n + 1 n+1 n + 1 .
If the rule used to extend b 1 ↾ n b_1\mathbin{\upharpoonright}n b 1 ↾ n to b 1 ↾ ( n + 1 ) b_1\mathbin{\upharpoonright}(n+1) b 1 ↾ ( n + 1 ) is ¬ ∃ \neg\exists ¬∃ , ¬ ∨ \neg\vee ¬ ∨ , ¬ ¬ \neg\neg ¬¬ or an identity rule there is nothing to do: the next sentence is predetermined by those rules and there is no ordinal assignment move. So we focus on three cases: Special Σ k \Sigma_k Σ k -cut; Special ∃ \exists ∃ and Special ∨ \vee ∨ .
Suppose that Special Σ k \Sigma_k Σ k -cut is used on the Σ k \Sigma_k Σ k sentence ∃ x ˉ φ ( x ˉ ) \exists\bar{x}\varphi(\bar{x}) ∃ x ˉ φ ( x ˉ ) .
φ ( d ˉ ) , s \varphi(\bar{d}),\ s φ ( d ˉ ) , s
∀ y ˉ < rank-lex d ˉ ¬ φ ( y ˉ ) . \forall\bar{y}<_{\operatorname{rank-lex}}\bar{d}\ \neg\varphi(\bar{y}). ∀ y ˉ < rank-lex d ˉ ¬ φ ( y ˉ ) .
Then we see that M 0 ⊨ φ ( d ˉ ) ∧ ∀ y ˉ < rank-lex d ˉ ¬ φ ( y ˉ ) \mathcal{M}_0\models\varphi(\bar{d})\land\forall\bar{y}<_{\operatorname{rank-lex}}\bar{d}\ \neg\varphi(\bar{y}) M 0 ⊨ φ ( d ˉ ) ∧ ∀ y ˉ < rank-lex d ˉ ¬ φ ( y ˉ ) . Thus, M 0 ⊨ ∃ x ˉ φ ( x ˉ ) \mathcal{M}_0\models\exists\bar{x}\varphi(\bar{x}) M 0 ⊨ ∃ x ˉ φ ( x ˉ ) and so b ∗ b^* b ∗ must also turn left, meaning that b 1 b_1 b 1 and b ∗ b^* b ∗ agree on their ( n + 1 ) (n+1) ( n + 1 ) th sentences as required. Moreover, since M 0 ⊨ ∀ y ˉ < rank-lex d ˉ ¬ φ ( y ˉ ) \mathcal{M}_0\models\forall\bar{y}<_{\operatorname{rank-lex}}\bar{d}\ \neg\varphi(\bar{y}) M 0 ⊨ ∀ y ˉ < rank-lex d ˉ ¬ φ ( y ˉ ) , we see that φ ( y ˉ ) \varphi(\bar{y}) φ ( y ˉ ) cannot be satisfied in M 0 \mathcal{M}_0 M 0 with any ordinal assignment lexicographically preceding the ranks of d 0 M 0 , … , d m M 0 d_0^{\mathcal{M}_0},\ldots,d_m^{\mathcal{M}_0} d 0 M 0 , … , d m M 0 . Thus, we preserve minimal-rank-satisfaction and so if we use the ordinal assignment corresponding to the ranks of d 0 M 0 , … , d m M 0 d_0^{\mathcal{M}_0},\ldots,d_m^{\mathcal{M}_0} d 0 M 0 , … , d m M 0 , b 1 b_1 b 1 will agree with b ∗ b^* b ∗ as required.
Suppose that in b 0 b_0 b 0 , we take the right move and add ∀ x ˉ ¬ φ ( x ˉ ) \forall\bar{x}\neg\varphi(\bar{x}) ∀ x ˉ ¬ φ ( x ˉ ) . Then we see that M 0 ⊨ ∀ x ˉ ¬ φ ( x ˉ ) \mathcal{M}_0\models\forall\bar{x}\neg\varphi(\bar{x}) M 0 ⊨ ∀ x ˉ ¬ φ ( x ˉ ) . But this means that b ∗ b^* b ∗ cannot take the left turn and thus, must also add ∀ x ˉ ¬ φ ( x ˉ ) \forall\bar{x}\neg\varphi(\bar{x}) ∀ x ˉ ¬ φ ( x ˉ ) as required.
Suppose that Special ∨ \vee ∨ was used on the sentence φ ( c ˉ ) ∨ ψ ( c ˉ ) \varphi(\bar{c})\vee\psi(\bar{c}) φ ( c ˉ ) ∨ ψ ( c ˉ ) .
M 0 ⊨ φ ( c ˉ ) ∧ ∀ y ˉ ≤ rank-lex d ˉ ¬ ( ψ ( y ˉ ) ∧ Ψ ( y ˉ ) ) \mathcal{M}_0\models\varphi(\bar{c})\land\forall\bar{y}\leq_{\operatorname{rank-lex}}\bar{d}\neg(\psi(\bar{y})\land\Psi(\bar{y})) M 0 ⊨ φ ( c ˉ ) ∧ ∀ y ˉ ≤ rank-lex d ˉ ¬ ( ψ ( y ˉ ) ∧ Ψ ( y ˉ ))
where d ˉ \bar{d} d ˉ are the constant symbols already occurring on b 0 b_0 b 0 and Ψ ( d ˉ ) \Psi(\bar{d}) Ψ ( d ˉ ) is the set of major sentences occurring so far. This means that b ∗ b^* b ∗ will also turn left at this point. Thus, b ∗ b^* b ∗ and b 1 b_1 b 1 both add φ ( c ˉ ) \varphi(\bar{c}) φ ( c ˉ ) . No ordinal assignment occurs in the application of the Special ∨ \vee ∨ rules, so this suffices.
M 0 ⊨ ψ ( c ˉ ) ∧ ∀ y ˉ ≤ rank-lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ ) ) \mathcal{M}_0\models\psi(\bar{c})\land\forall\bar{y}\leq_{\operatorname{rank-lex}}\bar{d}\neg(\varphi(\bar{y})\land\Psi(\bar{y})) M 0 ⊨ ψ ( c ˉ ) ∧ ∀ y ˉ ≤ rank-lex d ˉ ¬ ( φ ( y ˉ ) ∧ Ψ ( y ˉ ))
where Ψ ( d ˉ ) \Psi(\bar{d}) Ψ ( d ˉ ) is the set of major sentences occurring on the branch so far and d ˉ \bar{d} d ˉ are the constant symbols occurring in those sentences. Similarly, this means that b ∗ b^* b ∗ must turn right at this point, so b ∗ b^* b ∗ and b 1 b_1 b 1 continue to agree.
Suppose that Special ∃ \exists ∃ was used on ∃ x ˉ φ ( x ˉ , c ˉ ) \exists\bar{x}\,\varphi(\bar{x},\bar{c}) ∃ x ˉ φ ( x ˉ , c ˉ ) . Then b ∗ b^* b ∗ must also extend with:
φ ( d ˉ , c ˉ ) , s \varphi(\bar{d},\bar{c}),s φ ( d ˉ , c ˉ ) , s
∀ y ˉ , z ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) \forall\bar{y},\bar{z}<_{\mathrm{rank\text{-}lex}}\bar{c},\bar{d}\ \neg\bigl(\varphi(\bar{z},\bar{y})\land\bigwedge\Psi(\bar{y})\bigr) ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) )
where Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) is the set of major sentences already occurring and c ˉ \bar{c} c ˉ are the constant symbols occurring in them. Clearly, b ∗ b^* b ∗ and b 1 b_1 b 1 agree on the sentence added next. Moreover, we see that
M 0 ⊨ φ ( d ˉ , c ˉ ) ∧ ∀ y ˉ , z ˉ < r a n k - l e x c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) ) M_0\models\varphi(\bar{d},\bar{c})\land\forall\bar{y},\bar{z}<_{\mathrm{rank\text{-}lex}}\bar{c},\bar{d}\ \neg\bigl(\varphi(\bar{z},\bar{y})\land\bigwedge\Psi(\bar{y})\bigr) M 0 ⊨ φ ( d ˉ , c ˉ ) ∧ ∀ y ˉ , z ˉ < rank - lex c ˉ , d ˉ ¬ ( φ ( z ˉ , y ˉ ) ∧ ⋀ Ψ ( y ˉ ) )
where Ψ ( c ˉ ) \Psi(\bar{c}) Ψ ( c ˉ ) is the set of sentences occurring so far. Now let e ˉ = c ˉ , d ˉ \bar{e}=\bar{c},\bar{d} e ˉ = c ˉ , d ˉ and s : { e ˉ } → O r d M 0 s:\{\bar{e}\}\to Ord^{M_0} s : { e ˉ } → O r d M 0 be such that s ( e i ) = r a n k ( e i ) M 0 s(e_i)=rank(e_i)^{M_0} s ( e i ) = r ank ( e i ) M 0 for all e i e_i e i occurring in e ˉ \bar{e} e ˉ . We then see that this assignment agrees with the canonical branch b ∗ b^* b ∗ since the second clause of the conjunction above ensures that there is no way to find an ordinal assignment preceding ⟨ r a n k ( e 0 ) M 0 , … , r a n k ( e m ) M 0 ⟩ \langle rank(e_0)^{M_0},\ldots,rank(e_m)^{M_0}\rangle ⟨ r ank ( e 0 ) M 0 , … , r ank ( e m ) M 0 ⟩ .
Let M 1 M_1 M 1 be the model interpreted in M 0 M_0 M 0 using b 1 b_1 b 1 . We then observe that from the perspective of our background universe, these models are isomorphic.
Lemma 44. There is an isomorphism j : M 0 ≅ M 1 j:M_0\cong M_1 j : M 0 ≅ M 1 , where j j j is definable in the background universe, V \mathsf{V} V .
Proof. The sentences occurring on an open branch of any tableau determine the isomorphism type of the model it defines. Lemma 43 establishes that M 0 M_0 M 0 and M 1 M_1 M 1 are determined by branches with the same sentences. We then define the isomorphism by letting j ( c n M 0 ) = c n M 1 j(c_n^{M_0})=c_n^{M_1} j ( c n M 0 ) = c n M 1 , or equivalently, we send the ≈ M 0 \approx^{M_0} ≈ M 0 -class of c n c_n c n to the corresponding ≈ M 1 \approx^{M_1} ≈ M 1 -class.
The task is now to recover j − 1 ( c n M 1 ) j^{-1}(c_n^{M_1}) j − 1 ( c n M 1 ) by a definition inside M 0 M_0 M 0 without parameters. The ordinal assignment first recovers ordinals; membership then recovers sets of ordinals; and rooted codes together with Mostowski collapse recover arbitrary sets. For a little technical notation, we let t r c l trcl t r c l be the transitive closure operator and t r c o l l trcoll t r co l l be the transitive collapse function.
Lemma 45. There is a function f f f that is definable over M 0 M_0 M 0 without parameters such that
f : ω ↠ M 0 . f:\omega\twoheadrightarrow M_0. f : ω ↠ M 0 .
Proof. Working in M 0 M_0 M 0 , let b 1 b_1 b 1 be the canonical branch and let s : C → O r d s:C\to Ord s : C → O r d be its accumulated ordinal assignment. We proceed in four stages.
First, we define a partial surjection f 0 : C ⇀ O r d M 0 f_0:C\rightharpoonup Ord^{M_0} f 0 : C ⇀ O r d M 0 such that ⟨ c n , α ⟩ ∈ f 0 \langle c_n,\alpha\rangle\in f_0 ⟨ c n , α ⟩ ∈ f 0 iff M 1 ⊨ c n ∈ O r d M_1\models c_n\in Ord M 1 ⊨ c n ∈ O r d and s ( c n ) = α s(c_n)=\alpha s ( c n ) = α . The key points then are that:
f 0 ( c n ) = c n M 0 = j − 1 ( c n M 1 ) f_0(c_n)=c_n^{M_0}=j^{-1}(c_n^{M_1}) f 0 ( c n ) = c n M 0 = j − 1 ( c n M 1 )
whenever M 1 ⊨ c n ∈ O r d M_1\models c_n\in Ord M 1 ⊨ c n ∈ O r d ; and that since c n M 0 c_n^{M_0} c n M 0 is itself an ordinal,
α = s ( c n ) = r a n k M 0 ( c n M 0 ) = c n M 0 . \alpha=s(c_n)=rank^{M_0}(c_n^{M_0})=c_n^{M_0}. α = s ( c n ) = r an k M 0 ( c n M 0 ) = c n M 0 .
For β ∈ O r d M 0 \beta\in Ord^{M_0} β ∈ O r d M 0 , we choose c i c_i c i with c i M 0 = β c_i^{M_0}=\beta c i M 0 = β . Then c i M 1 = j ( β ) c_i^{M_1}=j(\beta) c i M 1 = j ( β ) is an ordinal and the definition gives f 0 ( c i ) = β f_0(c_i)=\beta f 0 ( c i ) = β .
Second, we define a partial surjection f 1 : C ↠ [ O r d ] < O r d f_1:C\twoheadrightarrow[Ord]^{<Ord} f 1 : C ↠ [ O r d ] < O r d such that f 1 ( c n ) = X f_1(c_n)=X f 1 ( c n ) = X iff M 1 ⊨ c n ⊆ O r d M_1\models c_n\subseteq Ord M 1 ⊨ c n ⊆ O r d and for all α \alpha α
α ∈ X ⟺ ∃ m ∈ ω ( f 0 ( c m ) = α ∧ M 1 ⊨ c m ∈ c n ) . \alpha\in X\Longleftrightarrow\exists m\in\omega\ (f_0(c_m)=\alpha\land M_1\models c_m\in c_n). α ∈ X ⟺ ∃ m ∈ ω ( f 0 ( c m ) = α ∧ M 1 ⊨ c m ∈ c n ) .
Similarly to the previous case, we then observe that
f 1 ( c n ) = c n M 0 = j − 1 ( c n M 1 ) . f_1(c_n)=c_n^{M_0}=j^{-1}(c_n^{M_1}). f 1 ( c n ) = c n M 0 = j − 1 ( c n M 1 ) .
From here it can be seen that:
α ∈ f 1 ( c n ) ⟺ ∃ m ( f 0 ( c m ) = α ∧ M 1 ⊨ c m ∈ c n ) ; (1) \alpha\in f_1(c_n)\Longleftrightarrow\exists m\ (f_0(c_m)=\alpha\land M_1\models c_m\in c_n); \tag*{(1)} α ∈ f 1 ( c n ) ⟺ ∃ m ( f 0 ( c m ) = α ∧ M 1 ⊨ c m ∈ c n ) ; (1)
∃ m ( f 0 ( c m ) = α ∧ M 1 ⊨ c m ∈ c n ) ⟺ j ( α ) ∈ c n M 1 ; (2) \exists m\ (f_0(c_m)=\alpha\land M_1\models c_m\in c_n)\Longleftrightarrow j(\alpha)\in c_n^{M_1}; \tag*{(2)} ∃ m ( f 0 ( c m ) = α ∧ M 1 ⊨ c m ∈ c n ) ⟺ j ( α ) ∈ c n M 1 ; (2)
j ( α ) ∈ c n M 1 ⟺ α ∈ c n M 0 . (3) j(\alpha)\in c_n^{M_1}\Longleftrightarrow\alpha\in c_n^{M_0}. \tag*{(3)} j ( α ) ∈ c n M 1 ⟺ α ∈ c n M 0 . (3)
If Y ⊆ O r d M 0 Y\subseteq Ord^{M_0} Y ⊆ O r d M 0 is a set, we choose c i c_i c i with c i M 0 = Y c_i^{M_0}=Y c i M 0 = Y . The displayed equivalences then establish that f 1 ( c i ) = Y f_1(c_i)=Y f 1 ( c i ) = Y .
Third, we define a relation F 2 F_2 F 2 on C × M 0 C\times M_0 C × M 0 . Given c n ∈ C c_n\in C c n ∈ C and x ∈ M 0 x\in M_0 x ∈ M 0 , let F 2 ( c n , x ) F_2(c_n,x) F 2 ( c n , x ) hold iff there are an ordinal κ \kappa κ , a bijection g : κ → trcl ( { x } ) g:\kappa\to\operatorname{trcl}(\{x\}) g : κ → trcl ({ x }) , a distinguished point r = g − 1 ( x ) r=g^{-1}(x) r = g − 1 ( x ) , a relation R ⊆ κ 2 R\subseteq\kappa^2 R ⊆ κ 2 obtained by pulling membership back along g g g , a set of ordinals Y Y Y coding the rooted structure ⟨ κ , R , r ⟩ \langle\kappa,R,r\rangle ⟨ κ , R , r ⟩ , and k ∈ ω k\in\omega k ∈ ω such that f 1 ( c k ) = Y f_1(c_k)=Y f 1 ( c k ) = Y and, in M 1 M_1 M 1 , the rooted relation decoded from c k c_k c k has a Mostowski collapse whose distinguished root is c n M 1 c_n^{M_1} c n M 1 . All of this is definable over M 0 M_0 M 0 without parameters.
To see what this relation does, temporarily reason in the background universe. If f 1 ( c k ) = Y f_1(c_k)=Y f 1 ( c k ) = Y , then c k M 1 = j ( Y ) c_k^{M_1}=j(Y) c k M 1 = j ( Y ) . Hence the rooted relation decoded from c k c_k c k is isomorphic to the j j j -image of ⟨ κ , R , r ⟩ \langle\kappa,R,r\rangle ⟨ κ , R , r ⟩ , whose rooted collapse has distinguished root j ( x ) j(x) j ( x ) . By uniqueness of the Mostowski collapse,
F 2 ( c n , x ) ⟺ c n M 1 = j ( x ) . F_2(c_n,x)\Longleftrightarrow c_n^{M_1}=j(x). F 2 ( c n , x ) ⟺ c n M 1 = j ( x ) .
Since j : M 0 ≅ M 1 j:M_0\cong M_1 j : M 0 ≅ M 1 is a bijection and the constants in C C C exhaust M 1 M_1 M 1 , F 2 F_2 F 2 is the graph of a total surjection f 2 : C ⟶ M 0 f_2:C\longrightarrow M_0 f 2 : C ⟶ M 0 . The same calculation also shows that the definition is independent of the choices of g g g and of the particular rooted code.
Fourth and finally, we let f : ω ⟶ M 0 f:\omega\longrightarrow M_0 f : ω ⟶ M 0 be such that f ( n ) = y f(n)=y f ( n ) = y iff f 2 ( c n ) = y f_2(c_n)=y f 2 ( c n ) = y .
Main proof
Finally, we can complete the proof of Lemma 30 .
Proof. (of Lemma 30 ) Let N \mathcal{N} N be a model of T = K P C + S T=KPC+S T = K P C + S and then work within N \mathcal{N} N . Let k > 3 k>3 k > 3 be such that every sentence in S S S has complexity Σ k \Sigma_k Σ k . Then let b 0 b_0 b 0 be the canonical branch through the tableau T \mathcal{T} T built using Special Σ k \Sigma_k Σ k -cut. Let M 0 \mathcal{M}_0 M 0 be the model interpreted using b 0 b_0 b 0 . Then we see that M 0 \mathcal{M}_0 M 0 satisfies T T T . Next we consider the tableau T M 0 \mathcal{T}^{\mathcal{M}_0} T M 0 built inside M 0 \mathcal{M}_0 M 0 and its canonical branch b 1 b_1 b 1 . We let M 1 \mathcal{M}_1 M 1 be the model interpreted from b 1 b_1 b 1 . Then using Lemma 45 , we see that there is a function f : ω M 0 ⟶ M 0 f:\omega^{\mathcal{M}_0}\longrightarrow\mathcal{M}_0 f : ω M 0 ⟶ M 0 definable without parameters over M 0 \mathcal{M}_0 M 0 , which is what we require.
Geology with little hammers
With the definable countable enumeration lemma in hand, we have addressed problem (1) from the sketch given at the beginning of § 3 . However, before we give any examples, we need to address problem (2). In particular, we need to obtain theories that have the stable definable ground property. For this purpose, we make use of some set theoretic geology. The idea is to make a small piece of the ground recognizable in its generic extension, and then use that piece to recover the whole ground.
There are two tasks here. First, we need a ground-model definition that works over a weak set theory. Schlutzenberg has already provided such a definition; we shall adapt it to use a smaller parameter. Second, we need to arrange that a suitable parameter is itself definable without parameters. We do this by coding it into the continuum function. The first task can be carried out over a weaker theory than the second, and we keep that distinction explicit.
As before, K P KP K P includes Full Set Induction and K P C KPC K P C adds Choice in the form that every set injects into an ordinal. We use the following axiomatization of M O S T MOST M O S T : Extensionality, set Foundation, Pairing, Union, Infinity, Powerset, Σ 1 \Sigma_1 Σ 1 -Separation, Σ 1 \Sigma_1 Σ 1 -Collection, and the assertion that every set is bijectable with an ordinal. Schlutzenberg denotes this theory by T 1 T_1 T 1 [Schlutzenberg, 2022, Definition 2.2]. Set Foundation says that every nonempty set has an ∈ \in ∈ -minimal member. We write
M O S T I n d = M O S T + Full Set Induction = K P C + Powerset + Σ 1 -Separation . MOST_{\mathrm{Ind}} = MOST + \text{Full Set Induction} = KPC + \text{Powerset} + \Sigma_1\text{-Separation}. M O S T Ind = M O S T + Full Set Induction = K P C + Powerset + Σ 1 -Separation .
We write Z F C Π n ZFC^{\Pi_n} Z F C Π n for K P C KPC K P C extended by Powerset, Π n \Pi_n Π n -Separation and Π n \Pi_n Π n -Collection. Thus Z F C Π 0 ZFC^{\Pi_0} Z F C Π 0 is K P C KPC K P C with Powerset. The coding construction in § 5.2 is carried out over Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 . We give the preservation argument for every n ≥ 3 n \ge3 n ≥ 3 , since the later applications also use stronger fragments.
Our forcing constructions must produce extensions satisfying the theory with which we began. Schlutzenberg proves internally that set forcing forces every axiom of M O S T MOST M O S T [Schlutzenberg, 2022, Lemma 2.5]. Over Z F C Π n ZFC^{\Pi_n} Z F C Π n , we must also verify the stronger Separation and Collection schemes. We first check these forcing assertions inside the ground theory, and then use the truth lemma to transfer them to a generic extension.
The usual name constructions give the required sets once the forcing predicates have the right complexity. The main point is existential forcing: local witness names can be collected and mixed into one name. This is where Collection and Choice enter.
Lemma 46. Let n ≥ 3 n \ge3 n ≥ 3 and work in Z F C Π n ZFC^{\Pi_n} Z F C Π n . Fix a set forcing P \mathbb{P} P . For every fixed Σ i \Sigma_i Σ i formula, where 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n , its forcing relation has a Σ i \Sigma_i Σ i definition. The corresponding assertion holds for Π i \Pi_i Π i formulas. Bounded forcing has a Δ 1 \Delta_1 Δ 1 definition.
Proof. Begin with the Δ 1 \Delta_1 Δ 1 definition of bounded forcing and proceed through the prenex quantifier blocks. Suppose the matrix ψ \psi ψ is Π i − 1 \Pi_{i-1} Π i − 1 and its forcing relation already has the required definition. If p ⊩ ∃ x ψ ( x , τ ⃗ ) p \Vdash\exists x\,\psi(x,\vec{\tau}) p ⊩ ∃ x ψ ( x , τ ) , then for every q ≤ p q \le p q ≤ p there are s ≤ q s \le q s ≤ q and a name x ˙ \dot{x} x ˙ such that s ⊩ ψ ( x ˙ , τ ⃗ ) s \Vdash\psi(\dot{x},\vec{\tau}) s ⊩ ψ ( x ˙ , τ ) . Collection gathers a set of such witness pairs, one available below each q ≤ p q \le p q ≤ p . At the first level Σ 1 \Sigma_1 Σ 1 -Collection suffices, since bounded forcing is Δ 1 \Delta_1 Δ 1 ; at later levels Π i − 1 \Pi_{i-1} Π i − 1 -Collection suffices.
Using Separation, retain from the collected set precisely those pairs ⟨ s , x ˙ ⟩ \langle s,\dot{x}\rangle ⟨ s , x ˙ ⟩ with s ≤ p s \le p s ≤ p , x ˙ \dot{x} x ˙ a P \mathbb{P} P -name, and s ⊩ ψ ( x ˙ , τ ⃗ ) s \Vdash\psi(\dot{x},\vec{\tau}) s ⊩ ψ ( x ˙ , τ ) . Using Choice, take a maximal antichain from their witnessing conditions and select one witness name for each antichain condition. The antichain is predense below p p p . Mix its selected names into a single name u ˙ \dot{u} u ˙ agreeing with each selected witness below its corresponding condition. This construction uses unions and bounded Separation on sets of names and conditions. Substitution and the density lemma give p ⊩ ψ ( u ˙ , τ ⃗ ) p \Vdash\psi(\dot{u},\vec{\tau}) p ⊩ ψ ( u ˙ , τ ) . Consequently
p ⊩ ∃ x ψ ( x , τ ⃗ ) ⟷ ∃ u ˙ p ⊩ ψ ( u ˙ , τ ⃗ ) . p \Vdash\exists x\,\psi(x,\vec{\tau}) \quad\longleftrightarrow\quad\exists\dot{u}\,p \Vdash\psi(\dot{u},\vec{\tau}). p ⊩ ∃ x ψ ( x , τ ) ⟷ ∃ u ˙ p ⊩ ψ ( u ˙ , τ ) .
The right side has a Σ i \Sigma_i Σ i definition. Quantification over dotted variables is over names; the Δ 1 \Delta_1 Δ 1 name predicate is absorbed into this bound. Negation gives the dual Π i \Pi_i Π i definition, since a condition forces a negation exactly when no stronger condition forces the negated formula. Repeated quantifiers of the same kind are handled in the same block. This proves the induction for each fixed formula. □
Working in Z F C Π n ZFC^{\Pi_n} Z F C Π n , we now verify that every instance of Π n \Pi_n Π n -Separation and Π n \Pi_n Π n -Collection is forced. Fix a Π n \Pi_n Π n formula φ \varphi φ and names a ˙ , τ ⃗ \dot{a},\vec{\tau} a ˙ , τ . For Separation, form
b ˙ = { ⟨ x ˙ , q ⟩ ∈ dom ( a ˙ ) × P : q ⊩ x ˙ ∈ a ˙ ∧ q ⊩ φ ( x ˙ , τ ⃗ ) } . \dot{b}=\{\langle\dot{x},q\rangle\in\operatorname{dom}(\dot{a})\times\mathbb{P}:q\Vdash\dot{x}\in\dot{a}\ \land\ q\Vdash\varphi(\dot{x},\vec{\tau})\}. b ˙ = {⟨ x ˙ , q ⟩ ∈ dom ( a ˙ ) × P : q ⊩ x ˙ ∈ a ˙ ∧ q ⊩ φ ( x ˙ , τ )} .
By Lemma 46, this set exists by Π n \Pi_n Π n -Separation. The forcing clauses give
1 ⊩ ∀ x ( x ∈ b ˙ ↔ ( x ∈ a ˙ ∧ φ ( x , τ ⃗ ) ) ) . 1\Vdash\forall x\,(x\in\dot{b}\leftrightarrow(x\in\dot{a}\land\varphi(x,\vec{\tau}))). 1 ⊩ ∀ x ( x ∈ b ˙ ↔ ( x ∈ a ˙ ∧ φ ( x , τ ))) .
For Collection, suppose p ⊩ ∀ x ∈ a ˙ ∃ y φ ( x , y , τ ⃗ ) p\Vdash\forall x\in\dot{a}\,\exists y\,\varphi(x,y,\vec{\tau}) p ⊩ ∀ x ∈ a ˙ ∃ y φ ( x , y , τ ) . For every ⟨ x ˙ , r ⟩ ∈ a ˙ \langle\dot{x},r\rangle\in\dot{a} ⟨ x ˙ , r ⟩ ∈ a ˙ and q ≤ p , r q\leq p,r q ≤ p , r , there are s ≤ q s\leq q s ≤ q and a name y ˙ \dot{y} y ˙ with s ⊩ φ ( x ˙ , y ˙ , τ ⃗ ) s\Vdash\varphi(\dot{x},\dot{y},\vec{\tau}) s ⊩ φ ( x ˙ , y ˙ , τ ) . The triples ⟨ x ˙ , r , q ⟩ \langle\dot{x},r,q\rangle ⟨ x ˙ , r , q ⟩ form a set, and the relation describing a witness pair ⟨ s , y ˙ ⟩ \langle s,\dot{y}\rangle ⟨ s , y ˙ ⟩ is Π n \Pi_n Π n . Thus Π n \Pi_n Π n -Collection gathers enough witness pairs. Let Y Y Y be the set of their name components, discarding any objects which are not names, and let b ˙ = { ⟨ y ˙ , 1 ⟩ : y ˙ ∈ Y } \dot{b}=\{\langle\dot{y},1\rangle:\dot{y}\in Y\} b ˙ = {⟨ y ˙ , 1 ⟩ : y ˙ ∈ Y } . Below each relevant q q q there is a condition forcing that a suitable witness belongs to b ˙ \dot{b} b ˙ . The density lemma therefore gives
p ⊩ ∀ x ∈ a ˙ ∃ y ∈ b ˙ φ ( x , y , τ ⃗ ) . p\Vdash\forall x\in\dot{a}\,\exists y\in\dot{b}\,\varphi(x,y,\vec{\tau}). p ⊩ ∀ x ∈ a ˙ ∃ y ∈ b ˙ φ ( x , y , τ ) .
The remaining basic axioms use the usual name constructions, as in the MOST argument. In particular, Powerset is obtained from the set of subnames of dom ( a ˙ ) × P \operatorname{dom}(\dot{a})\times\mathbb{P} dom ( a ˙ ) × P . Every non-induction axiom instance of Z F C Π n ZFC^{\Pi_n} Z F C Π n is therefore forced.
To pass to a generic extension we use the truth lemma. A definable dense class need not be a set in a weak ground model, so meeting the ground’s dense sets does not by itself give the truth lemma at every complexity. External well-foundedness does not remove this distinction.
Let M ⊨ Z F C Π n \mathcal{M}\models ZFC^{\Pi_n} M ⊨ Z F C Π n . For fixed n n n , the non-induction axiom instances have a common finite complexity bound. Choose a standard j ≥ 1 j\geq1 j ≥ 1 such that they are all B Σ j B\Sigma_j B Σ j , including any further formulas needed in the argument when choosing j j j . Lemma 18 then transfers these forced assertions to M P / G \mathcal{M}^{P}/G M P / G whenever G G G is B Σ b ( j ) B\Sigma_{b(j)} B Σ b ( j ) -generic over M \mathcal{M} M . This applies to both externally well-founded and ill-founded grounds. The bound b ( j ) \mathrm{b}(j) b ( j ) supplies a sufficient genericity level for transfer; the sharper definitions in Lemma 46 justify the earlier uses of Separation and Collection. If G G G is definable over M \mathcal{M} M , Lemma 19 supplies Full Set Induction separately.
Ground model definability in a weak set theory
Ground model definability was proved independently by Laver and Woodin; see Laver [2007] and the historical account in Fuchs et al. [2015], Section 1. Informally speaking, it tells us that the inner models that generically extend to the universe, its grounds, are uniformly definable using a parameter. Schluzenberg’s version works over MOST . We use it to supply the candidate grounds, and then compare candidates to obtain a smaller parameter needed for coding.
Theorem 47. (Schlutzenberg.) Over M O S T MOST M O S T there is a fixed formula grd ( t , x ) \operatorname{grd}(t,x) grd ( t , x ) such that the classes W t = { x : grd ( t , x ) } W_t=\{x:\operatorname{grd}(t,x)\} W t = { x : grd ( t , x )} enumerate exactly the set-forcing grounds, including the universe itself. If V = W [ G ] V=W[G] V = W [ G ] and the forcing belongs to t = ( H η + ) W t=(H_{\eta^+})^W t = ( H η + ) W , then W t = W W_t=W W t = W .
This is Schlutzenberg [2022], Definition 2.9 and Corollary 2.10. A ground here satisfies M O S T MOST M O S T . If the ambient universe has Full Set Induction, each of these definable transitive grounds has it too: relativize the formula in an induction instance to the ground and apply ambient induction. Thus this family supplies grounds strong enough for the interpretation arguments of the paper.
The hereditary-size parameter in Theorem 47 recalls the large initial segment V α W V^W_\alpha V α W used in Laver’s first proof. Laver [2007] published the ground-model definability theorem using Hamkins’s approximation and cover argument, which allows the parameter P ( δ ) W \mathcal{P}(\delta)^W P ( δ ) W . Hamkins and Johnstone subsequently observed that ( < δ 2 ) W (<\delta2)^W ( < δ 2 ) W suffices. See Fuchs et al. [2015, Theorem 6 and the discussion following Lemma 8] for this history.
For the coding applications in Section 6.1, we need this smaller parameter. We shall make the ground definable without parameters by coding a set that determines it into the continuum function. In our construction that set is r κ = ( < κ + 2 ) W r_\kappa=(<\kappa^+2)^W r κ = ( < κ + 2 ) W , where κ \kappa κ is fixed before the coding begins. The coding forcing can be much larger than r κ r_\kappa r κ , so we need a ground definition whose parameter does not grow with the size of that forcing. Theorem 48 provides this over M O S T MOST M O S T .
Our strategy is to use the family supplied by Theorem 47 and select its intended member using the smaller parameter. We require a candidate ground to have the specified < δ <\delta < δ -sequences, to have δ \delta δ -approximation and δ \delta δ -cover in the ambient universe, and to agree with that universe on δ + \delta^+ δ + . The intended ground satisfies these requirements. Lemma 49 will show that every candidate satisfying them is that ground. We can therefore quantify over the indices in Theorem 47, leaving only the smaller parameter in the definition.
Recall that W ⊆ V W\subseteq V W ⊆ V has δ \delta δ -cover if every set a ⊆ W a\subseteq W a ⊆ W with ∣ a ∣ V < δ |a|^V<\delta ∣ a ∣ V < δ is contained in a set b ∈ W b\in W b ∈ W with ∣ b ∣ W < δ |b|^W<\delta ∣ b ∣ W < δ . It has δ \delta δ -approximation if a set A ⊆ W A\subseteq W A ⊆ W belongs to W W W whenever A ∩ b ∈ W A\cap b\in W A ∩ b ∈ W for every b ∈ W b\in W b ∈ W with ∣ b ∣ W < δ |b|^W<\delta ∣ b ∣ W < δ . Here δ \delta δ will be an infinite cardinal regular in the models in question.
Theorem 48. (MOST) There is a single first-order formula ϑ ( x , r ) \vartheta(x,r) ϑ ( x , r ) with the following property. Suppose V = W [ G ] V=W[G] V = W [ G ] is a set-forcing extension of a proper inner model W ⊨ M O S T W\models MOST W ⊨ M O S T . If δ \delta δ is an infinite cardinal regular in both W W W and V V V , the extension has the δ \delta δ -cover and δ \delta δ -approximation properties, and ( δ + ) W = ( δ + ) V (\delta^+)^W=(\delta^+)^V ( δ + ) W = ( δ + ) V , then, for r = ( < δ 2 ) W r=(<\delta2)^W r = ( < δ 2 ) W ,
W = { x ∈ V : V ⊨ ϑ ( x , r ) } . W=\{x\in V:V\models\vartheta(x,r)\}. W = { x ∈ V : V ⊨ ϑ ( x , r )} .
In particular, every proper ground is uniformly definable from such a parameter: if G G G is generic for P ∈ W \mathbb{P}\in W P ∈ W , we may take δ = ( ∣ P ∣ + ) W \delta=(|\mathbb{P}|^+)^W δ = ( ∣ P ∣ + ) W .
The definition has a simple form. We search the family W t W_t W t for a ground with the given < δ <\delta < δ -sequences and the approximation, cover and cardinal-agreement properties in the theorem. There are two things to prove: the intended ground meets these requirements, and every ground meeting them is the intended one. Theorem 47 provides an index for the first part. Lemma 49 will give the second, once agreement on < δ <\delta < δ -sequences has been upgraded to agreement on P ( δ ) \mathcal{P}(\delta) P ( δ ) .
Lemma 49. (MOST.) Suppose M , N M,N M , N belong to the ground family above, δ \delta δ is regular in M , N , V M,N,V M , N , V , and both inclusions into V V V have δ \delta δ -approximation and δ \delta δ -cover. If
P ( δ ) M = P ( δ ) N , ( δ + ) M = ( δ + ) N = ( δ + ) V , \mathcal{P}(\delta)^M=\mathcal{P}(\delta)^N,\qquad(\delta^+)^M=(\delta^+)^N=(\delta^+)^V, P ( δ ) M = P ( δ ) N , ( δ + ) M = ( δ + ) N = ( δ + ) V , then M = N M=N M = N .
The idea of Lemma 49 is to place each small set inside a cover common to both grounds. Subsets of that cover can then be coded below δ + \delta^+ δ + , where the grounds agree. Approximation turns this local agreement into agreement on all sets of ordinals. We give the set-existence details because the grounds are defined by a formula whose complexity need not be low.
Proof. We first explain why the sets used in the comparison exist. For every ambient set a a a , the intersection a ∩ W t a\cap W_t a ∩ W t is a set. For a default index W t = V W_t=V W t = V , this is immediate. For a true index, membership in W t W_t W t is given by the local-witness formula φ g r d ( t , x ) \varphi_{\mathrm{grd}}(t,x) φ grd ( t , x ) of Schlutzenberg [2022], Definition 2.9. Choose an infinite cardinal ξ \xi ξ with ∣ tc ( { t , a } ) ∣ ≤ ξ |\operatorname{tc}(\{t,a\})|\leq\xi ∣ tc ({ t , a }) ∣ ≤ ξ , and let B = H ( 2 ξ ) + B=H(2^\xi)^+ B = H ( 2 ξ ) + .
The witness bound in Schlutzenberg’s Remark 2.11 applies uniformly to all x ∈ a x\in a x ∈ a : when a witness exists, it can be taken to be a local ground of H ξ + H_{\xi^+} H ξ + , with the whole witnessing structure of hereditary size at most 2 ξ 2^\xi 2 ξ . The same remark gives absoluteness of the witness test, so
x ∈ W t ⟷ B ⊨ φ g r d ( t , x ) ( x ∈ a ) . x\in W_t\quad\longleftrightarrow\quad B\models\varphi_{\mathrm{grd}}(t,x)\qquad(x\in a). x ∈ W t ⟷ B ⊨ φ grd ( t , x ) ( x ∈ a ) .
Here t t t is a true index in the ambient universe; we do not ask B B B to decide that. Since φ g r d \varphi_{\mathrm{grd}} φ grd is fixed, the right-hand side is just its relativization to the set B B B . Bounded Separation on a a a therefore gives a ∩ W t a\cap W_t a ∩ W t .
Fix an ordinal α \alpha α . Given a ⊆ α a\subseteq\alpha a ⊆ α of ambient size less than δ \delta δ , alternately cover in M M M and N N N to obtain, for i < δ i<\delta i < δ ,
a ∪ ⋃ j < i Y j ⊆ X i ⊆ Y i ⊆ α , a\cup\bigcup_{j<i}Y_j\subseteq X_i\subseteq Y_i\subseteq\alpha, a ∪ j < i ⋃ Y j ⊆ X i ⊆ Y i ⊆ α ,
where X i X_i X i is small in M M M and Y i Y_i Y i is small in N N N . This is a recursion on sets. Indeed, all possible covers and their bijections with ordinals below δ \delta δ lie in the intersections with M M M and N N N of
P ( α ) ∪ P ( δ × α ) . \mathcal{P}(\alpha)\cup\mathcal{P}(\delta\times\alpha). P ( α ) ∪ P ( δ × α ) .
These intersections are sets by the preceding paragraph. Well-order the two families, and at each stage take the first suitable cover together with its witnessing bijection. Regularity and cover ensure that a choice is always possible. The partial histories form a subset of a fixed function set; their uniqueness and compatibility give the recursion by taking unions.
Let C = ⋃ i < δ X i = ⋃ i < δ Y i C=\bigcup_{i<\delta}X_i=\bigcup_{i<\delta}Y_i C = ⋃ i < δ X i = ⋃ i < δ Y i . The retained bijections show that ∣ C ∣ V ≤ δ |C|^V\leq\delta ∣ C ∣ V ≤ δ . If b ∈ M b\in M b ∈ M is small in M M M , regularity bounds the stages at which members of C ∩ b C\cap b C ∩ b enter the union. Thus C ∩ b = X i ∩ b ∈ M C\cap b=X_i\cap b\in M C ∩ b = X i ∩ b ∈ M for some i i i , and approximation gives C ∈ M C\in M C ∈ M . The same argument gives C ∈ N C\in N C ∈ N . We have obtained a common cover of a a a , of ambient size at most δ \delta δ .
Agreement on P ( δ ) \mathcal{P}(\delta) P ( δ ) gives agreement on the subsets of every β < δ + \beta<\delta^+ β < δ + . To see this, choose in M M M a bijection from some d ≤ δ d\leq\delta d ≤ δ onto β \beta β and pull back the ordinal order to d d d . A fixed ordinal pairing codes this relation by a subset of δ \delta δ . The code belongs to N N N , and its ordinal collapse there is the same as in M M M . Consequently the bijection belongs to both grounds, and it transports their common subsets of d d d to the same subsets of β \beta β .
Now let A ⊆ α A \subseteq\alpha A ⊆ α belong to M M M , and let b ∈ N b \in N b ∈ N be small in N N N . Choose a common cover C C C of b ∩ α b \cap\alpha b ∩ α as above. Its increasing enumeration belongs to both grounds. Its order type β \beta β is below the common δ + \delta^{+} δ + , since ∣ C ∣ V ≤ δ |C|^{V} \leq\delta ∣ C ∣ V ≤ δ . The code of A ∩ C A \cap C A ∩ C is a subset of β \beta β , and hence belongs to both grounds. It follows that A ∩ b ∈ N A \cap b \in N A ∩ b ∈ N . Approximation gives A ∈ N A \in N A ∈ N . By symmetry, M M M and N N N have the same sets of ordinals.
Finally, every set in either ground has an ordinal code for its pointed transitive closure. The same code belongs to the other ground, and its collapse recovers the same set. The needed collapse is available in MOST : Σ 1 \Sigma_{1} Σ 1 -Separation forms the set of nodes admitting partial collapses, Σ 1 \Sigma_{1} Σ 1 -Collection collects compatible predecessor collapses, and well-foundedness rules out a least failure. Uniqueness of collapse gives agreement. Thus M = N M=N M = N . □
We can now recover a ground from its < δ <\delta < δ -sequences.
Proof. (of Theorem 48.) Recover δ \delta δ from r r r by δ = ⋃ { dom ( s ) : s ∈ r } \delta=\bigcup\{\operatorname{dom}(s):s\in r\} δ = ⋃ { dom ( s ) : s ∈ r } . Let C ( t , r ) C(t,r) C ( t , r ) say that
r = ( ⟨ δ 2 ⟩ ) W t , ( δ + ) W t = ( δ + ) V , r=(\langle\delta2\rangle)^{W_t}, \qquad(\delta^{+})^{W_t}=(\delta^{+})^{V}, r = (⟨ δ 2 ⟩ ) W t , ( δ + ) W t = ( δ + ) V ,
that δ \delta δ is infinite regular in W t W_t W t and V V V , and that W t ⊆ V W_t\subseteq V W t ⊆ V has δ \delta δ -approximation and δ \delta δ -cover. Define
ϑ ( x , r ) ⟷ ∃ t ( C ( t , r ) ∧ grd ( t , x ) ) . \vartheta(x,r)\longleftrightarrow\exists t(C(t,r)\land\operatorname{grd}(t,x)). ϑ ( x , r ) ⟷ ∃ t ( C ( t , r ) ∧ grd ( t , x )) .
All occurrences of W t W_t W t are replaced by its fixed defining formula. Thus r r r is the only parameter. The conditions in C ( t , r ) C(t,r) C ( t , r ) are additional requirements on a candidate; Theorem 47 does not assert that every candidate satisfies them.
First, the intended ground qualifies. Fix W , G , δ , r W,G,\delta,r W , G , δ , r as in the theorem. Theorem 47 supplies an index t 0 t_0 t 0 with W t 0 = W W_{t_0}=W W t 0 = W . The hypotheses on W ⊆ V W\subseteq V W ⊆ V give C ( t 0 , r ) C(t_0,r) C ( t 0 , r ) . Hence every member of W W W satisfies ϑ ( x , r ) \vartheta(x,r) ϑ ( x , r ) .
Next, suppose C ( t , r ) C(t,r) C ( t , r ) holds, and let M = W t M=W_t M = W t . Equality of the < δ <\delta < δ -sequences gives agreement between M M M and W W W on all bounded subsets of δ \delta δ . If A ∈ W A\in W A ∈ W and A ⊆ δ A\subseteq\delta A ⊆ δ , then A ∩ α ∈ M A\cap\alpha\in M A ∩ α ∈ M for every α < δ \alpha<\delta α < δ . For any b ∈ M b\in M b ∈ M with ∣ b ∣ M < δ |b|^{M}<\delta ∣ b ∣ M < δ , regularity bounds b ∩ δ b\cap\delta b ∩ δ by some α < δ \alpha<\delta α < δ . Thus
A ∩ b = ( A ∩ α ) ∩ b ∈ M . A\cap b=(A\cap\alpha)\cap b\in M. A ∩ b = ( A ∩ α ) ∩ b ∈ M .
Approximation for M ⊆ V M\subseteq V M ⊆ V gives A ∈ M A\in M A ∈ M . The symmetric argument gives P ( δ ) M = P ( δ ) W \mathcal{P}(\delta)^{M}=\mathcal{P}(\delta)^{W} P ( δ ) M = P ( δ ) W .
We can now apply Lemma 49. Its hypotheses hold for W W W by assumption and for M M M because C ( t , r ) C(t,r) C ( t , r ) holds. Hence M = W M=W M = W . Every qualifying index therefore defines the same ground, so ϑ ( x , r ) \vartheta(x,r) ϑ ( x , r ) defines W W W . For forcing of size less than δ \delta δ , the small-forcing argument gives δ \delta δ -cover and δ \delta δ -approximation and preserves δ \delta δ and its successor. We may consequently take δ = ( ∣ P ∣ + ) W \delta=(|\mathbb{P}|^{+})^{W} δ = ( ∣ P ∣ + ) W . □
The small parameter selects the ground; it need not be an index in Schlutzenberg’s family. We have used Theorem 47 to quantify over definable candidates, and Lemma 49 to show that the requirements leave only the intended ground.
A uniquely definable ground theorem
Our goal is to construct set forcings whose generic extensions can define their associated grounds without parameters, for use in the stable definable ground property. We construct a family G κ \mathbb{G}_{\kappa} G κ for suitable regular cardinals κ \kappa κ . At a fixed index κ \kappa κ , the universe has at most one ground from which it arises by the designated forcing, and that ground is definable from κ \kappa κ . For the preserved indices ω \omega ω and ω 2 \omega_2 ω 2 used in our applications, this gives a definition without parameters.
Theorem 48 reduces recovery of the ground to making r = ( ⟨ δ 2 ⟩ ) V r=(\langle\delta^2\rangle)^V r = (⟨ δ 2 ⟩ ) V recognizable. We first add a small generic set, and then code r r r much farther up the continuum function. This strategy uses Hamkins’s approximation and cover argument; see Fuchs et al. [2015, Theorem 6 and Lemma 8]. Together the two steps give approximation and cover, while the closed tail preserves the relevant low cardinals. The code must begin at a recognizable place. Once the extension can locate and read it, Theorem 48 recovers the ground.
We first give the two-stage form and then construct the forcing used at the second stage. Lemma 50 will supply Code ( r , θ ) \operatorname{Code}(r,\theta) Code ( r , θ ) whenever θ \theta θ is infinite regular and ∣ tc ( { r } ) ∣ < θ |\operatorname{tc}(\{r\})|<\theta ∣ tc ({ r }) ∣ < θ . This forcing will be < θ + <\theta^+ < θ + -directed closed,33 preserve θ \theta θ and all smaller cardinals, and make r r r uniformly recoverable from θ \theta θ .
Let κ \kappa κ be an infinite regular cardinal with κ < κ = κ \kappa^{<\kappa}=\kappa κ < κ = κ , and let r κ = ( ⟨ κ + ⟩ 2 ) V r_\kappa=(\langle\kappa^+\rangle^2)^V r κ = (⟨ κ + ⟩ 2 ) V . Thus the approximation-and-cover cardinal in Theorem 48 will be δ = κ + \delta=\kappa^+ δ = κ + . In the intermediate Add ( κ , 1 ) \operatorname{Add}(\kappa,1) Add ( κ , 1 ) -extension let θ = ( 2 κ + + ) + \theta=(2^{\kappa^{++}})^+ θ = ( 2 κ ++ ) + , and let Q ˙ κ \dot{\mathbb{Q}}_\kappa Q ˙ κ be the canonical name for Code ( r ˇ κ , θ ˙ ) \operatorname{Code}(\check{r}_\kappa,\dot{\theta}) Code ( r ˇ κ , θ ˙ ) . Since ∣ tc ( { r κ } ) ∣ ≤ ( 2 κ ) V < θ |\operatorname{tc}(\{r_\kappa\})|\leq(2^\kappa)^V<\theta ∣ tc ({ r κ }) ∣ ≤ ( 2 κ ) V < θ , this is defined. Let
G κ = Add ( κ , 1 ) ∗ Q ˙ κ . \mathbb{G}_\kappa=\operatorname{Add}(\kappa,1)*\dot{\mathbb{Q}}_\kappa. G κ = Add ( κ , 1 ) ∗ Q ˙ κ .
The name retains the original ground parameter r κ r_\kappa r κ .
The first factor has size κ \kappa κ , is < κ <\kappa < κ -directed closed, and preserves cardinals. The tail’s < θ + <\theta^+ < θ + -directed closure is more than is needed to preserve κ < κ = κ \kappa^{<\kappa}=\kappa κ < κ = κ and all cardinals through κ + + \kappa^{++} κ ++ . Thus the whole forcing has these preservation properties and is nontrivial and < κ <\kappa < κ -directed closed. The tail also preserves the intermediate power set of κ + + \kappa^{++} κ ++ and the cardinals through θ \theta θ . Consequently the final universe computes the same θ = ( 2 κ + + ) + \theta=(2^{\kappa^{++}})^+ θ = ( 2 κ ++ ) + from κ \kappa κ . It can then read an ordinal code X ⊆ θ X\subseteq\theta X ⊆ θ , recover r κ r_\kappa r κ , and use Theorem 48 to define the ground. Lemma 52 will verify this recovery.
For general κ \kappa κ the definition uses κ \kappa κ as a parameter. In the applications κ = ω \kappa=\omega κ = ω or ω 2 \omega_2 ω 2 , subject to κ < κ = κ \kappa^{<\kappa}=\kappa κ < κ = κ . Preservation of all cardinals through κ \kappa κ keeps this index equal to the extension’s own ω \omega ω or ω 2 \omega_2 ω 2 , so the definition is parameter-free. We write G = G ω \mathbb{G}=\mathbb{G}_\omega G = G ω where the assumption ω < ω = ω \omega^{<\omega}=\omega ω < ω = ω is automatic.
For κ = ω \kappa=\omega κ = ω , this is the promised example
V ⊆ V [ c ] ⊆ U = V [ c ] [ H ] , r = ( ⟨ ω 1 ⟩ 2 ) V . V\subseteq V[c]\subseteq U=V[c][H],\qquad r=(\langle\omega_1\rangle^2)^V. V ⊆ V [ c ] ⊆ U = V [ c ] [ H ] , r = (⟨ ω 1 ⟩ 2 ) V .
The tail codes this original r r r , not the < ω 1 <\omega_1 < ω 1 -sequences in V [ c ] V[c] V [ c ] . It is closed enough to add no ordinal sequences of length at most ω 2 \omega_2 ω 2 . We shall use Fact 53 for approximation and cover, and preservation of ω 2 \omega_2 ω 2 for the remaining cardinal agreement in Theorem 48 .34
For Code ( r , θ ) \operatorname{Code}(r,\theta) Code ( r , θ ) we use a local version of the continuum coding in Reitz [2007, Section 3, proof of Theorem 11]. Compare also the preparation of a coding interval in Fuchs et al. [2015, proof of Theorem 67]. Each bit is recorded by whether G C H GCH GC H holds at its coding cardinal, after preparing the cardinal arithmetic there. The additional problem is to construct this forcing and verify its preservation properties in the weaker theory. Lemma 51 supplies that verification.
Let r r r be a set and let θ \theta θ be an infinite regular cardinal with ∣ tc ( { r } ) ∣ < θ |\operatorname{tc}(\{r\})|<\theta ∣ tc ({ r }) ∣ < θ . Use a fixed ordinal pairing to code a domain, a binary relation and a distinguished root by a subset of θ \theta θ . We consider all such codes X ⊆ θ X\subseteq\theta X ⊆ θ of ⟨ tc ( { r } ) , ∈ , r ⟩ \langle\operatorname{tc}(\{r\}),\in,r\rangle ⟨ tc ({ r }) , ∈ , r ⟩ . Note that to obtain a particular code for r r r , we use Choice, but this does not give us a uniformly definable choice of code. To get around this, we use a lottery sum over all possible codes.35
For each such code X ⊆ θ X\subseteq\theta X ⊆ θ , let P X = R θ ∗ E ˙ X \mathbb{P}_X=\mathbb{R}_\theta*\dot{\mathbb{E}}_X P X = R θ ∗ E ˙ X . The first factor prepares G C H GCH GC H throughout a sufficiently long interval and is independent of X X X . The second codes X X X at consecutive successor cardinals in that interval. Define Code ( r , θ ) \operatorname{Code}(r,\theta) Code ( r , θ ) to be the lottery sum of these P X \mathbb{P}_X P X , with a greatest condition adjoined. Every component codes the same fixed set r r r .
To prepare the interval we use the following collapse. For an infinite regular cardinal ρ \rho ρ and a cardinal χ ≥ ρ \chi\ge\rho χ ≥ ρ , let Coll ( ρ , χ ) \operatorname{Coll}(\rho,\chi) Coll ( ρ , χ ) consist of partial functions from ρ \rho ρ to χ \chi χ of size below ρ \rho ρ , ordered by reverse inclusion. This forcing is < ρ <\rho < ρ -directed closed and makes ∣ χ ∣ = ρ |\chi|=\rho ∣ χ ∣ = ρ .
Let R θ \mathbb{R}_\theta R θ be a full-support iteration of length θ + 1 \theta+1 θ + 1 . Write M i M_i M i for the extension by its first i i i stages. Define the cardinals μ i \mu_i μ i , for i ≤ θ i\le\theta i ≤ θ , during the iteration by
μ 0 = θ , μ i + 1 = ( μ i + ) M i + 1 ( i < θ ) , μ i = sup j < i μ j ( 0 < i ≤ θ a limit ) . \mu_0=\theta,\qquad\mu_{i+1}=(\mu_i^+)^{M_{i+1}}\quad(i<\theta),\qquad\mu_i=\sup_{j<i}\mu_j\quad(0<i\le\theta\text{ a limit}). μ 0 = θ , μ i + 1 = ( μ i + ) M i + 1 ( i < θ ) , μ i = j < i sup μ j ( 0 < i ≤ θ a limit ) .
At stage i ≤ θ i\le\theta i ≤ θ , force over M i M_i M i with Coll ( μ i + , 2 μ i ) \operatorname{Coll}(\mu_i^+,2^{\mu_i}) Coll ( μ i + , 2 μ i ) , with both parameters computed in M i M_i M i . The collapse therefore uses a regular successor even when μ i \mu_i μ i is singular.
In the completed preparation extension W W W , let η = μ θ \eta=\mu_\theta η = μ θ and, for ξ < θ \xi<\theta ξ < θ , let
λ ξ = θ + ( ξ + 1 ) , F X ( λ ξ ) = { λ ξ + , ξ ∈ X , λ ξ + + , ξ ∉ X . \lambda_\xi=\theta^{+(\xi+1)},\qquad F_X(\lambda_\xi)=
\begin{cases}
\lambda_\xi^+,&\xi\in X,\\
\lambda_\xi^{++},&\xi\notin X.
\end{cases} λ ξ = θ + ( ξ + 1 ) , F X ( λ ξ ) = { λ ξ + , λ ξ ++ , ξ ∈ X , ξ ∈ / X .
Define E X \mathbb{E}_X E X in W W W to be the full-support product
E X = ∏ ξ < θ Add ( λ ξ , F X ( λ ξ ) ) . \mathbb{E}_X=\prod_{\xi<\theta}\operatorname{Add}(\lambda_\xi,F_X(\lambda_\xi)). E X = ξ < θ ∏ Add ( λ ξ , F X ( λ ξ )) .
Here Add ( λ , ν ) \operatorname{Add}(\lambda,\nu) Add ( λ , ν ) consists of partial functions from ν × λ \nu\times\lambda ν × λ to 2 2 2 of size below λ \lambda λ . All the cardinals, factors and their sets of conditions in this product are computed in W W W . With only θ \theta θ coordinates, all above θ \theta θ , full support satisfies the Easton support requirement.
For the large-cardinal applications in § 6.1 , we also need the coding forcing to remain small relative to the cardinal we wish to preserve. Inaccessibility suffices for this size estimate; the stronger large-cardinal hypothesis enters the subsequent preservation argument.
Lemma 50. (Z F C Π 3 1 \mathsf{ZFC}^{\Pi^1_3} ZFC Π 3 1 .) The forcing Code ( r , θ ) \operatorname{Code}(r,\theta) Code ( r , θ ) is uniformly definable from r , θ r,\theta r , θ and is < θ + <\theta^+ < θ + -directed closed. It preserves θ \theta θ and all smaller cardinals. In every generic extension, r r r is uniformly definable
from θ \theta θ : the chosen code is
X = { ξ < θ : 2 θ + ( ξ + 1 ) = θ + ( ξ + 2 ) } , X=\{\xi<\theta:2^{\theta^{+(\xi+1)}}=\theta^{+(\xi+2)}\}, X = { ξ < θ : 2 θ + ( ξ + 1 ) = θ + ( ξ + 2 ) } ,
and its rooted collapse recovers r r r . Here the index operations are ordinal operations and all the displayed cardinals are computed in the final extension. If ζ \zeta ζ is inaccessible and θ < ζ \theta<\zeta θ < ζ , the forcing has a set of conditions of size below ζ \zeta ζ .
Proof. At preparation stage i i i , the collapse is < μ i + <\mu_i^{+} < μ i + -directed closed, preserves μ i \mu_i μ i and μ i + \mu_i^{+} μ i + , and adds no subsets of μ i \mu_i μ i . It makes the existing power set have size μ i + \mu_i^{+} μ i + , so it forces 2 μ i = μ i + 2^{\mu_i}=\mu_i^{+} 2 μ i = μ i + . The next stage, and the full-support tail after it, are closed enough to preserve this equality and its two cardinals. At limits the supremum of the earlier preserved cardinals remains a cardinal. Induction therefore gives, in W W W ,
μ i = θ + i , 2 μ i = μ i + ( i ≤ θ ) . \mu_i=\theta^{+i},\qquad2^{\mu_i}=\mu_i^{+}\quad(i\leq\theta). μ i = θ + i , 2 μ i = μ i + ( i ≤ θ ) .
Thus GCH holds at every cardinal from θ \theta θ through η = θ + θ \eta=\theta^{+\theta} η = θ + θ , including the singular limits and the endpoint. In particular, 2 < θ + = θ + 2^{<\theta^{+}}=\theta^{+} 2 < θ + = θ + and 2 η = η + 2^\eta=\eta^{+} 2 η = η + .
Work now in W W W . The function F X F_X F X is nondecreasing, and its values have cofinality greater than their arguments. Each factor of E X E_X E X is < θ + <\theta^{+} < θ + -directed closed. Coordinatewise unions give the same closure for the product. The preparation and its two-step iteration with this product have that closure as well. Consequently they preserve θ \theta θ and all smaller cardinals.
Fix a coding cardinal λ \lambda λ and factor E X = P × Q E_X=P\times Q E X = P × Q at λ \lambda λ , with P P P containing the coordinates at most λ \lambda λ . A condition in P P P has combined domain of size < λ <\lambda < λ . Local GCH gives λ < λ = λ \lambda^{<\lambda}=\lambda λ < λ = λ , so the generalized Δ \Delta Δ -system argument gives the λ + \lambda^{+} λ + -chain condition: among λ + \lambda^{+} λ + conditions, two agree on their common domain and hence are compatible. In W W W , the tail Q Q Q is < λ + <\lambda^{+} < λ + -closed. Easton’s lemma therefore gives
1 P ⊩ Q ˙ is < λ + -distributive . 1_P\Vdash\dot Q\text{ is }<\lambda^{+}\text{-distributive}. 1 P ⊩ Q ˙ is < λ + -distributive .
In particular, the tail adds no subsets of λ \lambda λ over the extension by P P P .
The product preserves all cofinalities. To see this, suppose a ground cofinality decreases to τ \tau τ , where τ \tau τ is regular in the final extension and hence was already regular in W W W . If τ ≤ θ \tau\leq\theta τ ≤ θ , the product’s closure prevents the new cofinal sequence. If θ < τ < η \theta<\tau<\eta θ < τ < η , then τ \tau τ is a coding cardinal: every limit cardinal in this interval has cofinality at most θ \theta θ . The factorization at τ \tau τ puts the sequence in the extension by the product through τ \tau τ , whose τ + \tau^{+} τ + -chain condition prevents the decrease. Finally, η \eta η is singular of cofinality θ \theta θ , and all product domains can be coded in a set of size η \eta η . Thus ∣ E X ∣ ≤ 2 η = η + |E_X|\leq2^\eta=\eta^{+} ∣ E X ∣ ≤ 2 η = η + , which preserves every ground cofinality at least η + + \eta^{++} η ++ . This rules out a decrease to any regular τ ≥ η + \tau\geq\eta^{+} τ ≥ η + . Preservation of cofinalities also gives preservation of cardinals.
Return to the factorization at λ \lambda λ . By monotonicity, the domains of conditions in P P P lie in a set of size F X ( λ ) F_X(\lambda) F X ( λ ) . Local GCH gives
∣ P ∣ ≤ F X ( λ ) < λ = F X ( λ ) , ( λ + ) λ = λ + , ( λ + + ) λ = λ + + . |P|\leq F_X(\lambda)^{<\lambda}=F_X(\lambda),\qquad
(\lambda^{+})^\lambda=\lambda^{+},\qquad
(\lambda^{++})^\lambda=\lambda^{++}. ∣ P ∣ ≤ F X ( λ ) < λ = F X ( λ ) , ( λ + ) λ = λ + , ( λ ++ ) λ = λ ++ .
For the last equality, every function from λ \lambda λ to λ + + \lambda^{++} λ ++ is bounded, and its range lies in an ordinal of cardinality at most λ + \lambda^{+} λ + . The λ + \lambda^{+} λ + -chain condition therefore bounds nice names for subsets of λ \lambda λ by F X ( λ ) F_X(\lambda) F X ( λ ) . The λ \lambda λ -coordinate adds that many distinct subsets, and the tail adds no more. Hence 2 λ ξ = F X ( λ ξ ) 2^{\lambda^\xi}=F_X(\lambda^\xi) 2 λ ξ = F X ( λ ξ ) in the final extension.
Since the product preserves cardinals, its coding cardinals are still the final universe’s own θ + ( ξ + 1 ) \theta^{+(\xi+1)} θ + ( ξ + 1 ) . The displayed test recovers X X X , and its rooted collapse recovers r r r . A directed family of non-greatest conditions in the lottery sum lies in one summand, so the lottery has the same closure bound. Lemma 51 supplies the set construction, the weak-theory verification of the preservation argument, and the inaccessible size bound. □
The remaining check concerns set existence and complexity. The cited coding arguments are carried out in Z F C ZFC Z F C ; here we bound the names, construction histories and preservation arguments needed over Z F C Π 3 ZFC\Pi^3 Z F C Π 3 .
Lemma 51. (Z F C Π 3 ZFC\Pi^3 Z F C Π 3 .) The construction of Code ( r , θ ) \operatorname{Code}(r,\theta) Code ( r , θ ) above is uniformly definable as a set forcing. If θ < ζ \theta< \zeta θ < ζ and ζ \zeta ζ is inaccessible, that forcing belongs to V ζ V_\zeta V ζ and has size less than ζ \zeta ζ .
Proof. Powerset has a Π 1 \Pi_1 Π 1 graph, and cardinalization and cardinal succession have Σ 2 \Sigma_2 Σ 2 graphs. Their set-length iterations are available by Σ 2 \Sigma_2 Σ 2 -Collection and Full Set Induction: at limits collect the earlier histories and take their compatible union. Use the ground-model bounds
χ 0 = ( 2 θ ) + , χ i = ( ℶ ω ( sup j < i χ j ) ) + ( 0 < i ≤ θ + 3 ) . \chi_0 = (2^\theta)^+,\qquad\chi_i = \left(\beth_\omega\left(\sup_{j<i}\chi_j\right)\right)^+ \qquad(0 < i \leq\theta+ 3). χ 0 = ( 2 θ ) + , χ i = ( ℶ ω ( j < i sup χ j ) ) + ( 0 < i ≤ θ + 3 ) .
where ℶ ω ( μ ) \beth_\omega(\mu) ℶ ω ( μ ) is the supremum of the finite powerset iterates starting at μ \mu μ . At preparation stage i ≤ θ i \leq\theta i ≤ θ , maintain ∣ R θ ↾ i ∣ ≤ χ i |R_\theta\mathbin{\upharpoonright} i| \leq\chi_i ∣ R θ ↾ i ∣ ≤ χ i and 1 ⊩ μ i ≤ χ ˇ i 1 \Vdash\mu_i \leq\check{\chi}_i 1 ⊩ μ i ≤ χ ˇ i . The additional bounds cover the endpoint stage and the name for the final product.
Use bounded families of names and their mixtures throughout. If S S S supplies representatives for the elements of a named set, subnames on S × ( R θ ↾ i ) S \times(R_\theta\mathbin{\upharpoonright} i) S × ( R θ ↾ i ) represent its subsets, and mixtures along antichains represent its elements. Each preparation stage uses cardinal succession, a power set, partial-function sets and finitely many such name operations, all absorbed by the next ℶ ω \beth_\omega ℶ ω bound. At a limit i i i , if μ \mu μ bounds the earlier representative families and ∣ i ∣ |i| ∣ i ∣ , the full-support conditions are bounded by μ ∣ i ∣ ≤ 2 μ \mu^{|i|} \leq2^\mu μ ∣ i ∣ ≤ 2 μ .
In the prepared model, the final product is a subset of a fixed function space. Another finite number of powerset and name operations therefore bounds its name and the two-step conditions. Retain all representatives in these families, so the definition requires no choice of preferred names or well-orders.
Include the auxiliary powersets, function sets, representative families and atomic forcing tables in the construction histories. Powerset correctness is Π 1 \Pi_1 Π 1 , the tables are Δ 1 \Delta_1 Δ 1 , and cardinalization and the bound sequence are Σ 2 \Sigma_2 Σ 2 . With these sets supplied, the tests for collapse and product conditions are bounded. An initial existential block for the auxiliary sets therefore gives the same Σ 3 \Sigma_3 Σ 3 bound on valid histories. The available Σ 3 \Sigma_3 Σ 3 -Collection and Separation assemble these histories, and Full Set Induction proves their existence and compatibility. This constructs the preparation, the final product name and the lottery sum as sets, uniformly from r , θ r,\theta r , θ .
The preservation proof uses the same bounded resources. For fixed input posets, ordinals and names, its Δ \Delta Δ -systems, antichains, nice names and descending sequences lie in fixed powersets and function sets. In Easton’s lemma, the λ + \lambda^+ λ + -chain condition bounds each antichain by λ \lambda λ . Deciding a sequence of length at most λ \lambda λ uses descending constructions of length at most λ \lambda λ , with lower bounds supplied by < λ + <\lambda^+ < λ + -closure. Nice names are subsets of λ × P \lambda\times\mathbb{P} λ × P . For a proposed cofinality decrease, fix the ordinal domain and target, so the relevant name families and value sets are again sets. Choice supplies well-orders for these existence proofs, and the recursions then have bounded tests in the supplied sets. Collecting the auxiliary witnesses uses the same Σ 3 \Sigma_3 Σ 3 bounds. Thus the local product proof is available over Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 without unrestricted Replacement. The forcing preliminaries of Section 5 supply preservation of this background and transfer to sufficiently generic definable extensions.
If θ < ζ \theta< \zeta θ < ζ and ζ \zeta ζ is inaccessible, strong limitness and regularity keep every χ i \chi_i χ i below ζ \zeta ζ . There are fewer than ζ \zeta ζ stages, each taking only a countable powerset iteration and a successor cardinal. The same induction bounds the hereditary sizes and ranks of the representative names and conditions below a common bound below ζ \zeta ζ . This covers the preparation, the final product name and their two-step iteration. There are at most 2 θ < ζ 2^\theta< \zeta 2 θ < ζ lottery summands, with uniform bounds. Conditions are tagged by X ⊆ θ X \subseteq\theta X ⊆ θ , so the rank of r r r is irrelevant to their rank bound. The whole forcing therefore belongs to V ζ V_\zeta V ζ and has size below ζ \zeta ζ . □
We now have the forcing and its preservation properties. We use them to show that its generic extensions can recognize their grounds.
Lemma 52. (Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 ) For a fixed ordinal κ \kappa κ , V V V has at most one ground M ⊨ Z F C Π 3 M \models ZFC^{\Pi_3} M ⊨ Z F C Π 3 such that M M M regards κ \kappa κ as an infinite regular cardinal satisfying κ < κ = κ \kappa^{<\kappa}=\kappa κ < κ = κ and V V V is a G κ M \mathbb{G}^M_\kappa G κ M -generic extension of M M M . If that ground exists, it is uniformly definable from κ \kappa κ . In particular, for κ = ω \kappa=\omega κ = ω or ω 2 \omega_2 ω 2 , it is uniformly definable without parameters.
Let us denote this ground as M G κ M_{G_\kappa} M G κ , and write M G M_G M G when κ = ω \kappa=\omega κ = ω . This should be understood as a defined relation symbol, in the same way that we refer to L L L . More generally, the index may be given by a parameter-free definition, provided its value is a regular cardinal satisfying κ < κ = κ \kappa^{<\kappa}=\kappa κ < κ = κ in the candidate grounds and is unchanged in their designated extensions. Definability of the index alone does not suffice. The preserved indices ω \omega ω and ω 2 \omega_2 ω 2 will suffice for the applications.
To prove this, we need the following theorem of Hamkins. Its Z F C ZFC Z F C form is Hamkins [ [15 ] , Lemma 13, with closure points defined immediately before it in Definition 12. Our additional task is to verify that the proof works over Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 .
Fact 53. (Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 ; closure-point forcing. ) Suppose R ∗ Q ˙ \mathbb{R} * \dot{\mathbb{Q}} R ∗ Q ˙ has an atomless first factor of size at most an infinite cardinal κ \kappa κ , and 1 R 1_{\mathbb{R}} 1 R forces that Q ˙ \dot{\mathbb{Q}} Q ˙ is ≤ κ \leq\kappa ≤ κ -strategically closed. Its generic extensions have δ \delta δ -approximation and δ \delta δ -cover over the ground, where δ = ( κ + ) V \delta=(\kappa^+)^V δ = ( κ + ) V . The same conclusions transfer to the sufficiently generic definable extensions used here.
Proof. We follow Hamkins [ [15 ] , pp. 265–266, and assume that the reader has that proof to hand. We recall the argument, then check the set constructions that matter in the weaker theory. Write the extension as V [ g ] [ H ] V[g][H] V [ g ] [ H ] .
Cover is immediate from the two factors. The tail adds no ordinal sequences of length at most κ \kappa κ . For a first-stage name for such a sequence, there are at most ∣ R ∣ |\mathbb{R}| ∣ R ∣ possible values at each coordinate, so their union is a ground set of size at most κ \kappa κ . Ground well-orders reduce sets of ground elements to this case. The same small-forcing calculation preserves δ \delta δ .
For approximation, argue by induction on the length τ \tau τ of a binary sequence s s s whose restrictions to ground sets of size at most κ \kappa κ belong to the ground. Every proper initial segment of s s s is then old. If cf V ( τ ) ≤ κ \operatorname{cf}^{V}(\tau) \leq\kappa cf V ( τ ) ≤ κ , closure puts s s s in V [ g ] V[g] V [ g ] , and the small-forcing argument applies. At larger cofinality, Hamkins builds a ground tree of tail names which split the possible initial segments of s s s . A new binary sequence of length at most κ \kappa κ added by the first factor selects a branch. Strategic closure gives a lower bound, forcing the union of the corresponding initial segments to be old. The splitting recovers the new branch from this union, a contradiction.
The first point to check is the use of the ground in forcing assertions. For a fixed name of length τ \tau τ , let
B = ( ≤ τ 2 ) V , C = { u ⊆ τ : ∣ u ∣ V ≤ κ } . B = (\leq_{\tau} 2)^{V}, \qquad C = \{u \subseteq\tau: \lvert u\rvert^{V} \leq\kappa\}. B = ( ≤ τ 2 ) V , C = { u ⊆ τ : ∣ u ∣ V ≤ κ } .
These are sets: the size test can quantify over P ( κ × τ ) \mathcal{P}(\kappa\times\tau) P ( κ × τ ) once that powerset has been supplied. In the proof, being an old binary sequence means membership in B ˇ \check{B} B ˇ , and the approximation tests range over C ˇ \check{C} C ˇ . No predicate for the ground, or truth predicate for it, is needed.
Next, bound the names used in the tree. Tail conditions have representatives among mixtures of the member-names of Q ˙ \dot{\mathbb{Q}} Q ˙ along first-factor antichains. Such mixtures are indexed by a powerset of a fixed product. A name for a play of length at most κ + 1 \kappa+1 κ + 1 is a sequence of these representatives, so the plays and the values of the named strategy also range over sets. Include their transitive closures and the needed check names, and form the atomic and bounded forcing tables on them. These tables have Δ 1 \Delta_{1} Δ 1 definitions.
With these sets and tables supplied, deciding an old initial segment, comparing conditions, finding a split and following the strategy are bounded tests. The same is true of the uniformity step that fixes the first coordinate: its quantifiers range over the first forcing, the chosen tail names and τ \tau τ . Fix well-orders of the sets of choices. The resulting plays and tree construction have histories in fixed function sets; bounded Separation selects valid histories, and uniqueness makes them compatible. Taking their union gives the required recursion. Thus no unrestricted Replacement is hidden in the tree construction.
Finally, the auxiliary powersets have Π 1 \Pi_{1} Π 1 correctness conditions, and the forcing tables are Δ 1 \Delta_{1} Δ 1 . Collecting these witnesses and the name families uses at most the Σ 3 \Sigma_{3} Σ 3 bounds described in Lemma 51. The available Π 3 \Pi_{3} Π 3 schemes supply Σ 3 \Sigma_{3} Σ 3 -Separation and Collection, while Full Set Induction supplies the induction on τ \tau τ and the existence of the recursion histories. This verifies the proof over Z F C Π 3 \mathsf{ZFC}_{\Pi_{3}} ZFC Π 3 . For the definable generics of the paper, take the finite genericity level high enough for the fixed assertions just used and apply Lemma 19 separately.
The role of the first factor is now visible: it supplies the new branch of length < κ <\kappa < κ used in the approximation argument. The tail is closed enough to preserve the low information used to recognize the ground, while writing its code farther up.
Proof. (of Lemma 52.) Work in Z F C Π 3 \mathsf{ZFC}_{\Pi_{3}} ZFC Π 3 . Let W = V [ G ] W=V[G] W = V [ G ] be a G κ \mathbb{G}_{\kappa} G κ -extension and write the generic according to the two-step iteration. The first factor is atomless and has size κ \kappa κ , while the second is < θ + <\theta^{+} < θ + -directed closed, with θ = ( 2 κ + ) + \theta=(2^{\kappa^{+}})^{+} θ = ( 2 κ + ) + computed in the intermediate model. In particular it is ≤ κ \leq\kappa ≤ κ -strategically closed. The full iteration preserves κ + \kappa^{+} κ + and κ + + \kappa^{++} κ ++ . Fact 53 gives approximation and cover at δ = κ + \delta=\kappa^{+} δ = κ + , and preservation of κ + + \kappa^{++} κ ++ supplies the successor-cardinal agreement required by Theorem 48. Hence V V V is definable in W W W from r κ r_{\kappa} r κ by ϑ ( x , r κ ) \vartheta(x,r_{\kappa}) ϑ ( x , r κ ) .
We have defined the ground from its parameter. We now make that parameter definable from κ \kappa κ . By Lemma 50, the tail adds no subsets of κ + + \kappa^{++} κ ++ and preserves the intermediate cardinal θ = ( 2 κ + + ) + \theta=(2^{\kappa^{++}})^{+} θ = ( 2 κ ++ ) + . Thus W W W computes the same θ \theta θ . It reads the code at the cardinals θ + ( ξ + 1 ) \theta^{+(\xi+1)} θ + ( ξ + 1 ) , for ξ < θ \xi< \theta ξ < θ , and takes its rooted collapse, recovering the original r κ r_\kappa r κ .
Consequently there is a fixed formula D ( r , κ ) D(r,\kappa) D ( r , κ ) saying that r r r is the set recovered from this continuum pattern, and in the extension
x ∈ V ⟷ ∃ r ( D ( r , κ ) ∧ ϑ ( x , r ) ) . x \in V \longleftrightarrow\exists r(D(r,\kappa) \land\vartheta(x,r)). x ∈ V ⟷ ∃ r ( D ( r , κ ) ∧ ϑ ( x , r )) .
This is the purpose of the construction. Theorem 48 defines V V V from r κ r_\kappa r κ ; the continuum pattern defines r κ r_\kappa r κ from κ \kappa κ . For κ = ω \kappa= \omega κ = ω , the starting cardinal is the extension’s own ( 2 ω ) + (2^{\omega})^{+} ( 2 ω ) + , so both the coding range and the decoded parameter are recognizable without parameters. The displayed formula therefore defines V V V without parameters.
If V 0 V_0 V 0 and V 1 V_1 V 1 are two such grounds at the same index κ \kappa κ , their common extension computes the same κ + + \kappa^{++} κ ++ and θ \theta θ , reads the same code, and therefore recovers the same r r r . The formula ϑ ( x , r ) \vartheta(x,r) ϑ ( x , r ) defines both grounds, so V 0 = V 1 V_0 = V_1 V 0 = V 1 . For κ = ω \kappa= \omega κ = ω or ω 2 \omega_2 ω 2 , preservation of the index makes this definition parameter-free.
The same argument works for every G κ V \mathbb{G}^{V}_{\kappa} G κ V -generic extension of the chosen ground: the definition of the forcing retains the same r κ r_\kappa r κ , the index is preserved, and decoding gives that parameter back. This is the stability needed in the stable definable ground property. □
We have therefore supplied the recovery part of the intended applications: the designated forcing extension recognizes its ground, and recognizes the same ground when the construction is repeated. Whether an additional axiom survives the designated forcing is a separate question, to be checked in each application.
Applications
Large cardinals beyond L L L and other extensions
Finally, we can offer a representative sample of strong inductive set theories with weak Separation and Collection that are not tight.
Proposition 54. Let n ≥ 3 n \ge3 n ≥ 3 and let Φ \Phi Φ be a tautology or any of the statements below. If Z F C Π n + Φ \mathrm{ZFC}\Pi_n + \Phi ZFC Π n + Φ is consistent, then it is not tight.
¬ ∃ α V α ⊨ Z F C Π n \neg\exists\alpha\ V_\alpha\models\mathrm{ZFC}\Pi_n ¬∃ α V α ⊨ ZFC Π n ;
There is a measurable cardinal;
There is a supercompact cardinal;
I 3 I3 I 3 ;
There is a proper class of extendible cardinals;
P F A \mathrm{PFA} PFA ;
M M \mathrm{MM} MM .
Proof. Let S = Z F C Π n + Φ S = \mathrm{ZFC}\Pi_n + \Phi S = ZFC Π n + Φ . In each case we first obtain a consistent strengthening R ⊇ S R \supseteq S R ⊇ S and choose κ ∈ { ω , ω 2 } \kappa\in\{\omega,\omega_2\} κ ∈ { ω , ω 2 } so that R R R proves κ < κ = κ \kappa^{<\kappa} = \kappa κ < κ = κ and forcing with G κ \mathbb{G}_\kappa G κ preserves R R R . § 5 already supplies the uniform recovery of the ground. Our task is to choose an index at which the additional axiom survives the coding forcing, and then verify the forcing assertions required by Definition 29 . We carry out these two checks in that order.
For the tautology case, take R = S R=S R = S and κ = ω \kappa=\omega κ = ω . The assertion ω < ω = ω \omega^{<\omega}=\omega ω < ω = ω is automatic, and the set-forcing preservation recalled at the beginning of § 5 gives preservation of R R R by G ω \mathbb{G}_\omega G ω .
For the anti-rank assertion, let S 0 = Z F C Π n S_0=ZFC\Pi_n S 0 = Z F C Π n . Consistency of S S S implies consistency of S 0 S_0 S 0 , so the second incompleteness theorem gives consistency of R = S 0 + ¬ Con ( S 0 ) R=S_0+\neg\operatorname{Con}(S_0) R = S 0 + ¬ Con ( S 0 ) . This theory implies the displayed anti-rank assertion, since a set model of S 0 S_0 S 0 supplies the usual soundness proof. Its additional arithmetic sentence is preserved by set forcing, so take κ = ω \kappa=\omega κ = ω .
For the large-cardinal assertions, take R = S R=S R = S and κ = ω \kappa=\omega κ = ω . We first check that the whole forcing G ω \mathbb{G}_\omega G ω is small below an inaccessible λ \lambda λ . The first Cohen factor preserves the inaccessibility of λ \lambda λ . In the intermediate extension, the retained ground parameter r ω r_\omega r ω has hereditary size below λ \lambda λ and θ = ( 2 ω 2 ) + < λ \theta=(2^{\omega^2})^+<\lambda θ = ( 2 ω 2 ) + < λ . Lemma 51 therefore bounds the coding tail below λ \lambda λ . A maximal antichain in the countable first factor chooses bounds and names for enumerations of that tail. Regularity of λ \lambda λ gives a common bound below λ \lambda λ , and the corresponding pairs of conditions and named enumeration entries form a dense subset of the whole iteration of size below λ \lambda λ . We may replace this dense subset by an isomorphic poset in V λ V_\lambda V λ when applying the small-forcing arguments.
The preservation of measurability and supercompactness can be checked using measures, so the weak background need not construct a proper-class ultrapower. Let U U U be a normal λ \lambda λ -complete ground measure on a set D D D , and let B B B be the Boolean completion of the small forcing. Since λ \lambda λ is strong limit, ∣ B ∣ < λ |B|<\lambda ∣ B ∣ < λ . For a name X ˙ \dot{X} X ˙ for a subset of D D D , the Boolean values ∥ d ˇ ∈ X ˙ ∥ B \lVert\check{d}\in\dot{X}\rVert_B ∥ d ˇ ∈ X ˙ ∥ B , for d ∈ D d\in D d ∈ D , partition D D D into fewer than λ \lambda λ ground sets. One cell belongs to U U U . According to whether its Boolean value belongs to the generic, that cell lies in X X X or in its complement. Thus the filter generated by U U U in the extension is an ultrafilter.
This filter is still λ \lambda λ -complete: for fewer than λ \lambda λ named members, choose maximal antichains deciding ground measure-one subsets of them and intersect the fewer than λ \lambda λ ground sets so obtained. Normality is preserved by deciding a regressive function on a ground measure-one set; below any condition, one stronger condition decides its values on a measure-one subset, where ground normality makes it constant. These constructions use atomic forcing values and sets of names, partitions and antichains available in Z F C Π 3 ZFC\Pi_3 Z F C Π 3 . For measurability take D = λ D=\lambda D = λ . For supercompactness take D = ( P λ ( η ) ) V D=(P_\lambda(\eta))^V D = ( P λ ( η ) ) V for each η ≥ λ \eta\geq\lambda η ≥ λ , and extend the lifted measure to the new P λ ( η ) P_\lambda(\eta) P λ ( η ) by concentrating on D D D . It remains normal and fine, as required.
The rank-embedding cases use the usual small-forcing lifting argument. For an I 3 I3 I 3 witness j : V ρ → V ρ j:V_\rho\to V_\rho j : V ρ → V ρ with critical point λ \lambda λ , the equivalent forcing in V λ V_\lambda V λ is fixed by j j j , and the lift is given by j ∗ ( τ G ) = j ( τ ) G j^*(\tau_G)=j(\tau)_G j ∗ ( τ G ) = j ( τ ) G . The rank-name calculation identifies its domain and target with V ρ V [ G ] V_\rho^{V[G]} V ρ V [ G ] . For a proper class of extendible cardinals, fix the forcing and take an extendible λ \lambda λ above its size. Given a target height α > λ \alpha>\lambda α > λ , choose an inaccessible ρ > α \rho>\alpha ρ > α and an extendibility witness j : V ρ → V σ j:V_\rho\to V_\sigma j : V ρ → V σ with j ( λ ) > ρ j(\lambda)>\rho j ( λ ) > ρ . Lift this set embedding and restrict it to V α V [ G ] V_\alpha^{V[G]} V α V [ G ] . Thus every sufficiently large extendible remains extendible. The assumed proper class supplies the inaccessible heights used here. Satisfaction for these set structures and the bounded name and valuation constructions are available in the weak background. Together with the set-forcing preliminaries of § 5 , this proves preservation of R R R .
For P F A PFA P F A and M M MM M M , use their usual formulations [2 , 10 ] and take κ = ω 2 \kappa= \omega_2 κ = ω 2 . Both axioms are preserved by < ω 2 <\omega_2 < ω 2 -directed closed set forcing.36 To recall the argument over the weak background, let P \mathbb{P} P be such a forcing and suppose p ∈ P p \in\mathbb{P} p ∈ P forces that Q ˙ \dot{\mathbb{Q}} Q ˙ is proper, respectively stationary-set preserving, and that ⟨ D ˙ ξ : ξ < ω 1 ⟩ \langle\dot{D}_{\xi} : \xi< \omega_1\rangle ⟨ D ˙ ξ : ξ < ω 1 ⟩ is a family of dense subsets. The two-step iteration T = ( P ↓ p ) ∗ Q ˙ \mathbb{T} = (\mathbb{P}\mathbin{\downarrow}p) * \dot{\mathbb{Q}} T = ( P ↓ p ) ∗ Q ˙ belongs to the corresponding forcing class. Apply the ground forcing axiom to the dense sets E ξ = { ⟨ q , s ˙ ⟩ ∈ T : q ⊩ s ˙ ∈ D ˙ ξ } E_{\xi} = \{\langle q,\dot{s}\rangle\in\mathbb{T} : q \Vdash\dot{s} \in\dot{D}_{\xi}\} E ξ = {⟨ q , s ˙ ⟩ ∈ T : q ⊩ s ˙ ∈ D ˙ ξ } .
From a filter F F F meeting all the E ξ E_{\xi} E ξ , choose one condition for each requirement and close the chosen family under common extensions in F F F through ω \omega ω stages. This gives a directed set A ⊆ F A \subseteq F A ⊆ F of size at most ω 1 \omega_1 ω 1 . A lower bound p ∗ ≤ p p^* \leq p p ∗ ≤ p of its first coordinates forces that its second coordinates are directed and generate a filter meeting every D ˙ ξ \dot{D}_{\xi} D ˙ ξ . Since the construction works below every p p p , it proves the required forcing assertion. The closure is taken on iteration conditions, so it controls both coordinates.
The weak-background requirements are local. The two-step properness proof uses countable elementary submodels and their interpreted extensions; the stationary-preservation proof uses names for clubs in ω 1 \omega_1 ω 1 . Satisfaction for the relevant set structures and representative families of names are sets. Once they are fixed, the choice and closure constructions above take place in fixed powersets. The necessary Collection, Separation and set recursions are available in Z F C Π 3 ZFC\Pi_3 Z F C Π 3 .
We may arrange ω 2 < ω 2 = ω 2 \omega_2^{<\omega_2} = \omega_2 ω 2 < ω 2 = ω 2 without strengthening the consistency assumption. In a model of S S S , let τ = ∣ < ω 2 2 ∣ \tau= |{}^{<\omega_2}2| τ = ∣ < ω 2 2∣ and force a surjection from ω 2 \omega_2 ω 2 onto τ \tau τ using partial functions of size below ω 2 \omega_2 ω 2 . This forcing is < ω 2 <\omega_2 < ω 2 -directed closed, so it preserves the forcing axiom and ω 2 \omega_2 ω 2 , adds no sequences of length below ω 2 \omega_2 ω 2 , and makes ∣ < ω 2 2 ∣ = ω 2 |{}^{<\omega_2}2| = \omega_2 ∣ < ω 2 2∣ = ω 2 . Equivalently, ( ω 2 ) < ω 2 = ω 2 (\omega_2)^{<\omega_2} = \omega_2 ( ω 2 ) < ω 2 = ω 2 . Thus R = S + { ω 2 < ω 2 = ω 2 } R = S + \{\omega_2^{<\omega_2} = \omega_2\} R = S + { ω 2 < ω 2 = ω 2 } is consistent.
The forcing G ω 2 \mathbb{G}_{\omega_2} G ω 2 preserves R R R , by its directed closure and the preceding preservation argument. Here preservation of ω 2 < ω 2 = ω 2 \omega_2^{<\omega_2} = \omega_2 ω 2 < ω 2 = ω 2 also uses preservation of ω 2 \omega_2 ω 2 : the forcing adds no sequences of length below that cardinal, so the old bounds on the short function spaces remain valid.
In each case let N = M G κ N = M_{G_\kappa} N = M G κ and let S ∗ S^* S ∗ extend R R R by asserting that N N N is a G κ N G^N_\kappa G κ N -ground of the universe and satisfies R R R . The ground clause uses the M O S T MOST M O S T -ground family of § 5 ; the stronger axioms of R R R are imposed separately on N N N by relativization. This is still a theory of the form K P C + U ∗ KPC + U^* K P C + U ∗ with U ∗ U^* U ∗ quantifier bounded. Indeed, n n n and the definitions of the index and the ground are fixed. For the non-induction axioms, relativization therefore retains a common complexity bound. Full Set Induction in N N N follows from ambient Full Set Induction, applied to each definable subclass of N N N , and need not be included among the extra axioms.
To witness consistency, use Lemma 30 to choose a model of R R R with a definable countable enumeration, and take a definable G κ G_\kappa G κ -generic at a finite level covering the non-induction axioms and the recovery assertions. Lemma 18 transfers those forced assertions, Lemma 19 supplies Full Set Induction, and Lemma 52 recovers the ground. The resulting extension satisfies S ∗ S^* S ∗ . The same method justifies the preliminary consistency step for R = S + { ω 2 < ω 2 = ω 2 } R = S + \{\omega_2^{<\omega_2} = \omega_2\} R = S + { ω 2 < ω 2 = ω 2 } in the forcing-axiom cases.
We now verify the four clauses of Definition 29 . The induction instances require one additional observation. Set forcing forces each instance of Full Set Induction over a ground satisfying Full Set Induction. Fix a formula φ \varphi φ , with names for its parameters, and work below a condition p p p forcing ∃ x φ ( x ) \exists x\,\varphi(x) ∃ x φ ( x ) . Use ground Full Set Induction to choose a name τ \tau τ of least rank for which some q ≤ p q \leq p q ≤ p forces φ ( τ ) \varphi(\tau) φ ( τ ) . If a stronger condition forced φ \varphi φ of a member of τ \tau τ , the atomic membership clause would give a further extension equating that member with a member-name of τ \tau τ . Substitution would then contradict the minimality of its rank. Hence q q q forces that τ \tau τ is a minimal member of the class defined by φ \varphi φ . The density of such conditions proves the induction instance.
In a model of S ∗ S^* S ∗ , let Q = G κ N \mathbb{Q} = \mathbb{G}^{N}_{\kappa} Q = G κ N . Then Q ∈ N \mathbb{Q} \in N Q ∈ N is definable there and nontrivial, and the defining ground assertion in S ∗ S^* S ∗ supplies V = N [ g ] V = N[g] V = N [ g ] . These give the first and third clauses. The forced form of Lemma 52 and preservation of the index identify the recovered ground with the original universe. In particular, in a designated extension we have ( M G κ ) N [ h ] = N (M\mathbb{G}_{\kappa})^{N[h]} = N ( M G κ ) N [ h ] = N . This gives the fourth clause.
For the second clause, argue internally in N N N . The preceding preservation arguments force the non-induction axioms of R R R , and the minimal-name argument forces each induction instance. Since the recovered ground is the original universe, each axiom of R R R also holds when relativized to that ground. The canonical generic name supplies the assertion that the extension is obtained from it by Q \mathbb{Q} Q . Thus N ⊨ 1 Q ⊩ S ∗ N \models1_{\mathbb{Q}} \Vdash S^* N ⊨ 1 Q ⊩ S ∗ , instance by instance.
Finally, fix a common standard complexity bound j j j for the non-induction axioms and the fixed recovery and stability assertions, after expanding the definitions. Choose k ≥ b ( j ) k \ge b(j) k ≥ b ( j ) , enlarged for the product-forcing argument in Theorem 31. Lemma 18 transfers these assertions to the designated definable generics. Their Full Set Induction comes from Lemma 19; it is not being transferred at a single finite complexity bound. We have therefore verified all four clauses of the stable definable ground property. Theorem 31 applies to S ∗ S^* S ∗ , and its distinct bi-interpretable extensions, being extensions of S S S , also witness that S S S is not tight. □
Remark. Note that the tautology case already follows from Theorem 27 and the set-forcing preservation recalled at the beginning of Section 5.
The preceding proposition concerned restrictions on the Separation and Collection schemes. We now consider the consequences of a theory at a fixed quantifier complexity. This is a different restriction since proofs of sentences of low complexity may use axioms of arbitrarily high complexity.37 The following argument extends Enayat’s observation about the bounded consequences of Z F ZF Z F and Z F C ZFC Z F C to stronger theories, including theories incompatible with V = L V = L V = L .
We use the forcings G κ \mathbb{G}_{\kappa} G κ and the assertions κ < κ = κ \kappa^{<\kappa} = \kappa κ < κ = κ from Section 5. In the proposition, preservation of T T T means that T ⊢ 1 G κ ⊩ ψ T \vdash1_{\mathbb{G}_{\kappa}} \Vdash\psi T ⊢ 1 G κ ⊩ ψ for every axiom ψ \psi ψ of T T T , and hence for every theorem of T T T .
Proposition 55. Let κ \kappa κ be ω \omega ω or ω 2 \omega_2 ω 2 , and let T T T be a consistent extension of Z F C + { κ < κ = κ } ZFC + \{\kappa^{<\kappa} = \kappa\} Z F C + { κ < κ = κ } which is preserved by G κ \mathbb{G}_{\kappa} G κ . If U U U is a quantifier bounded collection of theorems of T T T , then K P + U KP + U K P + U is not tight. Indeed, its distinct bi-interpretable extensions may be chosen to extend Z F C Π 3 + U ZFC\Pi_3 + U Z F C Π 3 + U .
Only the chosen consequences and their forcing translations need a common complexity bound; the theory T T T itself need not have one. We shall use T T T to witness the consistency of a suitable theory of grounds, apply the Definable Countable Enumeration Lemma there, and then invoke our tightness failure template.
Proof. Let
R = Z F C Π 3 + { κ < κ = κ } + { 1 G κ ⊩ φ : φ ∈ U } . R = ZFC^{\Pi_3} + \{\kappa^{<\kappa} = \kappa\} + \{1_{G_\kappa} \Vdash\varphi: \varphi\in U\}. R = Z F C Π 3 + { κ < κ = κ } + { 1 G κ ⊩ φ : φ ∈ U } .
Every axiom of R R R is a theorem of T T T , so R R R is consistent. By Lemma 7, the forcing translations of the sentences in U U U have a common finite complexity bound. After expanding the fixed definitions, R R R is therefore K P C KPC K P C plus a quantifier bounded set of sentences. Full Set Induction is already included in K P C KPC K P C .
Write N = M G κ \mathrm{N}=M_{G_\kappa} N = M G κ for the ground defined in Lemma 52. Let S S S consist of Z F C Π 3 + U ZFC^{\Pi_3}+U Z F C Π 3 + U , the assertion that N \mathrm{N} N is a G κ N G^{\mathrm{N}}_\kappa G κ N -ground of the universe, and the relativizations to N \mathrm{N} N of the non-induction axioms of R R R . The ground inherits Full Set Induction from the ambient universe, so S S S proves that N \mathrm{N} N satisfies all of R R R . Relativization to this fixed definition retains a common complexity bound; thus S S S is also K P C KPC K P C plus a quantifier bounded set of sentences.
To see that S S S is consistent, apply Lemma 30 to obtain a model W W W of R R R with a definable countable enumeration. Use that enumeration to define a G κ W G^W_\kappa G κ W -generic filter at a finite level sufficient for U U U , the non-induction axioms of Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 , and the fixed ground-recovery assertions. The forcing assertions in R R R and Lemma 18 give U U U in the extension. The preservation results of Section 5 give the non-induction axioms of Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 , and Lemma 19 gives Full Set Induction. Lemma 52 recovers W W W as the designated ground. The extension therefore satisfies S S S .
Finally, S S S has the stable definable ground property. Its ground N \mathrm{N} N satisfies R R R , and hence forces every member of U U U . The forcing preserves Z F C Π 3 ZFC^{\Pi_3} Z F C Π 3 and recovers the original universe as its designated ground, which still satisfies R R R . The canonical generic name supplies the assertion that the extension is obtained by the designated forcing. Thus N \mathrm{N} N forces every axiom of S S S , including each induction instance, as in the proof of Proposition 54. Nontriviality and stability are supplied by the same forcing and recovery results. Theorem 31 now makes S S S non-tight. Since S S S extends Z F C Π 3 + U ZFC^{\Pi_3}+U Z F C Π 3 + U , its two distinct bi-interpretable extensions also witness the required conclusion. □
For a syntactic class Γ \Gamma Γ , write
T Γ = { φ ∈ Γ : T ⊢ φ } . T_\Gamma= \{\varphi\in\Gamma: T \vdash\varphi\}. T Γ = { φ ∈ Γ : T ⊢ φ } .
The subscript thus denotes consequences of T T T , while the superscript in Z F C Π n ZFC^{\Pi_n} Z F C Π n restricts axiom schemes.
Corollary 56. Let Φ \Phi Φ be a tautology or one of the following assertions: there is a measurable cardinal; there is a supercompact cardinal; I 3 I3 I 3 ; there is a proper class of extendible cardinals; P F A PFA P F A ; or M M MM M M . Suppose Z F C + Φ ZFC+\Phi Z F C + Φ is consistent. Then, for every standard n ∈ ω n \in\omega n ∈ ω , the theories
K P + ( Z F C + Φ ) Σ n and K P + ( Z F C + Φ ) Π n KP + (ZFC+\Phi)_{\Sigma_n}
\qquad\text{and}\qquad
KP + (ZFC+\Phi)_{\Pi_n} K P + ( Z F C + Φ ) Σ n and K P + ( Z F C + Φ ) Π n are neither tight nor solid. The same holds with B Σ n B\Sigma_n B Σ n in place of Σ n \Sigma_n Σ n or Π n \Pi_n Π n , and with Full Set Induction in place of K P KP K P .
Proof. For the tautology and the large-cardinal cases, take κ = ω \kappa=\omega κ = ω and T = Z F C + Φ T=ZFC+\Phi T = Z F C + Φ . The preservation arguments of Proposition 54 apply. For P F A PFA P F A and M M MM M M , take κ = ω 2 \kappa=\omega_2 κ = ω 2 and T = Z F C + Φ + { ω 2 < ω 2 = ω 2 } T=ZFC+\Phi+\{\omega_2^{<\omega_2}=\omega_2\} T = Z F C + Φ + { ω 2 < ω 2 = ω 2 } . The preliminary closed forcing used there shows that T T T is consistent, and G ω 2 \mathbb{G}_{\omega_2} G ω 2 preserves it. In each case the chosen consequences of Z F C + Φ ZFC+\Phi Z F C + Φ are a quantifier bounded collection of theorems of T T T . Apply
Proposition 55. Non-tightness passes to subtheories, giving the Full Set Induction versions, and solidity implies tightness.
In particular, if Z F ZF Z F is consistent, the result applies to the Σ n \Sigma_n Σ n -, Π n \Pi_n Π n - and B Σ n B\Sigma_n B Σ n -consequences of either Z F ZF Z F or Z F C ZFC Z F C , together with Full Set Induction. Here we use the equiconsistency of Z F ZF Z F and Z F C ZFC Z F C and the inclusion of the Z F ZF Z F -theorems among the Z F C ZFC Z F C -theorems. This case can also be obtained using the constructible-enumeration argument of Section 2. The general enumeration lemma supplies the stronger applications above.
The inexpressibility of V = H O D V=HOD V = H O D in quantifier bounded set theories
In the face of the Definable Countable Enumeration Lemma, a natural worry emerges. What if we added the axiom V ≠ H O D V\ne HOD V = H O D to one of our suitable bounded theories? Then the obvious thing to think is that models of such a theory cannot have a definable well-ordering, let alone a definable countable enumeration. The problem is that the sentence we use to express that the universe is hereditarily ordinal definable over Z F ZF Z F doesn’t do the same job over theories with less Separation and Collection.
To avoid confusion, let us write χ H O D \chi_{\mathrm{HOD}} χ HOD to denote the usual first-order sentence of L ∈ \mathcal{L}_{\in} L ∈ which expresses that every set is definable in some V α V_\alpha V α by a formula of set theory only using ordinal parameters. Thus, χ H O D \chi_{\mathrm{HOD}} χ HOD is the sentence we use to express V = H O D V=HOD V = H O D in Z F ZF Z F and its extensions. In the context of Z F ZF Z F , χ H O D \chi_{\mathrm{HOD}} χ HOD is equivalent to saying that there is a definable well-ordering of the universe. But over the weak set theories, we’ve been considering, χ H O D \chi_{\mathrm{HOD}} χ HOD merely implies this: the converse does not hold. In particular, the Definable Countable Enumeration Lemma implies the following.
Proposition 57. Let T = K P C + S T=KP\mathord{\mathrm C}+S T = K P C + S , where S S S is quantifier bounded. If T + ¬ χ H O D T+\neg\chi_{\mathrm{HOD}} T + ¬ χ HOD is consistent, then it has a model M \mathcal{M} M admitting a definable well-ordering.
Proof. The set of additional axioms S ∪ { ¬ χ H O D } S\cup\{\neg\chi_{\mathrm{HOD}}\} S ∪ { ¬ χ HOD } is quantifier bounded, since χ H O D \chi_{\mathrm{HOD}} χ HOD is a single fixed first-order sentence. We then apply the Definable Countable Enumeration Lemma (Lemma 30) to K P C + S + ¬ χ H O D KP\mathord{\mathrm C}+S+\neg\chi_{\mathrm{HOD}} K P C + S + ¬ χ HOD to obtain a model M \mathcal{M} M of T + ¬ χ H O D T+\neg\chi_{\mathrm{HOD}} T + ¬ χ HOD along with a parameter-free formula defining a class surjection f : ω M ↠ M f:\omega^\mathcal{M}\twoheadrightarrow\mathcal{M} f : ω M ↠ M . We can then well-order M \mathcal{M} M by letting x ≺ y x\prec y x ≺ y iff, in M \mathcal{M} M , the least n ∈ ω n\in\omega n ∈ ω such that f ( n ) = x f(n)=x f ( n ) = x is such that n < m n<m n < m where m ∈ ω m\in\omega m ∈ ω is the least such that f ( m ) = y f(m)=y f ( m ) = y .
Thus, we see there are models of such theories where χ H O D \chi_{\mathrm{HOD}} χ HOD is false and yet we still have a definable well-ordering of the universe. In a nutshell, without Full Reflection, the falsity of χ H O D \chi_{\mathrm{HOD}} χ HOD is not enough to block the existence of a complex definable well-ordering.
Solidity and the ground axiom
For the final section of the paper, we return to solidity and observe that the sensible thing is true: solid theories cannot describe generic extensions.
Over a weak theory, however, we must say how generic the extension is. An ordinary generic need not give the truth lemma for every sentence in U U U . Since U U U is quantifier bounded, only a fixed finite level of genericity is needed. We incorporate that requirement into the ground axiom.
Let M O S T I n d = K P C + Powerset + Σ 1 -Separation MOST_{\mathrm{Ind}}=KP\mathord{\mathrm C}+\text{Powerset}+\Sigma_1\text{-Separation} M O S T Ind = K P C + Powerset + Σ 1 -Separation , as in Section 5, and let W t W_t W t be Farmer’s uniformly defined family of M O S T MOST M O S T -grounds. For each fixed standard n ≥ 1 n\ge1 n ≥ 1 , define ¬ G A n \neg GA_n ¬ G A n to say that there are t , P ∈ W t t, \mathbb{P} \in W_t t , P ∈ W t and a filter G ⊆ P G \subseteq\mathbb{P} G ⊆ P such that
W t ⊊ V , V = W t [ G ] , G is B Σ b ( n ) -generic over W t . W_t \subsetneq V,\qquad V = W_t[G],\qquad G\text{ is }B\Sigma_{b(n)}\text{-generic over }W_t. W t ⊊ V , V = W t [ G ] , G is B Σ b ( n ) -generic over W t .
Thus we retain the existing ground clause and strengthen its genericity requirement. The same P \mathbb{P} P and G G G must witness both the extension and the additional genericity.
This is a first-order sentence. For fixed n n n , use the partial satisfaction predicate from Section 2, relativized to W t W_t W t , to quantify over formula codes and finite tuples of ground parameters. The additional clause says that G G G meets each dense subclass of P \mathbb{P} P so defined. We do not add Full Set Induction to the ground clause: in a model of M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind , every definable transitive class inherits Full Set Induction by relativization. In particular, each M O S T MOST M O S T -ground occurring here satisfies M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind .
Theorem 58. Suppose T = M O S T I n d + U T = MOST_{\mathrm{Ind}} + U T = M O S T Ind + U , where U ⊆ B Σ n U \subseteq B\Sigma_n U ⊆ B Σ n for some standard n ≥ 1 n \ge1 n ≥ 1 . If T T T is solid, then
T ⊢ G A n . T \vdash GA_n. T ⊢ G A n .
We prove the theorem contrapositively. A model of T + ¬ G A n T + \neg GA_n T + ¬ G A n gives a ground in which each finite part of U U U can be forced. Compactness and definable countable enumeration then give a ground over which two canonical generic extensions can be defined. Both extensions satisfy T T T and can interpret one another. The first defines an isomorphism with the round-trip interpretation of itself, but cannot define an isomorphism to the intervening extension. This is the failure of solidity we need.
We shall use the following three results: the set-forcing preliminaries in Section 2, together with Farmer’s preservation lemma [Schlutzenberg, 2022, Lemma 2.5], give the required forcing and preservation results over M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind ; a proper ground is uniformly definable from Farmer’s parameter, as in Theorem 47; and the Definable Countable Enumeration Lemma (Lemma 30) applies to any consistent theory consisting of K P C KP C K P C and a quantifier bounded set of additional sentences, including a fixed finite expansion by constants. Solidity allows parameters, so the small-parameter coding of Section 5 is not needed here.
Fix T T T , U U U and n n n as in the theorem. We first obtain a consistent theory of grounds. Call a forcing atomless if below every condition there are two incompatible conditions. This will ensure that the generic extensions used later are proper.
Lemma 59. Suppose T + ¬ G A n T + \neg GA_n T + ¬ G A n is consistent. In the language obtained by adding a constant P ˙ \dot{\mathbb{P}} P ˙ , let Γ U \Gamma_U Γ U consist of M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind , the assertion that P ˙ \dot{\mathbb{P}} P ˙ is an atomless forcing notion with a greatest condition, and, for each φ ∈ U \varphi\in U φ ∈ U , the sentence 1 P ˙ ⊩ φ 1_{\dot{\mathbb{P}}} \Vdash\varphi 1 P ˙ ⊩ φ . Then Γ U \Gamma_U Γ U is consistent.
Proof. Fix a model V ⊨ T + ¬ G A n V \models T + \neg GA_n V ⊨ T + ¬ G A n and write V = W [ G ] V = W[G] V = W [ G ] , where W = W t W = W_t W = W t is a proper M O S T MOST M O S T -ground and G ⊆ P ∈ W G \subseteq\mathbb{P} \in W G ⊆ P ∈ W is B Σ b ( n ) B\Sigma_{b(n)} B Σ b ( n ) -generic over W W W . As observed above, W ⊨ M O S T I n d W \models MOST_{\mathrm{Ind}} W ⊨ M O S T Ind . It is enough to satisfy a finite fragment of Γ U \Gamma_U Γ U . Let F ⊆ U F \subseteq U F ⊆ U be finite. Since ⋀ F \bigwedge F ⋀ F is B Σ n B\Sigma_n B Σ n and W [ G ] ⊨ ⋀ F W[G] \models\bigwedge F W [ G ] ⊨ ⋀ F , the truth lemma for arbitrary models (Lemma 18) gives some p ∈ G p \in G p ∈ G such that p ⊩ W ⋀ F p \Vdash_W \bigwedge F p ⊩ W ⋀ F .
Call a ∈ P a \in\mathbb{P} a ∈ P an atom if every two conditions below a a a are compatible. In W W W let
D = { a ∈ P : a is an atom } ∪ { q ∈ P : no atom lies below q } . D = \{a \in\mathbb{P}: a\text{ is an atom}\}\cup\{q \in\mathbb{P}: \text{ no atom lies below }q\}. D = { a ∈ P : a is an atom } ∪ { q ∈ P : no atom lies below q } .
This set is dense in P \mathbb{P} P . Since the extension W [ G ] W[G] W [ G ] is proper, G G G contains no atom: a generic containing an atom is determined by that atom and hence belongs to W W W . Choose d ∈ G ∩ D d \in G \cap D d ∈ G ∩ D . Then no atom lies below d d d . Since p , d ∈ G p,d \in G p , d ∈ G , choose q ∈ G q \in G q ∈ G with q ≤ p , d q \leq p,d q ≤ p , d . No atom lies below q q q , so the cone Q = P ↾ q \mathbb{Q}=\mathbb{P}\mathbin{\upharpoonright}q Q = P ↾ q is atomless, with greatest condition q q q . Moreover, q ≤ p q \leq p q ≤ p , and hence
1 Q ⊩ W ⋀ F . 1_{\mathbb{Q}}\Vdash_W\bigwedge F. 1 Q ⊩ W ⋀ F .
Thus W W W expanded by Q \mathbb{Q} Q satisfies the chosen finite fragment. Compactness gives the result. □ \square □
Since U ⊆ B Σ n U \subseteq B\Sigma_n U ⊆ B Σ n , the uniform forcing-bound lemma (Lemma 7) gives a common Δ b ( n ) \Delta_{b(n)} Δ b ( n ) bound for the sentences 1 P ⊩ φ 1_{\mathbb{P}}\Vdash\varphi 1 P ⊩ φ , where φ ∈ U \varphi\in U φ ∈ U . The additional axioms in M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind and the assertion that P \mathbb{P} P is atomless also have fixed finite complexity. Hence Γ U \Gamma_U Γ U is K P C KPC K P C plus a quantifier bounded set of sentences in the expanded language, and the Definable Countable Enumeration Lemma (Lemma 30 ) applies to it.
For the next lemma, fix a model N N N of M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind carrying a definable class surjection e : ω ↠ N e:\omega\twoheadrightarrow N e : ω ↠ N , and let P ∈ N \mathbb{P}\in N P ∈ N be atomless. Let m = b ( n ) = 2 n + 3 m=b(n)=2n+3 m = b ( n ) = 2 n + 3 , and let ⟨ G 0 , G 1 ⟩ \langle G_0,G_1\rangle ⟨ G 0 , G 1 ⟩ be the canonical B Σ m B\Sigma_m B Σ m -generic pair for P × P \mathbb{P}\times\mathbb{P} P × P over N N N obtained from e e e by the least-extension construction. Write
W = N [ G 0 × G 1 ] . W=N[G_0\times G_1]. W = N [ G 0 × G 1 ] .
We want each coordinate to recover the same ground and enumeration, and hence the same canonical pair. The common product extension will then let us compare the two coordinates by Set Induction.
The construction is the one from § 2 , with least e e e -index in place of the constructible well-order. Enumerate formula-parameter pairs using e e e and, at each stage, take the extension with least e e e -index meeting the current requirement, if there is one. Full Set Induction gives every internally finite initial history. Thus the resulting filters are definable classes of N N N ; they need not be sets of N N N . The fixed formula defining e e e , its parameters, P \mathbb{P} P and m m m determine the construction.
Farmer’s preservation lemma gives M O S T MOST M O S T in both coordinate extensions and in W W W . For its application, use Choice to take fixed isomorphic copies of the forcing notions on ordinals. Since the filters are definable over N N N and m ≥ 1 m\geq1 m ≥ 1 , Lemma 19 gives Full Set Induction in all three extensions. They therefore satisfy M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind .
We also need each coordinate to be generic over the other for dense sets. Suppose D ˙ ∈ N \dot{D}\in N D ˙ ∈ N names a dense subset of P \mathbb{P} P in N [ G 0 ] N[G_0] N [ G 0 ] . By the bounded case of Lemma 18, some p ∈ G 0 p\in G_0 p ∈ G 0 forces that D ˙ \dot{D} D ˙ is dense. Below ⟨ p , 1 ⟩ \langle p,1\rangle ⟨ p , 1 ⟩ , the class
E = { ⟨ r , s ⟩ ∈ P × P : r ≤ p and r ⊩ s ˇ ∈ D ˙ } E=\{\langle r,s\rangle\in\mathbb{P}\times\mathbb{P}:r\leq p\text{ and }r\Vdash\check{s}\in\dot{D}\} E = {⟨ r , s ⟩ ∈ P × P : r ≤ p and r ⊩ s ˇ ∈ D ˙ }
is dense: given a second-coordinate condition, density of D ˙ \dot{D} D ˙ lets us strengthen the first coordinate to force some ground condition below it into D ˙ \dot{D} D ˙ . Atomic forcing and Σ 1 \Sigma_1 Σ 1 -Separation make E E E a set of N N N . Adjoin the conditions incompatible with ⟨ p , 1 ⟩ \langle p,1\rangle ⟨ p , 1 ⟩ to obtain a globally dense set. The product generic meets it below ⟨ p , 1 ⟩ \langle p,1\rangle ⟨ p , 1 ⟩ , so G 1 G_1 G 1 meets D D D . The other direction is symmetric.
Choose a cardinal η \eta η in N N N large enough that the fixed ordinal copies of P \mathbb{P} P and P × P \mathbb{P}\times\mathbb{P} P × P belong to
t = ( H η + ) N . t=(H_{\eta+})^N. t = ( H η + ) N .
Farmer’s ground definition recovers N N N from this same t t t in both coordinates and in W W W . Relativizing the enumeration formula to the recovered ground recovers the same e e e . We allow t t t , the forcing notions, the fixed isomorphisms and any parameters of e e e in the interpretations below. All are ground objects. By the canonical interpretation of the other coordinate, we mean the quotient of N N N -names by its recovered generic, with equality and membership defined by forcing.
Lemma 60. No isomorphism from N [ G 0 ] N[G_0] N [ G 0 ] to its canonical interpretation of N [ G 1 ] N[G_1] N [ G 1 ] is parametrically definable over N [ G 0 ] N[G_0] N [ G 0 ] .
Proof. Work in W = N [ G 0 × G 1 ] W=N[G_0 \times G_1] W = N [ G 0 × G 1 ] . The common ground N N N is definable in W W W from the parameter t t t . Valuation of N N N -names using G 0 G_0 G 0 and G 1 G_1 G 1 therefore defines the two transitive coordinate classes in W W W . If the first coordinate defined an isomorphism to its canonical interpretation of the second, relativizing that definition to the first coordinate and applying valuation in W W W would give a parametrically definable isomorphism h : N [ G 0 ] ⟶ N [ G 1 ] h:N[G_0]\longrightarrow N[G_1] h : N [ G 0 ] ⟶ N [ G 1 ] in W W W .
Full Set Induction in W W W shows that h ( x ) = x h(x)=x h ( x ) = x for every x ∈ N [ G 0 ] x \in N[G_0] x ∈ N [ G 0 ] . Indeed, suppose all members of x x x are fixed. Membership preservation gives x ⊆ h ( x ) x \subseteq h(x) x ⊆ h ( x ) ; conversely, transitivity of the range and surjectivity of h h h show that every member of h ( x ) h(x) h ( x ) is h ( y ) h(y) h ( y ) for some y ∈ x y \in x y ∈ x , and hence belongs to x x x . Extensionality gives h ( x ) = x h(x)=x h ( x ) = x . The two coordinate classes would consequently be equal.
But G 1 ∉ N [ G 0 ] G_1 \notin N[G_0] G 1 ∈ / N [ G 0 ] : otherwise P ∖ G 1 \mathbb{P} \setminus G_1 P ∖ G 1 would, by atomlessness and bounded Separation, be a dense set in N [ G 0 ] N[G_0] N [ G 0 ] disjoint from G 1 G_1 G 1 , contrary to the mutual genericity just proved. This is a contradiction. □
We can now finish the argument. The common ground and canonical pair give the interpretations in both directions; valuation of names identifies the round trip with the original model.
Proof. We now prove Theorem 58 contrapositively. Assume T + ¬ G A n T+\neg\mathrm{GA}_n T + ¬ GA n is consistent. By Lemma 59 and the Definable Countable Enumeration Lemma (Lemma 30 ), fix a model N ⊨ Γ U N \models\Gamma_U N ⊨ Γ U carrying a definable class surjection e : ω ↠ N e:\omega\twoheadrightarrow N e : ω ↠ N . Let P \mathbb{P} P denote the distinguished atomless forcing notion of N N N .
Apply the preceding construction to P × P \mathbb{P} \times\mathbb{P} P × P at the B Σ b ( n ) \mathrm{B}\Sigma_{b(n)} B Σ b ( n ) level, and let
M 0 = N [ G 0 ] and N = N [ G 1 ] . \mathcal{M}_0=N[G_0]\qquad\text{and}\qquad\mathcal{N}=N[G_1]. M 0 = N [ G 0 ] and N = N [ G 1 ] .
Both coordinates satisfy M O S T I n d MOST_{\mathrm{Ind}} M O S T Ind , as verified above. Moreover, 1 P ⊩ φ 1_{\mathbb{P}}\Vdash\varphi 1 P ⊩ φ for every φ ∈ U \varphi\in U φ ∈ U , and each projection is B Σ b ( n ) \mathrm{B}\Sigma_{b(n)} B Σ b ( n ) -generic over N N N . The truth lemma for arbitrary models (Lemma 18 ) therefore transfers every sentence of U U U to both coordinate extensions. Thus M 0 , N ⊨ T \mathcal{M}_0,\mathcal{N}\models T M 0 , N ⊨ T . We do not require the product extension W W W to satisfy U U U .
Choose the common ground parameter t t t as above. Thus, using t t t and P \mathbb{P} P , together with the other fixed ground parameters, M 0 \mathcal{M}_0 M 0 recovers N N N , its definable enumeration e e e and the canonical pair ⟨ G 0 , G 1 ⟩ \langle G_0,G_1\rangle ⟨ G 0 , G 1 ⟩ . Equality and membership in the interpreted extension are defined by forcing on ground names. Hence it interprets N \mathcal{N} N . Symmetrically, N \mathcal{N} N interprets a copy M 1 \mathcal{M}_1 M 1 of the first coordinate extension.
The round trip reconstructs the same canonical first coordinate, so the usual valuation map on N N N -names gives a parametrically definable isomorphism
M 0 ≅ M 1 . (4) \mathcal{M}_0\cong\mathcal{M}_1. \tag*{(4)} M 0 ≅ M 1 . (4)
Inside M 0 \mathcal{M}_0 M 0 , the filter G 0 G_0 G 0 is a set and valuation of ground names is definable. Every object is the value of such a name, and equality modulo G 0 G_0 G 0 makes the valuation independent of the representative. We therefore have M 0 ▹ p a r N ▹ p a r M 1 \mathcal{M}_0 \mathrel{\triangleright_{\mathrm{par}}} \mathcal{N} \mathrel{\triangleright_{\mathrm{par}}} \mathcal{M}_1 M 0 ▹ par N ▹ par M 1 and a parametrically definable isomorphism M 0 ≅ M 1 \mathcal{M}_0 \cong\mathcal{M}_1 M 0 ≅ M 1 . By Lemma 60 , there is no parametrically definable isomorphism from M 0 \mathcal{M}_0 M 0 to this interpretation of N \mathcal{N} N . Thus T T T is not solid.
Hence Con ( T + ¬ G A n ) \operatorname{Con}(T + \neg\mathrm{GA}_n) Con ( T + ¬ GA n ) implies that T T T is not solid. If T T T is solid, T + ¬ G A n T + \neg\mathrm{GA}_n T + ¬ GA n is therefore inconsistent, and so T ⊢ G A n T \vdash\mathrm{GA}_n T ⊢ GA n . □
Every quantifier bounded U U U is contained in B Σ n B\Sigma_n B Σ n for some standard n ≥ 1 n \ge1 n ≥ 1 , so the theorem applies to every theory of the stated form. If r ≥ n r \ge n r ≥ n , then G A n \mathrm{GA}_n GA n implies G A r \mathrm{GA}_r GA r : stronger genericity gives fewer possible witnesses to failure of the ground axiom. The same argument also yields the ordinary Ground Axiom over full Z F C \mathrm{ZFC} ZFC .
Corollary 61. Suppose U U U is quantifier bounded. If M O S T I n d + U \mathrm{MOST}_{\mathrm{Ind}} + U MOST Ind + U is solid, then
Z F C + U ⊢ G A , \mathrm{ZFC} + U \vdash\mathrm{GA}, ZFC + U ⊢ GA , where G A \mathrm{GA} GA is the usual Ground Axiom for Z F C \mathrm{ZFC} ZFC -grounds.
Proof. Choose a standard n ≥ 1 n \ge1 n ≥ 1 with U ⊆ B Σ n U \subseteq B\Sigma_n U ⊆ B Σ n . By Theorem 58 , M O S T I n d + U ⊢ G A n \mathrm{MOST}_{\mathrm{Ind}} + U \vdash\mathrm{GA}_n MOST Ind + U ⊢ GA n . But an ordinary generic over a Z F C \mathrm{ZFC} ZFC -ground meets every definable dense subclass of its forcing, since Separation makes each such class a set. Thus a proper Z F C \mathrm{ZFC} ZFC -ground witnessing ¬ G A \neg\mathrm{GA} ¬ GA would also witness ¬ G A n \neg\mathrm{GA}_n ¬ GA n . □
AI assistance. The main ideas of this paper were developed by the authors before any use of AI. We subsequently used OpenAI’s Sol and Astra to assist with the mathematical development and preparation of this paper, including drafting proofs, identifying errors and suggesting repairs, locating references, and revising the exposition. Their contributions were most significant in the ground model definability, coding forcing, and Ground Axiom arguments.