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!

5 thoughts on “Diamond on the ordinals

  1. Maybe I am wrong, but I don’t understand the situation for square. It claims the existence of a sequence where the elements of the sequence have relations between them. While for diamond we have a sequence and we want to guess some some sets. So by restricting the sets to definable ones, we have fewer sets and it is easier to build a diamond relative to them.

    Also it is consistent with V=HOD to have a supercompact cardinal κ,
    and then square fails above κ at singulars.

  2. I don’t see why there must be an A “such that A∩α≠A_α for every α∈C”. I must be missing something

    • If you are referring to the argument in the last paragraph of the main theorem, then this follows from the assumption (toward contradiction) that AααOrd is not a sequence. If there were no definable A and C like that, then it would be a sequence.

Leave a Reply to Joel David Hamkins Cancel reply

Your email address will not be published. Required fields are marked *