description/proof of finite product of countable sets is countable
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of countable set.
- The reader admits the proposition that any finite composition of surjections is a surjection, if the codomains of the constituent surjections equal the domains of the succeeding surjections.
- The reader admits 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.
Target Context
- The reader will have a description and a proof of the proposition that any finite product 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 finite index sets }\}\), with \(\vert J \vert = n\) and any ordering
\(\{S_j \in \{\text{ the countable sets }\} \vert j \in J\}\):
//
Statements:
\(\times_{j \in J} S_j \in \{\text{ the countable sets }\}\)
//
2: Note
When \(J\) is infinite countable, \(\times_{j \in J} S_j\) is not countable in general, especially, when each \(S_j\) is infinite, \(\times_{j \in J} S_j\) is always not countable, by the proposition that any infinite product of sets each of which has more than \(1\) elements is uncountable.
3: Proof
Whole Strategy: Step 1: augment \(S_j\) to any infinite countable \(S'_j\) if necessary; Step 2: take a surjection, \(g: \mathbb{N} \setminus \{0\} \to \times_{j \in J} S'_j\).
Step 1:
For each \(j \in J\), if \(S_j\) is finite, let \(S_j\) be augmented to be infinite countable \(S'_j\), which is possible, because for example, \(S'_j := S_j \cup \mathbb{N}\) will do.
That we do because doing some special treatments for the case that some \(S_j\) s are finite is bothersome.
Step 2:
For each \(j \in J\), there is a bijection, \(g_j: \mathbb{N} \setminus \{0\} \to S'_j\).
Let us define a map, \(g: \mathbb{N} \setminus \{0\} \to \times_{j \in J} S'_j\), inductively as this.
For \(n\), let us take \(\{f' \in \times_{j \in J} S'_j \vert {g_{J_1}}^{- 1} \circ f' (J_1) + ... + {g_{J_n}}^{- 1} \circ f' (J_n) = n\}\), which has \(1\) element, because \({g_{J_1}}^{- 1} \circ f' (J_1) = ... = {g_{J_n}}^{- 1} \circ f' (J_n) = 1\) is the only possibility.
Then, let us define \(g (1)\) as the element.
Now, we have \(g \vert_{\{1, ..., m_n\}}\), where \(m_n = 1\).
For \(n + 1\), let us take \(\{f' \in \times_{j \in J} S'_j \vert {g_{J_1}}^{- 1} \circ f' (J_1) + ... + {g_{J_n}}^{- 1} \circ f' (J_n) = n + 1\}\), which has \(n\) elements, because \({g_{J_1}}^{- 1} \circ f' (J_1) = 2 \land {g_{J_2}}^{- 1} \circ f' (J_2) = ... = {g_{J_n}}^{- 1} \circ f' (J_n) = 1, ..., {g_{J_1}}^{- 1} \circ f' (J_1) = ... = {g_{J_{n - 1}}}^{- 1} \circ f' (J_{n - 1}) = 1 \land {g_{J_n}}^{- 1} \circ f' (J_n) = 2\) are the only possibilities.
Let us order the elements in the lexical order of \(({g_{J_1}}^{- 1} \circ f' (J_1), ..., {g_{J_n}}^{- 1} \circ f' (J_n))\), which means that for each \(f'_1, f'_2\), if \({g_{J_1}}^{- 1} \circ f'_1 (J_1) \neq {g_{J_1}}^{- 1} \circ f'_2 (J_1)\), the order of \(f'_1, f'_2\) is determined accordingly, otherwise, if \({g_{J_2}}^{- 1} \circ f'_1 (J_2) \neq {g_{J_2}}^{- 1} \circ f'_2 (J_2)\), the order of \(f'_1, f'_2\) is determined accordingly, and so on.
Then, let us define \(g (m_n + 1), ..., g (m_n + n)\) as the ordered elements.
Now, we have \(g \vert_{\{1, ..., m_{n + 1}\}}\), where \(m_{n + 1} = n + 1\).
Let us suppose that for \(n' - 1\), we have \(g \vert_{\{1, ..., m_{n' - 1}\}}\).
For \(n'\), let us take \(\{f' \in \times_{j \in J} S'_j \vert {g_{J_1}}^{- 1} \circ f' (J_1) + ... + {g_{J_n}}^{- 1} \circ f' (J_n) = n'\}\).
One does not bother to count the number of the elements, but it is certainly finite, because it is smaller than \(n'^n\), because each \({g_{J_j}}^{- 1} \circ f (J_j)\) can have only \(1, ..., n'\), and what is important is that the set of the elements is uniquely determined and finite, not to show the explicit formula of the number.
Let us order the set of the elements in the lexical order of \(({g_{J_1}}^{- 1} \circ f' (J_1), ..., {g_{J_n}}^{- 1} \circ f' (J_n))\).
Then, let us define \(g (m_{n' - 1} + 1), ..., g (m_{n'})\) as the ordered elements.
Now, we have \(g \vert_{\{1, ..., m_{n'}\}}\).
Thus, \(g\) has been defined.
\(g\) is a surjection, because for each \(f' \in \times_{j \in J} S'_j\), \({g_{J_1}}^{- 1} \circ f' (J_1) + ... + {g_{J_n}}^{- 1} \circ f' (J_n)\) has a definite value equal to or larger than \(n\), so, \(f\) is covered by the step for \({g_{J_1}}^{- 1} \circ f' (J_1) + ... + {g_{J_n}}^{- 1} \circ f' (J_n)\).
Let us define \(g': \times_{j \in J} S'_j \to \times_{j \in J} S_j\) such that for each \(f' \in \times_{j \in J} S'_j\), when \(f' (j) \in S_j\) for each \(j \in J\), \(g' (f')\) is the one such that \(g' (f') (j) = f' (j)\), and otherwise, \(g' (f')\) is the element of \(\times_{j \in J} S_j\) such that \(({g_{J_1}}^{- 1} \circ f (J_1), ..., {g_{J_n}}^{- 1} \circ f (J_n)) = (1, ..., 1)\).
\(g'\) is a surjection, because for each \(f \in \times_{j \in J} S_j\), there is the corresponding element of \(\times_{j \in J} S'_j\), which is mapped to \(f\).
\(g' \circ g: \mathbb{N} \setminus \{0\} \to \times_{j \in J} S_j\) is a surjection, by the proposition that any finite composition of surjections is a surjection, if the codomains of the constituent surjections equal the domains of the succeeding surjections
When \(\times_{j \in J} S_j\) is finite, \(\times_{j \in J} S_j\) is countable.
Otherwise, there is a bijection, \(g'': \mathbb{N} \setminus \{0\} \to \times_{j \in J} S_j\), 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, \(\times_{j \in J} S_j\) is countable.
So, \(\times_{j \in J} S_j\) is countable, anyway.
