Kelley-Morse set theory does not prove the class Fodor Principle, CUNY Set Theory Seminar, March, 2019

This will be talk for the CUNY Set Theory seminar, Friday, March 22, 2019, 10 am in room 6417 at the CUNY Graduate Center.
Abstract. I shall discuss recent joint work with Victoria Gitman and Asaf Karagila, in which we proved that Kelley-Morse set theory (which includes the global choice principle) does not prove the class Fodor principle, the assertion that every regressive class function F:SOrd defined on a stationary class S is constant on a stationary subclass. Indeed, it is relatively consistent with KM for any infinite λ with ωλOrd that there is a class function F:Ordλ that is not constant on any stationary class. Strikingly, it is consistent with KM that there is a sequence of classes An, each containing a class club, but the intersection of all An is empty. Consequently, it is relatively consistent with KM that the class club filter is not σ-closed.
I am given to understand that the talk will be streamed live online. I’ll post further details when I have them.

Diamond on the ordinals

I was recently surprised to discover that if there is a definable well-ordering of the universe, then the diamond principle on the ordinals holds for definable classes, automatically. In fact, the diamond principle for definable classes is simply equivalent in ZFC to the existence of a definable well-ordering of the universe. It follows as a consequence that the diamond principle for definable classes, although seeming to be fundamentally scheme-theoretic, is actually expressible in the first-order language of set theory.

In set theory, the diamond principle asserts the existence of a sequence of objects Aα, of growing size, such that any large object at the end is very often anticipated by these approximations.  In the case of diamond on the ordinals, what we will have is a definable sequence of Aαα, such that for any definable class of ordinals A and any definable class club set C, there are ordinals θC with Aθ=Aθ.  This kind of principle typically allows one to undertake long constructions that will diagonalize against all the large objects, by considering and reacting to their approximations Aα. Since every large object A is often correctly approximated that way, this enables many such constructions to succeed.

Let me dive right in to the main part of the argument.

Theorem. In ZFC, if there is a definable well-ordering of the universe, then Ord holds for definable classes. That is, there is a p-definable sequence Aαα<Ord, such that for any definable class AOrd and any definable closed unbounded class of ordinals COrd (allowing parameters), there is some θC with Aθ=Aθ.

Proof. The theorem is proved as a theorem scheme; namely, I shall provide a specific definition for the sequence A=Aαα<Ord, using the same parameter p as the definition of the global well-order and with a definition of closely related syntactic complexity, and then prove as a scheme, a separate statement for each definable class AOrd and class club COrd, that there is some αC with Aα=Aα. The definitions of the classes A and C may involve parameters and have arbitrary complexity.

Let be the definable well-ordering of the universe, definable by a specific formula using some parameter p. I define the Ord-sequence A=Aαα<Ord by transfinite recursion. Suppose that Aθ has been defined. I shall let Aθ= unless θ is a -fixed point above the rank of p and there is a set Aθ and a closed unbounded set Cθ, with both A and C definable in the structure Vθ, (allowing parameters), such that AαAα for every αC. In this case, I choose the least such pair (A,C), minimizing first on the maximum of the logical complexities of the definitions of A and of C, and then minimizing on the total length of the defining formulas of A and C, and then minimizing on the Gödel codes of those formulas, and finally on the parameters used in the definitions, using the well-order ⊲↾Vθ. For this minimal pair, let Aθ=A. This completes the definition of the sequence A=AααOrd.

Let me remark on a subtle point, since the meta-mathematical issues loom large here. The definition of A is internal to the model, and at stage θ we ask about subsets of θ definable in Vθ,, using the truth predicate for this structure. If we were to run this definition inside an ω-nonstandard model, it could happen that the minimal formula we get is nonstandard, and in this case, the set A would not actually be definable by a standard formula. Also, even when A is definable by a standard formula, it might be paired (with some constants), with a club set C that is defined only by a nonstandard formula (and this is why we minimize on the maximum of the complexities of the definitions of A and C together). So one must give care in the main argument keeping straight the distinction between the meta-theoretic natural numbers and the internal natural numbers of the object theory ZFC.

Let me now prove that the sequence A is indeed a Ord-sequence for definable classes. The argument follows in spirit the classical proof of in L, subject to the mathematical issues I mentioned. If the sequence A is not a diamond sequence, then there is some definable class AOrd, defined in V, by a specific formula φ and parameter z, and definable club COrd, defined by some ψ and parameter y, with AαAα for every αC. We may assume without loss that these formulas are chosen so as to be minimal in the sense of the construction, so that the maximum of the complexities of φ and ψ are as small as possible, and the lengths of the formulas, and the Gödel codes and finally the parameters z,y are -minimal, respectively, successively. Let m be a sufficiently large natural number, larger than the complexity of the definitions of , A, C, and large enough so that the minimality condition we just discussed is expressible by a Σm formula. Let θ be any Σm-correct ordinal above the ranks of the parameters used in the definitions. It follows that the restrictions ⊲↾Vθ and also Aθ and Cθ and Aθ are definable in Vθ, by the same definitions and parameters as their counterparts in V, that Cθ is club in θ, and that Aθ and Cθ form a minimal pair using those definitions with AαAα for any αCθ. Thus, by the definition of A, it follows that Aθ=Aθ. Since Cθ is unbounded in θ and C is closed, it follows that θC, and so Aθ=Aθ contradicts our assumption about A and C. So there are no such counterexample classes, and thus A is a Ord-sequence with respect to definable classes, as claimed.
QED

