# Cardinality of the infinite sets

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?

-

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

-
To avoid further confusion in the comments to this answer: You're saying in particular that $\# B = \# D = \# E = 2^{\aleph_0}$. By not complaining about the OP's computations, you're also saying $2^{\aleph_0} = \# A = \# B = \# D = \# E \lt \# C = 2^{2^{\aleph_0}}$. –  t.b. Jun 6 '11 at 23:23
@Theo: What I'm saying is that B,D,E have cardinality $2^{\aleph_0}$. I purposely do not answer the whole problem presented in the question because the OP doesn't ask for that. His question is what are the cardinalities of B,D,E (in a way comparable with the others). Maybe he doesn't want an answer to the problem posed for whatever reasons. –  Apostolos Jun 7 '11 at 11:28
There were some strange claims here which you probably didn't see. I managed to convince the people involved to delete the comments and added mine in order to avoid further confusion, as I wrote. There's nothing wrong with your answer! –  t.b. Jun 7 '11 at 11:31
@Theo: Oh I see. Indeed I saw no other comments here. That makes more sense, thanks. –  Apostolos Jun 7 '11 at 11:40

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.

-