整列定理

数学において、ツェルメロの定理としても知られる整列定理は、すべての集合は整列可能であることを述べている。集合X は、 Xのすべての空でない部分集合がその順序の下で最小の要素を持つ場合、厳密な全順序によって整列されている。整列定理は、ツォルンの補題とともに、選択公理(しばしば AC と呼ばれる。選択公理 §同値性も参照)と同値な最も重要な数学的命題である。 ^{[ 1 ] [ 2 ]}エルンスト・ツェルメロは、整列定理を証明するために、「異議のない論理原理」として選択公理を導入した。^{[ 3 ]}整列定理から、すべての集合は超限帰納法の適用を受けられると結論付けることができる。これは数学者によって強力な手法と考えられている。^{[ 3 ]} 

ゲオルク・カントールは整列定理を「思考の根本原理」とみなした。^{[ 4 ]} しかし、整列を視覚化することは困難、あるいは不可能であると考えられている。${\displaystyle \mathbb {R} }$、すべての実数の集合。このような視覚化には選択公理を組み込む必要があるだろう。^{[ 5 ]} 1904年、Gyula Kőnigは、そのような整列は存在し得ないことを証明したと主張した。数週間後、Felix Hausdorffは証明に誤りがあることを発見した。^{[ 6 ]} しかし、一階述語論理では、整列定理は選択公理と同等であることが判明した。つまり、選択公理を含むツェルメロ・フレンケル公理​​は整列定理を証明するのに十分であり、逆に、選択公理を含まないが整列定理を含むツェルメロ・フレンケル公理​​は選択公理を証明するのに十分である。 （ツォルンの補題についても同様である。）しかし、二階述語論理では、整列定理は選択公理よりも厳密に強い。整列定理から選択公理を導出することはできるが、選択公理から整列定理を導出することはできない。^{[ 7 ]}

この3つの命題と、それらが直感的に理解しやすいかどうかについて、よく知られたジョークがある。

選択公理は明らかに真であり、整列原理は明らかに偽であり、ゾルンの補題については誰が断言できるだろうか？^{[ 8 ]}

整列定理は選択公理から次のように導かれる。^{[ 9 ]}

整列させようとしている集合を次のようにします。${\displaystyle A}$、そして${\displaystyle f}$空でない部分集合の族の選択関数である${\displaystyle A}$すべての序数について${\displaystyle \alpha }$超限再帰によって要素を定義する$\displaystyle a_{\alpha }}$それは${\displaystyle A}$設定することで${\displaystyle a_{\alpha }\ =\ f(A\setminus \{a_{\xi }\mid \xi <\alpha \})}$この補語が${\displaystyle A\setminus \{a_{\xi }\mid \xi <\alpha \}}$空でない、または$\displaystyle a_{\alpha }}$補集合が空集合の場合は未定義です。つまり、$\displaystyle a_{\alpha }}$の要素の集合から選択されます${\displaystyle A}$順序付けにまだ位置が割り当てられていないもの（または全体の${\displaystyle A}$正常に列挙されました。次に、${\displaystyle <}$の上${\displaystyle A}$定義される$\displaystyle a_{\alpha }<a_{\beta }}$かつその場合に限り${\displaystyle \alpha <\beta }$（通常の順序の整列）は、${\displaystyle A}$ご希望に応じて、注文タイプ${\displaystyle \{\alpha \mid a_{\alpha }{\text{ が定義される}}\}}$（フォン・ノイマン表現において）

選択公理は、整列定理から次のように証明できる。

空でない集合の集合の選択関数を作成するには、${\displaystyle E}$集合の和集合を取る${\displaystyle E}$そしてそれを呼ぶ${\displaystyle X}$整列が存在する${\displaystyle X}$; させて${\displaystyle R}$そのような順序付けである。各セットに対する関数は${\displaystyle S}$の${\displaystyle E}$最小の要素を関連付ける${\displaystyle S}$（制限により）${\displaystyle S}$の）${\displaystyle R}$はコレクションの選択関数です${\displaystyle E}$。

この証明の重要な点は、たった一つの任意の選択、すなわち${\displaystyle R}$;各要素に整列定理を適用する${\displaystyle S}$の${\displaystyle E}$別々に行うとうまくいかない。なぜなら、定理は整列の存在のみを主張しており、各に対して選択するからである。${\displaystyle S}$整列には、各要素から要素を選択するのと同じ数の選択肢が必要となる。${\displaystyle S}$。

• Mizar システムの証明: http://mizar.org/version/current/html/wellord2.html