シュピルライン拡張定理

順序理論において、1930年にエドワード・シュピルラインによって証明されたシュピルライン拡張定理（順序拡張原理とも呼ばれる） ^[1]は、すべての部分順序は全順序に含まれていると述べています。直感的に言えば、この定理は、いくつかのペアが比較不可能になるような要素の比較方法は、すべてのペアが比較可能になるように拡張できることを示しています。この定理は、特定の特性を持つ最大集合を見つけるためにゾルンの補題の形で選択公理を使用する多くの例の1つです。

集合上の二項関係は 、集合の要素の順序付きペアの集合として正式に定義され、しばしば次のように略される。${\displaystyle R}$${\displaystyle X}$${\displaystyle (x,y)}$${\displaystyle X,}$${\displaystyle (x,y)\in R}$${\displaystyle xRy.}$

関係がすべての要素に対して成り立つ場合、それは反射的であり、すべてが成り立つ場合、それは推移的であり、すべてが成り立つ場合、それは反対称的であり、すべてが成り立つ場合、それは連結関係です。 半順序は、定義により、反射的、推移的、および反対称的な関係です。 全順序は連結である半順序です。 ${\displaystyle xRx}$${\displaystyle x\in X;}$${\displaystyle xRy{\text{ と }}yRz}$${\displaystyle xRz}$${\displaystyle x,y,z\in X;}$${\displaystyle xRy{\text{ と }}yRx}$${\displaystyle x=y}$${\displaystyle x,y\in X;}$${\displaystyle xRy{\text{ または }}yRx}$${\displaystyle x,y\in X.}$

関係が別の関係に含まれるのは、 のすべての順序付きペアが にも現れるときです。つまり、すべて に対して が成り立ちます。拡張定理は、反射的、推移的、反対称的 (つまり、部分順序) なすべての関係は、反射的、推移的、反対称的、連結的 (つまり、全順序) な別の関係に含まれることを述べています。 ${\displaystyle R}$${\displaystyle S}$${\displaystyle R}$${\displaystyle S;}$${\displaystyle xRy}$${\displaystyle xSy}$${\displaystyle x,y\in X.}$${\displaystyle R}$${\displaystyle S}$

この定理は 2 つのステップで証明されます。まず、半順序が 2 つの要素を比較しない場合は、比較可能なペアのスーパーセットを持つ順序に拡張できることを示します。定義により、最大半順序は拡張できないため、このステップから、最大半順序は全順序でなければならないことがわかります。2 番目のステップでは、Zorn の補題を適用して、任意の半順序を拡張する最大半順序を見つけます。

最初のステップとして、与えられた半順序がと を比較しないと仮定します。次に、まず のペアを関係に追加することによって順序が拡張されます。これにより、非推移的な関係になる可能性があります。次に、 となるすべてのペアを追加することによって推移性を復元します。これにより、依然として反射的、反対称的、推移的であり、元の関係を厳密に含む関係が生成されます。拡張する半順序自体が拡張によって部分的に順序付けられている場合、この拡張順序の任意の最大要素は全順序でなければなりません。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle xRy}$${\displaystyle qRp}$${\displaystyle qRx{\text{ と }}yRp.}$${\displaystyle R}$

次に、 を拡張し、拡張によって順序付けられた半順序のposet が最大元を持つことを示します。このような最大元の存在は、この poset にZorn の補題を適用することによって証明されます。Zorn の補題は、すべてのチェーンが上限を持つ半順序が最大元を持つと述べています。この poset 内のチェーンは、2 つの関係ごとに一方が他方を拡張する関係の集合です。チェーンの上限は、チェーン内の関係の和集合 として見つけることができます。この和集合 は、 を拡張する関係です。 のすべての要素は、を部分集合として持つ半順序であるためです。次に、が推移的な関係であることを示します。 および が 内にあると仮定して、 および となる が存在するとします。はチェーンであるため、 または のいずれかが他方を拡張し、と の両方を含む必要があり、推移性により も を含み、和集合 も同様です。同様に、 が反対称であることを示すことができます。したがって、は の拡大であるため、 の拡大の半集合に属し、 は の上限となります。 ${\displaystyle R}$${\displaystyle {\mathcal {C}}}$${\displaystyle \textstyle \bigcup {\mathcal {C}}}$${\displaystyle R}$${\displaystyle {\mathcal {C}}}$${\displaystyle R}$${\displaystyle \textstyle \bigcup {\mathcal {C}}}$${\displaystyle (x,y)}$${\displaystyle (y,z)}$${\displaystyle \textstyle \bigcup {\mathcal {C}},}$${\displaystyle S,T\in {\mathcal {C}}}$${\displaystyle (x,y)\in S}$${\displaystyle (y,z)\in T}$${\displaystyle {\mathcal {C}}}$${\displaystyle S}$${\displaystyle T}$${\displaystyle (x,y)}$${\displaystyle (y,z)}$${\displaystyle (x,z)}$${\displaystyle \textstyle \bigcup {\mathcal {C}}}$${\displaystyle \textstyle \bigcup {\mathcal {C}}}$${\displaystyle R}$${\displaystyle R}$${\displaystyle {\mathcal {C}}}$

この議論は、ゾルンの補題が の拡大の poset に適用され、最大元 を生成できることを示しています。最初のステップでは、この最大元は全順序でなければならず、証明が完了します。 ${\displaystyle R}$${\displaystyle Q}$

シュピルライン拡張定理を証明するには、何らかの選択公理が必要である。拡張定理は有限選択公理を意味する。有限集合族の和集合に空の部分順序が与えられ、これが全順序に拡張されると、拡張によって各有限集合からの選択が定義され、全順序における最小要素が定義される。有限選択は選択公理の弱いバージョンではあるが、選択のないツェルメロ・フランケル集合論とは独立している。^[2]

シュピルライン拡張定理と選択公理の別の帰結である、すべての全順序には共終整列 順序があるという原理を組み合わせると、選択公理全体が証明されます。これらの仮定により、任意の集合の空の部分順序を拡張し、共終整列順序を見つけ、その整列順序から最小の要素を選択することで、任意の集合から要素を選択できます。^[3]

アローは、あらゆる前順序（反射的かつ推移的な関係）は、全前順序（推移的かつ連結的な関係）に拡張できると主張した。 ^[4]この主張は後にハンソンによって証明された。^{[5] [6]}

鈴村は、二項関係が全順序関係に拡張できるのは、それが鈴村無矛盾である場合のみであることを証明した。鈴村無矛盾とは、連続する要素の任意のペアとに対して、サイクル内にはが成り立たない連続する要素のペアが存在することを意味する。 ^[6]${\displaystyle xRy}$${\displaystyle (x,y),}$${\displaystyle (x,y)}$${\displaystyle yRx}$