「カントールの対角線論法」の版間の差分
削除された内容 追加された内容
Wanderer8128 (会話 | 投稿記録) m リンク/誤字訂正:ゲオルク・カントール |
編集の要約なし |
||
11行目:
'''対角線論法'''とは、陰に陽に以下の補題を使って定理を証明する[[背理法]]の事である。
* Xを集合とし、2<sup>X</sup>をXのべき集合とする。さらにψをXから2<sup>X</sup>への写像とする。Xの部分集合Yを<math>Y=\{x\in X: x\notin\psi(x)\}</math>により定義すると、ψ(x)=Yとなるx∈Xは存在しない。
上の補題は以下のように示せる。ψ(x)=Yとなるx∈Xが存在すると仮定したうえでxがYの元であるか否かを考える。もしxがYの元であればx∈Y=ψ(x)である。しかしYの定義より、Yは<math>x\notin\psi(x)</math>を満たすxの集合であるので、<math>x\notin\psi(x)</math>でなければならず、矛盾する。反対にもしxがYの元でなければ<math>x\notin Y=\psi(x)</math>であるが、Yの定義により、<math>x\notin\psi(x)</math>であるxはYの元でなければならず、やはり矛盾する。
57行目:
''X''を任意の集合とするとき、''X''から''X''の冪集合2<sup>''X''</sup>への全射が存在しない（従って特に全単射が存在しない）事（'''カントールの定理'''、カントール、[[1890年]]）を以下のように対角線論法で証明できる。
Xから2<sup>X</sup>への全射ψが存在したとする。<math>Y=\{x\in X: x\notin\psi(x)\}</math>により定義すると、対角線論法より、ψ(x)=Yとなるx∈Xは存在しない。これはψの全射性に反する。
| |||