Models of ZFC with one or zero extensions to a model of GBC

by kamerynwilliams

This is more or less notes from a talk I gave in the CUNY Graduate Center’s set theory seminar on March 13, 2015.

Some motivation

I wish to consider the question of how many different class structures can be put on models of {\mathsf{ZFC}} to get a model of second-order set theory. I will focus here on {\mathsf{GBC}} as my second-order set theory.

{\mathsf{GBC}} includes {\mathsf{ZFC}} for the first-order part with the following extra axioms/axiom schema for classes:

  • Extensionality;
  • Replacement for class functions—if {F} is a class function then for any set {x}, {F''x} is a set;
  • {\Delta^0_\infty}-comprehension schema—if {\phi(x,\bar y)} is a formula with only set quantifiers (but possibly class parameters), then for all {\bar y}, {\{ x : \phi(x, \bar y) \}} is a class; and
  • Global choice—there is a class which is a global well-order. Equivalently, there is a class function {\mathrm{Ord} \rightarrow V}.

In general, models of {\mathsf{GBC}} look like {(M,S,\epsilon,\eta)} where {\epsilon \subseteq M^2} and {\eta \subseteq M \times S} are the elementhood relations. However, the extensionality axiom for classes implies that every model of {\mathsf{GBC}} is isomorphic to a model {(M,\mathfrak{X},\epsilon,\in)}, where {\mathfrak{X} \subseteq \mathcal{P}(M)}. Of course, {M} doesn’t have to be transitive, so {\epsilon} may fail to be the true elementhood relation. Nevertheless, for the sake of readability, my convention will be to use the symbol {\in} for the elementhood relation for models of set theory, even if {\in^M} isn’t the true elementhood relation. As such, models of {\mathsf{GBC}} can be shortly written as {(M,\mathfrak{X})}.

The following theorem implies that {\mathsf{GBC}} is conservative over {\mathsf{ZFC}} for first-order formulae; if {\mathsf{GBC}} proves some sentence with only set variables, then {\mathsf{ZFC}} proves it.

Theorem 1 (Solovay) If {M \models \mathsf{ZFC}} is countable, then there is countable {\mathfrak{X} \subseteq \mathcal{P}(M)} so that {(M,\mathfrak{X}) \models \mathsf{GBC}}. Indeed, {\mathfrak{X} = \mathord{\mathrm{Def}}(M,G)}, all classes definable from some global well-order of {M}.

Solovay’s theorem is proved by finding {G} so that {(M,G) \models \mathsf{ZFC}(G)}, i.e. the theory where a predicate symbol for {G} is allowed in the formulae for the axiom schemata. Any global well-order added by forcing will satisfy this. One way to force this is to force with the poset consisting of set well-orders in {M}, ordered by extension.

To fix some terminalogy, if {M \models \mathsf{ZFC}} and {(M,\mathfrak{X}) \models \mathsf{GBC}}, we call {\mathfrak{X}} a {\mathsf{GBC}}realization of {M}. If a {\mathsf{GBC}}-realization of {M} exists, we say {M} is {\mathsf{GBC}}-realizable. Under this terminology, Solovay’s theorem says that every countable model of {\mathsf{ZFC}} is {\mathsf{GBC}}-realizable.

If {M} has a definable global well-order, then we don’t need to do any work to find a {\mathsf{GBC}}-realization of {M}; {(M,\mathord{\mathrm{Def}}(M)) \models \mathsf{GBC}} in this case. This holds even if {M} is uncountable.

Remark 1 If {M \models \mathsf{ZFC}} is countable, then {M} has infinitely many {\mathsf{GBC}}-realizations.

Proof: Let {(M,\mathord{\mathrm{Def}}(M,G)) \models \mathsf{GBC}} where {G \not \in \mathord{\mathrm{Def}}(M)}. The key fact used is that Solovay’s argument goes through for {(M,\mathord{\mathrm{Def}}(M,G))}, giving us a global well-order {H} which is {(M,\mathord{\mathrm{Def}}(M,G))}-generic. Obviously, {H \not \in \mathord{\mathrm{Def}}(M,G)}. I claim that as well {G \not \in \mathord{\mathrm{Def}}(M,H)}. Otherwise, {(M,G,H)} defines {G} by some formula {\phi(x,H)} which doesn’t mention {G}. Thus, {(M,\mathord{\mathrm{Def}}(M,G,H)) \models \forall x\ x \in G \iff \phi(x,H)}. This happens iff it is forced by some condition {p}, i.e. {(M,\mathord{\mathrm{Def}}(M,G)) \models [p \Vdash \forall x\ x \in G \iff \phi(x,\dot H)]}. But then for all {x \in M}, {x \in G} iff {(M,\mathord{\mathrm{Def}}(M,G)) \models [p \Vdash \phi(\check x, \dot H)]}. But {p \Vdash \phi(\check x, \dot H)} is a formla which doesn’t mention {G}, so this is true in {M}, getting that {x \in G} iff {M \models [p \Vdash \phi(\check x,\dot H)]}. That is, {G} is definable in {M}, contradicting our assumption that {G} was definable in {(M,H)}.

