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 , 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 , such that for any definable class of ordinals and any definable class club set , there are ordinals with . 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 . Since every large object 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 , if there is a definable well-ordering of the universe, then holds for definable classes. That is, there is a -definable sequence , such that for any definable class and any definable closed unbounded class of ordinals (allowing parameters), there is some with .
Proof. The theorem is proved as a theorem scheme; namely, I shall provide a specific definition for the sequence , using the same parameter 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 and class club , that there is some with . The definitions of the classes and may involve parameters and have arbitrary complexity.
Let be the definable well-ordering of the universe, definable by a specific formula using some parameter . I define the -sequence by transfinite recursion. Suppose that has been defined. I shall let unless is a -fixed point above the rank of and there is a set and a closed unbounded set , with both and definable in the structure (allowing parameters), such that for every . In this case, I choose the least such pair , minimizing first on the maximum of the logical complexities of the definitions of and of , and then minimizing on the total length of the defining formulas of and , and then minimizing on the Gödel codes of those formulas, and finally on the parameters used in the definitions, using the well-order . For this minimal pair, let . This completes the definition of the sequence .
Let me remark on a subtle point, since the meta-mathematical issues loom large here. The definition of is internal to the model, and at stage we ask about subsets of definable in , 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 would not actually be definable by a standard formula. Also, even when is definable by a standard formula, it might be paired (with some constants), with a club set that is defined only by a nonstandard formula (and this is why we minimize on the maximum of the complexities of the definitions of and 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 .
Let me now prove that the sequence is indeed a -sequence for definable classes. The argument follows in spirit the classical proof of in , subject to the mathematical issues I mentioned. If the sequence is not a diamond sequence, then there is some definable class , defined in by a specific formula and parameter , and definable club , defined by some and parameter , with for every . 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 are -minimal, respectively, successively. Let be a sufficiently large natural number, larger than the complexity of the definitions of , , , and large enough so that the minimality condition we just discussed is expressible by a formula. Let be any -correct ordinal above the ranks of the parameters used in the definitions. It follows that the restrictions and also and and are definable in by the same definitions and parameters as their counterparts in , that is club in , and that and form a minimal pair using those definitions with for any . Thus, by the definition of , it follows that . Since is unbounded in and is closed, it follows that , and so contradicts our assumption about and . So there are no such counterexample classes, and thus is a -sequence with respect to definable classes, as claimed.
QED
Theorem. The following are equivalent over .
- There is a definable well-ordering of the universe, using some set parameter .
- , for some set .
- holds for definable classes. That is, there is a set parameter and a definable sequence , such that for any definable class and definable class club , there is some with .
Proof. Let me first give the argument, and then afterward discuss some issues about the formalization, which involves some subtle issues.
() Suppose that is a -definable well-ordering of , which means that every set has a -minimal element. Let us refine this order by defining , just in case or and . The new order is also a well-order, which now respects rank. In particular, the order is set-like, and so every object is the element with respect to the -order, for some ordinal . Thus, every object is definable from and an ordinal, and so , as desired.
() If , then we have the canonical well-order of using parameter , similar to how one shows that the axiom of choice holds in . Namely, define if and only if , or the ranks are the same, but is definable from and ordinal parameters in some with a smaller than is, or the ranks are the same and the is the same, but is definable in that 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 -definable well-ordering of the universe.
() This is the content of the theorem above.
() If is a -definable -sequence for definable classes, then it is easy to see that if is a set of ordinals, then must arise as for unboundedly many . In , 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 , just in case is coded by a set of ordinals that appears earlier on than any set of ordinals coding . This is clearly a well-ordering, since the map sending to the ordinal for which codes is an -ranking of . So there is a -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 and are bounded. Basically, once one gets the global well-order, then one can construct a -sequence that works for all definable classes. In this sense, we may regard the diamond principle 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 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 will satisfy GBC and even KM, but it won’t have with respect to all classes, even though it has a definable well-ordering of the universe (since there is such a well-ordering in ). But meanwhile, there will be a -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 , even when the full fails. Stay tuned!
Are there any similar theorems for rather than ?
Merry Christmas!
I’ve been thinking about it, but I don’t have anything yet. Ali Enayat and I are writing up a paper with this result and some others.
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 to have a supercompact cardinal at singulars.
and then square fails above
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 is not a sequence. If there were no definable and like that, then it would be a sequence.