Why this proof is bad

2018 April 24


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 tth 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.