Class choice and the surprising weakness of Kelley-Morse set theory

PDF   Bibtex

V. Gitman, J. D. Hamkins, and T. Johnstone, “Class choice and the surprising weakness of Kelley-Morse set theory.”

Suppose that for every natural number $n$ there is a class $X$ for which some property $\varphi(n,X)$ holds-assume we are working in a suitable set theory with classes, including the axiom of choice and even the global choice principle. Should we expect to find a uniformizing class $Z\subseteq\omega\times V$ for which $\varphi(n,Z_n)$ holds for all the various sections? Similarly, if every ordinal $\alpha$ has a class $X$ for which $\varphi(\alpha,X)$ holds, then should we we expect to find a class $Z\subseteq{\rm Ord}\times V$ for which $\varphi(\alpha,Z_\alpha)$ holds on every section? Or if every set $x$ admits a class $X$ with $\varphi(x,X)$, then will we find a class $Z\subseteq V\times V$ which unifies these witnesses $\varphi(x,Z_x)$?

These would all be instances of the class choice scheme, a central concern of this article. The class $Z$ in each case uniformizes the witnesses, in effect choosing for each index $x$ a class witness $Z_x$ on that section. The class choice scheme is therefore a choice principle enabling a choice of classes, rather than sets.

It is relatively easy to see that the class choice scheme is not provable in Gödel-Bernays ${\rm GBC}$ set theory, even with the axiom of global choice being available in that theory. A counterexample is provided by any transitive model of ${\rm ZFC}+V={\rm HOD}$, equipped with all and only its definable classes. To see this, observe that for each $n$ there is a definable $\Sigma_n$-truth predicate (a partial satisfaction class), but by Tarski's theorem on the non-definability of truth, these cannot be unified into a single definable class. Indeed, in this case we are not really 'choosing' the classes at all, since in fact for each $n$ there is a unique $\Sigma_n$-truth predicate. Rather, what is going on is that ${\rm GBC}$ is not strong enough (although ${\rm KM}$ is) to collect these various unique witnesses together into a single uniform class. The situation resembles more a class-wise failure of collection or even replacement than choice.

Perhaps it will be a little more surprising, however, to learn that the class choice scheme is also not provable in the considerably stronger Kelley-Morse ${\rm KM}$ set theory, against which the simple truth-predicate counterexample above is not successful, as ${\rm KM}$ does prove the existence of uniform first-order truth predicate satisfaction classes relative to any class parameter. Nevertheless, we show that ${\rm KM}$ does not prove the class choice scheme, and indeed the scheme can fail even in very low-complexity first-order instances and again with merely a set of indices. Kelley-Morse set theory ${\rm KM}$ simply does not prove the class choice scheme, even in easy-seeming cases.

Furthermore, the proof methods reveal several further surprising weaknesses of ${\rm KM}$, which may call into question the suitability of this theory as a foundation of set theory. Namely, ${\rm KM}$ does not prove the Łoś theorem scheme for second-order internal ultrapowers, even in the case of large-cardinal ultrapowers, such as those arising from a normal measure on a measurable cardinal-the familiar large cardinal embeddings can fail to be elementary in the language of ${\rm KM}$ set theory. In the case of ultrapowers by an ultrafilter on $\omega$, we show, the internal ultrapower of the ${\rm KM}$ universe is not itself always even a model of ${\rm KM}$. Finally, we will show that ${\rm KM}$ does not prove that second-order logical complexity is preserved by first-order quantifiers, even bounded quantifiers. In light of all these weaknesses, the theory ${\rm KM}$ appears not quite as robust a foundational theory as might have been thought.

Meanwhile, by augmenting the theory ${\rm KM}$ with the class choice scheme, thereby forming the theory we denote ${\rm KM}^+$, we addresses all these weaknesses, and in this sense ${\rm KM}^+$ succeeds as a robust foundational treatment of second-order set theory.

Background on sets and classes

