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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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