24
$\begingroup$

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?

  • 4
    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.2011-07-26

3 Answers 3

20

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.

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.

  • 1
    @Timothy: When you talk about class you are not talking about provability in ZF, but rather provability *about* ZF. The same thing holds when you talk about "ZF cannot prove such and such" (e.g. the axiom of choice). This is a statement *about* ZF, which can be formalized in ZF, but also in weak theories of arithmetic. This is not an abuse of language, this is simply what is the technical language mean. You wouldn't claim that Latin is an abuse of language of English, just because they share their letters, and the situation here is similar. Mathematical language is semi-natural, but not quite.2018-02-20
8

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

  • 0
    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.2013-03-17
2

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.

  • 0
    I guess you're right that it's a good idea to define the cardinality of a well-orderable set to be the initial ordinal that's isomorphic to that set. Some people define the cardinality of a finite set to be a natural number but in ZF, a natural number is defined to be a finite Von Neumann ordinal. That way, the statements we usually say in English about how many elements a finite set has will actually be true according to that definition. Maybe you could actually give that reason in your answer.2018-02-21