Elementary Set Theory – Cardinality of Infinite Sets

cardinalselementary-set-theory

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?

Best Answer

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.

Related Question