description/proof of for countable set, set of finite subsets is countable
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of countable set.
Target Context
- The reader will have a description and a proof of the proposition that for any countable set, the set of the finite subsets is countable.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(S\): \(\in \{\text{ the countable sets }\}\)
\(\widetilde{S}\): \(= \{s \in Pow (S) \vert \vert s \vert \in \mathbb{N}\}\)
//
Statements:
\(\widetilde{S} \in \{\text{ the countable sets }\}\)
//
2: Proof
Whole Strategy: Step 1: deal with the case that \(S\) is finite and suppose otherwise thereafter; Step 2: take any bijection, \(f: \mathbb{N} \setminus \{0\} \to S\), and define a bijection, \(\widetilde{f}: \mathbb{N} \setminus \{0\} \to \widetilde{S}\).
Step 1:
When \(S\) is finite, \(\widetilde{S}\) is obviously finite, so, is countable, by the definition of countable set.
Let us suppose otherwise, hereafter.
Step 2:
Let us suppose that \(S\) is infinite.
Let us define a map, \(\widetilde{f}: \mathbb{N} \setminus \{0\} \to \widetilde{S}\), inductively as follows.
The idea is that for each \(n \in \mathbb{N} \setminus \{0\}\), think of the subsets, \(\{f (n_1), ..., f (n_m)\}, ...\), such that \(n_1 + ... + n_m = n\) and \(n_1 \lt ... \lt n_m\): for each \(n\), there are only some finite such subsets and order the set of the subsets by the lexical order of \((n_1, ..., n_m)\): for the comparison of any distinct \((n_1, ..., n_m)\) and \((n'_1, ..., n'_{m'})\), if \(n_1 \lt n'_1\), \((n_1, ..., n_m) \lt (n'_1, ..., n'_{m'})\), if \(n'_1 \lt n_1\), \((n'_1, ..., n'_{m'}) \lt (n_1, ..., n_m)\), and if \(n_1 = n'_1\), compare \(n_2\) and \(n'_2\) likewise, and so on, and if \(n_m = n'_m\) when \(m \lt m'\), \((n_1, ..., n_m) \lt (n'_1, ..., n'_{m'})\), and if \(n_{m'} = n'_{m'}\) when \(m' \lt m\), \((n'_1, ..., n'_{m'}) \lt (n_1, ..., n_m)\): \(m = m'\) cannot happen, because that would mean that \((n_1, ..., n_m) = (n'_1, ..., n'_{m'})\).
Let \(\widetilde{f} (1) = \emptyset\).
For \(n = 1 \in \mathbb{N} \setminus \{0\}\), let us take the subsets, \(\{f (n_1), ..., f (n_m)\}, ...\), such that \(n_1 + ... + n_m = n\) and \(n_1 \lt ... \lt n_m\), in fact, \(\{f (1)\}\) is the subset, and let \(\widetilde{f} (2) = \{f (1)\}\).
For \(n = 2 \in \mathbb{N} \setminus \{0\}\), let us take the subsets, \(\{f (n_1), ..., f (n_m)\}, ...\), such that \(n_1 + ... + n_m = n\) and \(n_1 \lt ... \lt n_m\), in fact, \(\{f (2)\}\) is the subset, and let \(\widetilde{f} (3) = \{f (2)\}\).
For \(n = 3 \in \mathbb{N} \setminus \{0\}\), let us take the subsets, \(\{f (n_1), ..., f (n_m)\}, ...\), such that \(n_1 + ... + n_m = n\) and \(n_1 \lt ... \lt n_m\), in fact, \(\{f (1), f (2)\} \lt \{f (3)\}\) are the subsets, and let \(\widetilde{f} (4) = \{f (1), f (2)\}, \widetilde{f} (5) = \{f (3)\}\).
And so on, and \(\widetilde{f}\) has been determined.
\(\widetilde{f}\) is injective, obviously.
\(\widetilde{f}\) is surjective, because for each \(\{f (n_1), ..., f (n_m)\} \in \widetilde{S}\), \(\{f (n_1), ..., f (n_m)\}\) has been covered by the step for \(n = n_1 + ... + n_m\).
So, \(\widetilde{f}\) is a bijection.
So, \(\widetilde{S}\) is countable.
