I should like to give a brief account of the argument that KM implies Con(ZFC) and much more. This argument is well-known classically, but unfortunately seems not to be covered in several of the common set-theoretic texts.
First, without giving a full formal axiomatization, let us review a little what KM is. (And please see Victoria Gitman’s post on variant axiomatizations of KM.) In contrast to Zermelo-Frankael (ZFC) set theory, which has a purely first-order axiomatization, both Kelley-Morse (KM) set theory and Gödel-Bernays (GBC) set theory are formalized in the second-order language of set theory, where we have two sorts of objects, namely sets and classes, in addition to the usual set membership relation $\in$. A model of KM will have the form $\langle M,{\in^M},S\rangle$, where $M$ is the collection of sets in the model, and $S$ is a collection of classes in the model; each class $A\in S$ is simply the subset of $M$. Both KM and GBC will imply that $\langle M,{\in^M}\rangle$ is a model of ZFC. Both GBC and KM assert the global choice principle, which asserts that there is a class that is a well-ordering of all the sets (or equivalently that there is a class bijection of all the sets with the class of ordinals). Beyond this, both GBC and KM have a class comprehension principle, asserting that for certain formulas $\varphi$, having finitely many set and class parameters, that $\{x \mid \varphi(x)\}$ forms a class. In the case of GBC, we have this axiom only for $\varphi$ having only set quantifiers, but in KM we also allow formulas $\varphi$ that have quantification over classes (which are interpreted in the model by quanfying over $S$). Both theories also assert that the intersection of a class with a set is a set (which amounts to the separation axiom, and this follows from replacement anyway). In addition, both GBC and KM have a replacement axiom, asserting that if $u$ is a set, and for every $a\in u$ there is a unique set $b$ for which $\varphi(a,b)$, where $\varphi$ has finitely many class and set parameters, then $\{ b\mid \exists a\in u\, \varphi(a,b)\}$ is a set. In the case of GBC, we have the replacement axiom only when all the quantifiers of $\varphi$ are first-order quantifiers only, quantifying only over sets, but in KM we allow $\varphi$ to have second-order quantifiers. Thus, both GBC and KM can be thought of as rather direct extensions of ZFC to the second-order class context, but KM goes a bit further by applying the ZFC axioms also in the case of the new second-order properties that become available in that context, while GBC does not.
The theorem I want to discuss is:
Theorem. KM proves Con(ZFC).
Indeed, ultimately we’ll show in KM that there is transitive model of ZFC, and furthermore that the universe $V$ is the union of an elementary chain of elementary rank initial segments $V_\theta\prec V$, each of which, in particular, is a transitive model of ZFC.
We’ll prove it in several steps, which will ultimately reveal stronger results and a general coherent method and idea.
KM has a truth predicate for first-order truth. The first step is to argue in KM that there is a truth predicate Tr for first-order truth, a class of pairs $(\varphi,a)$, where $\varphi$ is a first-order formula in the language of set theory and $a$ is an assignment of the free variabes of $\varphi$ to particular sets, such that the class Tr gets the right answer on the quantifier-free formulas and obeys the recursive Tarskian truth conditions for Boolean combinations and first-order quantification, that is, the conditions explaining how the truth of a formula is determined from the truth of its immediate subformulas.
To construct the truth predicate, begin with the observation that we may easily define, even in ZFC, a truth predicate for quantifier-free truth, and indeed, even first-order $\Sigma_n$ truth is $\Sigma_n$-definable, for any meta-theoretic natural number $n$. In KM, we may consider the set of natural numbers $n$ for which there is a partial truth predicate $T$, one which is defined only for first-order formulas of complexity at most $\Sigma_n$, but which gives the correct answers on the quantifier-free formulas and which obeys the Tarskian conditions up to complexity $\Sigma_n$. The set of such $n$ exists, by the separation axiom of KM, since we can define it by a property in the second-order language (this would not work in GBC, since there is a second-order quantifier asking for the existence of the partial truth predicate). But now we simply observe that the set contains $n=0$, and if it contains $n$, then it contains $n+1$, since from any $\Sigma_n$ partial truth predicate we can define one for $\Sigma_{n+1}$. So by induction, we must have such truth predicates for all natural numbers $n$. This inductive argument really used the power of KM, and cannot in general be carried out in GBC or in ZFC.
A similar argument shows by induction that all these truth predicates must agree with one another, since there can be no least complexity stage where they disagree, as the truth values at that stage are completely determined via the Tarski truth conditions from the earlier stage. So in KM, we have a unique truth predicate defined on all first-order assertions, which has the correct truth values for quantifier-free truth and which obeys the Tarskian truth conditions.
The truth predicate Tr agrees with actual truth on any particular assertion. Since the truth predicate Tr agrees with the actual truth of quantifier-free assertions and obeys the Tarskian truth conditions, it follows by induction in the meta-theory (and so this is a scheme of assertions) that the truth predicate that we have constructed agrees with actual truth for any meta-theoretically finite assertion.
The truth predicate Tr thinks that all the ZFC axioms are all true. Here, we refer not just to the truth of actual ZFC axioms (which Tr asserts as true by the previous paragraph), but to the possibly nonstandard formulas that exist inside our KM universe. We claim nevertheless that all such formulas the correspond to an axiom of ZFC are still decreed true by the predicate Tr. We get all the easy axioms by the previous paragraph, since those axioms are true under KM. It remains only to verify that Tr asserts as true all instances of the replacement axiom. For this, suppose that there is a set $u$, such that Tr thinks every $a\in u$ has a unique $b$ for which Tr thinks $\varphi(a,b)$. But now by KM (actually we need only GB here), we may apply the replacement axiom with Tr a predicate, to find that $\{ b\mid \exists a\in u\, \text{Tr thinks that} \varphi(a,b)\}$ is a set, whether or not $\varphi$ is an actual finite length formula in the metatheory. It follows that Tr will assert this instance of replacement, and so Tr will decree all instances of replacement as being true.
KM produces a closed unbounded tower of transitive models of ZFC. This is the semantic approach, which realizes the universe as the union of an elementary chain of elementary substructures $V_\theta$. Namely, by the reflection theorem, there is a closed unbounded class of ordinals $\theta$ such that $\langle V_\theta,{\in},\text{Tr}\cap V_\theta\rangle\prec_{\Sigma_1}\langle V,{\in},\text{Tr}\rangle$. (We could have used $\Sigma_2$ or $\Sigma_{17}$ here just as well.) It follows that $\text{Tr}\cap V_\theta$ fulfills the Tarskian truth conditions on the structure $\langle V_\theta,\in\rangle$, and therefore agrees with the satisfaction in that structure. It follows that $V_\theta\prec V$ for first-order truth, and since ZFC was part of what is asserted by Tr, we have produced here a transitive model of ZFC. More than this, what we have is a closed unbounded class of ordinals $\theta$, which form an elementary chain $$V_{\theta_0}\prec V_{\theta_1}\prec\cdots\prec V_\lambda\prec\cdots,$$ whose union is the entire universe. Each set in this chain is a transitive model of ZFC and much more.
An alternative syntactic approach. We could alternatively have reasoned directly with the truth predicate as follows. First, the truth predicate is complete, and contains no contradictions, simply because part of the Tarskian truth conditions are that $\neg\varphi$ is true according to Tr if and only if $\varphi$ is not true according to Tr, and this prevents explicit contradictions from ever becoming true in Tr, while also ensuring completeness. Secondly, the truth predicate is closed under deduction, by a simple induction on the length of the proof. One must verify that certain logical validities are decreed true by Tr, and then it follows easily from the truth conditions that Tr is closed under modus ponens. The conclusion is that the theory asserted by Tr contains ZFC and is consistent, so Con(ZFC) holds. Even though Tr is a proper class, the set of sentences it thinks are true is a complete consistent extension of ZFC, and so Con(ZFC) holds. QED
The argument already shows much more than merely Con(ZFC), for we have produced a proper class length elementary tower of transitive models of ZFC. But it generalizes even further, for example, by accommodating class parameters. For any class $A$, we can construct in the same way a truth predicate $\text{Tr}_A$ for truth in the first-order language of set theory augmented with a predicate for the class $A$.
In particular, KM proves that there is a truth predicate for truth-about-truth, that is, for truth-about-Tr, and for truth-about-truth-about-truth, and so on, iterating quite a long way. (Of course, this was also clear directly from the elementary tower of transitive models.)
The elementary tower of transitive elementary rank initial segments $V_\theta\prec V$ surely addresses what is often seen as an irritating limitation of the usual reflection theorem in ZFC, that one gets only $\Sigma_n$-reflection $V_\theta\prec_{\Sigma_n} V$ rather than this kind of full reflection, which is what one really wants in a reflection theorem. The point is that in KM we are able to refer to our first-order truth predicate Tr and overcome that restriction.
Doesn’t the existence of a truth predicate violate Tarski’s theorem on the non-definability of truth? No, not here, since the truth predicate Tr is not definable in the first-order language of set theory. Tarski’s theorem asserts that there can be no definable class (even definable with set parameters) that agrees with actual truth on quantifier-free assertions and which satisfies the recursive Tarskian truth conditions. But nothing prevents having some non-definable class that is such a truth predicate, and that is our situation here in KM.
Although the arguments here show that KM is strictly stronger than ZFC in consistency strength, it is not really very much stronger, since if $\kappa$ is an inaccessible cardinal, then it is not difficult to argue in ZFC that $\langle V_\kappa,\in,V_{\kappa+1}\rangle$ is a model of KM. Indeed, there will be many smaller models of KM, and so the consistency strength of KM lies strictly between that of ZFC, above much of the iterated consistency hierarchy, but below that of ZFC plus an inaccessible cardinal.
Thanks for the great post Joel! Just to clarify, I think the axioms of KM are precisely the following:
1) Set axioms: extensionality, foundation, pairing, infinity, union, powerset.
2) Class axioms: extensionality, full class comprehension, replacement (stating that the restriction of a class function to a set is a set), global well-order class exists.
The Wikipedia article on KM uses the so called “limitation of size” axiom stating that a class is proper if and only if it maps 1-1 into V instead of replacement+global well-order exists. I think it is easy to see that the axiomatizations are equivalent. Interestingly, Mendelson in his Mathematical Logic text does not assume the global choice axiom as part of KM.
Thanks so much, Vika. I have sometimes been a little worried that I had my own private understanding of KM, but I’m glad to hear that what I think of KM is the same theory as what other people think of as KM. Except Mendelson, I guess, which is rather strange to hear about; does he put global choice into GBC? I think most people understand GBC to include global choice, so it would be strange if he didn’t.
Nope, unless I am mistaken, Mendelson includes only the set version of AC.
Pingback: A natural strengthening of Kelley-Morse set theory, CUNY Logic Workshop, May 2014 | Joel David Hamkins
I have been using MK (or KM) to investigate the Russell-Myhill paradox of propositions. So I have a theory, MK + P (P for propositions). See Analysis, 2012.
I don’t see how satisfaction for formulas of MK can be defined in the usual Tarskian fashion. How does one get the truth of say “R is a proper class.” This can’t be analyzed as “R is an element of the extension of “proper class;” there is no such extension. Is reflection useful here. Do you count statements such as “R is a proper class as second order. Technically, MK is a first order theory and therefore has a countable model. Harry
The assertion ‘R is a proper class’ is a first-order assertion about R, namely, $\neg\exists x\ R\in x$. But meanwhile, in the post where I am referring to having a satisfaction class for first-order truth, what was meant is that the satisfaction class is only defined with set parameters, not class parameters. Nevertheless, with any finite list of class parameters, one can define in KM the satisfaction class for first-order assertions about those particular classes, simply by relativizing the construction to accommodate those fixed class parameters.
Pingback: Open determinacy for proper class games implies Con(ZFC) and much more | Joel David Hamkins
Dear Joel,
This is a fab post! Very interesting stuff.
Just one quibble (and a very pedantic one at that), and one question.
Quibble: You say that MK is formulated in the second-order language of set theory. I’m confused as to what you have in mind here; normally MK is a two-sorted first-order theory. This is important philosophically, in particular if MK is two-sorted first-order, then it has a countable model, but if we are quantifying into predicate position (and using the full semantics) then there is no countable model of second-order set theory (i.e. ZFC_2). Given your views on the interpretation of second-order variables, I guess this doesn’t matter, but for some people thinking about MK the distinction is important.
Question (also available on mathematics Stack Exchange). Is the *exact* consistency strength of MK known?
Best Wishes,
Neil
I’m glad you enjoyed the post, Neil.
About your quibble, we do not disagree. This is just a matter of terminology. I refer to the two-sorted language as the language of second-order set theory, since the two sorts correspond to sets (first-order objects) and classes (second-order objects). This is the same language that one would use if one intended to use full actual second-order logic, with the full second-order semantics, although in KM we do not insist on those semantics. Ultimately, KM is a first-order theory even though it uses the language of second-order set theory.
It is just the same situation with what is called second-order number theory in reverse mathematics, where one has the two-sorted language with first-order variables for numbers and second-order variables for sets of numbers. The various theories $\text{ACA}_0$ and $\text{ATR}_0$ and so on are commonly called second-order theories, but ultimately they are first-order expressible using the two sorts, just as with the situation for GBC and KM.
In practice, it is convenient to be able to refer to the two quantifiers as first-order quantifiers and second-order quantifiers in KM, although people also call them set-quantifiers and class-quantifiers. I would find it confusing in practice to insist on referring to the class quantifiers arising in KM as first-order quantifiers, just because we are treating classes as a sort.
Regarding your final question, on the strength of KM, I am not sure what kind of answer you would want. We describe the strength of theories by comparing them with other famous landmark theories, such as well-known large cardinals or theories. So the exact consistency strength of KM is: KM itself. This theory is one of the landmark theories that we might use. Meanwhile, one can also make comparisons with other theories. The theory KM is strictly stronger in consistency strength than ZFC+Con(ZFC)+Con(ZFC+Con(ZFC)) and so on, as I explained in my post. You can iterate many times, not just finitely much. KM is strictly stronger than a stationary proper class of worldly cardinals, since the tower of elementary substructures in my post produces a club of such cardinals, and by elementarity each will agree that the worldly cardinals form a stationary proper class. Meanwhile, the strength is strictly below ZFC+”there is an inaccessible cardinal”, since if $\kappa$ is measurable, then $\langle V_\kappa,\in,V_{\kappa+1}\rangle$ is a model of KM, and so the existence of an inaccessible cardinal implies Con(KM) and Con(KM+Con(KM)) and more. I fleshed these ideas out a bit more in an answer to your question on math.stackexchange.
I trust you about the current state of MK set theory, but I wanted to mention that the original “K” set theory, as I learned it from the appendix of Kelley’s topology book long ago, is a one-sorted first-order theory. The notion of “set” is defined within the theory as Kelley’s Definition 1: a set is a class that is an element of another class.
Thanks, Carl, yes, I am aware of that, and I had thought to mention it. Meanwhile, although this is one-sort treatment is slick for axiomatization, I think most set theorists do not favor that treatment now. It is irritating to pretend that sets and classes are really just one kind of thing, when the whole theory works much more coherently if we separate those notions. For example, I suppose that one could do the same slick trick in second-order number theory. But does anyone do that in reverse mathematics, having only one sort for classes and for numbers, and define number as an element of a class? I haven’t seen it.
I have never seen that in second order arithmetic, maybe because the arithmetical operations + and *, which have function symbols in the language, don’t extend naturally to sets, and so they are normally only defined on the number objects. Of course any multi-sorted first-order theory can be reduced to a purely relational signature in only one sort. I am genuinely curious, though, about the issues with having one sort for classes and sets. My own perspective was no doubt affected by learning MK before ZFC, but I always thought that classes and sets were basically the same thing – roughly, one could say both are intended to be collections, however sets are intended to be elements of $V_{O}$ and classes are intended to be elements of $V_{O +1}$, if the ordinals of the model are O. I can see how working with models of ZFC would make that perspective more difficult, but are there some other reasons that would not be obvious to a non set-theorist?
It is interesting that you learned Kelley-Morse first and this affected how you view the matter. From my perspective, sets and classes are so different, because you can’t really do much set theory with (proper) classes; you can’t build set-theoretic structure on top of classes, or take power classes or even make singletons, and so on. The kind of set theory that you can do with classes is so limited that they aren’t really the same thing.
I’m with Joel on this one. This plays out also in the philosophical literature, where usually proper classes are given a different interpretation from sets in order to (try and) avoid worrying questions for those who want just one maximal maximal universe about why proper classes look so much like sets. Uzquiano does things with plural reference (so a thoroughgoing class nominalism), whereas Welch and Horsten opt for a mereological conception of classes (rather than a combinatorial one). Carl presents an interesting view though, I’ll have a think about it.
The math.stackexchange answer is awesome, thanks for that! I’ll add a comment there to clarify my question. I suppose I’m interested if there are any `natural’ looking theories of the same consistency strength of MK (it looks like there are no known ones for the reasons you point out).
On the issue of second-order quantifiers, you’re right of course about the two formulations being equivalent if we insist on certain semantics. It’s just that I think, philosophically, different interpretations are suggested by the different kinds of syntax. For example, if you’re going for two-sorted first-order it all looks very `class-theoretic’ whereas quantifying into predicate position looks more `property-theoretic’. One might think that one formalism captures one’s preferred interpretation better. This really is all cosmetic though (as you rightly note). Plus I think the term `second-order’ property/set theory is pretty ubiquitous when discussing models/embeddings and so forth.
“it looks like there are no known ones for the reasons you point out”.
I mean here “no known ones apart from ones immediately related to KM (e.g. KM+)”. Clearly a proof-theoretic ordinal is out of reach, so I’m inquisitive about any combinatorial principles.
An example: Suppose that Con(PFA)=>Con(“There is a supercompact”). Then PFA would be the kind of thing I was looking for (now, I was a little muddled before, I was wondering if there might be a weakening of weak inaccessible or something similar that was equiconsistent).
Yes, it is a good question: is KM equiconsistent with some large-cardinal-like concept or other (different from KM itself) natural hypothesis?
I don’t know any examples, but we do have fairly close-in lower and upper bounds, as my answer indicates.
I am interest in the last paragraph of your blogpost:
“Although the arguments here show that $KM$ is strictly stronger than $ZFC$ in consistency strength, it is not really very much stronger…”, especially that “if $\kappa$ is an inaccessible cardinal, then it is not difficult to argue in $ZFC$ that $$ is a model of $KM$”. If one assumes $\kappa$ is the least inaccessible cardinal so that $V_{\kappa}$ is a model of ZFC$ + “There is no inaccessible cardinal.” then by the usual understanding of $V_{|kappa+ 1}$ (i.e. $V_{\kappa +1}$ = $Powerset$($V_{\kappa}$) since one is arguing in $ZFC$), both $\kappa$ and $V_{\kappa}$ are sets in $V_{\kappa + 1}$ and the model of $KM$ in question is not merely a model of $KM$ but is a model of $KM$ + “There is a proper class of inaccessible cardinals” (at least). Am I correctly understanding the state of affairs and if not, would you please point out the errors in my under standing? Thanks. By the way, it is a very interesting blogpost.
A model of KM consists of the first-order part, the sets, and a second-order part, the classes. If $\kappa$ is inaccessible, then we get a model of KM by taking the sets to be the elements of $V_kappa$, and the classes to be all subsets of $V_\kappa$. So the model can be described as $\langle V_\kappa,\in,V_{\kappa+1}\rangle$. If $\kappa$ is the least inaccessible cardinal, then there will be no smaller inaccessible cardinals, and so this model of KM will also model “there are no inaccessible cardinals.” To get a model of KM or even ZFC with a proper class of inaccessible cardinals or even just two inaccessible cardinals would have a strictly stronger consistency strength than ZFC plus just one inaccessible cardinal, so what you seem to be describing cannot work that way, unless I have misunderstood you.
So can $V_{\kappa +1}$ be considered the ‘power set’ (object?) of $V_{\kappa}$ since $V_{\kappa}$, $V_{\kappa + 1}$ seem to be stages of the cumulative hierarchy?
$V_\kappa$ is playing the role of $V$ in such a model of KM, and $V_{\kappa+1}$ is the collection of all classes in the model. Of course, $V_{\kappa+1}$ is the power set of $V_\kappa$ in the universe in which we are building this model, but inside the model, $V_\kappa$ is the (proper) class of all sets, and $V_{\kappa+1}$ is not an object at all, but its elements consist of all the classes that the model can see.
Thanks. This is helpful.
By way of clarification, the classes the model of $KM$ can ‘see’ are just the classes $KM$’s class comprehension principle satisfies, correct?