description/proof of that infinite product of sets each of which has more than \(1\) elements is uncountable
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 infinite product of sets each of which has more than \(1\) elements is uncountable.
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 infinite index sets }\}\)
\(\{S_j \in \{\text{ the sets } \} \vert j \in J, 1 \lt \vert S_j \vert\}\):
//
Statements:
\(\times_{j \in J} S_j \notin \{\text{ the countable sets }\}\)
//
2: Note
When each \(S_j\) has only \(1\) element, \(\times_{j \in J} S_j\) is countable, in fact, has only \(1\) element, because for each \(f \in \times_{j \in J} S_j\), \(f (j)\) is the only element of \(S_j\) for each \(j \in J\), so, \(f\) is uniquely determined.
3: Proof
Whole Strategy: Step 1: suppose that there was a surjection, \(g: \mathbb{N} \to \times_{j \in J} S_j\), and find a contradiction.
Step 0:
Note that the axiom of choice is used without being mentioned explicitly where.
Step 1:
As \(J\) is infinite, there is an injection, \(g': \mathbb{N} \to J\): define it inductively as this: for \(0\), choose an element of \(J\); for \(1\), choose an element of the rest of \(J\), ..., and so on.
Let us suppose that there was a surjection, \(g: \mathbb{N} \to \times_{j \in J} S_j\).
Let \(f \in \times_{j \in J} S_j\) be as this: for each \(n \in \mathbb{N}\), \(f (g' (n)) \neq g (n) (g' (n))\), which would be possible, because \(S_{g' (n)}\) had more than \(1\) elements, so, while \(g (n) (g' (n))\) was determined, choose \(f (g' (n))\) from \(S_{g' (n)} \setminus \{g (n) (g' (n))\}\): as \(g'\) is injective, there is no duplication in \(\{g' (n) \vert n \in \mathbb{N}\}\); for each \(j \in J \setminus g' (\mathbb{N})\), take any element of \(S_{j}\) as \(f (j)\).
Then, \(f\) would not be covered by \(g\), because for each \(n \in \mathbb{N}\), \(f \neq g (n)\), because \(f (g' (n)) \neq g (n) (g' (n))\).
That is a contradiction against that \(g\) was surjective.
So, there is no surjection, \(g: \mathbb{N} \to \times_{j \in J} S_j\).
So, \(\times_{j \in J} S_j\) is not countable.
