カウンタブルセット（可算集合）のサブセット（部分集合）はカウンタブル（可算）であることの記述/証明
話題
About: セット（集合）
この記事の目次
開始コンテキスト
- 読者は、カウンタブルセット（可算集合）の定義を知っている。
ターゲットコンテキスト
- 読者は、任意のカウンタブルセット（可算集合）の任意のサブセット（部分集合）はカウンタブル（可算）であるという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\(S'\): \(\in \{\text{ 全てのカウンタブルセット（可算集合）たち }\}\)
\(S\): \(\subseteq S'\)
//
ステートメント（言明）たち:
\(S \in \{\text{ 全てのカウンタブルセット（可算集合）たち }\}\)
//
2: 証明
全体戦略: ステップ1: \(S\)がファイナイト（有限）であるケースに対称し、それ以降は、そうでないと仮定する; ステップ2: あるバイジェクション（全単射）\(f': \mathbb{N} \setminus \{0\} \to S'\)を取り、\(f'\)からあるバイジェクション（全単射）\(f: \mathbb{N} \setminus \{0\} \to S\)を構築する
ステップ1:
\(S\)がファイナイト（有限）である時は、\(S\)はカウンタブル（可算）である、カウンタブルセット（可算集合）の定義によって。
これ以降は、そうでないと仮定しよう。
ステップ2:
\(S'\)もインフィニット（無限）である、明らかに。
あるバイジェクション（全単射）\(f': \mathbb{N} \setminus \{0\} \to S'\)、がある、カウンタブルセット（可算集合）の定義によって。
あるマップ（写像）\(f: \mathbb{N} \setminus \{0\} \to S\)を定義しよう、インダクティブ（帰納的）に、以下のとおり。
\(1\)に対して、以下を満たす最小\(n \in \mathbb{N} \setminus \{0\}\)、つまり、\(f' (n) \in S\)、を取ろう、それは、存在する、なぜなら、第1に、\(f' (1) \in S\)であるかチェックし、もしも、そうでない場合、\(f' (2) \in S\)であるかチェックし、もしも、そうでない場合、...、等々と続く、そして、\(f' (n) \in S\)を満たす\(n\)がある、なぜなら、もしも、そうでなかったら、\(S\)は空であることになる、そして、\(f (1) = f' (n)\)としよう。
各\(n \in \{1, ..., f'^{-1} \circ f (1)\} \setminus \{f'^{-1} \circ f (1)\}\)に対して、\(f' (n) \notin S\)、なぜなら、\(f'^{-1} \circ f (1)\)は、\(f' (n) \in S\)を満たす最小\(n\)である。
\(2\)に対して、以下を満たす最小\(n \in \mathbb{N} \setminus \{0\}\)、つまり、\(f'^{-1} \circ f (1) \lt n\)および\(f' (n) \in S\)、を取ろう、それは、存在する、なぜなら、第1に、\(f' (f'^{-1} \circ f (1) + 1) \in S\)であるかチェックし、もしも、そうでない場合、\(f' (f'^{-1} \circ f (1) + 2) \in S\)であるかチェックし、もしも、そうでない場合、...、等々と続く、そして、\(f' (n) \in S\)を満たす\(n\)がある、なぜなら、そうでなかったら、\(S\)はファイナイト（有限）であることになる、そして、\(f (2) = f' (n)\)としよう。
今や、\(f (1), f (2)\)が、以下を満たすように定義された、つまり、\(f'^{-1} \circ f (1) \lt n = f'^{-1} \circ f' (n) = f'^{-1} \circ f (2)\)および各\(n \in \{1, ..., f'^{-1} \circ f (2)\} \setminus \{f'^{-1} \circ f (1), f'^{-1} \circ f (2)\}\)に対して、\(f' (n) \notin S\)、なぜなら、以下を満たす各そうした\(n\)、つまり、\(n \lt f'^{-1} \circ f (1)\)、に対して、\(f' (n) \notin S\)、そして、以下を満たす各そうした\(n\)、つまり、\(f'^{-1} \circ f (1) \lt n\)に対して、\(f' (n) \notin S\)、なぜなら、\(f'^{-1} \circ f (n')\)は、\(f' (n) \in S\)を満たす最小\(n\)である。
\(f (1), ..., f (n' - 1)\)が以下を満たすように定義されている、つまり、\(f'^{-1} \circ f (1) \lt ... \lt f'^{-1} \circ f (n' - 1)\)および各\(n \in \{1, ..., f'^{-1} \circ f (n' - 1)\} \setminus \{f'^{-1} \circ f (1), ..., f'^{-1} \circ f (n' - 1)\}\)に対して、\(f' (n) \notin S\)、と仮定しよう、\(3 \le n'\)に対して。
\(n'\)に対して、以下を満たす最小\(n \in \mathbb{N} \setminus \{0\}\)、つまり、\(f'^{-1} \circ f (n' - 1) \lt n\)および\(f' (n) \in S\)、を取ろう、それは、存在する、なぜなら、第1に、\(f' (f'^{-1} \circ f (n' - 1) + 1) \in S\)であるかチェックし、もしも、そうでない場合、\(f' (f'^{-1} \circ f (n' - 1) + 2) \in S\)であるかチェックし、もしも、そうでない場合、...、等々と続く、そして、\(f' (n) \in S\)を満たす\(n\)がある、なぜなら、そうでなかったら、\(S\)はファイナイト（有限）だということになる、そして、\(f (n') = f' (n)\)としよう。
すると、\(f'^{-1} \circ f (n' - 1) \lt n = f'^{-1} \circ f' (n) = f'^{-1} \circ f (n')\)、したがって、\(f'^{-1} \circ f (1) \lt ... \lt f'^{-1} \circ f (n')\)、そして、各\(n \in \{1, ..., f'^{-1} \circ f (n')\} \setminus \{f'^{-1} \circ f (1), ..., f'^{-1} \circ f (n')\}\)に対して、\(f' (n) \notin S\)、なぜなら、以下を満たす各そうした\(n\)、つまり、\(n \lt f'^{-1} \circ f (n' - 1)\)に対して、\(f' (n) \notin S\)、当該インダクション（帰納）仮説によって、そして、以下を満たす各そうした\(n\)、つまり、\(f'^{-1} \circ f (n' - 1) \lt n\)、に対して、\(f' (n) \notin S\)、なぜなら、\(f'^{-1} \circ f (n')\)は、\(f' (n) \in S\)を満たす最小\(n\)である。
こうして、インダクティブ（帰納的）に、\(f\)が定義された。
\(f\)はインジェクティブ（単射）である、なぜなら、以下を満たす各\(n, n' \in \mathbb{N} \setminus \{0\}\)、つまり、\(n \lt n'\)、に対して、\(f'^{-1} \circ f (n) \lt f'^{-1} \circ f (n')\)、それが意味するのは、\(f'^{-1} \circ f (n) \neq f'^{-1} \circ f (n')\)および\(f (n) = f' \circ f'^{-1} \circ f (n) \neq f' \circ f'^{-1} \circ f (n') = f (n')\)。
\(f\)はサージェクティブ（全射）である、なぜなら、各\(f' (n) \in S\)に対して、\(n\)は\(f'^{-1} \circ f (1) \lt f'^{-1} \circ f (2) \lt ...\)内のどこかに現われる、\(f'^{-1} \circ f (n')\)として、なぜなら、当該シーケンス（列）はそのうちに\(n\)を超えるところ、\(n\)はある項として現われる、なぜなら、各\(n \in \{1, 2, ...\} \setminus \{f'^{-1} \circ f (1), f'^{-1} \circ f (2), ...\}\)に対して、\(f' (n) \notin S\)、したがって、\(n = f'^{-1} \circ f (n')\)、したがって、\(f' (n) = f (n')\)。
したがって、\(f\)はあるバイジェクション（全単射）である。
したがって、\(S\)はカウンタブル（可算）である。
