Defining cardinality in the absence of choice
Under ZFC we can define cardinality $|A|$ for any set $A$ as $$ |A|=\min\{\alpha\in \operatorname{Ord}: \exists\text{ bijection } A \to \alpha\}. $$ This is because the axiom of choice allows any set to be well-ordered, so that the set after $\min$ is nonempty.
If we don't assume the axiom of choice (i.e. work in ZF), then there's (at least) two approaches to cardinality. The first is that we use the same definition as above. However, the definition makes sense only for those sets that can be well-ordered. Hence the price we pay for the absence of choice is that cardinality of some sets (the nonwellorderable) is left undefined. But note that even though $|A|$ does not necessarily make sense for all sets $A$ in this approach, the various equalities and inequalities of the form $|A|=|B|$, $|A|\leq|B|$ etc. do, since we can always interpret them as shorthands for "there is a bijection/injection $A\to B$".
The second approach is that we define cardinality for all the sets in the universe using Scott's trick (hopefully I'll get it right): $$ \gamma(A)=\min\{\alpha\in\operatorname{Ord}:\exists x\in V_\alpha\ \exists\text{ bijection }A\to x\} $$ and $$ |A|=\{x\in V_{\gamma(A)}:\exists\text{ bijection }A\to x\}. $$ We manage to define cardinality for all the sets in such a way that $|A|=|B|$ iff there is a bijection $A \to B$. However, to me it seems that this time the price we have to pay is that the we get very unnatural cardinals compared to the first. For example
- cardinals seem to be quite complicated sets compared to the plain and simple initial ordinals of the first approach,
- $|\alpha|=\alpha$ does not hold for most (any?) of the initial ordinals $\alpha$ anymore,
- $|0|=1$, $|1|=\{1\}$, etc.
My question is that what do we gain, if anything, using the second approach (besides managing to define cardinality for all the sets)? Is it an unnecessary complication having no actual advantage over the first approach (i.e. just a trick) or does it have a real use in ZF set theory?
Solution 1:
The idea behind Scott's trick of turning the equivalence classes into rather complicated sets is merely to allow working with the partial order of cardinalities within the theory with ease.
In the presence of AC, we can always pick a canonical example for each cardinality, namely the initial ordinal of the equivalence class.
It is consistent with ZF that no choice of canonical representatives exist. Namely, there is no definable class-function $C$ such that for all $X\in V$:
- $C(X)=C(Y)\iff |X|=|Y|$;
- $|C(X)|=|X|$
This sort of $C$ exists naturally with the axiom of choice, as I have mentioned above. It seems that we somewhat take for granted this existence.
With or without the axiom of choice we can consider $|X|$ as in Scott's trick, namely taking the equipollent sets of the least possible rank. However with the axiom of choice we can set $C(X)=\min\{a\in Ord\mid |X|=|a|\}$, and just assume $|X|=C(X)$.
The point is that without the axiom of choice we simply cannot have this luxury, and we are reduced to handling these complicated sets of cardinalities. This is just one more reason why the cardinal arithmetics become so heavy when leaving the axiom of choice behind.
When canonical representatives are not guaranteed, the use of Scott's trick become essential when writing theorems about cardinalities.
Suppose $A$ is amorphous (that is $B\subseteq A$ implies $B$ is finite or $A\setminus B$ is finite).
I want to describe $(\{|Y|\colon Y\subseteq A\},<)$. Using Scott's trick this is easily done, since $Y\mapsto |Y|$ is a definable function, the domain of this partially ordered set is definable nicely from $A$.
However using the first approach I am left to wonder what is the domain of the cardinalities of subsets of $A$? In this approach $|A|$ is a syntactic object, not semantic.
I can describe that this is a linearly ordered set (i.e. every two subsets of $A$ have comparable cardinalities) but can I prove that this set is exactly $\omega+\omega^*$? (that is to say, a linear order in which every point has either finitely many points above or finitely below; but not both) No, I cannot.
This is because $B_X=\{|B|\colon |B|<|X|\}$ cannot be described uniformly within the model, and so we cannot describe its size in a uniform way (that is as a function $X\mapsto |B_X|$).
As Andres commented on the main question, in many cases it is not a big issue. This is the main reason why this "example" seems a bit artificial. However it does help when you have a nice way to define cardinalities in the times you actually need it.
I should mention that ordinals are always well-ordered and therefore of an $\aleph$-number kind of cardinality, and such $C$ can be defined for the class of well-orderable sets. The thing is that without the axiom of choice we just tend to have sets which cannot be bijected with ordinals with the absence of choice.
For more information: T. Jech, The Axiom of Choice Ch. 11
Added note: Scott's trick makes a heavy use of the axiom of regularity (also: axiom of foundation), and I am not aware of a clean way for defining cardinalities with the lack of both regularity as well choice (or even with only the former absent).
Another important note is that Scott's trick is not only useful to define cardinalities when lacking choice, but also to define any other equivalent relation over classes. Things such as ultraproducts of the universe, for example, rely heavily on this construction.
Solution 2:
Allow me to object to the assertion in the question that "we get very unnatural cardinals" when we use Scott's trick. I think Scott's trick brings us closer than the "initial ordinal" definition does to the most natural notion of cardinal, namely Frege's notion. Frege's idea was that abstractions like cardinality (where we abstract from the particular elements of a set and care only about how many there are) should be given by equivalence classes. So, for Frege, the number $3$ is the collection of all $3$-element sets. [Note that this is not circular; one can define "$3$-element set" without presupposing this number $3$.] This is the simplest mathematical entity that is common to all $3$-element sets. Frege's approach runs into trouble in the usual set theories (like ZF) because the collection of all $3$-element sets is not a set but a proper class. Scott's trick is intended to be a minimal tweaking of Frege's notion to produce a set. (In some other set theories, like New Foundations, cardinals in Frege's sense are sets, and I believe this is the preferred definition of cardinal numbers in such theories.) Notice also that Frege's approach, supplemented by Scott's trick, can be applied to any equivalence "relation" on the universe of sets, not just to the relation of being in one-to-one correspondence. (The quotation marks around "relation" are because it would be a proper class of ordered pairs rather than a set.)
Solution 3:
As pointed out in Andreas Blass's answer, Scott's cardinals are not so unnatural (and a large ordinal number is also a complicated object). Even with the Axiom of Choice, the initial ordinal definition makes cardinal & ordinal arithmetic confusing. For example, $2^\omega = \omega < \omega^2$, but $2^{\aleph_0} > \aleph_0 = \aleph_0^2$. Thus there is an advantage in ensuring that transfinite cardinals are not ordinal numbers.
The question does point out one serious problem with Scott's cardinals: his $0$ is the ordinal number $1$, which is confusing. Since finite ordinals and finite cardinals have the same arithmetic, I propose that (with or without AC) we apply Scott's trick to transfinite sets, and define the cardinal number of a finite (i.e. Dedekind finite & well orderable) set to be the appropriate ordinal number.