Set of Finite Subsets of Countable Set is Countable/Proof 1

Theorem

Let $A$ be a countable set.

Then the set of finite subsets of $A$ is countable.

Proof

By the definition of a countable set, there exists an injection $g: A \to \N$.

Let $\FF$ denote the set of all finite subsets of $A$.

Let $f: \FF \to \N$ be the mapping defined by:

$\ds \map f F = \prod_{k \mathop \in \map g F} p_{k + 1}$

where $p_n$ denotes the $n$th prime number.

We define $\map f \O = 1$, the vacuous product.

Let $F, G \in \FF$, and suppose that $\map f F = \map f G$.

By Expression for Integer as Product of Primes is Unique:

$\map g F = \map g G$

By Subset equals Preimage of Image iff Mapping is Injection:

$F = \map {g^{-1} } {\map g F} = \map {g^{-1} } {\map g G} = G$

That is, $f$ is an injection.

$\blacksquare$