Two sets E and F have the same cardinality, written Card(E) = Card(F), if there exists a bijection ff from E onto F. This is an equivalence relation on the class of sets. We speak here of a "class" because there can be no set of all sets. The relation is indeed reflexive, symmetric and transitive: the identity is a bijection, the inverse of a bijection is a bijection, and so is the composition of two bijections.
-
The set of all sets --------------------------------
Why does the set of all sets not exist? It would be the set whose elements were all sets. Bertrand Russell showed that no such object can exist. Suppose, then, that it did. By definition, this hypothetical set would belong to itself. That may sound strange, but why not? A priori, nothing in logic prevents us from entertaining the idea. By way of contradiction, consider the sets that do not belong to themselves, and then the set of all those sets. Does it belong to itself? If it belongs to itself, then it does not; and if it does not belong to itself, then it does. Absurd, isn't it? Without care, we can create such monstrosities. As for the set of all sets, let us pursue the matter no further: it must be ruled out.
Let us return to cardinalities. Similarly, we write Card(E) ≤ Card(F) if E has the same cardinality as a subset of F. In this case, there is a subset E' of F and a bijection ff from E onto E'; ff is then an injection from E into F. By extending the inverse f−1f^{-1} of ff, mapping every element of the complement of E' in F to any element of E, we obtain a surjection from F onto E. It is easy to prove that Card(E) ≤ Card(F) is equivalent both to the existence of an injection from E into F and to that of a surjection from F onto E. These equivalences readily show that cardinal inequality is a reflexive and transitive relation on the class of sets. The next paragraph also proves that it is antisymmetric, which is the Cantor–Bernstein theorem: if E and F are two sets such that there is an injection from E into F and an injection from F into E, then there is a bijection from E onto F. Thus, this is an order relation on the class of sets.