description/proof of that for infinite set, if there is surjection from natural numbers set onto set, there is bijection from natural numbers set onto set
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of surjection.
- The reader knows a definition of bijection.
Target Context
- The reader will have a description and a proof of the proposition that for any infinite set, if there is a surjection from the natural numbers set onto the set, there is a bijection from the natural numbers set onto the set.
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 infinite sets }\}\)
//
Statements:
\(\exists f: \mathbb{N} \to S \in \{\text{ the surjections }\}\)
\(\implies\)
\(\exists f': \mathbb{N} \to S \in \{\text{ the bijections }\}\)
//
2: Note
The domain's being \(\mathbb{N}\) is crucial for this proposition.
If the domain was \(\mathbb{R}\), the proposition would not hold: for example, for \(S = \mathbb{Q}\), there is a surjection, \(f: \mathbb{R} \to \mathbb{Q}\), for example, \(f \vert_{\mathbb{Q}} = id\) and \(f \vert_{\mathbb{R} \setminus \mathbb{Q}} = 0\), but there is no bijection, \(f': \mathbb{R} \to \mathbb{Q}\), as is well known.
3: Proof
Whole Strategy: Step 1: inductively define \(f'\) and see that \(f'\) is a bijection.
Step 1:
Let \(f' (0) = f (0)\).
Now, we have the pair, \((f' \vert_{\{0\}}, n_0 := 0)\), where \(f' \vert_{\{0\}}\) is injective and \(n_0\) indicates that \(\{f (0), ..., f (0)\}\) has been covered.
For \(1\), let us take the smallest \(n_1 \in \mathbb{N}\) such that \(n_0 \lt n_1\) and \(f (n_1) \notin \{f' (0)\}\), which exists, because \(S\) is infinite.
Then, let \(f' (1) = f (n_1)\).
Now, we have \((f' \vert_{\{0, 1\}}, n_1)\), where \(f' \vert_{\{0, 1\}}\) is injective.
Let us suppose that for \(2 \le n'\), we have \((f' \vert_{\{0, ..., n' - 1\}}, n_{n' - 1})\), where \(f' \vert_{\{0, ..., n' - 1\}}\) is injective.
For \(n'\), let us take the smallest \(n_{n'} \in \mathbb{N}\) such that \(n_{n' - 1} \lt n_{n'}\) and \(f (n_{n'}) \notin \{f' (0), ..., f' (n' - 1)\}\), which exists, because \(S\) is infinite.
Then, let \(f' (n') = f (n_{n'})\).
Now, we have \((f' \vert_{\{0, .., n'\}}, n_{n'})\), where \(f' \vert_{\{0, ..., n'\}}\) is injective.
Thus, \(f'\) has been defined inductively.
\(f'\) is injective, because for each \(n, n' \in \mathbb{N}\) such that \(n \lt n'\), \(f' (n') \notin \{f' (0), ..., f' (n' - 1)\}\) while \(f' (n) \in \{f' (0), ..., f' (n' - 1)\}\), which means that \(f' (n) \neq f' (n')\).
\(f'\) is surjective, because for each \(s \in S\), let \(n := Min (f^{-1} (s))\), then, \(s = f (n)\), and as \(n_0 \lt n_1 \lt n_2 ...\), \(n \lt n_m\) for the smallest \(m\), then, \(n_{m - 1} \le n\), but if \(n_{m - 1} \lt n\), \(f (n) \notin \{f' (0) = f (0), ..., f' (m - 1) = f (n_{m - 1})\}\), because \(n = Min (f^{-1} (s))\), which contradicts the fact that \(n_m\) was the smallest such \(n\) as \(n \lt n_m\), so, \(n_{m - 1} = n\), so, \(f (n) = f (n_{m - 1}) = f' (m - 1)\).
So, \(f'\) is a bijection.
