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
Let me dive right in to the main part of the argument.
Theorem. In
Proof. The theorem is proved as a theorem scheme; namely, I shall provide a specific definition for the sequence
Let
Let me remark on a subtle point, since the meta-mathematical issues loom large here. The definition of
Let me now prove that the sequence
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.
(
(
(
(
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
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
This leads to several extremely interesting questions, about which I am currently thinking, concerning instances where we can have
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
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
such that for every nonempty set . - There is a bijection between
and . - There is a global well-ordering of
. That is, there is a class relation on that is a linear order, such that every nonempty set has a -least member. - There is a global set-like well-ordering of
. There is a class well-ordering as above, such that all -initial segments are sets. - Every proper class is bijective with
. - Every class injects into
. - AC holds for sets and
injects into every proper class. surjects onto every class.- Every class is comparable with
by injectivity; that is, one injects into the other. - Any two classes are comparable by injectivity.
Proof.
(
(
(
(
(
(
(
(
(
(
(
(
(
(
QED
Let’s notice a few things.
First, we cannot omit the AC assertion in statement 7. To see this, consider the model
must be a proper subclass
elements of
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
arising as the rank of an element of