Theorem. The following are equivalent over ZFC.

  1. There is a definable well-ordering of the universe, using some set parameter p.
  2. V=HOD{p}, for some set p.
  3. Ord holds for definable classes. That is, there is a set parameter p and a definable sequence A=Aαα<Ord, such that for any definable class AOrd and definable class club COrd, there is some αC with Aα=Aα.

Proof. Let me first give the argument, and then afterward discuss some issues about the formalization, which involves some subtle issues.

(12) Suppose that is a p-definable well-ordering of V, which means that every set has a -minimal element. Let us refine this order by defining xy, just in case rank(x)<rank(y) or rank(x)=rank(y) and xy. The new order is also a well-order, which now respects rank. In particular, the order is set-like, and so every object x is the αth element with respect to the -order, for some ordinal α. Thus, every object is definable from p and an ordinal, and so V=HOD{p}, as desired.

(21) If V=HOD{p}, then we have the canonical well-order of HOD using parameter p, similar to how one shows that the axiom of choice holds in HOD. Namely, define xy if and only if rank(x)<rank(y), or the ranks are the same, but x is definable from p and ordinal parameters in some Vθ with a smaller θ than y is, or the ranks are the same and the θ is the same, but x is definable in that Vθ by a formula with a smaller Gödel code, or with the same formula but smaller ordinal parameters. It is easy to see that this is a p-definable well-ordering of the universe.

(13) This is the content of the theorem above.

(31) If A is a p-definable Ord-sequence for definable classes, then it is easy to see that if A is a set of ordinals, then A must arise as Aα for unboundedly many α. In ZFC, using the axiom of choice, it is a standard fact that every set is coded by a set of ordinals. So let us define that xy, just in case x is coded by a set of ordinals that appears earlier on A than any set of ordinals coding y. This is clearly a well-ordering, since the map sending x to the ordinal α for which Aα codes x is an Ord-ranking of . So there is a p-definable well-ordering of the universe.
QED

An observant reader will notice some meta-mathematical issues concerning the previous theorem. The issue is that statements 1 and 2 are known to be expressible by statements in the first-order language of set theory, as single statements, but for statement 3 we have previously expressed it only as a scheme of first-order statements. So how can they be equivalent? The answer is that the full scheme-theoretic content of statement 3 follows already from instances in which the complexity of the definitions of A and C are bounded. Basically, once one gets the global well-order, then one can construct a Ord-sequence that works for all definable classes. In this sense, we may regard the diamond principle Ord for definable classes as not really a scheme of statements, but rather equivalent to a single first-order assertion.

Lastly, let me consider the content of the theorems in Gödel-Bernays set theory or Kelley-Morse set theory. Of course, we know that there can be models of these theories that do not have Ord in the full second-order sense. For example, it is relatively consistent with ZFC that an inaccessible cardinal κ does not have κ, and in this case, the structure Vκ,,Vκ+1 will satisfy GBC and even KM, but it won’t have Ord with respect to all classes, even though it has a definable well-ordering of the universe (since there is such a well-ordering in Vκ+1). But meanwhile, there will be a Ord-sequence that works with respect to classes that are definable from that well-ordering and parameters, simply by following the construction given in the theorem.

This leads to several extremely interesting questions, about which I am currently thinking, concerning instances where we can have κ for definable classes in Vκ, even when the full κ fails. Stay tuned!

The global choice principle in Gödel-Bernays set theory

I’d like to follow up on several posts I made recently on MathOverflow (see here, here and here), which engaged several questions of Gérard Lang that I found interesting. Specifically, I’d like to discuss a number of equivalent formulations of the global choice principle in Gödel-Bernays set theory. Let us adopt the following abbreviations for the usually considered theories:

  • GB is the usual Gödel-Bernays set theory without any choice principle.
  • GB+AC is GB plus the axiom of choice for sets.
  • GBC is GB plus the global choice principle.

The global choice principle has a number of equivalent characterizations, as proved in the theorem below, but for definiteness let us take it as the assertion that there is a global choice function, that is, a class F which is a function such that F(x)x for every nonempty set x.

