Cardinality of the infinite sets

Question

Consider the following problem:

Which of the following sets has the greatest cardinality?

A. ${\mathbb R}$

B. The set of all functions from ${\mathbb Z}$ to ${\mathbb Z}$

C. The set of all functions from ${\mathbb R}$ to $\{0,1\}$

D. The set of all finite subsets of ${\mathbb R}$

E. The set of all polynomials with coefficients in ${\mathbb R}$

What I can get is that $\#(A)=2^{\aleph_0}$ and $\#(C)=2^{2^{\aleph_0}}.$ And I think $\#(D)=\#(E)$. For B, one may get $\aleph_0^{\aleph_0}$. But how should I compare it with others(especially C)?

Here is my question:

What are cardinalities for B, D and E?

Answer 1

You are correct to think that the cardinality of the functions from $\mathbb{Z}$ to $\mathbb{Z}$ is $\aleph_0^{\aleph_0}$. To calculate this observe that $2^{\aleph_0}\leq\aleph_0^{\aleph_0}\leq (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$. Now using the Cantor-Bernstein theorem you get that $\aleph_0^{\aleph_0}=2^{\aleph_0}$.

Indeed E and D have the same cardinality. The finite subsets of $\mathbb{R}$ are exactly as many as the real numbers. This is because $|\mathbb{R}\times\mathbb{R}|=|\mathbb{R}|$ and thus (by induction) for every natural number $n$ we have that $|\mathbb{R}^n|=|\mathbb{R}|$. Since the set of finite subsets of $\mathbb{R}$ is $\bigcup_{n<\omega}\mathbb{R}^n$, we have that the cardinality we are looking for is $\sum_{n<\omega}{|\mathbb{R}^n|}=\sum_{n<\omega}{|\mathbb{R}|}$. The cardinality of this is $\aleph_0\cdot 2^{\aleph_0}=2^{\aleph_0}$.

Answer 2

The correct answer is the functions from $\mathbb R$ to $\{0,1\}$, the calculations and comparisons are given here:

1. $\mathbb R=2^{\aleph_0}$.
2. All the functions from $\mathbb Z$ to $\mathbb Z$ is the same as $\mathbb N$ to $\mathbb N$, which is $2^{\aleph_0}\le\aleph_0^{\aleph_0}\le 2^{\aleph_0\times\aleph_0}=2^{\aleph_0}$.
3. The functions from $\mathbb R$ to $\{0,1\}$ are basically characteristic functions for subsets of $\mathbb R$, i.e. it is the same as $|\mathcal P(\mathbb R)|$ which is of cardinality $2^{2^{\aleph_0}}$ (by Cantor's theorem).
4. All the finite subsets of $\mathbb R$ is at most all the finite sequences of $\mathbb R$, which is $\bigcup_{n\in\mathbb N}\mathbb R^n$, which is of cardinality at least $\mathbb R$, and only the other hand $\le\mathbb R^{\mathbb N} = 2^{\aleph_0}$, so it is of cardinality of the continuum.
5. By the same argument as (4), the set of polynomials is of cardinality continuum (identify a polynomial with a finite sequence of its coefficients, and the collection of finite sequences is at least the cardinality of all finite sets).

In particular it means that the set of functions from $\mathbb R$ to $\{0,1\}$ is the largest, and in fact it is the only one not of cardinality continuum.