カントールの対角線論法

カントールの対角線論証（基数2）による、無数集合の存在に関する説明図。一番下の列は、上の列の列挙のどこにも現れない。

無限集合は、自然数から偶数への単射f ( x )=2 xが示すように、それ自身の真部分集合と同じ濃度を持つことがあります。しかしながら、カントールの対角線論法が示すように、濃度の異なる無限集合も存在します。

カントールの対角線論証（類似の名称は様々^{[注 1]}）は、自然数の無限集合と一対一に対応付けられない無限集合が存在するという数学的証明である 。非公式には、ある意味で正の整数の数よりも多くの要素を含む集合が存在するという証明である。このような集合は現在では無数集合と呼ばれ、無限集合の大きさはカントールが提唱した基数理論によって扱われている。

ゲオルク・カントールはこの証明を1891年に発表した^{[1] [2] : 20–  [3]}が、これは実数の非可算性の彼の最初の証明ではなかった。実数の非可算性の証明は1874年に発表された^{[4] [5] 。しかし、これはその後、}ゲーデルの不完全性定理の最初のもの^{[2]や、チューリングの}帰納問題に対する解答[ ^6]など 、幅広い証明に用いられる一般的な手法を示している。対角化の議論は、ラッセルのパラドックス^{[7] [8]}やリチャードのパラドックス^{[  2} ]のような矛盾の原因となることもよくある。

不可算集合

カントルは、2進数の無限列（つまり各桁が0か1）全体の集合Tを考察した。 ^{[注 2]}彼は以下の補題の構成的証明 から始める。

s ₁、s ₂、 ... 、s _n 、 ... がTの要素の任意の列挙である場合、^{[注 3]} 、列挙内のどのs _nにも対応しないTの要素s を構築できます。

証明はTの要素の列挙から始まります。例えば

