proving a set is countable

Let's write $S(E)$ a slightly different way:

$S(E) = \left\{A \subseteq E \mid \text{card}(A) = n, n\in \mathbb{N}\right\}$

Note that this is similar to the power set, but the power set includes subsets with infinite cardinality and the empty set.

Let $P$ be the set of primes (as suggested in the hint). Define $f:E \to P$ to be any injection. Such an injection exists since both $E$ and $P$ are countable. Then, define $g:S(E) \to \mathbb{N}$ by $g(A) = \prod_{e \in A}f(e)$ . Prove that $g$ is an injection.

Another proof of this: If $E$ is finite, then $S(E) = \mathcal{P}(E) \setminus \{\emptyset\}$ . Hence, $\text{card}(S(E)) = 2^{\text{card}(E)}-1$ where $\mathcal{P}(E)$ is the power set of $E$ , so $S(E)$ is finite and therefore countable. Suppose $E$ is infinite and let $E = \{e_0,e_1,\ldots\}$ be an enumeration of the elements of $E$ . Then, define $h: S(E) \to \mathbb{N}$ by $h(A) = \sum_{e_k \in A}2^k$ . Show that $h$ is a bijection.