By iterating this argument, we get infinitely many {\mathsf{GBC}}-realizations for {M}. \Box

It’s not terribly difficult to tweak this argument to get that {M} has continuum many {\mathsf{GBC}}-realizations. This gives us models of {\mathsf{ZFC}} with as many {\mathsf{GBC}}-realizations as possible. The remainder of this blog post will be devoted to constructing the opposite, models of {\mathsf{ZFC}} with few {\mathsf{GBC}}-realizations. In particular, we will see that there are models with a unique {\mathsf{GBC}}-realization and models with no {\mathsf{GBC}}-realization.

{\omega_1}-like models

Necessarily, such models must be uncountable. A natural first place to look as at {\omega_1}-like models, in some sense the smallest uncountable models. To spoil any suprise, this turns out to be the right place to look.

Definition 2 {M \models \mathsf{ZFC}} is {\omega_1}like if {\lvert M \rvert = \omega_1} and for all {a \in M}, {\{b \in M : M \models b \in a\}} is at most countable. Equivalently, we could require that this holds just for {V_\alpha}s or that it holds just for ordinals.

We can build {\omega_1}-like models of set theory by growing them up from countable models of set theory. If, when we extend, we only add new sets “on top”, then after {\omega_1} many extensions, we will have an {\omega_1}-like model.

Definition 3 {M \models \mathsf{ZFC}}. {N} is a top extension of {M}, written {M \subseteq_{\mathsf{top}} N} if for all {b \in N \setminus M} and {a \in M}, {N \models \mathrm{rk}(b) > \mathrm{rk}(a)}. We will be concerned just with elementary top extensions, written {M \prec_{\mathsf{top}} N}.

Lemma 4 If {\langle M_\alpha : \alpha < \omega_1 \rangle} is an elementary chain of top extensions of countable models, then {M = \bigcup_{\alpha < \omega_1} M_\alpha} is {\omega_1}-like.

Proof: Obviously {\lvert M \rvert = \omega_1}. We have only to check that each element in {M} only at most countably many predecessors. Fix {a \in M}. Then, {a \in M_\alpha} for some {\alpha}. As {M_\alpha \prec_{\mathsf{top}} M}, {\{ b \in M : M \models b \in a \} = \{ b \in M_\alpha : M_\alpha \models b \in a \}}, which is countable. \Box

One method of constructing elementary top extensions goes through Skolem ultrapowers. Starting with a model of {\mathsf{GBC}}, we want to have the class functions on the ordinals of the model represent points in the extension, where we mod out by an ultrafilter on the classes of ordinals.

Let’s fix some notation: {(M,\mathfrak{X}) \models \mathsf{GBC}}. Set {\mathcal{F}_\mathfrak{X} = \{ f \in \mathfrak{X} : f \text{ is a function } \mathrm{Ord}^M \rightarrow M \}} and {\mathcal{B}_\mathfrak{X} = \mathfrak{X} \cap \mathcal{P}(\mathrm{Ord}^M)}. If {\mathcal{U}} is an ultrafilter on the boolean algebra {\mathcal{B}_\mathfrak{X}} and {f,g \in \mathcal{F}_\mathfrak{X}}, say that {f \sim_\mathcal{U} g} if {\{ \alpha \in \mathrm{Ord}^M : f(\alpha) = g(\alpha) \} \in \mathcal{U}} and {f \in_\mathcal{U} g} if {\{ \alpha \in \mathrm{Ord}^M : f(\alpha) \in g(\alpha) \} \in \mathcal{U}}. Let {N = \mathrm{Ult}(M,\mathfrak{X},\mathcal{U}) = \mathcal{F}_\mathfrak{X} / \sim_\mathcal{U}}.

Theorem 5 (Łoś) {N \models \phi([g])} iff {\{ \alpha : M \models \phi(g(\alpha)) \} \in \mathcal{U}}.

