カウンタブルセット（可算集合）に対して、ファイナイトサブセット（有限部分集合）たちのセット（集合）はカウンタブル（可算）であることの記述/証明
話題
About: セット（集合）
この記事の目次
開始コンテキスト
- 読者は、カウンタブルセット（可算集合）の定義を知っている。
ターゲットコンテキスト
- 読者は、任意のカウンタブルセット（可算集合）に対して、全てのファイナイトサブセット（有限部分集合）たちのセット（集合）はカウンタブル（可算）であるという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\(S\): \(\in \{\text{ 全てのカウンタブルセット（可算集合）たち }\}\)
\(\widetilde{S}\): \(= \{s \in Pow (S) \vert \vert s \vert \in \mathbb{N}\}\)
//
ステートメント（言明）たち:
\(\widetilde{S} \in \{\text{ 全てのカウンタブルセット（可算集合）たち }\}\)
//
2: 証明
全体戦略: ステップ1: \(S\)はファイナイト（有限）であるというケースに対処し、それ以降は、そうでないと仮定する; ステップ2: 任意のバイジェクション（全単射）\(f: \mathbb{N} \setminus \{0\} \to S\)を取り、あるバイジェクション（全単射）\(\widetilde{f}: \mathbb{N} \setminus \{0\} \to \widetilde{S}\)を定義する。
ステップ1:
\(S\)がファイナイト（有限）である時、\(\widetilde{S}\)は明らかにファイナイト（有限）である、したがって、カウンタブル（可算）である、カウンタブルセット（可算集合）の定義によって。
これ以降は、そうでないと仮定する。
ステップ2:
\(S\)はインフィニット（無限）であると仮定しよう。
あるマップ（写像）\(\widetilde{f}: \mathbb{N} \setminus \{0\} \to \widetilde{S}\)を定義しよう、インダクティブ（帰納的）に、以下のとおり。
アイデアは、各\(n \in \mathbb{N} \setminus \{0\}\)に対して、以下を満たす全てのサブセット（部分集合）たち\(\{f (n_1), ..., f (n_m)\}, ...\)、つまり、\(n_1 + ... + n_m = n\)および\(n_1 \lt ... \lt n_m\)、を考えることである: 各\(n\)に対して、ファイナイト（有限）個のみのそうしたサブセット（部分集合）たちがあり、当該サブセット（部分集合）たちのセット（集合）を\((n_1, ..., n_m)\)の辞書的順序で並べる: 任意の互いに異なる\((n_1, ..., n_m)\)および\((n'_1, ..., n'_{m'})\)に対して、もしも、\(n_1 \lt n'_1\)である場合、\((n_1, ..., n_m) \lt (n'_1, ..., n'_{m'})\)、もしも、\(n'_1 \lt n_1\)である場合、\((n'_1, ..., n'_{m'}) \lt (n_1, ..., n_m)\)、そして、もしも、\(n_1 = n'_1\)である場合、\(n_2\)と\(n'_2\)を同様に比較する、等々と続く、そして、もしも、\(m \lt m'\)である時に\(n_m = n'_m\)である場合、\((n_1, ..., n_m) \lt (n'_1, ..., n'_{m'})\)、そして、もしも、\(m' \lt m\)である時に\(n_{m'} = n'_{m'}\)である場合、\((n'_1, ..., n'_{m'}) \lt (n_1, ..., n_m)\): \(m = m'\)は起こり得ない、なぜなら、それが意味することになるのは、\((n_1, ..., n_m) = (n'_1, ..., n'_{m'})\)。
\(\widetilde{f} (1) = \emptyset\)としよう。
\(n = 1 \in \mathbb{N} \setminus \{0\}\)に対して、以下を満たす全てのサブセット（部分集合）たち\(\{f (n_1), ..., f (n_m)\}, ...\)、つまり、\(n_1 + ... + n_m = n\)および\(n_1 \lt ... \lt n_m\)、を取ろう、実のところ、\(\{f (1)\}\)が当該サブセット（部分集合）である、そして、\(\widetilde{f} (2) = \{f (1)\}\)としよう。
\(n = 2 \in \mathbb{N} \setminus \{0\}\)に対して、以下を満たす全てのサブセット（部分集合）たち\(\{f (n_1), ..., f (n_m)\}, ...\)、つまり、\(n_1 + ... + n_m = n\)および\(n_1 \lt ... \lt n_m\)、を取ろう、実のところ、\(\{f (2)\}\)が当該サブセット（部分集合）である、そして、\(\widetilde{f} (3) = \{f (2)\}\)としよう。
\(n = 3 \in \mathbb{N} \setminus \{0\}\)に対して、以下を満たす全てのサブセット（部分集合）たち\(\{f (n_1), ..., f (n_m)\}, ...\)、つまり、\(n_1 + ... + n_m = n\)および\(n_1 \lt ... \lt n_m\)、を取ろう、実のところ、\(\{f (1), f (2)\} \lt \{f (3)\}\)が当該サブセット（部分集合）たちである、そして、\(\widetilde{f} (4) = \{f (1), f (2)\}, \widetilde{f} (5) = \{f (3)\}\)としよう。
等々と続く、そして、\(\widetilde{f}\)が決定された。
\(\widetilde{f}\)はインジェクティブ（単射）である、明らかに。
\(\widetilde{f}\)はサージェクティブ（全射）である、なぜなら、各\(\{f (n_1), ..., f (n_m)\} \in \widetilde{S}\)に対して、\(\{f (n_1), ..., f (n_m)\}\)は、\(n = n_1 + ... + n_m\)に対するステップでカバーされた。
したがって、\(\widetilde{f}\)はあるバイジェクション（全単射）である。
したがって、\(\widetilde{S}\)はカウンタブル（可算）である。