s 1 =	(0,	0,	0,	0,	0,	0,	0,	...）
s 2 =	（1、	1、	1、	1、	1、	1、	1、	...）
s 3 =	(0,	1、	0,	1、	0,	1、	0,	...）
s 4 =	（1、	0,	1、	0,	1、	0,	1、	...）
s 5 =	（1、	1、	0,	1、	0,	1、	1、	...）
s 6 =	(0,	0,	1、	1、	0,	1、	1、	...）
s 7 =	（1、	0,	0,	0,	1、	0,	0,	...）
...

次に、シーケンスsは、1番目の桁をs ₁の1番目の桁の補数（0を1と入れ替え、逆も同様）として選択し、2番目の桁をs ₂の2番目の桁の補数として選択し、3番目の桁をs ₃の3番目の桁の補数として選択し、一般にすべてのnについて、n番目の桁をs _nのn番目の桁の補数として選択することで構築されます。上記の例では、これは次のようになります。

1ページ	＝	（0 ,	0,	0,	0,	0,	0,	0,	...）
2ページ	＝	（1、	1、	1、	1、	1、	1、	1、	...）
3秒	＝	(0,	1、	0 ,	1、	0,	1、	0,	...）
4ページ	＝	（1、	0,	1、	0 ,	1、	0,	1、	...）
5秒	＝	（1、	1、	0,	1、	0 ,	1、	1、	...）
6秒	＝	(0,	0,	1、	1、	0,	1、	1、	...）
7ページ	＝	（1、	0,	0,	0,	1、	0,	0 ,	...）
...
s	＝	（1、	0 ,	1、	1、	1、	0 ,	1、	...）

構造上、sはTの要素であり、各s _nとはn番目の数字が異なるため（例で強調表示）、異なる要素である。したがって、s は列挙中に出現することはできない。

この補題に基づいて、カントルは背理法による証明を用いて次のことを証明する。

集合Tは可算名詞です。

証明は、T が可算であると仮定することから始まります。この場合、 T のすべての要素は、列挙s ₁、s ₂、 ... 、s _n 、 ... に書き表すことができます。前の補題をこの列挙に適用すると、 Tの要素ではあるものの、列挙には含まれない数列sが生成されます。しかし、 Tが列挙されている場合、このsを含むTのすべての要素は列挙に含まれます。この矛盾は、最初の仮定が誤りであることを意味します。したがって、Tは可算ではありません。^[1]

実数

実数の非可算性はカントールの最初の非可算性証明によってすでに確立されているが、それは上記の結果からも導かれる。これを証明するために、無限二進文字列の集合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... を小数点 0.0111... にマッピングする代わりに、基数-bの 0.0111... bにマッピングすることができます。これにより、関数族f _b ( t ) = 0. t _bが得られます。関数f _b ( t )はf ₂ ( t )を除いて単射です。この関数を修正して、TとRの間の一対一関係を生成します。    

TとR間の一対一の構築

この構成は、1878年に発表されたカントールの手法を用いている。彼はこの手法を用いて、閉区間[0, 1]と開区間(0, 1)の無理数との間の一対一関係を構築した。まず、これらの集合から可算無限部分集合を一つずつ取り除き、残りの非可算集合間の一対一関係を実現した。取り除かれた可算無限部分集合間には一対一関係が存在するため、二つの一対一関係を組み合わせると、元の集合間の一対一関係が実現される。[9] カントール法を用いて関数f 2 ( t ) = 0. t 2 を変形し、 Tから (0, 1) への一対一写像を生成することができます。しかし、数によっては2つの二進展開を持つため、f 2 ( t )は 単射でさえありません。例えば、f 2 (1000...) =  0.1000... 2  = 1/2 であり、f 2 (0111...) =  0.0111... 2  = 1/4 + 1/8 + 1/16 + ... = 1/2 であるため、1000... と 0111... はどちらも同じ数 1/2 に写像されます。 f 2  ( t )を修正するには、 (0, 1) の可算無限部分集合とTの可算無限部分集合を除いて、これが全単射であることに注目してください。2 つの二進展開を持つ (0, 1) の数字については、全単射ではありません。これらは二項数と呼ばれ、 m  /  2 ^nの形式を持ちます。ここで、mは奇数の整数で、nは自然数です。これらの数字をr  = (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ...) という数列に並べます。また、 0、1 の二進展開で二進小数点の後に現れるTの文字列と、数列rの数字については、 f 2  ( t )は (0, 1) への全単射ではありません。これらの最終的に定数となる文字列をシーケンスs  = ( 000 ..., 111 ..., 1 000 ..., 0 111 ..., 01 000 ..., 00 111 ..., 11 000 ..., 10 111 ..., ...) に配置します。Tから(0, 1) への一対一写像g ( t )を定義します。tがシーケンスsのn^番目の文字列である場合、g ( t )をシーケンスrのn^番目の数値とします。それ以外の場合は、g ( t ) = 0. t 2 です。   TからRへの全単射を構築するには、まず正接関数tan( x )から始めます。これは (−π/2, π/2) からRへの全単射です(右の図を参照)。次に、線形関数 h ( x ) = π x – π/2が (0, 1) から (−π/2, π/2) への全単射であることに注目してください (左の図を参照)。合成関数tan( h ( x )) = tan(π x – π/2)は、 (0, 1) からRへの全単射です。この関数をg ( t ) と合成すると、関数 tan( h ( g ( t ))) = tan(π g ( t ) – π/2)が生成され、これはTからRへの全単射です。

一般セット

一般化された対角線議論の図解：一番下の集合はの範囲のどこにも出現しない。例の写像fは、上の図の例の列挙sに対応する。${\displaystyle T=\{n\in \mathbb {N} :n\not \in f(n)\}}$ ${\displaystyle f:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )}$

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

fをSからP ( S )への任意の関数とする。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}$

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

排中律がない場合

構成的数学においても、完全な定義域から関数の空間や部分集合の集合への全射は存在しない。つまり、これら2つの集合は無数である。ここでも、証明された単射性の存在を示す「 」と単射性不在を併せて用いると、と が成り立つ。さらに、前述の通り、 が成り立つ。同様に、、そしてもちろんも、構成的集合論において成り立つ。 ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle {\mathcal {P}}({\mathbb {N} })}$ ${\displaystyle <}$ ${\displaystyle {\mathbb {N} }<2^{\mathbb {N} }}$ ${\displaystyle S<{\mathcal {P}}(S)}$ ${\displaystyle \neg ({\mathcal {P}}(S)\leq S)}$ ${\displaystyle 2^{\mathbb {N} }\leq {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle 2^{S}\leq {\mathcal {P}}(S)}$ ${\displaystyle S\leq S}$

しかしながら、順序数や基数を構成的に順序付けることはより困難または不可能である。例えば、シュレーダー・ベルンシュタインの定理は排中律を必要とする。^[10]実際、有理数の順序付けを拡張した実数上の標準的な順序付けも、必ずしも決定可能ではない。興味深い関数のクラスのほとんどの特性も、ライスの定理により決定可能ではない。すなわち、部分可算集合の数え上げ数の集合は再帰的でない可能性があり、したがって可算でない可能性がある。集合の部分集合の精巧なコレクションは、その特性関数のコレクションと構成的に交換可能ではない。それ以外の点では構成的なコンテキスト（排中律が公理とされないコンテキスト）では、排中律の結果と矛盾する非古典的な公理を採用しても一貫している。やなどの非可算集合は部分可算であると主張されることがある。^{[11] [12]} これは古典的な文脈では冗長なサイズの概念ですが、そうでなければ可算性を意味する必要はありません。非可算なものから、またはへの注入の存在は、ここでも起こり得ます。^[13]そのため、基数関係は反対称ではありません。その結果、古典的に非可算である関数空間セットが存在する場合でも、直観主義者はこの関係が超限サイズの階層を構成するとは受け入れません。^[14]べき集合の公理が採用されていない 場合、構成的なフレームワークでは、すべてのセットの部分可算性さえも一貫しています。そうは言っても、一般的な集合論では、すべてのセットの集合が存在しないことは、述語的分離からもすでにわかっています。 ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }}$

集合論では、数学の理論がモデル化されます。論理公理が弱いということは、制約条件が少ないことを意味し、より豊富なモデルのクラスが可能になります。集合は、実数公理またはその構成的な言い換えを満たす場合、実数体のモデルとして識別されます。コーシー実数やデデキント実数など、さまざまなモデルが研究されています。前者は数列の商に関連し、後者は、存在する場合、べき集合から取られた行儀の良いカットです。排中律がある場合、それらはすべて同型で不可算です。そうでない場合、デデキント実数の変種は可算^[15]または自然数に注入できますが、同時ではありません。可算選択を仮定すると、構成的なコーシー実数は明示的な収束係数がなくてもコーシー完全^[16]になり、デデキント実数はそれらと同型になるように単純化されます。実際、ここで選択は対角線の構築にも役立ち、それを仮定すると、実数のコーシー完全モデルは無数になります。

より広い文脈での対角化

ラッセルのパラドックスは、無制限の内包スキームを含む集合論が矛盾していることを示しました。Tの構成とラッセルのパラドックスにおける集合との間には類似性があることに留意してください。したがって、ラッセルのパラドックスを回避するために内包公理スキームをどのように修正するかによって、すべての集合の集合が存在しないといった議論が妥当性を保つかどうかが決まります。

対角線論法の類似物は、数学において特定の対象の存在または非存在を証明するために広く用いられています。例えば、停止問題の解けないことの従来の証明は、本質的に対角線論法です。また、対角化は元々、任意に困難な計算量クラスの存在を示すために用いられ、 P が NP と等しくないことを証明する初期の試みにおいて重要な役割を果たしました。

クワインの新しい基礎のためのバージョン

上記の証明は、WVクワインの「新基礎」集合論（NF）では成立しません。NFでは、素朴公理体系の理解は、ある種の「局所的」型理論を導入することでパラドックスを回避するために修正されています。この公理体系では、

{ s ∈ S : s ∉ f ( s ) }

は集合ではない、つまり公理スキームを満たさない。一方で、次の点に注目して、修正された対角線論証を作成しようとするかもしれない。

{ s ∈ S : s ∉ f ({ s }) }

はNFの集合である。この場合、P ₁ ( S ) がSの1要素部分集合の集合であり、f がP ₁ ( S )からP ( S ) への単射であるとすると、背理法を用いて | P ₁ ( S )| < | P ( S )| であることを証明できる。

証明は、もしf が実際にP ( S )への 写像であるならば、 f ({ r }) が上記の修正対角集合と一致するような r をS内に見つけることができるという事実から導かれる。したがって、 r がf ({ r })に含まれないならばrはf ({ r })に含まれる、またその逆もまた成り立つ と結論付けられる。

P ₁ ( S ) とSは型が異なるため、 1 対 1 の関係にすることはできません。そのため、そのように定義された関数は、理解スキームの型付け規則に違反することになります。

参照

• カントールの最初の非可算性証明
• 連続体仮説
• カントールの理論をめぐる論争
• 対角線の補題

注記

1. 対角化論証、対角線スラッシュ論証、反対角線論証、対角線法、カントールの対角化証明
2. カントールは「0」と「1」の代わりに「 m」と「 w 」、「 T 」の代わりに「 M 」 、 「 s _i 」の代わりに「 E _i 」を使用しました。
3. カントールは、 Tのすべての要素がこの列挙に含まれているとは想定していません。
4. 0.0111... と 0.1000... は二進分数として解釈すると等しくなります（単射性が破れるため）。しかし、 fのように小数として解釈すると、両者は異なります。一方、 tは二進文字列であるため、小数における 0.0999... = 0.1000... という等式はここでは関係ありません。

参考文献

1. ゲオルク・カントール (1891)。 「Ueber eine elementare Frage der Mannigfaltigkeitslehre」。Jahresbericht der Deutschen Mathematikar-Vereinigung。1 : 75–78。2023年 1 月 3 日のオリジナルからアーカイブ。2018 年6 月 11 日に取得。英語訳：ウィリアム・B・エヴァルト編（1996年）『イマヌエル・カントからダヴィド・ヒルベルトまで：数学基礎論集 第2巻』オックスフォード大学出版局、  920～ 922頁。ISBN 0-19-850536-1。
2. キース・シモンズ（ 1993年7月30日）『普遍性と嘘つき：真理と対角線論法に関する試論』ケンブリッジ大学出版局。ISBN 978-0-521-43069-2。
3. ルディン、ウォルター (1976). 『数学解析の原理』（第3版）. ニューヨーク: マグロウヒル. p. 30. ISBN 0070856133。
4. Gray, Robert (1994), "Georg Cantor and Transcendental Numbers" (PDF) , American Mathematical Monthly , 101 (9): 819– 832, doi :10.2307/2975129, JSTOR 2975129, 2022年1月21日時点 のオリジナル(PDF)からアーカイブ。 2013年12月6日閲覧。
5. ブロック、イーサン・D. (2011). 『実数と実解析』 ニューヨーク: シュプリンガー. p. 429. ISBN 978-0-387-72176-7。
6. シェパード、バーナビー (2014). 『無限の論理』（イラスト入り）ケンブリッジ大学出版局. p. 73. ISBN 978-1-107-05831-6。73ページの抜粋
7. ラッセルのパラドックス。スタンフォード哲学百科事典。2021年。2022年8月30日時点のオリジナルよりアーカイブ。2016年7月12日閲覧。
8. バートランド・ラッセル (1931). 『数学の原理』 ノートン. pp.  363– 366.
9. Georg Cantor (1878)の 254 ページを参照、「Ein Beitrag zur Mannigfaltigkeitslehre」、 Journal für die Reine und Angewandte Mathematik、84 : 242–258、2018年 11 月 6 日にオリジナルからアーカイブ、2017 年8 月 17 日に取得この証明はジョセフ・ドーベン（1979）『ゲオルク・カントール：無限の数学と哲学』（ハーバード大学出版、ISBN 978-4-8533-1111）で論じられている。 0-674-34871-0、61～62ページ、65ページ。65ページで、ダウベンはカントールの証明よりも強い結果を証明している。彼は「φ _{ν を}[0, 1] 内の任意の有理数列とする」としている。カントールはφ _{ν を}[0, 1] 内の有理数を列挙する列とする。これは彼が [0, 1] と (0, 1) 内の無理数との間の一対一写像を構成するために必要な列である。
10. Pradic, Cécilia; Brown, Chad E. (2019). 「カントール＝バーンスタイン法は排中律を示唆する」arXiv : 1904.09193 [math.LO].
11. Bell, John L. (2004)、「ラッセルのパラドックスと構成的文脈における対角化」(PDF)、Link, Godehard (編)、『ラッセルのパラドックスの100年』、De Gruyter Series in Logic and its Applications、第6巻、de Gruyter、ベルリン、pp.  221– 225、MR  2104745
12. Rathjen, M.「構成的集合論と古典的集合論における選択原理」、論理コロキウム紀要、2002年
13. Bauer, A. 「N^NからNへの注入」2011年11月27日アーカイブ、Wayback Machineにて
14. エットーレ・カルッチョ (2006). 『歴史と現代思想における数学と論理学』 Transaction Publishers. p. 354. ISBN 978-0-202-30850-0。
15. バウアー、ハンソン (2024). 「可算実数」. arXiv : 2404.01256 [math.LO].
16. Robert S. Lubarsky, 構成的コーシー実数のコーシー完全性について、2015年7月

外部リンク

• MathPagesにおけるカントールの対角線証明
• ワイスタイン、エリック・W.「カントール対角法」。MathWorld。