カントールの対角線論法

実数の非可算性は、カントールの最初の非可算性証明によって既に確立されていますが、上記の結果からも導かれます。これを証明するために、無限二進文字列の集合Tから実数の集合Rへの単射を構成します。Tは非可算であるため、この関数の像（ Rの部分集合）は非可算です。したがって、Rは非可算です。また、カントールが考案した構成法を用いて、TとRの間に全単射を構成します。したがって、TとR は同じ濃度を持ち、これは「連続体の濃度」と呼ばれ、通常は で表されます。${\displaystyle {\mathfrak {c}}}$または${\displaystyle 2^{\aleph _{0}}}$。

TからRへの単射は、 Tのバイナリ文字列を小数にマッピングすることによって与えられます。例えば、t  =  0111... を小数 0.0111... にマッピングします。この関数はf ( t ) = 0. tで定義され、異なる文字列を異なる数値にマッピングするため、単射です。^{[注 4 ]}

TとRの間の全単射を構築することは、少し複雑です。0111... を 10 進数の 0.0111... にマッピングする代わりに、基数- b の数 0.0111... _bにマッピングできます。これにより、関数の族f _b ( t ) = 0. t _bが得られます。関数f _b ( t )は、 f ₂ ( t )を除いて単射です。この関数は、 TとRの間の全単射を生成するように変更されます。

カントールは、対角線論法の一般化された形式を用いて、カントールの定理を証明した。すなわち、任意の集合Sに対して、Sの冪集合（つまり、 Sのすべての部分集合の集合（ここではP ( S )と表記））は、 S自身と一対一で対応し得ない、という定理である。この証明は次のように進められる。

SからP ( S )への任意の関数f を考えます。fが全射ではないことを証明すれば十分です。これは、 P ( S )の要素T 、つまりSの部分集合がfの像に含まれないことを意味します。候補として、集合を考えます。

${\displaystyle T=\{s\in S:s\notin f(s)\}.}$

Sのすべてのsに対して、s はTに含まれるか含まれないかのどちらかです。s が T に含まれる場合、Tの定義により、s はf ( s ) に含まれないため、Tはf ( s )と等しくありません。一方、s がTに含まれない場合、 Tの定義により、sはf ( s )に含まれるため、やはりT はf ( s )と等しくありません。図を参照してください。

この証明のより詳細な説明については、カントールの定理を参照してください。

等号をそれらの基礎となる集合間の全単射の存在として定義すると、カントールは基数の二項述語も定義する。${\displaystyle |S|}$そして${\displaystyle |T|}$注射の存在に関して${\displaystyle S}$そして${\displaystyle T}$これは先行順序の性質を持ち、ここでは次のように書かれています。${\displaystyle \leq }$「自然数を二進数列に埋め込むことで、様々な挿入存在命題を明示的に証明することができ、この意味で${\displaystyle |{\mathbb {N} }|\leq |2^{\mathbb {N} }|}$、 どこ${\displaystyle 2^{\mathbb {N} }}$関数空間を表す${\displaystyle {\mathbb {N} }\to \{0,1\}}$しかし、前の節の議論から、全射は存在せず、したがって全単射も存在しない、つまり集合は非可算集合である。これについては次のように書ける。${\displaystyle |{\mathbb {N} }|<|2^{\mathbb {N} }|}$、 どこ "${\displaystyle <}$「」は、単射の存在と全単射の非存在の証明（カントールの順序の否定や、割り当てられた順序数による定義などの代替案とは対照的に）を意味すると理解される。また${\displaystyle |S|<|{\mathcal {P}}(S)|}$この意味では、すでに述べたように、同時に、${\displaystyle \neg (|{\mathcal {P}}(S)|\leq |S|)}$すべてのセットについて${\displaystyle S}$。

排中律を仮定すると、特性関数は冪集合に射影され、そして${\displaystyle |2^{S}|=|{\mathcal {P}}(S)|}$。したがって、数えられない${\displaystyle 2^{\mathbb {N} }}$も列挙可能ではなく、また、にマッピングすることもできます。${\displaystyle {\mathbb {N} }}$古典的には、シュレーダー・ベルンシュタインの定理が有効であり、互いに単射像である任意の2つの集合は全単射でもあると述べている。ここで、すべての非有界部分集合は${\displaystyle {\mathbb {N} }}$は、${\displaystyle {\mathbb {N} }}$それ自体、そしてすべての部分可算集合（射影の観点からの性質）は既に可算である、つまり の射影像において${\displaystyle {\mathbb {N} }}$この文脈では可能性は尽きてしまい、「${\displaystyle \leq }$「厳密でない半順序、あるいは選択を仮定すれば全順序です。したがって、対角線論法は、検討対象の両方の集合が無限であるにもかかわらず、実際には自然数よりも多くの1と0の無限列が存在することを示しています。カントールの結果は、すべての集合の集合という概念が矛盾していることも意味します。${\displaystyle S}$もしそれが全ての集合の集合ならば${\displaystyle {\mathcal {P}}(S)}$同時に、より大きくなるだろう${\displaystyle S}$そしてそのサブセット${\displaystyle S}$。

ラッセルのパラドックスは、無制限の内包体系を含む集合論が矛盾していることを示している。Tの構成とラッセルのパラドックスにおける集合の間には類似性があることに注意されたい。したがって、ラッセルのパラドックスを回避するために内包の公理体系をどのように修正するかによって、すべての集合の集合が存在しないといった議論が妥当性を保つ場合もあれば、そうでない場合もある。

対角線論法の類似手法は、数学において特定の対象の存在または非存在を証明するために広く用いられている。例えば、停止問題の解けなさを証明する従来の方法は、本質的に対角線論法である。また、対角線論法はもともと、任意の難易度を持つ複雑性クラスの存在を示すために用いられ、 P≠NPの証明を試みる初期の試みにおいて重要な役割を果たした。