Proof: This is proved by induction. The only interesting case is the existential step, i.e. when we are trying to prove that {N \models \exists x \phi(x,[g])} iff {\{ \alpha : M \models \exists x \phi(x,g(\alpha)) \} \in \mathcal{U}}. The forward direction of the implication is trivial. For the backward direction, fix a global well-order {G \in \mathfrak{X}}. For {\mathcal{U}}-many {\alpha}, let {x_\alpha} be {G}-least such that {M \models \phi(x_\alpha, g(\alpha)}. Then, if {f(\alpha) = x_\alpha}, {\{ \alpha : M \models \phi(f(\alpha),g(\alpha)) \} \in \mathcal{U}}. Thus by inductive hypothesis, {N \models \phi([f],[g])}. \Box

This gives that {M \preceq N}, where {M} embeds via the map {a \rightarrow [\mathsf{const}_a]}. We needed the second-order structure on {M} so that we could use a global well-order to pick witnesses, but the ultrapower doesn’t carry this second-order structure up to {N}. If {M} has a definable global well-order, then we could take {\mathfrak{X} = \mathord{\mathrm{Def}}(M)} and carry out the construction.

In general, Skolem ultrapowers don’t have to create top extensions, but if we choose the ultrafilter correctly, we can ensure this happens.

Lemma 6 Suppose for all {f \in \mathcal{F}_\mathfrak{X}} that if there is {A \in \mathcal{U}} so that {f} is bounded in {A}, then there is {B \in \mathcal{U}} so that {f} is constant on {B}. Then, {M \prec_{\mathsf{top}} N}.

Proof: Consider {[f] \in N} and suppose {a \in M} and {N \models [f] < [\mathsf{const}_a]}. Then, {\{ \alpha : M \models f(\alpha) < a \} \in \mathcal{U}}, so {f} is constant on some set in {\mathcal{U}}. Thus, {[f] \sim_U [\mathsf{const}_b]}, for some {b \in M}. \Box

Rather classless models

We now have the groundwork laid in place to build models of set theory with {0} or {1} {\mathsf{GBC}}-realizations.

Definition 7 {M \models \mathsf{ZFC}}. {A \subseteq M} is amenable (to {M}) if every initial segment of {A} is in {M}: for all {\alpha \in \mathrm{Ord}^M}, there is {a \in M} so that {M \models b \in a} iff {b \in A} and {\mathrm{rk} b < \alpha}. Write {\mathrm{Am}(M)} for the collection of amenable subsets of {M}.

Examples of amenable sets are easy to find. If {M = V_\kappa}, then any {A \in V_{\kappa+1}} is amenable. If {A} is definable in {M}, then {A} is necessarily amenable. However, there are models of set theory with many non-amenable subsets. If {M} is {\omega}-nonstandard, then {A = \omega \cup (\mathrm{Ord}^M \setminus \omega^M)} is not amenable as {A \cap \omega^M} is the true {\omega}, which cannot be a set in {M}. Even in transitive models, we can see this. If {0^\sharp} exists, then {A = 0^\sharp \cup (\mathrm{Ord} \setminus \omega)} is not amenable to {L} as {A \cap \omega = 0^\sharp}.

Definition 8 {M \models \mathsf{ZFC}} is rather classless if {\mathrm{Am}(M) = \mathord{\mathrm{Def}}(M)}.

We’ve already seen that {\mathord{\mathrm{Def}}(M) \subseteq \mathrm{Am}(M)} for any {M}. We can think of {M} being rather classless as saying that {M} has as few amenable subsets as possible. We can trivially observe that no countable {M} is rather classless: any cofinal {\omega}-sequence is amenable, but never definable. However, there are {\omega_1}-like rather classless models.

But before actually constructing any rather classless models, let’s see that they answer our original question.

Let {M \models \mathsf{ZFC}} be rather classless. If {M} has a definable global well-order, then {M} has a unique {\mathsf{GBC}}-realization. If {M} does not have a definable global well-order, then {M} has no {\mathsf{GBC}}-realization.

Proof: Observe that if {(M,\mathfrak{X}) \models \mathsf{ZFC}}, then {\mathfrak{X} \subseteq \mathrm{Am}(M)}; this is just separation. Hence, the only possible {\mathsf{GBC}}-realization for rather classless {M} is {\mathord{\mathrm{Def}}(M)}. {(M,\mathord{\mathrm{Def}}(M)) \models \mathsf{GBC}} iff {M} has a definable global well-order. \Box

Remark 2 Note that having a definable global well-order is expressible as a single first-order sentence. This is as having a global well-order definable from parameter {a} is equivalent to {V = \mathrm{HOD}(a)}. Hence, the sentence {\exists x\ V = \mathrm{HOD}(x)} asserts the existence of a definable global well-order.

We are now ready to construct {\omega_1}-like rather classless models of set theory. The key step is contained in the following lemma:

Lemma 9 (Key Lemma) {(M,\mathfrak{X}) \models \mathsf{GBC}} countable, {S \in \mathrm{Am}(M) \setminus \mathfrak{X}}. Then there is {N \succ_{\mathsf{top}} M} so that {S} is not coded in {N}, i.e. for all {b \in N}, {\{ a \in M : N \models a \in b \} \ne S}.

Proof: We will find an ultrafilter {\mathcal{U}} on {\mathcal{B}_\mathfrak{X}} so that {N = \mathrm{Ult}(M,\mathfrak{X},\mathcal{U})} is as desired. Well order {\mathcal{F}_\mathfrak{X}} as {\langle f_n : n \in \omega \rangle}. We will define a descending sequence {\langle A_n : n \in \omega \rangle} of unbounded classes in {\mathcal{B}_\mathfrak{X}} which will generate {\mathcal{U}}. Start with {A_0 = \mathrm{Ord}^M}.

Suppose {A_n} has already been defined and look at {f_n}. If {f_n} is bounded in {A_n}, then use the pigeonhole principle to find unbounded {A_{n+1} \subseteq A_n} on which {f_n} is constant.

Otherwise, {f_n} is unbounded in {A_n}. We want to ensure that {f_n} does not represent a set in {N} which codes {S}. To see how to do this, let’s introduce an auxiliary tree. Set {T = \{ (x,\alpha) : x \subseteq V_\alpha^M \land x \in M \}}, where {(x,\alpha) \le (y,\beta)} iff {\alpha \le \beta} and {x = y \cap V_\alpha^M}. {T} is not quite a tree in the usual set theoretic sense; if {M} is ill-founded, then chains in {T} don’t have to be well-founded. However, if we slightly generalize the notion of tree to allow chains to be ill-founded but linear, then {T} is a tree in this less restrictive sense. Any {C \in \mathrm{Am}(M)} induces a cofinal branch through {T}: {\mathrm{br} C = \{ (x,\alpha) \in T : x = C \cap V_\alpha^M \}}.

For {(x,\alpha) \in T}, set {B_{x,\alpha} = \{ \xi \in A_n : f_n(\xi) \cap V_\alpha^m = x \}}. Then, {E = \{ (x,\alpha) \in T : B_{x,\alpha} \text{ is unbounded} \}} is the collection of nodes for which it is possible to have {f_n} extend while still being able to continue the construction of the ultrafilter. The sets {B_{x,\alpha}} for {(x,\alpha) \in E} are the possibilities for {A_{n+1}}. Clearly, {E \in \mathfrak{X}} and {B_{x,\alpha} \in \mathfrak{X}} for every {(x,\alpha) \in T}. That is, picking one of these to be {A_{n+1}} will keep us within {\mathcal{B}_\mathfrak{X}}.

Further note that {E} is unbounded. This is easy to see: for any {\alpha \in \mathrm{Ord}^M}, there are only {M}-set many possibilities for {f_n(\xi) \cap V_\alpha^M}. Hence, there must be an unbounded class on which they are all the same.

Observe that if on {\mathcal{U}}-many {\xi}, {f_n(\xi)} extends a node in {T \setminus \mathrm{br} S}, then {[f_n]} does not code {S}. Hence, if {E \not \subseteq \mathrm{br} S}, we can find {A_{n+1}} so that {[f_n]} will not code {S}. to see this, suppose otherwise that {E \subseteq \mathrm{br} S}. As {E} is unbounded, this would imply that {\bigcup\{ x \in M : \exists \alpha \in \mathrm{Ord}^M\ (x,\alpha) \in E \} = S}. But this first subset of {M} is in {\mathfrak{X}}, as {E \in \mathfrak{X}}, and {E \not \in \mathfrak{X}}. Hence, we were wrong to suppose that {E \subseteq \mathrm{br} S}. We can thus pick unbounded {A_{n+1} \subseteq A_n} which ensures {[f_n]} does not code {S}.

Let {\mathcal{U}} be the filter generated by {\{A_n\}}. {\mathcal{U}} is an ulrtafilter as every characteristic function of a {B \in \mathcal{B}_\mathfrak{X}} is bounded and hence constant on a class in {\mathcal{U}}. {N = \mathrm{Ult}(M,\mathfrak{X},\mathcal{U}) \succ_{\mathsf{top}} M}, by the earlier lemma. By construction, no {[f] \in N} codes {S}. \Box

Theorem 10 (Keisler) Assume {\diamond} and let {M_0 \models \mathsf{ZFC}} be countable. Then there is an elementary top extension {M} of {M_0} which is {\omega_1}-like and rather classless.

Proof: Fix a diamond sequence {\langle S_\alpha : \alpha \in \omega_1 \rangle}. We will construct an {\omega_1} chain of elementary top extensions of countable models {M_\alpha}. At limit stages, we just take unions. At successors of successors, we let {M_{\alpha + 2} = M_{\alpha + 1}}. The only interesting case is in defining successors of limits. Without loss of generality, {M_\lambda}‘s universe is {\lambda}. Hence, {S_\lambda \subseteq M_\lambda}. If {S_\lambda \in \mathord{\mathrm{Def}}(M_\lambda)}, then let {M_{\lambda+1}} be any top extension of {M_\lambda}. We can use the Key Lemma to get this top extension. Otherwise, if {S_\lambda} is not definable in {M}, then we can find countable {\mathfrak{X}} so that {S_\lambda \not \in \mathfrak{X}} and {(M,\mathfrak{X}) \models \mathsf{GBC}}: if {(M_\lambda,S_\lambda) \models \mathsf{ZFC}(S_\lambda)} then take {\mathfrak{X} = \mathord{\mathrm{Def}}(M_\lambda,G)} where {G} is {(M_\lambda,S_\lambda)}-generic; if {(M_\lambda,S_\lambda) \not \models \mathsf{ZFC}(S_\lambda)} then take any {\mathfrak{X}}. We can now apply the Key Lemma and find {M_{\lambda+1} \succ_{\mathsf{top}} M_\lambda} which kills {S_\lambda}. Finally, let {M} be the union of this elementary chain. {M} is {\omega_1}-like.

To see that {M} is rather classless, consider {S \in \mathrm{Am}(M)}. I claim there is a club of {\alpha} so that {(M_\alpha, S \cap M_\alpha) \prec (M,S)}. Closedness is easy. To see unboundedness, fix {\alpha_0 < \omega_1}. By taking Skolem closures, we can find

\displaystyle  M_{\alpha_0} \subseteq B_0 \subseteq M_{\alpha_1} \subseteq B_1 \subseteq \cdots

so that {(M \upharpoonright B_n, S \cap B_n) \prec (M,S)}. Then, if {\alpha = \sup \alpha_n}, {(M_\alpha, S \cap M_\alpha) \prec (M,S)}.

{\diamond} then gives us a {\lambda} so that {S \cap M_\lambda = S_\lambda} and {(M_\lambda, S_\lambda) \prec (M,S)}. Pick {\xi \in \mathrm{Ord}^{M_{\lambda+1}} \setminus \mathrm{Ord}^{M_\lambda}}. Then, {S \cap V_\xi^M \in M_{\lambda+1}}. This element of {M_{\lambda+1}} codes {S_\lambda}, so by construction, {S_\lambda} must have been definable in {M_\lambda}. By elementarity, {S \in \mathord{\mathrm{Def}}(M)}, as desired. \Box

We have constructed rather classless models of set theory, but only from the assumption of {\diamond}. However, this assumption can be eliminated.

Theorem 11 (Shelah) The assumption of {\diamond} can be eliminated from Keiser’s theorem.

Working through an argument for this will have to wait for the future.

Corollary 12 Let {M \models \mathsf{ZFC}} be countable. If {M \models \exists x \ V = \mathrm{HOD}(x)}, then there is an elementary top extension of {M} which has a unique {\mathsf{GBC}}-realization. If {M \models \forall x \ V \ne \mathrm{HOD}(x)} then there is an elementary top extension of {M} which has no {\mathsf{GBC}}-realization.

Proof: In either case, take {N \succ_{\mathsf{top}} M} to be {\omega_1}-like and rather classless. \Box

It is natural to ask if a model of set theory can have few, but more than one, {\mathsf{GBC}}-realization.

For which {n \in \omega} are there models of set theory with exactly {n} {\mathsf{GBC}}-realizations?

1. Some references

The original construction of rather classless models is due to Keisler. He proved a more general result than the one presented here, showing that, for example, every countably model of {\mathsf{PA}} has an elementary end extension to an {\omega_1}-like rather classless model. Keisler drew the corollary that there are models of set theory with unique {\mathsf{GBC}}-realizations, but said nothing about models with no {\mathsf{GBC}}-realizations. The elimination of {\diamond} is due to Shelah.

  • H. Jerome Keisler, “Models with tree structures,” Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
  • Saharon Shelah, “Models with second-order properties. II. Trees with no undefined branches,” Ann. Math. Logic 14 (1978), no. 1, 73–87.

Advertisements