# 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?

-
Scott's trick does exactly what you want: it guarantees that two sets have the same cardinality if and only if there's a bijection between them, and it does this in a fairly elegant way. That's the only property that matters: anything else is just implementation details. What more could you ask for (that isn't false in the absence of AC)? –  Qiaochu Yuan Jul 26 '11 at 0:17
@Qiaochu: I believe that the question is not whether or not we can still define cardinality within ZF, but rather the possible "gain" from using this definition rather than $\aleph$-numbers or some canonical representatives, I addressed this issue in my answer. –  Asaf Karagila Jul 26 '11 at 0:21
@Asaf: it just seems to me that defining cardinality for all sets so that it has the main property you want it to have is already a big enough gain. Again, what more could you ask for? –  Qiaochu Yuan Jul 26 '11 at 0:27
@Qiaochu: I could ask for canonical representatives, which the axiom of choice allows me to have (despite not being a global principle!) –  Asaf Karagila Jul 26 '11 at 0:29
I do not think there are many instances where it actually matters to have a set representing a cardinality class, so Scott's trick, though nice, does not seem to me to be actually useful in practice. A small remark: One can always define $|A|$ by cases: If $A$ is well-orderable, define in terms of ordinals, else using Scott's trick. –  Andres Caicedo Jul 26 '11 at 7:56

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$:

1. $C(X)=C(Y)\iff |X|=|Y|$;
2. $|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.

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.

-
Silly question: how much weaker - if at all - is the existence of a class functions satisfying 1. and 2. of your answer? –  t.b. Jul 26 '11 at 0:37
@Theo: This is a wonderful question, which I was wondering about it myself. Reading Jech's book the proof relies on the Mostowski model, in which every set can be linearly ordered. Giving you an accurate bound seems to be impossible at this moment (at least by myself, but I'm not certain whether or not it is known). It might take some time but I will certainly come back to this question once I have perfected some ideas I have regarding models of ZF. I will let you know at some point what is the answer. It does seem weaker than full blown choice, though. –  Asaf Karagila Jul 26 '11 at 0:43
Yes, please! And thanks for that first glimpse. I'm glad you understood my meaning ("weaker than choice" instead of "weaker"). –  t.b. Jul 26 '11 at 0:50
@Theo: I have to warn you that it might take a couple of years down the road. However since this question is of great interest to me to begin with (as are many other "How crazy cardinals act when they have no choice?" questions) I can assure you that I will return to it at one point or another. (And what could "weaker" mean other than "weaker than AC" in this context? :-)) –  Asaf Karagila Jul 26 '11 at 0:52
Sure, take your time! Maybe I'll then drop by and bring some usquebaugh from the highlands :) –  t.b. Jul 26 '11 at 0:59

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.)

-
While I do agree, I think that the ordinals have enough wonderful properties that we may forget about Frege's cardinals and focus on them when possible. –  Asaf Karagila Mar 17 '13 at 21:08

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.

-