Note in particular that I do not use the set version of choice AC in the equivalences, since most of the statements imply AC for sets outright (except in the case of statement 7, where it is stated specifically in order to make the equivalence).

Theorem. The following are equivalent over GB.

  1. The global choice principle. That is, there is a class function F such that F(x)x for every nonempty set x.
  2. There is a bijection between V and Ord.
  3. There is a global well-ordering of V. That is, there is a class relation on V that is a linear order, such that every nonempty set has a -least member.
  4. There is a global set-like well-ordering of V. There is a class well-ordering as above, such that all -initial segments are sets.
  5. Every proper class is bijective with Ord.
  6. Every class injects into Ord.
  7. AC holds for sets and Ord injects into every proper class.
  8. Ord surjects onto every class.
  9. Every class is comparable with Ord by injectivity; that is, one injects into the other.
  10. Any two classes are comparable by injectivity.

Proof. 

(12) Assume that F is a global choice class function. Using the axiom of replacement, we may recursively define a class sequence of sets xααOrd, where xα=F(Xα), where Xα is the set of minimal-rank sets x not among {xββ<α}. That is, we use F to choose the next element among the minimal-rank sets not yet chosen. Thus, we have an injection of V into Ord. If a set x does not appear as some xα on this sequence, then no set of that rank or higher can appear, since we always add sets of the minimal rank not yet having appeared; thus, in this case we will have injected Ord into some Vβ. But this is impossible by Hartog’s theorem, and so in fact we have bijection between Ord and V.

(23) If there is a bijection between Ord and V, then we may define a global well-ordering by x<y if x appears before y in that enumeration.

(31) Let F(x) be the least element of x with respect to a fixed global well-ordering.

(34) If there is a global well-ordering <, then we may refine it to a set-like well-ordering, by defining xy just in case the rank of x is less than the rank of y, or they have the same rank and x<y. This relation is still a well-order, since the least member of any nonempty set X will be the -least member of the set of members of X having minimal rank. The relation is set-like, because the -predecessors of any set x are amongst the sets having rank no larger than x, and this is a set.

(45) If there is a global set-like well-ordering < of V and X is a proper class, then < on X is a well-ordering of X, and we may map any ordinal α to the αth member of X. This will be a bijection of Ord with X.

(56) If every proper class is bijective with Ord, then V is bijective with Ord, and so every set injects into Ord by restriction.

(67) If every class injects into Ord, then in particular, V injects into Ord. The image of this injection is a proper class subclass of Ord, and all such classes are bijective with Ord by mapping α to the αth member of the class, and so every proper class is bijective with Ord. So Ord injects the other way, and also AC holds.

(73) Suppose that AC holds and Ord injects into every proper class. Let W be the class of all well-orderings of some rank-initial segment Vα of the set-theoretic universe V. Since for each α there are only a set number of such well-orderings of Vα, if we inject Ord into W, then there must be well-orderings of unboundedly many Vα in the range of the injection. From this, we may easily construct a global well-ordering of V, by defining x<y just in case x has lower rank than y, or they have the same rank and x<y in the first well-ordering of a sufficiently large Vα to appear in the range of the injection.

(58) Immediate.

(83) If Ord surjects onto V, then there is a global well-ordering, defined by x<y if the earliest appearance of x in the surjection is earlier than that of y.

(69) Immediate.

(93) Assume every class is comparable with Ord via injectivity. It follows that AC holds for sets, since Ord cannot inject into a set, and if a set injects into Ord then it is well-orderable. Now, if Ord injects into the class W used above, consisting of all well-orderings of a Vα, then we saw before that we can build a well-ordering of V. And if W injects into Ord, then W is well-orderable and we can also in this case build a well-ordering of V.

(510) If V is bijective with Ord, then every class is bijective with Ord or with an ordinal, and these are comparable by injections. So any two classes are comparable by injections.

(109) Immediate.

QED

Let’s notice a few things.

First, we cannot omit the AC assertion in statement 7. To see this, consider the model V=L(R), in a case where it does not satisfy AC. I claim that in this model, Ord injects into every proper class that is definable from parameters. The reason is that every object in L(R) is definable from ordinal and real parameters, and indeed, definable in some VαL(R) by some real and ordinal parameters. Indeed, one needs only one ordinal and real parameter. If W is any proper class, then there
must be a proper subclass W0W whose elements are all defined by the same definition in this way. And by partitioning further, we may find a single real that works with various ordinal parameters using that definition to define a proper class of
elements of W. Thus, we may inject Ord into W, even though AC fails in L(R).

Second, the surjectivity analogues of a few of the statements are not equivalent to global choice. Indeed, ZF proves that every proper class surjects onto Ord, with no choice at all, since if W is a proper class, then there are unboundedly many ordinals
arising as the rank of an element of W, and so we may map each element xW to α, if the rank of x is the αth ordinal that is the rank of any element of W.