Set Theory/Cardinals

Infinite Sets and Cardinality


The Size of a Finite Set

When deciding how large finite sets are, we generally count the number of elements in the set, and say two sets are the same size if they have the same number of elements. This approach doesn't work too well if the sets are infinite, however, because we can't count the number of elements in an infinite set.

However, there is another way to define when two sets have the same size that works equally well for finite and infinite sets. We say that two sets   and   have the same size if we can define a function   which satisfies the following properties:

  •   is defined for every  .
  •  ,   such that  . We say that f is onto or surjective.
  •  ,  . We say that f is one-to-one or injective.

Functions which satisfy these properties are called bijections.


The sets   and   both have three elements. We can define a bijection between them like this:  .

The set of all positive integers,   is the same size as the set of nonnegative integers,  . Let  , and more generally  .


Prove that the above function is a bijection.

Often it is difficult to construct an explicit bijection between two sets of the same cardinality, so the following theorem can come in handy:

Cantor-Schroeder-Bernstein Theorem

See proof at Cantor–Bernstein–Schroeder theorem

If   and   are two sets and there exist injective functions   and  , then there exists a bijection between   and  .



There are many ways of defining cardinality, and one method is to use ordinals as a reference. The cardinality of a set can be defined to be the smallest ordinal in one-to-one correspondence with the set. However, when speaking of cardinality, it is common to compare with the set of real numbers etc. when speaking of cardinalities greater than the countable cardinal, so in practice cardinality is thought of as something simply compared between two sets. One reason for this is because the possible sizes of ordinals can generally depend on the axioms one is working with.

See also


Ordinals · Zermelo-Fraenkel Axiomatic Set Theory