Find the cardinality of the set of all finite subsets of $\mathbb{R}$.

I have proved that the set of all finite subsets of $\mathbb{N}$ is countable . But I cannot find the cardinality of the set in case of $\mathbb{R}$ .

My Attempt:

First I have considered the set $$A_k=\{\{a_1, a_2, ..., a_k\}| a_i \in \mathbb{R} \ and\ a_1<...<a_k \}$$

Then $S=$ The set of all finite subsets of $\mathbb{R}=\bigcup_{n=1}^{\infty}A_{n}$,
and now in the case of $\mathbb{N}$, I could show that this $A_k$ is countable and consequently the set of all finite subset of $\mathbb{N}$ is countable.

But in this case I cannot say anything like this...In this case the set will be of the cardinality as that of $\mathbb{R}$ (I think). But cannot prove it.

I appreciate your help. Thank you.

  • 3
    $\begingroup$ @avs The power set is the set of all subsets, the OP asked for the set of all finite subsets. $\endgroup$
    – David
    Dec 13 '16 at 23:49
  • 2
    $\begingroup$ Can you prove that the countable union of sets, each of which has the same cardinality as $\Bbb R$, also has the cardinality of $\Bbb R$? (This is related to multiplication of cardinals, if you know anything about that at this point.) $\endgroup$ Dec 14 '16 at 0:08
  • $\begingroup$ It's easier if you know that $|\mathbb R|=|\mathcal P(\mathbb N)|.$ $\endgroup$ Mar 27 '19 at 20:18

We can show that $\#S \ge {c}$ via the injection $f: \mathbb{R} \rightarrow S$, $f(x) = \{x\}$.

If you show $\#S \le c$ then you can conclude $\#S = c$ invoking Bernstein's theorem.

Let's prove the following: let $X = \{X_k,\ k \in \mathbb{N}\}$ be a family of subsets such that $\#X_i \le c$, $\ \forall i \in \mathbb{N}$, and let $V = \bigcup_{k\in \mathbb{N}}X_k$. Then $\#V \le c$.

Because $\#X_i \le c$, we have for each $i$ a surjective $f_i: \mathbb{R} \rightarrow X_i$. We define $g: \mathbb{N} \times \mathbb{R} \rightarrow V$, $g(n,x) = f_n(x)$.

$g$ is an surjective function: let $x \in V$, then $x \in X_i$ for some $i$, then we have $a \in \mathbb{R}$ such that $f_i(a) = x$ because $f_i$ is surjective. Then $g(i,a) = f_i(a) = x$, with $(i,a) \in \mathbb{N}\times\mathbb{R}$.

We conclude that $g$ is surjective.

Thus $\#V \le \#(\mathbb{N}\times\mathbb{R})$, this is, $\#V \le c$.

Your set $S$ satisfies the hypotheses, so we have $\#S \le c$, and thus $\#S = c$.


Let $A$ be an element of the set of all the finite subsets of $\mathbb{R}$, which we shall denote simply by $\mathcal{P}_{<\omega}(\mathbb{R})$

Assertion: $\mathcal{P}_{<\omega}(\mathbb{R})\preccurlyeq\,^\omega\mathbb{R}$

We will identify $A$ with a $\omega$-sequence of elements of $\mathbb{R}$, that is, and element of $^\omega\mathbb{R}$, in the following way:

Assume that $A=\{a_0,\dots,a_n\}$. Then we can construct a $\omega$-sequence $(b_k)_{k\in\omega}$ defined by:

$$b_k=\begin{cases} a_k\qquad\qquad\text{if }k\le n \\ a_n+1\qquad\text{ if }k>n \end{cases}$$

It is clear that the correspondence $A\longmapsto(b_k)_{k\in\omega}$ is injective.

Now, on the one hand we have that $\mathbb{R}\preccurlyeq\mathcal{P}_{<\omega}(\mathbb{R})$, because the function $r\in\mathbb{R}\longmapsto\{r\}\in\mathcal{P}_{<\omega}(\mathbb{R})$ is obviously injective.

On the other hand, $\mathcal{P}_{<\omega}(\mathbb{R})\preccurlyeq\mathbb{R}$, since $\;\mathcal{P}_{<\omega}(\mathbb{R})\preccurlyeq\,^\omega\mathbb{R}\;$ and $\;^\omega\mathbb{R}\preccurlyeq\mathbb{R}$: in fact, $|^\omega\mathbb{R}|=\big(2^{\aleph_0}\big)^{\aleph_0}=2^{\aleph_0\times\aleph_0}=2^{\aleph_0}=|\mathbb{R}|$

From the Cantor-Bernstein therem, we obtain that $|\mathcal{P}_{<\omega}(\mathbb{R})|=|\mathbb{R}|=2^{\aleph_0}$


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.