The objects of first-order set theory are sets, and set theorists commonly take the classes of a model of first-order set theory to be simply the definable collections of sets (allowing parameters), which means that the study of their properties naturally takes place in the meta-theory. A formal framework for studying sets and classes, in contrast, is provided by second-order set theory. The most natural interpretation of second-order set theory is in a two-sorted logic with separate sorts (separate variables and quantifiers) for sets and classes. The language of second-order set theory has two membership relations, one deciding set membership in sets and the other deciding set membership in classes. Because foundational axioms of second-order set theory assert that classes are extensional collections of sets, the models of second-order set theory relevant for us have the form $\langle V,\in,\mathcal S\rangle$, where $\langle V,\in\rangle$ is a model of the language of first-order set theory and $\mathcal S$ is the family of classes, that is, collections of sets. Following the standard convention, we use lowercase letters for the sets and uppercase letters for the classes. In the meta-theory of second-order set theory, we can also study hyperclasses, the definable (with parameters) collections of classes.

Any reasonable axiomatic foundation for second-order set theory should assert that the collection of all sets satisfies ${\rm ZFC}$ and that, more generally, it continues to satisfy ${\rm ZFC}$ in the extended first-order language with predicates for any finitely many classes. The more general requirement translates into the class replacement axiom, which states that the image of a set under a class function is itself a set. A reasonable foundation should also include some class existence principles and should in particular generalize the notion of classes from first-order set theory by asserting that every first-order definable collection is a class. The two most commonly considered axiomatic foundations for second-order set theory are the Gödel-Bernays axioms (${\rm GBC}$) and the Kelley-Morse axioms (${\rm KM}$). They are distinguished by the strength of their comprehension axiom schemes that decide which (second-order) definable collections are classes. The theory ${\rm GBC}$ includes only the minimal first-order comprehension and it is equiconsistent with ${\rm ZFC}$. The theory ${\rm KM}$ asserts full second-order comprehension and strength-wise it lies between the existence of a transitive model of ${\rm ZFC}$ and the existence of an inaccessible cardinal.

Class choice schemes

Axiomatizations of second-order set theory often include choice principles for classes because these imply many properties desirable in this context. A commonly used choice principle is the class choice scheme, which asserts that every $V$-indexed definable family of hyperclasses has a choice function $\mathcal F:V\to \mathcal S$. Historically, this principle can be traced to Marek's PhD thesis in the 1970s [1] and was rediscovered several times, most recently in the work of Hrbáček on nonstandard second-order set theories with infinitesimals [2] and Antos and Friedman on definable hyperclass forcing over ${\rm KM}$ models (missing reference). To give the precise statement of the class choice scheme, we use the standard notation that if $Z$ is a class, then $$Z_x=\{y\mid(x,y)\in Z\}$$ denotes the class coded on section $x$ of $Z$. We think of such a class $Z$ as naturally encoding the function $x\mapsto Z_x$, enabling us in effect to refer to functions $\mathcal F:V\to\mathcal S$ as above. In general, if a collection of classes can be coded like this by a single class $Z$, we will say that it constitutes a codable hyperclass.

Definition: The class choice scheme is the following scheme of assertions, for any formula $\varphi$ in the language of second-order set theory and allowing any class parameter $A$: $$\forall x\,\exists X\,\varphi(x,X,A)\rightarrow\exists Z\,\forall x\,\varphi(x,Z_x,A).$$

As we hinted in the introduction, the class choice scheme can also be viewed as a collection principle rather than a choice principle, because it is equivalent over ${\rm GBC}$ to the following slightly weaker-seeming principle, the class-collection scheme: $$\forall x\,\exists X\,\varphi(x,X,A)\rightarrow \exists Z\,\forall x\,\exists y\,\varphi(x,Z_y,A).$$ In this formulation, the class witnesses $X$ are merely collected as sections $Z_y$, but not necessarily on the corresponding section $Z_x$. Note first that either principle over ${\rm GBC}$ implies ${\rm KM}$, and then the further point is that with the class collection scheme one can choose for each $x$ a suitable $y$ by global choice and thereby replace the sections on the correct index, making the two principles equivalent.

The class choice scheme admits several natural weakenings, by stratifying on the logical complexity of $\varphi$ or restricting to sets of indices.

Definition:

The main results

