Cardinality of the infinite sets

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.


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