# Set of Finite Subsets of Countable Set is Countable

## Theorem

Let $A$ be a countable set.

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

## Proof 1

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$

## Proof 2

By definition of a countable set, there is an injection $f: A \to \N$.

Let $\le_f$ be the ordering induced by $f$ on $A$.

By Injection Induces Well-Ordering, $\le_f$ is a well-ordering.

Let $A^{\text{fin}}$ be the set of finite subsets of $A$.

For $n \in \N$, denote with $A^{\left({n}\right)}$ the set of subsets of $A$ that have precisely $n$ elements.

For $A' \in A^{\left({n}\right)}$, we write $A' = \left\{{a'_1, a'_2, \ldots, a'_n}\right\}$ uniquely so that $i < j$ implies $a'_i <_f a'_j$.

Then we define $f^{\left({n}\right)}: A^{\left({n}\right)} \to \N$ by:

- $\displaystyle f^{\left({n}\right)} \left({A'}\right) := \prod_{i \mathop = 1}^n p_i^{f \left({a'_i}\right)}$

where $p_i$ denotes the $i$th prime.

By the Fundamental Theorem of Arithmetic, if $f^{\left({n}\right)} \left({A'}\right) = f^{\left({n}\right)} \left({A*}\right)$, then:*

- $\left({f \left({a'_1}\right), \dotsc, f \left({a'_n}\right)}\right) = \left({f \left({a
*_1}\right), \dotsc, f \left({a*_n}\right)}\right)$

As $f$ is injective, also:

- $\left({a'_1, \dotsc, a'_n}\right) = \left({a
*_1, \dotsc, a*_n}\right)$

and in particular $A' = A*$.*

Thus $f^{\left({n}\right)}: A^{\left({n}\right)} \to \N$ is an injection.

So $A^{\left({n}\right)}$ is countable.

Now define $f^{\text{fin}}: A^{\text{fin}} \to \N \times \N$ by:

- $f^{\text{fin}} \left({A'}\right) := \left({n, f^{\left({n}\right)} \left({A'}\right)}\right)$

where $n = \left\vert{A'}\right\vert$ is the cardinality of $A'$.

Suppose that:

- $f^{\text{fin}} \left({A'}\right) = f^{\text{fin}} \left({A
*}\right)$*

Then by Equality of Ordered Pairs:

- $n = \left\vert{A'}\right\vert = \left\vert{A
*}\right\vert$*

and:

- $f^{\left({n}\right)} \left({A'}\right) = f^{\left({n}\right)} \left({A
*}\right)$*

Since $f^{\left({n}\right)}$ was already shown to be an injection, it follows that:

- $A' = A
*$*

Thus $f^{\text{fin}}$ is also an injection.

By Cartesian Product of Natural Numbers with Itself is Countable, $\N \times \N$ is countable.

The result follows from Domain of Injection to Countable Set is Countable.

$\blacksquare$

## Proof 3

Let $A^{\paren n}$ be the set of subsets of $A$ with no more than $n$ elements.

Thus:

- $A^{\paren 0} = \set \O$
- $A^{\paren 1} = A^{\paren 0} \cup \set {\set a: a \in A}$

and $\forall n \ge 0$:

- $A^{\paren {n + 1} } = \set {a^{\paren n} \cup a^{\paren 1}: a^{\paren n} \in A^{\paren n} \land a^{\paren 1} \in A^{\paren 1} }$

Let us verify by induction that each $A^{\paren n}$ is countable.

Let $A$ be countable.

- $A^{\paren 1}$ is countable, as its cardinality is $1 + \card A$.

Suppose $A^{\paren n}$ is countable.

Then by Union of Countable Sets of Sets, so $A^{\paren {n + 1} }$ also countable.

By induction, each $A^{\paren n}$ is countable.

Denote with $A^f$ the set of finite subsets of $A$.

It is apparent that every finite subset is in some $A^{\paren n}$, and so:

- $A^f = \ds \bigcup_{n \mathop \in \N} A^{\paren n}$

The result follows from Countable Union of Countable Sets is Countable.

$\blacksquare$

Work In ProgressIn particular: This theorem is provable in Zermelo-Fraenkel set theoryYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{WIP}}` from the code. |

## Sources

- 2010: Raymond M. Smullyan and Melvin Fitting:
*Set Theory and the Continuum Problem*(revised ed.) ... (previous) ... (next): Chapter $1$: General Background: $\S 2$ Countable or uncountable?