description/proof of subset of countable set 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 any subset of any countable set 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 }\}\)
\(S\): \(\subseteq S'\)
//
Statements:
\(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 a bijection, \(f': \mathbb{N} \setminus \{0\} \to S'\), and construct a bijection, \(f: \mathbb{N} \setminus \{0\} \to S\) from \(f'\).
Step 1:
When \(S\) is finite, \(S\) is countable, by the definition of countable set.
Let us suppose otherwise, hereafter.
Step 2:
Also \(S'\) is infinite, obviously.
There is a bijection, \(f': \mathbb{N} \setminus \{0\} \to S'\), by the definition of countable set.
Let us define a map, \(f: \mathbb{N} \setminus \{0\} \to S\), inductively as follows.
For \(1\), let us take the smallest \(n \in \mathbb{N} \setminus \{0\}\) such that \(f' (n) \in S\), which exists, because 1st, check whether \(f' (1) \in S\), if not, check whether \(f' (2) \in S\), if not, ..., and so on, and there is the \(n\) such that \(f' (n) \in S\), because otherwise, \(S\) would be empty, and let \(f (1) = f' (n)\).
For each \(n \in \{1, ..., f'^{-1} \circ f (1)\} \setminus \{f'^{-1} \circ f (1)\}\), \(f' (n) \notin S\), because \(f'^{-1} \circ f (1)\) is the smallest \(n\) such that \(f' (n) \in S\).
For \(2\), let us take the smallest \(n \in \mathbb{N} \setminus \{0\}\) such that \(f'^{-1} \circ f (1) \lt n\) and \(f' (n) \in S\), which exists, because 1st, check whether \(f' (f'^{-1} \circ f (1) + 1) \in S\), if not, check whether \(f' (f'^{-1} \circ f (1) + 2) \in S\), if not, ..., and so on, and there is the \(n\) such that \(f' (n) \in S\), because otherwise, \(S\) would be finite, and let \(f (2) = f' (n)\).
Now, \(f (1), f (2)\) have been defined such that \(f'^{-1} \circ f (1) \lt n = f'^{-1} \circ f' (n) = f'^{-1} \circ f (2)\) and for each \(n \in \{1, ..., f'^{-1} \circ f (2)\} \setminus \{f'^{-1} \circ f (1), f'^{-1} \circ f (2)\}\), \(f' (n) \notin S\), because for each such \(n\) such that \(n \lt f'^{-1} \circ f (1)\), \(f' (n) \notin S\), and for each such \(n\) such that \(f'^{-1} \circ f (1) \lt n\), \(f' (n) \notin S\), because \(f'^{-1} \circ f (n')\) is the smallest \(n\) such that \(f' (n) \in S\).
Let us suppose that \(f (1), ..., f (n' - 1)\) have been defined such that \(f'^{-1} \circ f (1) \lt ... \lt f'^{-1} \circ f (n' - 1)\) and for each \(n \in \{1, ..., f'^{-1} \circ f (n' - 1)\} \setminus \{f'^{-1} \circ f (1), ..., f'^{-1} \circ f (n' - 1)\}\), \(f' (n) \notin S\), for \(3 \le n'\).
For \(n'\), let us take the smallest \(n \in \mathbb{N} \setminus \{0\}\) such that \(f'^{-1} \circ f (n' - 1) \lt n\) and \(f' (n) \in S\), which exists, because 1st, check whether \(f' (f'^{-1} \circ f (n' - 1) + 1) \in S\), if not, check whether \(f' (f'^{-1} \circ f (n' - 1) + 2) \in S\), if not, ..., and so on, and there is the \(n\) such that \(f' (n) \in S\), because otherwise, \(S\) would be finite, and let \(f (n') = f' (n)\).
Then, \(f'^{-1} \circ f (n' - 1) \lt n = f'^{-1} \circ f' (n) = f'^{-1} \circ f (n')\), so, \(f'^{-1} \circ f (1) \lt ... \lt f'^{-1} \circ f (n')\), and for each \(n \in \{1, ..., f'^{-1} \circ f (n')\} \setminus \{f'^{-1} \circ f (1), ..., f'^{-1} \circ f (n')\}\), \(f' (n) \notin S\), because for each such \(n\) such that \(n \lt f'^{-1} \circ f (n' - 1)\), \(f' (n) \notin S\), by the induction hypothesis, and for each such \(n\) such that \(f'^{-1} \circ f (n' - 1) \lt n\), \(f' (n) \notin S\), because \(f'^{-1} \circ f (n')\) is the smallest \(n\) such that \(f' (n) \in S\).
Thus, inductively, \(f\) has been defined.
\(f\) is injective, because for each \(n, n' \in \mathbb{N} \setminus \{0\}\) such that \(n \lt n'\), \(f'^{-1} \circ f (n) \lt f'^{-1} \circ f (n')\), which means that \(f'^{-1} \circ f (n) \neq f'^{-1} \circ f (n')\) and \(f (n) = f' \circ f'^{-1} \circ f (n) \neq f' \circ f'^{-1} \circ f (n') = f (n')\).
\(f\) is surjective, because for each \(f' (n) \in S\), \(n\) appears somewhere in \(f'^{-1} \circ f (1) \lt f'^{-1} \circ f (2) \lt ...\) as \(f'^{-1} \circ f (n')\), because while the sequence eventually exceeds \(n\), \(n\) appears as a term, because for each \(n \in \{1, 2, ...\} \setminus \{f'^{-1} \circ f (1), f'^{-1} \circ f (2), ...\}\), \(f' (n) \notin S\), so, \(n = f'^{-1} \circ f (n')\), so, \(f' (n) = f (n')\).
So, \(f\) is a bijection.
So, \(S\) is countable.
