Tag Archives: global choice
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_\alpha$, 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_\alpha\subseteq\alpha$, such that for any definable class of ordinals $A$ and any definable class club set $C$, there are ordinals $\theta\in C$ with $A\cap\theta=A_\theta$. 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_\alpha$. 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.$\newcommand\restrict\upharpoonright
\newcommand\of\subseteq
\newcommand\Ord{\text{Ord}}
\newcommand\HOD{\text{HOD}}\newcommand\ZFC{\text{ZFC}}$
Theorem. In $\ZFC$, if there is a definable well-ordering of the universe, then $\Diamond_{\Ord}$ holds for definable classes. That is, there is a $p$-definable sequence $\langle A_\alpha\mid\alpha<\Ord\rangle$, such that for any definable class $A\of\Ord$ and any definable closed unbounded class of ordinals $C\of\Ord$ (allowing parameters), there is some $\theta\in C$ with $A\cap\theta=A_\theta$.
Proof. The theorem is proved as a theorem scheme; namely, I shall provide a specific definition for the sequence $\vec A=\langle A_\alpha\mid\alpha<\Ord\rangle$, 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 $A\of\Ord$ and class club $C\of\Ord$, that there is some $\alpha\in C$ with $A\cap\alpha=A_\alpha$. The definitions of the classes $A$ and $C$ may involve parameters and have arbitrary complexity.
Let $\lhd$ be the definable well-ordering of the universe, definable by a specific formula using some parameter $p$. I define the $\Diamond_{\Ord}$-sequence $\vec A=\langle A_\alpha\mid\alpha<\Ord\rangle$ by transfinite recursion. Suppose that $\vec A\restrict\theta$ has been defined. I shall let $A_\theta=\emptyset$ unless $\theta$ is a $\beth$-fixed point above the rank of $p$ and there is a set $A\of\theta$ and a closed unbounded set $C\of\theta$, with both $A$ and $C$ definable in the structure $\langle V_\theta,\in\rangle$ (allowing parameters), such that $A\cap\alpha\neq A_\alpha$ for every $\alpha\in 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 $\lhd\restrict V_\theta$. For this minimal pair, let $A_\theta=A$. This completes the definition of the sequence $\vec A=\langle A_\alpha\mid\alpha\in\Ord\rangle$.
Let me remark on a subtle point, since the meta-mathematical issues loom large here. The definition of $\vec A$ is internal to the model, and at stage $\theta$ we ask about subsets of $\theta$ definable in $\langle V_\theta,\in\rangle$, using the truth predicate for this structure. If we were to run this definition inside an $\omega$-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 $\vec A$ is indeed a $\Diamond_{\Ord}$-sequence for definable classes. The argument follows in spirit the classical proof of $\Diamond$ in $L$, subject to the mathematical issues I mentioned. If the sequence $\vec A$ is not a diamond sequence, then there is some definable class $A\of\Ord$, defined in $\langle V,\in\rangle$ by a specific formula $\varphi$ and parameter $z$, and definable club $C\of\Ord$, defined by some $\psi$ and parameter $y$, with $A\cap\alpha\neq A_\alpha$ for every $\alpha\in 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 $\varphi$ and $\psi$ are as small as possible, and the lengths of the formulas, and the Gödel codes and finally the parameters $z,y$ are $\lhd$-minimal, respectively, successively. Let $m$ be a sufficiently large natural number, larger than the complexity of the definitions of $\lhd$, $A$, $C$, and large enough so that the minimality condition we just discussed is expressible by a $\Sigma_m$ formula. Let $\theta$ be any $\Sigma_m$-correct ordinal above the ranks of the parameters used in the definitions. It follows that the restrictions $\lhd\restrict V_\theta$ and also $A\cap\theta$ and $C\cap\theta$ and $\vec A\restrict\theta$ are definable in $\langle V_\theta,\in\rangle$ by the same definitions and parameters as their counterparts in $V$, that $C\cap\theta$ is club in $\theta$, and that $A\cap\theta$ and $C\cap\theta$ form a minimal pair using those definitions with $A\cap\alpha\neq A_\alpha$ for any $\alpha\in C\cap\theta$. Thus, by the definition of $\vec A$, it follows that $A_\theta=A\cap\theta$. Since $C\cap\theta$ is unbounded in $\theta$ and $C$ is closed, it follows that $\theta\in C$, and so $A_\theta=A\cap\theta$ contradicts our assumption about $A$ and $C$. So there are no such counterexample classes, and thus $\vec A$ is a $\Diamond_{\Ord}$-sequence with respect to definable classes, as claimed.
QED
Theorem. The following are equivalent over $\ZFC$.
- There is a definable well-ordering of the universe, using some set parameter $p$.
- $V=\HOD_{\{p\}}$, for some set $p$.
- $\Diamond_{\Ord}$ holds for definable classes. That is, there is a set parameter $p$ and a definable sequence $\vec A=\langle A_\alpha\mid\alpha<\Ord\rangle$, such that for any definable class $A\of\Ord$ and definable class club $C\of\Ord$, there is some $\alpha\in C$ with $A\cap\alpha=A_\alpha$.
Proof. Let me first give the argument, and then afterward discuss some issues about the formalization, which involves some subtle issues.
($1\to 2$) $\newcommand\rank{\text{rank}}$Suppose that $\lhd$ is a $p$-definable well-ordering of $V$, which means that every set has a $\lhd$-minimal element. Let us refine this order by defining $x\lhd’ y$, just in case $\rank(x)<\rank(y)$ or $\rank(x)=\rank(y)$ and $x\lhd y$. The new order is also a well-order, which now respects rank. In particular, the order $\lhd’$ is set-like, and so every object $x$ is the $\alpha^{th}$ element with respect to the $\lhd’$-order, for some ordinal $\alpha$. Thus, every object is definable from $p$ and an ordinal, and so $V=\HOD_{\{p\}}$, as desired.
($2\to 1$) 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 $x\lhd y$ 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_\theta$ with a smaller $\theta$ than $y$ is, or the ranks are the same and the $\theta$ is the same, but $x$ is definable in that $V_\theta$ 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.
($1\to 3$) This is the content of the theorem above.
($3\to 1$) If $\vec A$ is a $p$-definable $\Diamond_{\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_\alpha$ for unboundedly many $\alpha$. 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 $x\lhd y$, just in case $x$ is coded by a set of ordinals that appears earlier on $\vec A$ than any set of ordinals coding $y$. This is clearly a well-ordering, since the map sending $x$ to the ordinal $\alpha$ for which $A_\alpha$ codes $x$ is an $\Ord$-ranking of $\lhd$. 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 $\Diamond_{\Ord}$-sequence that works for all definable classes. In this sense, we may regard the diamond principle $\Diamond_{\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 $\Diamond_{\Ord}$ in the full second-order sense. For example, it is relatively consistent with ZFC that an inaccessible cardinal $\kappa$ does not have $\Diamond_\kappa$, and in this case, the structure $\langle V_\kappa,\in,V_{\kappa+1}\rangle$ will satisfy GBC and even KM, but it won’t have $\Diamond_{\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_{\kappa+1}$). But meanwhile, there will be a $\Diamond_{\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 $\Diamond_\kappa$ for definable classes in $V_\kappa$, even when the full $\Diamond_\kappa$ fails. Stay tuned!
The global choice principle in Gödel-Bernays set theory
$\newcommand\Ord{\text{Ord}}
\newcommand\R{\mathbb{R}}
\newcommand\HOD{\text{HOD}}$
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)\in 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.
- The global choice principle. That is, there is a class function $F$ such that $F(x)\in x$ for every nonempty set $x$.
- There is a bijection between $V$ and $\Ord$.
- There is a global well-ordering of $V$. That is, there is a class relation $\triangleleft$ on $V$ that is a linear order, such that every nonempty set has a $\triangleleft$-least member.
- There is a global set-like well-ordering of $V$. There is a class well-ordering $\triangleleft$ as above, such that all $\triangleleft$-initial segments are sets.
- Every proper class is bijective with $\Ord$.
- Every class injects into $\Ord$.
- AC holds for sets and $\Ord$ injects into every proper class.
- $\Ord$ surjects onto every class.
- Every class is comparable with $\Ord$ by injectivity; that is, one injects into the other.
- Any two classes are comparable by injectivity.
Proof.
($1\to 2$) Assume that $F$ is a global choice class function. Using the axiom of replacement, we may recursively define a class sequence of sets $\langle x_\alpha\mid\alpha\in\Ord\rangle$, where $x_\alpha=F(X_\alpha)$, where $X_\alpha$ is the set of minimal-rank sets $x$ not among $\{x_\beta\mid\beta<\alpha\}$. 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_\alpha$ 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_\beta$. But this is impossible by Hartog’s theorem, and so in fact we have bijection between $\Ord$ and $V$.
($2\to 3$) 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.
($3\to 1$) Let $F(x)$ be the least element of $x$ with respect to a fixed global well-ordering.
($3\to 4$) If there is a global well-ordering $<$, then we may refine it to a set-like well-ordering, by defining $x\triangleleft y$ 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 $\triangleleft$-least member of the set of members of $X$ having minimal rank. The relation $\triangleleft$ is set-like, because the $\triangleleft$-predecessors of any set $x$ are amongst the sets having rank no larger than $x$, and this is a set.
($4\to 5$) 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 $\alpha$ to the $\alpha^{th}$ member of $X$. This will be a bijection of $\Ord$ with $X$.
($5\to 6$) If every proper class is bijective with $\Ord$, then $V$ is bijective with $\Ord$, and so every set injects into $\Ord$ by restriction.
($6\to 7$) 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 $\alpha$ to the $\alpha^{th}$ member of the class, and so every proper class is bijective with $\Ord$. So $\Ord$ injects the other way, and also AC holds.
($7\to 3$) 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_\alpha$ of the set-theoretic universe $V$. Since for each $\alpha$ there are only a set number of such well-orderings of $V_\alpha$, if we inject $\Ord$ into $W$, then there must be well-orderings of unboundedly many $V_\alpha$ 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_\alpha$ to appear in the range of the injection.
($5\to 8$) Immediate.
($8\to 3$) 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$.
($6\to 9$) Immediate.
($9\to 3$) 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_\alpha$, 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$.
($5\to 10$) 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.
($10\to 9$) 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_\alpha^{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 $W_0\subset W$ 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 $x\in W$ to $\alpha$, if the rank of $x$ is the $\alpha^{th}$ ordinal that is the rank of any element of $W$.