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

  • 2
    $\begingroup$ 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}}$. $\endgroup$ – t.b. Jun 6 '11 at 23:23
  • $\begingroup$ @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. $\endgroup$ – Apostolos Jun 7 '11 at 11:28
  • 1
    $\begingroup$ 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! $\endgroup$ – t.b. Jun 7 '11 at 11:31
  • $\begingroup$ @Theo: Oh I see. Indeed I saw no other comments here. That makes more sense, thanks. $\endgroup$ – 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.

  • 1
    $\begingroup$ can you please explain "and only the other hand $≤ℝ^ℕ=2^ℵ$ " $\endgroup$ – Rizon May 16 '17 at 12:56

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.