Loading article…
順序理論は、二項関係を用いて順序という直感的な概念を研究する数学の一分野である。「これはあれより小さい」や「これはあれより前である」といった記述を形式的に表現する枠組みを提供する。
順序は数学やコンピュータサイエンスなどの関連分野で至るところに存在します。小学校でよく取り上げられる最初の順序は、自然数の標準的な順序です。例えば、「2は3より小さい」、「10は5より大きい」、「トムはサリーよりクッキーが少ないか」などです。この直感的な概念は、整数や実数などの他の数の集合の順序にも拡張できます。ある数より大きいか小さいかという考え方は、一般的に数体系の基本的な直感の一つです（ただし、通常は2つの数の実際の差にも関心がありますが、これは順序では示されません）。順序の他の身近な例としては、辞書の単語のアルファベット順や、人々の集団における直系の子孫という系譜上の性質などが挙げられます。
順序という概念は非常に一般的で、順序や相対的な量といった直感的で直接的な感覚を伴う文脈にとどまりません。他の文脈では、順序は包含関係や専門化といった概念を捉えることもあります。抽象的に言えば、この種の順序は部分集合関係に相当し、例えば「小児科医は医師である」や「円は楕円の特殊なケースにすぎない」といった関係が挙げられます。
自然数の「より小さい」関係や単語のアルファベット順など、一部の順序には特別な性質があります。それは、各要素を他のどの要素とも比較できる、つまり、より小さい（より早い）、より大きい（より遅い）、または同じである、という性質です。しかし、他の多くの順序にはそのような性質はありません。例えば、集合の集合の部分集合の順序を考えてみましょう。鳥の集合と犬の集合はどちらも動物の集合の部分集合ですが、鳥も犬も互いの部分集合ではありません。比較できない要素を許容する「部分集合」関係のような順序は部分順序と呼ばれ、すべての要素のペアが比較可能な順序は全順序と呼ばれます。
順序理論は、このような例から生じる順序の直感を、一般的な設定で捉えるものです。これは、関係 ≤ が数学的順序であるために満たさなければならない性質を規定することによって実現されます。このより抽象的なアプローチは非常に理にかなっています。なぜなら、特定の順序の詳細に焦点を当てることなく、一般的な設定で数多くの定理を導き出すことができるからです。そして、これらの知見は、より抽象度の低い多くの応用にも容易に適用できます。
順序の幅広い実用的な用途に後押しされ、数多くの特殊な順序集合が定義され、その中には独自の数学分野に発展したものもある。さらに、順序理論は様々な種類の順序関係に限定されることなく、それらの間の適切な関数も考慮する。関数の順序理論的な性質の簡単な例は、単調関数が頻繁に現れる解析学から得られる。
半順序に関する最も初期の明確な言及は、おそらく19世紀以前には見当たらないだろう。この点において、ジョージ・ブールの著作は非常に重要である。さらに、チャールズ・サンダース・パース、リヒャルト・デデキント、エルンスト・シュレーダーの著作も、順序理論の概念を考察している。
1961年の教科書には、秩序幾何学の貢献者たちが列挙されていた。
1882年にパッシュが、測定に頼らずとも秩序の幾何学を展開できることを初めて指摘した。彼の公理系は、ペアノ（1889年）、ヒルベルト（1899年）、ヴェブレン（1904年）によって徐々に改良されていった。
— HSM コクセター、幾何学入門
1901年、バートランド・ラッセルは「秩序の概念について」[ 1 ]を著し、数列の生成を通してこの概念の基礎を探求した。彼は『数学原理』第4部（1903年）でこのテーマに再び触れた。ラッセルは、二項関係aRb はaからbへ進む意味を持ち、その逆の関係は反対の意味を持ち、意味は「秩序と数列の源泉である」と指摘した（95ページ）。彼は、イマヌエル・カント[ 2 ]が「論理的対立と正と負の対立の違いを認識していた」ことを認めている。彼は、カントが「非対称関係の論理的重要性に最初に注目した」功績を称えられるべきだと書いている。
部分順序集合の略語としてのposetという用語は、影響力のある著書『格子理論』の第 2 版でギャレット・バーコフに帰せられています。[ 3 ] [ 4 ]
このセクションでは、集合論、算術、二項関係の概念に基づいて、順序集合を紹介します。
順序は特別な二項関係です。Pを集合とし、≤ をP上の関係とします（「集合上の関係」とは「集合の要素間の関係」、つまり ≤ は直積P × Pの部分集合であることを意味します）。このとき、≤ が半順序であるのは、それが反射的、反対称的、推移的である場合、すなわち、Pのすべてのa、b、cに対して、次の式が成り立つ場合です。
半順序を持つ集合は、半順序集合、poset、または意図する意味が明確な場合は単に順序集合と呼ばれます。これらの性質を調べると、自然数、整数、有理数、実数上のよく知られた順序はすべて上記の意味での順序であることがすぐにわかります。ただし、これらの例には、任意の2つの要素が比較可能であるという追加の性質があります。つまり、Pのすべてのaとbに対して、次のことが成り立ちます。
この性質を持つ半順序は全順序と呼ばれます。これらの順序は線形順序または連鎖とも呼ばれます。多くの馴染みのある順序は線形ですが、集合上の部分集合順序はそうでない例を示しています。別の例として、可除性（または「因数である」）関係 | があります。2 つの自然数nとmに対して、 n がm を割り切る場合、 n | mと書きます。これが半順序になることは容易にわかります。たとえば、3 は 13 を割り切れず、13 も 3 を割り切れないため、3 と 13 は整数の集合上の可除性関係の比較可能な要素ではありません。任意の集合上の恒等関係 = も、2 つの異なる要素が比較できない半順序です。また、半順序の反対称性と同値関係の対称性の両方を満たすため、半順序と同値関係の両方である唯一の関係でもあります。半順序集合の高度な性質の多くは、主に非線形順序に関して興味深いものです。
ハッセ図は、半順序の要素と関係を視覚的に表現できます。これは、頂点が半順序集合の要素であり、順序関係が辺と頂点の相対的な位置によって示されるグラフ図です。順序は下から上に描かれます。要素xがyより小さい（先行する）場合、 xからyへの上向きの経路が存在します。要素を結ぶ辺が交差する必要がある場合が多いですが、要素が辺の内側に位置してはなりません。参考になる演習として、|（割り切れる関係）で順序付けられた 13 以下の自然数の集合のハッセ図を描いてみましょう。
無限集合の一部も、有限部分順序に省略記号（…）を重ねることで図示できる。これは自然数には有効だが、0 より上位の直接の後継者が存在しない実数には適用できない。しかし、多くの場合、同様の図に関連する直観を得ることができる。
半順序集合には、特別な役割を果たす要素が存在する場合があります。最も基本的な例は、半順序集合の最小要素です。例えば、1 は正の整数の最小要素であり、空集合は部分集合順序の下で最小の集合です。形式的には、要素mが最小要素であるとは、次の条件を満たす場合です。
最小要素を表す記号として 0 がよく使われますが、これは数値が関係しない場合でも同様です。しかし、数値の集合の順序においては、0 が常に最小とは限らないため、この記号は不適切または曖昧になる場合があります。上記の割り算の順序 | がその一例です。1 は他のすべての数値を割り切るため、最小要素です。一方、0 は他のすべての数値で割り切れる数です。したがって、0 はこの順序の中で最大の要素です。最小要素と最大要素を表すその他の一般的な用語としては、bottomとtop、またはzeroとunit などがあります。
実数の例が示すように、最小値と最大値は存在しない場合もあります。しかし、存在する場合は常に一意です。対照的に、集合 {2,3,4,5,6} 上の整除関係 | を考えてみましょう。この集合には上も下もありませんが、要素 2、3、5 にはそれより小さい要素がなく、4、5、6 にはそれより大きい要素がありません。このような要素は、それぞれ最小値と最大値と呼ばれます。形式的には、要素mが最小値であるとは、次の条件を満たす場合です。
≤ を ≥ に置き換えると、極大性の定義が得られます。例が示すように、極大要素は多数存在し、一部の要素は極大かつ最小である可能性があります (上記の 5 など)。ただし、最小要素が存在する場合は、それが順序の中で唯一の最小要素となります。繰り返しますが、無限半順序集合では極大要素が常に存在するとは限りません。与えられた無限集合のすべての有限部分集合を部分集合の包含関係で順序付けした集合は、多くの反例の 1 つを提供します。特定の条件下で極大要素の存在を保証するための重要なツールは、ツォルンの補題です。
半順序集合の部分集合は順序を継承します。これは、誘導された可除性順序を持つ自然数の部分集合 {2,3,4,5,6} を考えることで既に適用しました。今度は、順序の何らかの部分集合に関して特別な半順序集合の要素も存在します。これは、上界の定義につながります。ある半順序集合Pの部分集合Sが与えられたとき、 Sの上界とは、 Sのすべての要素よりも大きいPの要素b のことです。形式的には、これは次のことを意味します。
下限は、再び順序を反転することによって定義されます。たとえば、−5 は整数の部分集合としての自然数の下限です。集合の集合が与えられた場合、部分集合の順序の下でのこれらの集合の上限は、それらの和集合によって与えられます。実際、この上限は非常に特殊です。それは、すべての集合を含む最小の集合です。したがって、集合の集合の最小上限を見つけました。この概念は上限または結合とも呼ばれ、集合Sに対してsup( S ) または最小上界の場合。逆に、最大下界はinfimumまたはmeetと呼ばれ、inf( S ) またはと表記されます。これらの概念は、順序理論の多くの応用において重要な役割を果たします。2つの要素xとyに対して、次のように書くこともできます。そしてそれぞれsup({ x , y }) と inf({ x , y }) に対して。
例えば、1は正の整数を整数の部分集合として捉えた場合の最小値である。
別の例として、自然数における関係 | をもう一度考えてみましょう。2 つの数の最小の上限は、両方の数で割り切れる最小の数、つまりそれらの数の最小公倍数です。逆に、最大の下限は最大公約数によって与えられます。
これまでの定義では、ある概念は、前の定義における順序を反転させるだけで定義できることをしばしば指摘してきました。これは、「最小」と「最大」、「最小値」と「最大値」、「上限」と「下限」などにも当てはまります。これは順序理論における一般的な状況です。与えられた順序は、方向を入れ替えるだけで反転できます。図で言えば、ハッセ図を上から下に反転させるということです。これにより、いわゆる双対順序、逆順序、または反対順序が得られます。
順序理論におけるすべての定義には双対が存在します。双対とは、定義を逆順序に適用することによって得られる概念です。すべての概念は対称であるため、この操作によって半順序の定理は維持されます。与えられた数学的結果に対して、順序を反転させ、すべての定義をその双対に置き換えるだけで、別の有効な定理が得られます。これは、1つの定理のコストで2つの定理が得られるため、重要かつ有用です。詳細と例については、順序理論における双対性に関する記事を参照してください。
与えられた順序から順序を構築する方法は数多くあります。双対順序はその一例です。もう一つの重要な構成は、 2つの半順序集合の直積と、要素のペアの積順序を組み合わせたものです。順序は、( a , x ) ≤ ( b , y ) がa ≤ bかつx ≤ yの場合に限り成り立つと定義されます。（この定義では、関係記号 ≤ には 3 つの異なる意味があることに注意してください。） 2 つの半順序集合の非交和も、順序構築の典型的な例であり、順序は元の順序の（非交）和になります。
すべての半順序 ≤ は、 a ≤ bかつb ≤ aでない場合にa < bと定義することで、いわゆる厳密な順序< を生み出します。この変換は、 a < bまたはa = bの場合にa ≤ bと設定することで反転できます。この 2 つの概念は同等ですが、状況によっては、一方の方が扱いやすい場合があります。
半順序集合間の関数には、2 つの集合の順序関係に関連する特定の追加的な性質があると考えるのが妥当です。この文脈で発生する最も基本的な条件は単調性です。半順序集合Pから半順序集合Qへの関数fは、 Pにおいてa ≤ bならばQにおいてf ( a ) ≤ f ( b ) が成り立つ場合、単調、または順序保存的であると言えます(厳密には、ここでの 2 つの関係は異なる集合に適用されるため、異なる関係であることに注意してください)。この含意の逆は、順序反映関数、つまり、 f ( a ) ≤ f ( b )ならばa ≤ bが成り立つような、上記のような関数fにつながります。一方、関数は、 a ≤ bならばf ( a ) ≥ f ( b )が成り立つ場合、順序反転または反音であることもあります。
順序埋め込みとは、順序を保存する関数であり、かつ順序を反映する関数である。これらの定義の例は容易に見つけることができる。例えば、自然数をその次の数に写像する関数は、自然数に関して単調であることは明らかである。離散的な順序、すなわち単位元順序で順序付けられた集合からの関数も単調である。各自然数を対応する実数に写像することは、順序埋め込みの例となる。冪集合の補集合は、反音関数の例である。
重要な問題は、2つの順序が「本質的に等しい」、つまり要素の名前変更を除いて同じであるのはどのような場合かということです。順序同型とは、そのような名前変更を定義する関数です。順序同型とは、単調逆関数を持つ単調全単射関数です。これは、全射順序埋め込みであることと同等です。したがって、順序埋め込みの像f ( P ) は常にPと同型であり、これが「埋め込み」という用語の正当性を示しています。
より複雑なタイプの関数は、いわゆるガロア接続によって与えられます。単調ガロア接続は、互いに「完全に」逆ではないものの、密接な関係を持つ、逆方向の2つの関数のペアで構成されているため、順序同型写像の一般化と見なすことができます。
半順序集合上の自己写像のもう一つの特殊なタイプは閉包演算子であり、これは単調であるだけでなく、冪等性（すなわちf ( x ) = f ( f ( x ))）と拡張性（または膨張性）（すなわちx ≤ f ( x )）も持ちます。これらは、数学に現れるあらゆる種類の「閉包」において多くの応用例があります。
順序関係だけでなく、半順序集合間の関数は、特別な要素や構成に関しても良好な振る舞いを示すことがあります。例えば、最小要素を持つ半順序集合について考える場合、この要素を保存する単調関数、つまり最小要素を最小要素に写像する関数のみを考慮するのが妥当に思えるかもしれません。二項下限∧が存在する場合、すべてのxとyについてf ( x∧y ) = f ( x )∧f ( y )を満たすことを要求するのが妥当な性質かもしれません。これらの性質、そして実際には他にも多くの性質を、極限保存関数というラベルの下にまとめることができます。
最後に、視点を反転させて、順序関数から関数の順序に切り替えることができます。実際、2つの半順序集合PとQの間の関数は、要素ごとの順序によって順序付けできます。2つの関数fとgについて、Pのすべての要素xに対してf ( x ) ≤g ( x )が成り立つ場合、f≤gとなります。これは、例えば関数空間が重要な役割を果たす領域理論で発生します。
順序理論で研究される構造の多くは、さらに特性を持つ順序関係を利用しています。実際、半順序ではない関係の中にも、特別な関心を集めるものがあります。中でも、前順序の概念は特に重要です。前順序とは、反射的かつ推移的であるものの、必ずしも反対称的ではない関係です。各前順序は、要素間に同値関係を誘導します。ここで、 a ≤ bかつb ≤ aの場合、aはbと同値です。前順序は、この関係に関して同値なすべての要素を特定することによって、順序に変換できます。
順序の項目に関する数値データから、いくつかの種類の順序を定義できます。各項目に異なる実数を付与し、数値比較を用いて項目を順序付けると、全順序が得られます。一方、異なる項目が同じ数値スコアを持つことを許容すると、厳密な弱順序が得られます。2つのスコアを比較する前に一定の閾値で区切る必要があるとすると、半順序の概念が生まれ、閾値を項目ごとに変化させると、区間順序が得られます。
空でないすべての部分集合が最小要素を持つことを要求することが、いわゆる整礎順序の定義特性である。整順序を線形順序から部分順序に一般化すると、集合の空でないすべての部分集合が有限個の最小要素を持つ場合、その集合は整部分順序であると言う。
特定の集合の下限と上限の存在が保証される場合、他にも多くの種類の順序が生じます。通常、順序の完全性と呼ばれるこの側面に注目すると、次のようになります。
しかし、さらに進むと、すべての有限非空下限が存在する場合、∧ は普遍代数の意味で全二項演算と見なすことができます。したがって、束では ∧ と ∨ の 2 つの演算が利用可能であり、次のような恒等式を与えることによって新しい性質を定義できます。
この条件は分配性と呼ばれ、分配束を生み出します。順序理論における分配性に関する記事で議論されている、他にも重要な分配法則がいくつかあります。代数演算と定義恒等式によって指定されることが多い追加の順序構造には、次のようなものがあります。
これらはどちらも、否定と呼ばれる新しい演算を導入します。これらの構造はどちらも数理論理学において重要な役割を果たし、特にブール代数はコンピュータ科学において重要な応用分野を持っています。最後に、数学におけるさまざまな構造は、クォンタレスの場合のように、順序とさらに多くの代数演算を組み合わせ、加算演算の定義を可能にします。
半順序集合には他にも多くの重要な性質が存在する。例えば、半順序集合は、その中のすべての閉区間[ a , b ] が有限である場合に局所的に有限である。局所的に有限な半順序集合は接続代数を生み出し、この接続代数を用いて有限有界半順序集合のオイラー標数を定義することができる。
順序付けられた集合では、与えられた順序に基づいて多くの種類の特別な部分集合を定義できます。簡単な例として、上位集合があります。これは、順序において自分より上位にあるすべての要素を含む集合です。形式的には、半順序集合P内の集合Sの上位閉包は、集合 { x ∈ P | S内にy ≤ xを満たすyが存在する} で与えられます。上位閉包と等しい集合を上位集合と呼びます。下位集合は双対的に定義されます。
より複雑な下位部分集合はイデアルであり、その要素の任意の2つがイデアル内に上限を持つという追加の性質を持つ。その双対はフィルターによって与えられる。関連する概念として、有向部分集合がある。これはイデアルと同様に有限部分集合の上限を含むが、下位集合である必要はない。さらに、これはしばしば前順序集合に一般化される。
部分順序集合として線形順序を持つ部分集合を鎖と呼ぶ。反対の概念である反鎖とは、比較可能な要素を2つも含まない部分集合、すなわち離散順序を持つ部分集合のことである。
ほとんどの数学分野では何らかの形で順序が用いられているが、単なる応用にとどまらない、より深い関係性を持つ理論もいくつか存在する。以下に、それらの理論と順序理論との主な接点についていくつか紹介する。
既に述べたように、普遍代数の手法と形式体系は、多くの順序論的考察において重要なツールである。特定の恒等式を満たす代数構造を用いて順序を形式化するだけでなく、代数との他の関連性を確立することもできる。例えば、ブール代数とブール環の対応関係が挙げられる。また、与えられた生成元に基づく自由束などの自由構成の存在も重要な課題である。さらに、閉包作用素は普遍代数の研究において重要である。
位相幾何学において、順序は非常に重要な役割を果たします。実際、開集合の集合は、完全束、より正確には完全ハイティング代数（または「フレーム」または「ロケール」）の古典的な例を提供します。フィルタとネットは順序理論と密接に関連する概念であり、集合の閉包演算子を使用して位相を定義することができます。これらの関係を超えて、位相幾何学は開集合束のみの観点から見ることができ、これは無点位相幾何学の研究につながります。さらに、位相幾何学の基礎となる集合の要素の自然な前順序は、いわゆる特殊化順序によって与えられます。これは、位相幾何学がT 0の場合、実際には部分順序です。
逆に、順序理論では、位相的な結果がよく利用されます。順序の部分集合を定義する方法はいくつかあり、それらは位相の開集合とみなすことができます。 半順序集合 ( X , ≤) 上の位相で、特殊化順序として ≤ を誘導するものを考えると、最も細かい位相は、すべての上側集合を開集合とすることで得られるアレクサンドロフ位相です。逆に、特殊化順序を誘導する最も粗い位相は、主イデアルの補集合(つまり、あるxに対して{ y in X | y ≤ x }の形の集合)を部分基底とする上側位相です。さらに、特殊化順序 ≤ を持つ位相は、順序整合的である可能性があり、これは、その開集合が (≤ に関して) 有向上限によって到達不可能であることを意味します。最も細かい順序整合的位相はスコット位相であり、これはアレクサンドロフ位相よりも粗いものです。この考え方に基づく 3 番目の重要な位相は、ローソン位相です。これらの位相と順序理論の概念の間には密接な関係がある。例えば、関数が有向上限を保持するのは、それがスコット位相に関して連続である場合に限る（このため、この順序理論的な性質はスコット連続性とも呼ばれる）。
ハッセ図を用いた順序の可視化には、単純な一般化が可能である。すなわち、小さい要素を大きい要素の下に表示する代わりに、グラフのエッジに方向を与えることで順序の方向を表現できる。このようにして、各順序は有向非巡回グラフと等価であることがわかる。このグラフのノードは半順序集合の要素であり、a ≤ bの場合に限り、aからbへの有向パスが存在する。非巡回性という条件を取り除けば、すべての前順序も得られる。
すべての推移的エッジを備えたこれらのグラフは、要素がオブジェクトであり、2 つの要素間の射の各集合が最大でシングルトンである特別なカテゴリになります。順序間の関数は、カテゴリ間のファンクターになります。順序理論の多くのアイデアは、小さなカテゴリ理論の概念にすぎません。たとえば、インフィマムはカテゴリ積にすぎません。より一般的には、インフィマとスプレマは、カテゴリ極限(または余極限)という抽象的な概念の下に捉えることができます。カテゴリのアイデアが現れるもう 1 つの場所は、(単調)ガロア接続の概念であり、これは随伴ファンクターのペアとまったく同じです。
しかし、圏論はより広い範囲で順序論にも影響を与えている。上で述べたように、適切な関数を持つ半順序集合のクラスは興味深い圏を形成する。積順序のような順序の構成を圏を用いて表現できる場合も多い。順序の圏が、例えば位相空間の圏など、他の圏と圏論的に同値であることが判明すると、さらなる洞察が得られる。この研究の流れは、ストーン双対性という名称でまとめられることが多い、様々な表現定理へと繋がる。
{{cite book}}ISBN /日付の不一致（ヘルプ）