FOM: Cardinality Operators

[Harvey Friedman]

Parsons 6:04PM 1/26/00 has asked whether there is a definable cardinality
operator for classes in class theory. He (essentially) observes that if the
class theory contains a weak form of the axiom of global choice (any two
proper classes are equinumerous), then the answer is clearly yes, since we
can use a well known construction of Scott for the sets, and the proper
classes all have the same cardinality.

By the way, the full axiom of global choice asserts that the class of all
sets is well ordered. Another form of choice is "choice for classes" which
asserts that for every class of pairwise disjoint nonempty sets has a
choice class. And then there is the above "any two proper classes are
equinumerous." All three are equivalent over VB (von Neumann Bernays class
theory). This is all well known.

Digression: Is NBG or VB more historically accurate as a name for this
class theory? I.e., what exactly was Godel's role?

We now give a sketch of a proof that the answer to this question is NO. I
would like some of the subscribers who are experts in forcing to look at
this sketch.

First let me be more formal about the question.

Since we are getting a negative answer, we use the strongest commonly
considered class theory for such a purpose. This is MK + AxC, which is the
Morse-Kelley theory of classes together with the axiom of choice for sets
only.

There are several ways to present MK and related theories of classes, which
are equivalent in the appropriate relevent senses. We use a single sorted
formulation with the predicate M(x) = "the class x is a set." Thus all
quantifiers range over classes. Let AxC be the usual axiom of choice for
sets; e.g., every set of pairwise disjoint nonempty sets has a choice set.

Now here is the question. Is there a formula phi(x,y) in the language of
MK, with at most the free variables shown, such that

i) MK + AxC proves (forall x)(therexists unique y)(phi(x,y));
ii) MK + AxC proves (forall x,y)(if x,y are equinumerous then (there exists
z)(phi(x,z) and phi(y,z)))?

We construct a countable transitive model R of MK such that for no formula
phi(x,y) is it the case that both those sentences holds in N. In fact, we
show that this holds even if parameters for classes are allowed in phi.

We start the construction with a countable transitive model M of MK +"every
class is constructible", where constructibility is formulated in terms of
well orderings on the class of all sets.  We also want M to be a beta model
in the sense that all internal well orderings on the class of sets are in
fact well orderings.

The existence of such an M follows easily from ZFC + "there exists an
inaccessible cardinal." However, the proof that we give can, by various
standard tricks, be redone just using the consistency of MK.

We write M' for the set part of M, which is a model of ZFC + V=L.

Let N' be a generic extension of M' obtained by Easton forcing in the
simplified situation where we add only an omega^2 sequence of generic
subsets of each uncountable successor cardinal of M'. N' satisfies ZFC.

We think of N' as being obtained from M' by adding a single generic class,
which we write as a function F:On x omega x omega into P(On), where P(On)
is the class of all sets of ordinal numbers. The idea is that F(alpha,n,m)
is the (omega x n  + m)-th subset of the alpha-th uncountable successor
cardinal added.

It is straightforward to verify that N' canonically generates a model N of
MK + AxC + "every class is constructible from F." AxC is the usual axiom of
choice for sets, but in fact, N satisfies MKC = MK + global choice, where
global choice asserts that the class of all sets is well ordered.

For each n < omega, let X(n,F) = {F(alpha,n,m): alpha is an ordinal and m <
omega}. Thus X(0,F),X(1,F),... forms a decomposition of the sets added by
the Easton forcing. Each of the X(n,F) are classes in N, and by a standard
forcing argument, they are mutually disjoint.

The final model, R, will be a submodel of N. Namely, R will be the model of
MK obtained from starting with N' and the X(n,F), and building the
construcible hierarchy of classes. This construction is easily made within
N using the fact that the sequence of these classes is a class in N.

In particular, it can be shown that R is a submodel of N that has the same
sets, and R is a model of MK + AxC.

By standard forcing arguments, it can also be seen that R consists of the
elements of N that are definable in N with parameters that are from N' and
from the X(n,F), n < omega.

It can now be verified by standard forcing arguments that none of the
X(n,F) are equinumerous in R.

Now assume that we have the phi(x,y) satisfying i) and ii), without
parameters. Then in R, the value of phi at the various X(n,F) must be
distinct.

Let n < omega. Look at the A = X(n,F). Now in R, A is a class of countably
infinite subsets of the uncountable successor cardinals in R; i.e., one
countably infinite subset of each uncountable successor cardinal. That is,
the enumerations of each of the elements of A exist in R.

For each ordinal alpha in R, consider A\V(alpha). It is easy to verify that
in R, these A\V(alpha) are all equinumerous. This is a consequence of AxC
in R. Hence the values of phi at the various A\V(alpha) are identical.

By a standard forcing arguement, this establishes that the value of phi at
A = X(n,F) is definable in N without any parameters. Since n is arbitrary,
we see by another standard forcing argument that the values of phi at the
various X(n,F) are identical, which is the desired contradiction.

The argument can be easily modified in the standard way to allow for
parameters in phi. I.e., there is no formula phi(x,y,z_1,...,z_k) in the
language of MK, with at most the free variables shown, such that MK + AxC
proves

(therexists z_1,...,z_k)[(forall x)(therexists unique
y)(phi(x,y,z_1,...,z_k)) and (forall x,y)(if x,y are equinumerous then
(there exists w)(phi(x,w,z_1,...,z_k) and phi(y,w,z_1,...,z_k)))].