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.

  1. The global choice principle. That is, there is a class function $F$ such that $F(x)\in 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 $\triangleleft$ on $V$ that is a linear order, such that every nonempty set has a $\triangleleft$-least member.
  4. 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.
  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. 

($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$.

7 thoughts on “The global choice principle in Gödel-Bernays set theory

  1. Hello:
    Your proof for 1→2 is quite difficult for me.And I think I have a easy way to prove.Thus can you have a look for me whether or not there is any mistake.

    For any ordinal number”α”.By the definition of the ordinal numbers there is a unique well-ordered set “A” isomorphism with “α”.And by the definition of “V”(every set is a member of it).It follows that Ord→V is injective.

    Now,for any Vβ∈V(“β” is a abitrary ordinal number),by the axiom of global choice,there is a class function such that can map any set in Vβ to a set “A” bijectively and A⊂Ord.Hence Ord→V is surjective.

    Therefore Ord→V is bijective.

    I am a 19 years old student who are fascinated in mathematics.Thus I am really looking forward you can tell me is there any mistake or insufficient part I have ignored and point it out.Thank you!

    King regards!

    • How impressive to engage with this kind of set theory for such a young student! I am sure that you have a positive future ahead of you.

      Meanwhile, your argument needs to be fleshed out. I think there is a problem in your third paragraph. You seem to be arguing that if every $V_\beta$ can be mapped bijectively to a set of ordinals, then we can fit these together to have a surjection from Ord to $V$. But in general, this isn’t true, since the axiom of choice is known to be weaker than the global axiom of choice. In a model with AC but not global AC, we have that every $V_\beta$ is bijective with a set of ordinals, but there is no way to put those bijections together coherently to form a class bijection of the entire universe $V$ with a class of ordinals. Thus, the key issue in the implication $(1\to 2$) is to use the global choice function to establish a uniform manner of enumerating all the sets in the universe.

      By the way, if you find the argument that I gave difficult, then I would suggest that you take a look at the usual proof, due to Zermelo, that the choice-function version of AC is equivalent to the well-order principle, since the underlying idea is the same in both cases. The complication here is the presence of proper classes, but if you master the original argument, I think you will be able to follow it better.

      • Thank you very much for your help.Actually,lot’s of set theory’s book use Zermelo’s system instead of von Neumann’s system.I don’t know why.Is it still in argument between mathematicans.

        Besides,as I have mentioned above,I don’t know what axiom of global choice exactly is.I can’t understand what you mean by class function “F”.You said F(x) where “x” is a non-empty set.And there is no relationship related to proper class.Therefore can you state this axiom more explicity.I want to prove that several consequence by myself.Thank you!

  2. Dear Author:
    For your (1→2),I can’t comprehend such abstract terms.But I have a new idea for that.Due to my limited knowledge.I will use a simple example to show my thought briefly:

    If we want to map a sequenceA={x1,x2,x3,…,xn,x(n+1),…}(with all the subsets included in A,such as{x1,x2}) bijectively into Ord.And suppose there is a relationship in A with”x1<x2<x3<…<xn<x(n+1)<…"then we can operate by induction:

    Suppose we have mapped B={x1,x2,x3,…,xn}(with all the subsets included in B)bijectively to a subset of Ord(which means it has been well-ordered).Then we can well-order the sets with "x(n+1)" is the last element(such as{X,x(n+1)} while "X"is any subset of "B"}.
    By assumption,it can be well-ordered(As "B"can be well-ordered).therefore sequence "A" can be injected to Ord.

    The same idea we can put in the model V.the transition from Vα to V(α+1) can be operated in the same way of above.Thus there is an injection from V→Ord.I don't know where does the axiom of global choice appear?Is this the key idea?Thanks!

Leave a Reply