Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We define cardinality as an equivalence relation on sets. But the class of all sets is not a set, so how do we do that? In particular, I'm interested in the proposition that equivalence classes form a partition of the initial set. It seems like it can be translated to cardinality, but I do not know how, at least in ZFC (and I don't even know ZFC :))

share|cite|improve this question
What is the initial set? – Qiaochu Yuan Feb 27 '11 at 15:43
I mean the set $A$ on which we define the relation $\sim\; \subset A^2$. This part doesn't translate well to the class of all sets :) – Alexei Averchenko Feb 27 '11 at 15:45
up vote 6 down vote accepted

We can of course define cardinality as you say: Two sets are equipotent (or have the same cardinality) iff there is a bijection between them.

You can prove directly that this notion is reflexive, symmetric and transitive. For example, the last statement is: For any sets $A,B,C$, if there is a bijection from $A$ to $B$ and a bijection from $B$ to $C$, then there is a bijection from $A$ to $C$. Note that this does not require that we reference directly the collection of equivalence classes or even that we consider a single equivalence class as a given object. What I mean is: We can do all that we need to do without talking about proper classes or collections of proper classes.

What would be the statement corresponding to "the equivalence classes of an equivalence relation on a non-empty set form a partition of the set into non-empty subsets"? Simply the conjunction of the following two statements: 1. "Cardinality is defined for all sets", which simply means that given any two sets $A$ and $B$, the statement "$A$ and $B$ have the same cardinality" is meaningful, and is either true or false. But of course that is the case, since $A$ and $B$ have the same cardinality iff there is a bijection between them, this is the very definition. In fact, "$A$ and $B$ have the same cardinality" is simply a linguistic shortcut for "there is a bijection between $A$ and $B$". 2. "Given two sets $A$ and $B$, if there is a set $C$ such that $A$ and $C$ have the same cardinality and also $B$ and $C$ have the same cardinality, then so do $A$ and $B$." And this can be easily proved in the expected way.

All of this can be easily formalized in set theory (ZFC or even much weaker systems). Again, the point is that there is no need to directly argue about proper classes or collections of classes (but, if you want, then there are also appropriate set theories, such as MK, where this is possible).

share|cite|improve this answer
How do we treat cardinals then? How do I say something like "Natural numbers are a subset of cardinals"? I guess it can be done by explicitly saying that $\vert\lbrace 1,\ldots,N\rbrace\vert = N$, but this approach makes cardinals as such very intangible. What if, on the other hand, we use NBG? Can we define cardinal numbers in a more tangible manner then, e.g. by having the class of cardinals and have each cardinal be a set? Can relations be translated to classes in NBG? Do partitions make sense for classes? – Alexei Averchenko Feb 27 '11 at 16:33
Well, using the axiom of choice, we can actually pick a canonical representative from each cardinality (an ordinal), and then statements about cardinals only need to refer to these special sets. Without choice but assuming the axiom of foundation, we can still assign a set to each cardinality, namely, the collection of sets of that cardinality that have smallest (set-theoretic) rank. This is in general not a single representative, as when we have choice, but it is a set, and so again, statements about cardinalities need only refer to these sets. – Andrés Caicedo Feb 27 '11 at 16:54
But even without choice and foundation, we can still talk about cardinalities by only talking about their members. I agree with you that this makes them "intangible" in a sense, but it is much less of an issue than one would think. For example: There is the notion of "Specker tree of a cardinality", which essentially is a tree (in the graph theoretic sense) whose nodes are cardinalities. Of course, one needs circumlocutions as above to make this formal, but the formalization ends up being straightforward, and nothing to worry about. – Andrés Caicedo Feb 27 '11 at 16:58
Finally, yes, NBG allows us to talk about cardinalities directly, and we can make sense of statements such as "cardinalities form a partition of the universe". It does not allow us to form the collection of equivalence classes, or anything that would require "hyperclasses", though. (But, once again, this ends up not being an issue.) – Andrés Caicedo Feb 27 '11 at 16:59
$\aleph_1$ thanks to you! – Alexei Averchenko Feb 27 '11 at 17:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.