Is cardinality a well defined function?

I was wondering if the cardinality of a set is a well defined function, more specifically, does it have a well defined domain and range?

One would say you could assign a number to every finite set, and a cardinality for an infinite set. So the range would be clear, the set of cardinal numbers. But what about the domain, here we get a few problems. This should be the set of all sets, yet this concept isn't allowed in mathematics as it leads to paradoxes like Russell's paradox.

So how do we formalize the notion of 'cardinality'? It seems to behave like a function that maps sets into cardinal numbers, but you can't define it this way as that definition would be based on a paradoxical notion. Even if we only restrict ourselves to finite sets the problem pops up, as we could define the set {A} for every set, thereby showing a one-to-one correspondence between 'the set of all sets' (that doesn't exist) and the 'set of all sets with one element'.

So how should one look at the concept of cardinality? You can't reasonably call it a function. Formalizing this concept without getting into paradoxes seems very hard indeed.

Solution 1:

The cardinality function is well-defined, but it is what known as a class function. Since every set has a cardinality, the domain of the function $A\mapsto |A|$ has to be the class of all sets, so this is indeed a proper class. And since every set has a strictly large cardinal, the class of cardinals is not a set either.

Using the axioms of set theory, we can canonically determine an object, in the set theoretic universe, which will represent the cardinal $|A|$. So the function $A\mapsto|A|$ is indeed definable.

It should be pointed, perhaps, that this class function is also amenable. Namely, restricting it to any set of sets will result in a function which is itself a set. Namely, a set of sets can only have a set of distinct cardinals. This is a direct consequence of the Replacement axiom.

There is some inherent difficulty at first when talking about existence of proper classes, and whether or not they are well-defined objects. In the case of $\sf ZFC$ and related theories, existence means "a set", but when we say that a class exists and it is well-defined, we mean to say that there is a definition which is provably giving us the function that we want. This is the case in your question.

But one can also work in class theories like $\sf KM$ (Kelley–Morse) or $\sf NBG$ (von Neumann–Godel–Bernays), and there the function assigning every set its cardinality is still a class function and not a set, but now it exists in "an internal way" as an object of the universe.

Solution 2:

The collection of all sets does not form a set in ZF(-style) set theory, indeed. Note that the same is true for the collection of all cardinals: there is no set containing all cardinals, because then its union would be a set as well, and it would be a greater cardinal than any of its elements.

So the function $X \mapsto |X|$ is not a function internally to ZFC. However, it can be made a function externally: that is, there is a formula $\phi(x,y)$, in two free variables, which holds if and only if $y$ is the cardinality of $x$. For this formula, we can prove $\phi(x,y) \land \phi(x,y') \to y = y'$, and we can prove $\forall x \exists y \phi(x,y)$. Hence, if we want to, we can introduce a function symbol $\mathrm{Card}$ to the language of set theory, such that $\mathrm{Card}(x)$ is interpreted as the unique $y$ such that $\phi(x,y)$. This is fine for the purposes for which we want to use cardinality.

Note also that if you are looking at a more limited part of the universe of sets, say $V_\alpha$ for some ordinal $\alpha$, then the restriction of the meta-function $\mathrm{Card}$ to this set does form a set.

Solution 3:

Being equinumerous or bijective is an equivalence relation on sets: $x\equiv y$ iff there is a bijection $f:x\text{ onto }y$. The problem is to define a total set function (a proper class of course) $F$ satisfying $x\equiv y$ iff $F(x)=F(y)$.

In ZFC this is done by the cardinality function $F(x)=\text{card}(x)$, whose values are cardinals, and it satisfies $x\equiv F(x)$, that is, is a true transversal.

In ZF, this is done by $F(x)=$ the set of all sets $y$ with $x\equiv y$, which have the least von Neumann's rank among all such sets, and then generally $x\not\equiv F(x)$, of course.

I don't know though if anyone has succeed to prove that in ZF there is no true transversal for $\equiv$.