Cardinal of Set of All Finite Subset of $\Bbb N$

Question

Let X be the set of all finite subset of $\Bbb N$. Then

let the set $S = \{\xi \mid \xi \approx X, \xi \leqslant 2^X\}$ then

Card(X) is the least element of S.

First, I can't start with how to exhaust all the element of S.

Any advice?

Answer 1

$\mathbb{N} \approx \mathbb{N}^2$ should be classical. (e.g. using the bijection $f(n,m) = (2n+1)2^m.)$

By induction: $\mathbb{N} \approx \mathbb{N}^k$ for every $k \in \mathbb{N}$. This only uses that $\approx$ is an equivalence relation.

The set of (non-empty) finite subsets of $\mathbb{N}$ has an injection into the set $T = \cup_{k \in \mathbb{N}} \mathbb{N}^k$, mapping each finite set to its unique ordered tuple in $T$ when writing it in increasing order. A countable union of countable sets is countable. It follows that $S$ is at most $\aleph_0$ (and as least $\aleph_0$ too, mapping $n$ to $\{n\}$ is an injection from $\mathbb{N}$ into $S$.). So it's exactly $\aleph_0$ by Cantor-Bernstein.