0
$\begingroup$

It is known that $|2^\Bbb{N}|=|\Bbb{R}|$ and that $2^\Bbb{N}$ contains all the subsets of $\Bbb{N}$, just an idea of a question I had and that I would like suggestions on how to tackle.

My question is this, Let $\Bbb{X}$ be the set of all finite subsets of $\Bbb{N}$, that is if $a\in\Bbb{X}$ then we have that $|a|<\infty$ and $a\subset\Bbb{N}$, now what is the cardinality of $\Bbb{X}$? I feel it should probably be same as $\Bbb{N}$ but not sure how to tackle.

$\endgroup$
3
$\begingroup$

Fix $\;n\in\Bbb N\;$ . How many subsets with $\;n\;$ elements from $\;\Bbb N\;$ are there? You could probably want to take a peek at $\;\overbrace{\Bbb N\times\ldots\times\Bbb N}^{n\;\text{times}}\;$ .

Well, now take the union over $\;n\;$ of the above.

$\endgroup$
1
$\begingroup$

The set of all finite subsets of $\Bbb N$ is countable.

Every finite subset has a maximum element. Also, for a given $n$, there are finitely many sets of natural numbers such that the maximum value is $n$. (In fact, there are $2^n$ of them.)

So to get a list of all finite subsets of $\Bbb N$, list all sets with a maximum value of $0$, then those with a maximum of $1$, and so on. This gives an infinite but countable list of all finite subsets.

Here is an explicit bijection between $\Bbb N$ and the set of all finite subsets of $\Bbb N$. The finite set corresponding to $n$ has $i$ as a member if and only if the $i$'th digit in the binary expansion of $n$ is a $1$.

$\endgroup$
0
$\begingroup$

Since there are infinitely many primes, you can associate each integer to a prime $p$ (just by $n \mapsto p_n$, for example). You can then construct an injection $f: \mathbb{X} \to \mathbb{N}$ by setting $$ f( A ) = \prod_{a \in A} p_a, $$ which is a finite product since $A$ is a finite set. This is clearly injective using the Fundamental Theorem of Arithmetic. Hence $\lvert \mathbb{X} \rvert \leqslant \lvert \mathbb{N} \rvert $.

Since $\{n\}$ is in $\mathbb{X}$ for all $n \in \mathbb{N}$, we also have the reverse inequality, so the cardinalities are equal (use Cantor–Bernstein if you feel the need).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.