In my *Intro to Mathematical Reasoning* course, I had to prove that the set of all finite subsets of ℕ is countable. Although I was able to easily do so, I now don't like my proof. Of course, I've already submitted my homework, so I can't change it, but I can at least address my problems with it here.

Here is my proof. Note that Corollary 1 states that the primes are countable.

`<p><b>Proposition 9.</b> <i>The set of all finite subsets of $\mathbb{N}$ is countable.</i></p> <p><i>Proof.</i> Let S be the infinite set of all finite subsets of $\mathbb{N}$. We construct a bijection $h : S \rightarrow (S_0 \subseteq \mathbb{N})$.</p> <p>Let $T \in S$. From Corollary 1, we know that there exists a bijection $f: \mathbb{N} \rightarrow \mathbb{P}$. We note that the image $f (T)$ is is a set of primes. The Fundamental Theorem of Arithmetic tells us that there exists a bijection $g$ which maps finite sets of primes to naturals whose prime factorizations do not repeat primes. We see that $f(T)$ is in the domain of $g$. </p> <p>Thus, the function $h = g \circ f$ is a bijection, so $S$ is countable. $\square$</p>`

If you have difficulty understanding the proof, then there's nothing wrong with you. Although this proof is valid and rigourous, it's just so abstract that it's unnecessarily hard to understand.

Specifically, I don't give an explicit definition of *f* nor *g*. I just say that such bijections exist, which is all that I needed to do. However, in doing so, I make the proof far too abstract. We will define *f* and *g* here.

`<p><b>Definition.</b> Let $P \in \mathscr{P}(\mathbb{P})$ be finite. Then we let $g$ be a function whose domain is the finite subset of $\mathscr{P}(\mathbb{P})$ and codomain is the set of all naturals which don't repeat prime factorizations. We define $g$ with $$g(P) = \prod_{p \in P} p$$ and $g^{-1}$ gives the prime factors of a natural. </p>`

By restricting the codomain of *g* to naturals which don't repeat prime factors, we see that *g* is a bijection.

Now we define *f*.

`<p><b>Definition.</b> The function $f: \mathbb{N} \rightarrow \mathbb{P}$ maps $n$ to the $n^{\mathrm{th}}$ prime. That is, $$f(1) = 2,$$ $$f(2) = 3,$$ $$f(3) = 5,$$ etc.</p> For convenience, if $N \subseteq \mathbb{N}$, we let $f(N)$ be the image of $N$ under $f$. This is essentially an abuse of notation.`

This makes it possible to give a more "tangible" description of the proof. Let *T* ∈ *S*. Then *f*(*T*) is the image of *T* under *f*, so it maps each element *t* ∈ *T* to the *t*^{th} prime. We see that *f*(*T*) is a set of primes, so *g*(*f*(*T*)) is the unique product of those primes. We see that *g* ∘ *f* is bijective because:

```
<li>the elements in $T$ are unique because it is a set,</li>
<li>and the elements in $f(T)$ are unique because $f$ is injective,</li>
<li>and the elements in $g(f(T))$ are unique because $g$ is injective.</li>
```

Thus, *g* ∘ *f* is an injection, so we let *h* = *g* ∘ *f*. From this, we can show that *h* is surjective because its codomain was restricted to its image, the set of naturals which don't repeat prime factors.

Thus, *h* is a bijection.