We aim to show that ${\rm KM}$ fails to prove even the weakest instances of the class choice scheme, concerning the existence of choice functions for $\omega$-indexed parameter-free first-order definable families. This provides an interesting counterpoint to the situation in second-order arithmetic, where ${\rm Z}_2$, usually considered a tight arithmetic analogue of ${\rm KM}$, proves all $\Sigma^1_2$ instances of the class choice scheme. We also show that ${\rm KM}$ together with the set-indexed class choice scheme does not imply the class choice scheme even for parameter-free first-order formulas and that ${\rm KM}$ together with the parameter-free class choice scheme does not imply the class choice scheme. We shall freely make use of mild large cardinal assumptions when proving the main results, since these assumption do not detract from our main point that ${\rm KM}$ does not prove the desired features for a foundational second-order theory of sets and classes, as set theorists want to use the foundational theory with those and far stronger large cardinals.

Theorem: (${\rm ZFC}\,+\,$there is a Mahlo cardinal) There is a model of ${\rm KM}$ in which an instance $$\forall n{\in}\omega\,\exists X\,\varphi(n,X)\rightarrow \exists Z\,\forall n{\in}\omega\,\varphi(n,Z_n)$$ of the class choice scheme fails for a first-order formula $\varphi(x,X)$.

Theorem: (${\rm ZFC}\,+\,$there is a Mahlo cardinal) There is a model of ${\rm KM}$ in which the set-indexed class choice scheme holds, but the class choice scheme fails for a parameter-free first-order formula.

Theorem: (${\rm ZFC}\,+\,$there is an inaccessible cardinal) There is a model of ${\rm KM}$ in which the parameter-free class choice scheme holds but the class choice scheme fails for a $\Pi^1_1$-formula.

The above theorem and its proof are motivated by the work in [3].

These failures of ${\rm KM}$ to prove even the weakest instances of the class choice scheme indicates a fundamental weakness in the theory and might lead us to reconsider its prominent role in second-order set theory. To highlight the weakness, we show that the Łoś theorem scheme can fail for the internal second-order ultrapower of the ${\rm KM}$ universe.

Theorem: (${\rm ZFC}\,+\,$there is an inaccessible cardinal) There is a model of ${\rm KM}$ whose internal second-order ultrapower by an ultrafilter on $\omega$ is not itself a ${\rm KM}$-model.

Similarly, we show that ${\rm KM}$ does not prove that large cardinal embeddings, such as the ultrapower of the universe by a normal measure on a measurable cardinal, are elementary in the language of ${\rm KM}$.

Theorem: (${\rm ZFC}\,+\,$measurable cardinal with an inaccessible above) There is a model of ${\rm KM}$ with a measurable cardinal $\delta$, such that the internal ultrapower of the universe by a normal measure on $\delta$ is not elementary in the language of ${\rm KM}$ set theory.

We also show that ${\rm KM}$ does not prove that $\Sigma^1_1$ formulas are (up to equivalence) closed under first-order quantifiers, even bounded first-order quantifiers.

Theorem: (${\rm ZFC}\,+\,$measurable cardinal with an inaccessible above) The theory ${\rm KM}$ fails to establish that $\forall \eta\lt\delta\,\psi(\eta,X)$ is provably equivalent to some $\Sigma^1_1$ formula whenever $\psi$ is.

In every case, these various deficiencies of ${\rm KM}$ are remedied by replacing it with the theory which we call ${\rm KM}^+$, which augments ${\rm KM}$ with the class choice scheme. A result of Marek shows that ${\rm KM}^+$ is bi-interpretable with the first-order theory ${\rm ZFC}^-$, that is, ${\rm ZFC}$ without the powerset axiom, together with the assertion that there is a largest cardinal that is furthermore an inaccessible cardinal [1].

References

  1. W. Marek, “On the metamathematics of impredicative set theory,” Dissertationes Math. (Rozprawy Mat.), vol. 98, p. 40, 1973.
  2. K. Khrbachek, “Remarks on nonstandard class theory,” Fundam. Prikl. Mat., vol. 11, no. 5, pp. 233–255, 2005. Available at: http://dx.doi.org/10.1007/s10958-007-0374-0
  3. W. Guzicki, “On weaker forms of choice in second order arithmetic,” Fund. Math., vol. 93, no. 2, pp. 131–144, 1976.