# Comparing the cardinalities of infinite sets

What is the set that has the greatest cardinality?

1. $\mathbb{R}$
2. The set of all functions from $\mathbb{Z}$ to itself.
3. The set of all functions from $\mathbb{R}$ to $\{0,1\}$.
4. The set of all finite subsets of $\mathbb{R}$.
5. The set of all polynomials with coefficients in $\mathbb{R}$.

How do I compare the cardinalities?

1. That of $\mathbb R$
2. That of $\mathbb R$
3. That of $2^\mathbb R$
4. That of $\mathbb R$
5. That of $\mathbb R$

That is all have the same cardinality except 3 which has greater cardinality.

Basically you have to use the definition for cardinality comparision:

$|A| \le |B|$ means that there exists a surjection from $B$ to $A$

$|A| = |B|$ means that there exists a bijection between $A$ and $B$

Now we can start with concluding that the first and second have the same cardinality. First we can transform the functions in the second a little to be the set of functions from $\mathbb N$ to $\mathbb N$ by just mapping $\mathbb Z$ to $\mathbb N$. Now the functions corresponds to a sequence of numbers which can be mapped to a single number (just concatenate the numbers in base 8 and separate them by 8 and interpret it as a decimal part of a number).

Next the third we note that these functions are characteristic function for some subset of $\mathbb R$. The cardinality for that set is same as $2^\mathbb R$, which is larger than $\mathbb R$.

The fourth and fifth are the same because a polynomial is given by a finite number of coefficients and consequently the number of polynomials of degree n is the same as $\mathbb R^n$ (which is the same as for $\mathbb R$). The number of subsets with $n$ elements are the same ($|\mathbb R|/n!$). Then all of them are just the countable union of sets of specified size, so the cardinality is again that of $\mathbb R$.