カウンタブルセット（可算集合）たちのファイナイト（有限）プロダクトはカウンタブル（可算）であることの記述/証明
話題
About: セット（集合）
この記事の目次
開始コンテキスト
- 読者は、カウンタブルセット（可算集合）の定義を知っている。
- 読者は、サージェクション（全射）たちの任意のファイナイト（有限）コンポジション（合成）はサージェクション（全射）である、もしも、構成要素サージェクション（全射）たちのコドメイン（余域）たちが、引き続くサージェクション（全射）たちのドメイン（定義域）たちに等しい場合、という命題を認めている。
- 読者は、任意のインフィニットセット（無限集合）に対して、もしも、ナチュラルナンバー（自然数）たちセット（集合）から当該セット（集合）の上へのあるサージェクション（全射）がある場合、ナチュラルナンバー（自然数）たちセット（集合）から当該セット（集合）の上へのあるバイジェクション（全単射）があるという命題を認めている。
ターゲットコンテキスト
- 読者は、カウンタブルセット（可算集合）たちの任意のファイナイト（有限）プロダクトはカウンタブル（可算）であるという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\(J\): \(\in \{\text{ 全てのファイナイト（有限）インデックスセット（集合）たち }\}\)で、\(\vert J \vert = n\)および任意のオーダリング（順序）を持つもの
\(\{S_j \in \{\text{ 全てのカウンタブルセット（可算集合）たち }\} \vert j \in J\}\):
//
ステートメント（言明）たち:
\(\times_{j \in J} S_j \in \{\text{ 全てのカウンタブルセット（可算集合）たち }\}\)
//
2: 注
\(J\)がインフィニット（無限）カウンタブル（可算）である時は、\(\times_{j \in J} S_j\)はカウンタブル（可算）でない、一般には、特に、各\(S_j\)がインフィニット（無限）である時は、\(\times_{j \in J} S_j\)は常にカウンタブル（可算）でない、セット（集合）たちでその各々が\(1\)個より多い要素たちを持つものの任意のインフィニット（無限）プロダクトはアンカウンタブル（不可算）であるという命題によって。
3: 証明
全体戦略: ステップ1: \(S_j\)を拡大して任意のインフィニット（無限）カウンタブル（可算）\(S'_j\)にする、もしも、必要であれば; ステップ2: あるサージェクション（全射）\(g: \mathbb{N} \setminus \{0\} \to \times_{j \in J} S'_j\)を取る。
ステップ1:
各\(j \in J\)に対して、もしも、\(S_j\)がファイナイト（有限）である場合、\(S_j\)を拡大してインフィニット（無限）カウンタブル（可算）\(S'_j\)としよう、それは、可能である、なぜなら、例えば、\(S'_j := S_j \cup \mathbb{N}\)でよい。
私たちがそれを行なうのは、いくつかの\(S_j\)たちがファイナイト（有限）であるケースに対して何らかの特別処理たちを行なうのが面倒だからである。
ステップ2:
各\(j \in J\)に対して、あるバイジェクション（全単射）\(g_j: \mathbb{N} \setminus \{0\} \to S'_j\)がある。
あるマップ（写像）\(g: \mathbb{N} \setminus \{0\} \to \times_{j \in J} S'_j\)を定義しよう、インダクティブ（帰納的）に、以下のとおり。
\(n\)に対して、\(\{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\)要素を持つ、なぜなら、\({g_{J_1}}^{- 1} \circ f' (J_1) = ... = {g_{J_n}}^{- 1} \circ f' (J_n) = 1\)だけがその可能性である。
そこで、\(g (1)\)を当該要素として定義しよう。
今や、私たちは、\(g \vert_{\{1, ..., m_n\}}\)を持つ、ここで、\(m_n = 1\)。
\(n + 1\)に対して、\(\{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\}\)を取ろう、それは、\(n\)要素たちを持つ、なぜなら、\({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\)たちだけがその可能性たちである。
当該要素たちを\(({g_{J_1}}^{- 1} \circ f' (J_1), ..., {g_{J_n}}^{- 1} \circ f' (J_n))\)の辞書順に並べよう、それが意味するのは、各\(f'_1, f'_2\)に対して、もしも、\({g_{J_1}}^{- 1} \circ f'_1 (J_1) \neq {g_{J_1}}^{- 1} \circ f'_2 (J_1)\)である場合、\(f'_1, f'_2\)の順序はそれに応じて決定される、そうでない場合、もしも、\({g_{J_2}}^{- 1} \circ f'_1 (J_2) \neq {g_{J_2}}^{- 1} \circ f'_2 (J_2)\)である場合、\(f'_1, f'_2\)の順序はそれに応じて決定される、等々と続く。
そこで、\(g (m_n + 1), ..., g (m_n + n)\)を当該順序付けられた要素たちとして定義しよう。
今や、私たちは、\(g \vert_{\{1, ..., m_{n + 1}\}}\)、ここで、\(m_{n + 1} = n + 1\)、を持つ。
\(n' - 1\)に対して、私たちは、\(g \vert_{\{1, ..., m_{n' - 1}\}}\)を持つと仮定しよう。
\(n'\)に対して、\(\{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'\}\)を取ろう。
著者は当該要素たちの数をカウントする労を取らないが、それは、確かにファイナイト（有限）である、なぜなら、それは、\(n'^n\)より小さい、なぜなら、各\({g_{J_j}}^{- 1} \circ f (J_j)\)は\(1, ..., n'\)のみを持てる、そして、重要なのは、当該要素たちのセット（集合）はユニークに決定されファイナイト（有限）であることであり、当該数の明示的フォーミュラを示すことではない。
当該要素たちのセット（集合）を\(({g_{J_1}}^{- 1} \circ f' (J_1), ..., {g_{J_n}}^{- 1} \circ f' (J_n))\)の辞書順に並べよう。
そこで、\(g (m_{n' - 1} + 1), ..., g (m_{n'})\)を当該順序付けられた要素たちとして定義しよう。
今や、私たちは、\(g \vert_{\{1, ..., m_{n'}\}}\)を持つ。
このように、\(g\)は定義された。
\(g\)はあるサージェクション（全射）である、なぜなら、各\(f' \in \times_{j \in J} S'_j\)に対して、\({g_{J_1}}^{- 1} \circ f' (J_1) + ... + {g_{J_n}}^{- 1} \circ f' (J_n)\)は、\(n\)以上のある決定された値を持つ、したがって、\(f\)は、\({g_{J_1}}^{- 1} \circ f' (J_1) + ... + {g_{J_n}}^{- 1} \circ f' (J_n)\)に対するステップによってカバーされる。
以下を満たす\(g': \times_{j \in J} S'_j \to \times_{j \in J} S_j\)を定義しよう、つまり、各\(f' \in \times_{j \in J} S'_j\)に対して、各\(j \in J\)に対して\(f' (j) \in S_j\)である時は、\(g' (f')\)は、\(g' (f') (j) = f' (j)\)を満たすもの、そうでない時は、\(g' (f')\)は、以下を満たす\(\times_{j \in J} S_j\)の要素、つまり、\(({g_{J_1}}^{- 1} \circ f (J_1), ..., {g_{J_n}}^{- 1} \circ f (J_n)) = (1, ..., 1)\)。
\(g'\)はあるサージェクション（全射）である、なぜなら、各\(f \in \times_{j \in J} S_j\)に対して、\(\times_{j \in J} S'_j\)の対応する要素があり、それが、\(f\)へマップされる。
\(g' \circ g: \mathbb{N} \setminus \{0\} \to \times_{j \in J} S_j\)はあるサージェクション（全射）である、サージェクション（全射）たちの任意のファイナイト（有限）コンポジション（合成）はサージェクション（全射）である、もしも、構成要素サージェクション（全射）たちのコドメイン（余域）たちが、引き続くサージェクション（全射）たちのドメイン（定義域）たちに等しい場合、という命題によって。
\(\times_{j \in J} S_j\)がファイナイト（有限）である時は、\(\times_{j \in J} S_j\)はカウンタブル（可算）である。
そうでない場合、あるバイジェクション（全単射）\(g'': \mathbb{N} \setminus \{0\} \to \times_{j \in J} S_j\)がある、任意のインフィニットセット（無限集合）に対して、もしも、ナチュラルナンバー（自然数）たちセット（集合）から当該セット（集合）の上へのあるサージェクション（全射）がある場合、ナチュラルナンバー（自然数）たちセット（集合）から当該セット（集合）の上へのあるバイジェクション（全単射）があるという命題によって、したがって、\(\times_{j \in J} S_j\)はカウンタブル（可算）である。
したがって、\(\times_{j \in J} S_j\)はカウンタブル（可算）である、いずれにせよ。
