description/proof of countable union of countable sets is countable
Topics
About: set
The table of contents of this article
Starting Context
Target Context
- The reader will have a description and a proof of the proposition that any countable union of countable sets 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:
\(J\): \(\in \{\text{ the countable index sets }\}\)
\(\{S_j \in \{\text{ the countable sets }\} \vert j \in J\}\):
//
Statements:
\(\cup_{j \in J} S_j \in \{\text{ the countable sets }\}\)
//
2: Proof
Whole Strategy: Step 1: take any bijection, \(g: \mathbb{N} \setminus \{0\} \to J\), for each \(g (n) \in J\), take any bijection, \(f_{g (n)}: \mathbb{N} \setminus \{0\} \to S_{g (n)}\), and take a surjection, \(f: \mathbb{N} \setminus \{0\} \to \cup_{g (n) \in J} S_{g (n)}\).
Step 1:
Let us take any bijection, \(g: \mathbb{N} \setminus \{0\} \to J\).
For each \(g (n) \in J\), there is a bijection, \(f_{g (n)}: \mathbb{N} \setminus \{0\} \to S_{g (n)}\).
Let us define a map, \(f: \mathbb{N} \setminus \{0\} \to \cup_{{g (n)} \in J} S_{g (n)}\), inductively as this.
For \(2\), let us take \(\{f_{g (n)} (n_{g (n)}) \vert n + n_{g (n)} = 2\}\), which has \(2 - 1\) elements, in fact, it is \(\{f_{g (1)} (1)\}\).
Then, let us define \(f (1) = f_{g (1)} (1)\).
Now, we have \(f \vert_{\{1, ..., m_2\}}\), where \(m_2 = 1\).
For \(3\), let us take \(\{f_{g (n)} (n_{g (n)}) \vert n + n_{g (n)} = 3\}\), which has \(3 - 1\) elements, in fact, it is \(\{f_{g (1)} (2), f_{g (2)} (1)\}\).
Then, let us define \(f (m_2 + 1) = f (2) = f_{g (1)} (2), f (m_2 + (3 - 1)) = f (3) = f_{g (2)} (1)\).
Now, we have \(f \vert_{\{1, ..., m_3\}}\), where \(m_3 = 3\).
Let us suppose that for \(n' - 1\), we have \(f \vert_{\{1, ..., m_{n' - 1}\}}\).
For \(n'\), let us take \(\{f_{g (n)} (n_{g (n)}) \vert n + n_{g (n)} = n'\}\), which has \(n' - 1\) elements, in fact, it is \(\{f_{g (1)} (n' - 1), ..., f_{g (n' - 1)} (1)\}\).
Then, let us define \(f (m_{n' - 1} + 1) = f_{g (1)} (n' - 1), ..., f (m_{n' - 1} + (n' - 1)) = f_{g (n' - 1)} (1)\).
Now, we have \(f \vert_{\{1, ..., m_{n'}\}}\), where \(m_{n'} = m_{n' - 1} + (n' - 1)\).
Thus, \(f\) has been defined.
\(f\) is surjective, because for each \(f_{g (n)} (n_{g (n)}) \in \cup_{{g (n)} \in J} S_{g (n)}\), \(f_{g (n)} (n_{g (n)})\) is covered by the step for \(n + n_{g (n)}\).
Note that \(f\) is not necessarily injective, because when \(S_{g (n)} \cap S_{g (n')} \neq \emptyset\), \(f_{g (n)} (m) = f_{g (n')} (m')\) is hit twice.
But there is a bijection, \(f': \mathbb{N} \setminus \{0\} \to \cup_{{g (n)} \in J} S_{g (n)}\), by 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.
So, \(\cup_{{g (n)} \in J} S_{g (n)}\) is countable.
