順序論

提供: testwiki
ナビゲーションに移動 検索に移動

テンプレート:More footnotes 順序論（じゅんじょろん、テンプレート:Lang-en-short）は、二項関係を用いて順序の直観的な概念を研究する数学の一分野である。「これはそれより小さい」や「これはそれに先行する」といった命題を記述するための正式な枠組みを提供する。

背景と動機

順序は数学および計算機科学などの関連分野のいたるところに存在する。小学校で最初に議論される順序は、例えば「2 は 3 より小さい」「10 は 5 より大きい」「トムはサリーよりクッキーが少ない？」といった自然数上の標準的な順序である。この直観的な概念は整数や実数などの他の数の集合の順序へと拡張できる。ある数が別の数より大きいまたは小さいという考えは、数体系一般の基本的な直観の一つである（ただし、通常は順序によって与えられない二数の実際の差にも関心が向く）。その他の身近な順序の例としては、辞書における語のアルファベット順や、ある集団の人々の間の直系血縁という系譜学的性質がある。

順序の概念は非常に一般的であり、系列や相対的量の直観的な感覚が即座に得られる文脈を超えて拡張される。他の文脈では、順序は包含または特殊化の概念を捉えることがある。抽象的には、この種の順序は部分集合関係に相当する。例えば「小児科医は医師である」「円は特殊なケースの楕円に過ぎない」といったものである。

「自然数上の小なり」や語のアルファベット順のような一部の順序は特別な性質を持つ。すなわち各要素は他の任意の要素と比較可能であり、小さい（先）か大きい（後）か同一かである。しかし、多くの他の順序はそうではない。例えば集合の集まり上の部分集合順序を考えよう。鳥の集合と犬の集合はいずれも動物の集合の部分集合であるが、鳥が犬の部分集合でも犬が鳥の部分集合でもない。「部分集合」関係のように比較不能な要素を許す順序は半順序と呼ばれ、すべての対の要素が比較可能な順序は全順序と呼ばれる。

順序論はこうした例から生じる順序の直観を一般的な設定で捉える。これは、関係 ≤ が数学的な順序であるために持つべき性質を規定することで達成される。この抽象的なアプローチは非常に有意義である。なぜなら、特定の順序の詳細に焦点を当てることなく、一般的な設定で多くの定理を導くことができ、これらの洞察を多くの具体的な応用に容易に転用できるからである。

順序の広い実際的な使用に動機づけられて、多くの特殊な種類の順序集合が定義されており、その一部は独自の数学的分野へと成長した。さらに、順序論は様々なクラスの順序関係に限らず、それらの間の適切な関数も考察する。関数に対する順序論的性質の単純な例は、関数解析学において単調関数が頻繁に見られることから来る。

基本的定義

本節では集合論、算術、二項関係の概念を基に順序集合を紹介する。

半順序集合

順序は特殊な二項関係である。P を集合とし、≤ を P 上の関係（「集合上の関係」とは「その要素間の関係」を意味し、すなわち ≤ は直積 P × P の部分集合である）とする。このとき ≤ が反射的、反対称的、推移的であれば、≤ は半順序と呼ばれる。すなわち P のすべての a, b, c に対して：

a ≤ a （反射性）
a ≤ b かつ b ≤ a ならば a = b （反対称性）
a ≤ b かつ b ≤ c ならば a ≤ c （推移性）

半順序集合、ポセット、または意図が明確な場合は単に順序集合と呼ばれる。これらの性質を確認することで、自然数、整数、有理数、実数上のよく知られた順序がすべて上記の意味での順序であることが直ちにわかる。しかし、これらの例にはさらに任意の二要素が比較可能という性質がある。すなわち P のすべての a, b に対して：

a ≤ b または b ≤ a

この性質を持つ半順序は全順序と呼ばれる。これらの順序は線形順序または鎖とも呼ばれる。多くの身近な順序は線形であるが、集合上の部分集合順序はそうでない例を提供する。別の例は整除関係（または「因数である」関係）| によって与えられる。二つの自然数 n と m に対して、n が m を余りなく割るならば n|m と書く。これが半順序を与えることは容易に確認できる。例えば 3 は 13 を割らず 13 も 3 を割らないので、整数の整除関係において 3 と 13 は比較不能な要素である。 任意の集合上の等号関係 = も、任意の二つの相異なる要素が比較不能な半順序である。これはまた、半順序の反対称性と同値関係の対称性を共に満たすため、半順序かつ同値関係である唯一の関係でもある。ポセットの多くの高度な性質は主として非線形順序に対して興味深い。

ポセットの視覚化

整除関係で半順序を付けた60の約数全体の集合のハッセ図

ハッセ図はポセットの要素と関係を視覚的に表現できる。これらはグラフの描画であり、頂点がポセットの要素で、順序関係は辺と頂点の相対的な配置の両方によって示される。順序は下から上に描かれる。要素 x が y より小さい（先行する）ならば、x から y への上方向のパスが存在する。要素を結ぶ辺が互いに交差することはしばしば必要であるが、要素は決して辺の内部に位置してはならない。実習として、13 以下の自然数の集合に対して | 関係（整除関係）でハッセ図を描くと良い。

無限集合の一部も、有限な部分順序に省略記号（…）を重ねることで図示できる。これは自然数ではうまくいくが、0 の上に直接の後継者がない実数ではうまくいかない。しかし、しばしば類似の種類の図に関連した直観を得ることができるテンプレート:Vague。

順序内の特殊な要素

半順序集合において特別な役割を果たすいくつかの要素があるかもしれない。最も基本的な例はポセットの最小元によって与えられる。例えば 1 は正の整数の最小元であり、空集合は部分集合順序の最小の集合である。形式的には、要素 m が最小元であるのは：

m ≤ a, 順序のすべての要素 a に対して。

記号 0 は最小元に対してよく用いられ、数が関わらない場合でも使われる。しかし数の集合の順序においては、数 0 が常に最小とは限らないので、この記法は不適切または曖昧になりうる。上記の整除順序 | での例では、1 はすべての他の数を割るので最小元である。対照的に、0 は他のすべての数に割られる数であるので、順序の最大元である。最小元と最大元の他のよく使われる用語は底と頂、または零と単位である。

最小元と最大元は、実数の例が示すように存在しないこともある。しかし存在するならば常に一意である。対照的に、集合 {2,3,4,5,6} 上の整除関係 | を考えよう。この集合は頂も底も持たないが、要素 2, 3, 5 はそれらより下の要素を持たず、4, 5, 6 はそれらより上の要素を持たない。そのような要素はそれぞれ極小および極大と呼ばれる。形式的には、要素 m が極小であるのは：

a ≤ m が a = m を意味する、順序のすべての要素 a に対して。

≤ を ≥ と交換することで極大性の定義が得られる。例が示すように、極大元は多数存在しうるし、ある要素は極大かつ極小でありうる（上の 5 など）。しかし最小元が存在すれば、それが順序の唯一の極小元である。再び、無限ポセットでは極大元は常に存在するわけではない——与えられた無限集合のすべての有限部分集合の集合を部分集合包含で順序付けたものが反例の一つを提供する。一定の条件の下で極大元の存在を保証する重要なツールはツォルンの補題である。

半順序集合の部分集合は順序を受け継ぐ。上で自然数の部分集合 {2,3,4,5,6} を誘導整除順序で考えることでこれを適用した。さてまた、順序の一部の部分集合に関して特別なポセットの要素もある。これが上界の定義に導く。あるポセット P の部分集合 S が与えられたとき、S の上界とは S のすべての要素より上にある P の要素 b である。形式的には：

s ≤ b, S のすべての s に対して。

下界は逆に順序を反転することで定義される。例えば −5 は整数の部分集合としての自然数の下界である。集合の集まりが与えられたとき、部分集合順序でのこれらの集合の上界はその和集合によって与えられる。実はこの上界は非常に特別で、すべての集合を含む最小の集合である。かくして集合の集まりの上限を見つけた。この概念は上限または結びとも呼ばれ、集合 S の上限を sup(S) または ⋁S で表す。逆に、下限は下限または交わりとして知られ inf(S) または ⋀S で表す。これらの概念は順序論の多くの応用において重要な役割を果たす。二つの要素 x と y に対して、sup({x,y}) と inf({x,y}) をそれぞれ x∨y と x∧y でも表す。

例えば 1 は整数の部分集合としての正の整数の下限である。

別の例として、自然数上の関係 | を再び考えよう。二つの数の上限は両方に割られる最小の数、すなわち数の最小公倍数である。下限は最大公約数によって与えられる。

双対性

前述の定義において、概念は以前の定義の順序を反転するだけで定義できることをしばしば注記した。これは「最小」と「最大」、「極小」と「極大」、「上界」と「下界」などについて当てはまる。これは順序論の一般的な状況である。与えられた順序はその方向を交換するだけで反転でき、図的にはハッセ図を上下逆にする。これにより双対、逆、または反対順序と呼ばれるものが得られる。

すべての順序論的定義はその双対を持つ。それは定義を逆順序に適用することで得られる概念である。すべての概念が対称的であるので、この操作は半順序の定理を保存する。与えられた数学的結果に対して、順序を反転してすべての定義をその双対で置き換えるだけで別の有効な定理が得られる。これは一つの価格で二つの定理を得るので重要かつ有用である。詳細と例については双対性 (順序論)の記事を参照。

新しい順序の構成

与えられた順序から順序を構成する多くの方法がある。双対順序はその一例である。もう一つの重要な構成は、二つの半順序集合の直積であり、要素の対に対する積順序と合わせて取られる。順序は (a, x) ≤ (b, y) が (かつその場合に限り) a ≤ b かつ x ≤ y によって定義される。（この定義において関係記号 ≤ には三つの異なる意味があることに注意されたい。）二つのポセットの非交和は順序構成の別の典型的な例であり、順序は元の順序の（非交和的な）和集合に過ぎない。

すべての半順序 ≤ は狭義順序 < を生じさせる。a ≤ b かつ b ≤ a でなければ a < b と定義することで。この変換は a < b または a = b ならば a ≤ b と設定することで反転できる。二つの概念は等価であるが、状況によってはどちらかがより扱いやすい。

順序間の関数

半順序集合間の関数を考察する際、二つの集合の順序関係に関連する追加的な性質を持つ関数を考慮することは合理的である。この文脈で最も基本的な条件は単調性である。ポセット P からポセット Q への関数 f が単調または順序保存的であるのは、P での a ≤ b が Q での f(a) ≤ f(b) を意味する場合である（厳密には、ここでの二つの関係は異なる集合に適用されるので異なることに注意）。この含意の逆は順序反映的な関数に至る。すなわち f(a) ≤ f(b) が a ≤ b を意味する上記の関数 f。一方、a ≤ b が f(a) ≥ f(b) を意味する場合、関数は順序反転的または反調であるかもしれない。

順序埋め込みは、順序保存的かつ順序反映的な両方の性質を持つ順序間の関数 f である。これらの定義の例は容易に見つかる。例えば、自然数をその後続者に写す関数は自然順序に関して明らかに単調である。離散順序、すなわち等号順序「=」で順序付けられた集合からの任意の関数も単調である。各自然数を対応する実数に写すことは順序埋め込みの例を与える。冪集合上の集合補元は反調関数の例である。

重要な問いは、二つの順序がいつ「本質的に等価」か、すなわち要素の名前を変えるだけで同じかどうかである。順序同型はそのような名前の変更を定義する関数である。順序同型とは単調な逆関数を持つ単調な全単射関数である。これは全射的な順序埋め込みであることと等価である。したがって、順序埋め込みの像 f(P) は常に P と同型であり、「埋め込み」という用語を正当化する。

より精緻な種類の関数はガロア接続によって与えられる。単調なガロア接続は順序同型の一般化とみなすことができる。それらは逆方向の二つの関数の対から成り、互いの「真の」逆ではないが、依然として密接な関係を持つ。

ポセット上の自己写像の別の特殊な型は閉包作用素であり、単調なだけでなく冪等、すなわち f(x) = f(f(x))、かつ拡張的（または膨張的）、すなわち x ≤ f(x) でもある。これらは数学に現れるあらゆる種類の「閉包」に多くの応用がある。

順序関係だけでなく、ポセット間の関数は特殊な要素や構成に関しても良く振る舞うかもしれない。例えば最小元を持つポセットを議論するとき、この元を保存する、すなわち最小元を最小元に写す単調関数のみを考えることは合理的に思える。二項の交わり ∧ が存在するならば、合理的な性質はすべての x と y に対して f(x ∧ y) = f(x) ∧ f(y) を要求することかもしれない。これらのすべての性質、そして実際にはさらに多くのものが、極限を保存する関数という標題の下に集めることができる。

最後に、順序の関数から関数の順序へと視点を逆転させることができる。実際、二つのポセット P と Q の間の関数は点ごとの順序を介して順序付けられうる。二つの関数 f と g に対して、P のすべての要素 x に対して f(x) ≤ g(x) ならば f ≤ g である。これは例えばドメイン理論において関数空間が重要な役割を果たす文脈で生じる。

特殊な種類の順序

順序論で研究される多くの構造は、さらなる性質を持つ順序関係を採用している。実際、半順序でない一部の関係さえも特別な関心の対象となる。主として前順序の概念に言及しなければならない。前順序とは反射的かつ推移的であるが必ずしも反対称的ではない関係である。各前順序は要素間の同値関係を誘導する。a ≤ b かつ b ≤ a ならば a は b と同値である。前順序は、この関係に関して同値なすべての要素を同一視することで順序に変換できる。

順序のいくつかの種類は順序の項目に対する数値データから定義できる。各項目に相異なる実数を付与し数値比較を用いて項目を順序付けることで全順序が得られる。代わりに相異なる項目が等しい数値スコアを持つことを許すと狭義弱順序が得られる。二つのスコアが比較される前に固定の閾値だけ離れていることを要求すると半順序の概念に、一方で項目ごとに閾値が変化することを許すと区間順序が得られる。

すべての空でない部分集合が極小元を持つことを要求するのが整礎順序と呼ばれるものの定義的性質である。線形から半順序への整順序の一般化として、集合はそのすべての空でない部分集合が有限個の極小元を持つならば整半順序である。

一定の集合の下限と上限の存在が保証されたとき、他の多くの種類の順序が生じる。順序の完備性と通常呼ばれるこの側面に焦点を当てることで、次が得られる。

さらに進むこともできる。すべての有限の空でない交わりが存在すれば、∧ は普遍代数学の意味での全二項演算として見ることができる。したがって束では二つの演算 ∧ と ∨ が利用可能で、等式を与えることで新しい性質を定義できる。例えば：

x ∧ (y ∨ z)  =  (x ∧ y) ∨ (x ∧ z), すべての x, y, z に対して。

この条件は分配律と呼ばれ分配束を生み出す。順序論における分配律の記事でいくつかの他の重要な分配律が議論されている。代数的演算と定義する等式によって規定されることの多い他の追加的な順序構造として：

があり、いずれも否定と呼ばれる新しい演算 ~ を導入する。両構造は数理論理学において役割を果たし、特にブール代数は計算機科学において大きな応用がある。 最後に、数学のさまざまな構造は量子包)) (quantale) の場合のように、さらに代数的な演算と順序を組み合わせ、加法演算の定義を可能にする。

多くの他の重要なポセットの性質が存在する。例えば、ポセットがすべての閉区間 [a, b] が有限ならば、ポセットは局所有限という。局所有限ポセットは入射代数を生み出し、それを用いて有限有界ポセットのオイラー標数を定義できる。

順序集合の部分集合

順序集合では、与えられた順序に基づいて多くの種類の特殊な部分集合を定義できる。単純な例は上集合、すなわち順序においてそれ以上の要素をすべて含む集合である。形式的には、ポセット P の集合 S の上部閉包は {x in P | S のある y について y ≤ x} によって与えられる。上部閉包と等しい集合を上集合という。下集合は双対的に定義される。

より複雑な下部分集合はイデアルであり、その二つの要素がイデアル内に上界を持つという追加の性質を持つ。その双対はフィルターによって与えられる。関連する概念として有向集合があり、イデアルのように有限部分集合の上界を含むが、下集合である必要はない。さらに、前順序集合に一般化されることが多い。

部分ポセットとして線形順序付けられた部分集合は鎖と呼ばれる。反対の概念、反鎖は比較可能な二要素を含まない部分集合、すなわち離散順序である。

関連数学分野

ほとんどの数学分野は何らかの形で順序を使うが、単なる応用を大きく超えた関係を持ついくつかの理論もある。順序論との主要な接点とともに、その一部を以下に紹介する。

普遍代数学

すでに述べたように、普遍代数学の方法と形式主義は多くの順序論的考察の重要なツールである。特定の等式を満たす代数的構造による順序の形式化のほか、代数への他の接続を確立することもできる。例としてブール代数とブール環の対応が挙げられる。その他の問題は、与えられた生成元の集合に基づく自由束のような自由な構成の存在に関する。さらに、閉包作用素は普遍代数学の研究において重要である。

位相幾何学

位相論において順序は非常に顕著な役割を果たす。実際、開集合の集まりは完備束、より正確には完備なハイティング代数（または「フレーム」あるいは「ロカール」）の古典的な例を提供する。フィルターとネットは順序論と密接に関連する概念であり、集合の閉包作用素は位相を定義するために使える。これらの関係を超えて、位相は開集合の束の観点からのみ見ることもでき、これはポイントレス位相論の研究に至る。さらに、位相の基礎集合の要素の自然な前順序は、位相がT₀である場合に実際には半順序となる特殊化順序として与えられる。

逆に、順序論では位相論の結果をしばしば利用する。順序の部分集合として位相の開集合とみなせるものを定義するさまざまな方法がある。ポセット (X, ≤) 上の位相でその特殊化順序として ≤ を誘導するものを考えると、そのような位相のうち最細のものはアレクサンドロフ位相であり、すべての上集合を開集合として取ることで与えられる。逆に、特殊化順序を誘導する最粗の位相は上位相であり、主要イデアルの補元（すなわちある x に対して {y in X | y ≤ x} の形の集合）を準開基として持つ。さらに、特殊化順序 ≤ を持つ位相は順序整合的であるかもしれない。すなわちその開集合が（≤ に関して）有向上限によって「到達不能」である。最細の順序整合位相はスコット位相であり、これはアレクサンドロフ位相より粗い。この精神における第三の重要な位相はローソン位相である。これらの位相と順序論の概念の間には密接な接続がある。例えば、関数が有向上限を保存するのは、それがスコット位相に関して連続である場合に限る（この理由から、この順序論的性質はスコット連続性とも呼ばれる）。

圏論

ハッセ図による順序の視覚化には直接的な一般化がある。より低い要素を上位の要素の下に表示する代わりに、順序の方向はグラフの辺に向きを与えることでも表現できる。このようにして各順序は有向非巡回グラフと等価とみなされ、ノードはポセットの要素であり、a ≤ b の場合に限り a から b への有向パスが存在する。非巡回性の要件を外すことで、すべての前順序も得ることができる。

推移的なすべての辺を装備したとき、これらのグラフはいずれも圏の特殊な例であり、要素が対象、任意の二要素間の射の集合は高々一元素集合である。順序間の関数は圏間の関手となる。順序論の多くの考えは小さな圏論の概念に過ぎない。例えば、交わりは単に圏論的直積である。より一般的に、交わりと結びは圏論的極限（または余極限）の抽象的な概念の下に捉えることができる。圏論的考えが現れる別の場所は（単調な）ガロア接続の概念であり、これは随伴関手の対とまったく同じである。

しかし圏論はより大きなスケールでも順序論に影響を及ぼす。上で議論したような適切な関数を持つポセットのクラスは興味深い圏を形成する。しばしば積順序のような順序の構成を圏の言語で述べることもできる。順序の圏が位相空間などの他の圏と圏論的に同値であることが判明すると、さらなる洞察が得られる。この研究の方向はストーン双対性の標題の下にしばしばまとめられるさまざまな表現定理に至る。

歴史

前述のように、順序は数学のいたるところに存在する。しかし、半順序の最も早い明示的な言及はおそらく19世紀以前には見出されない。この文脈ではジョージ・ブールの業績が重要である。さらにチャールズ・サンダース・パース、リヒャルト・デデキント、エルンスト・シュレーダーの業績も順序論の概念を考察している。

順序幾何学への貢献者は1961年の教科書に記録されている。 テンプレート:Blockquote

1901年にバートランド・ラッセルは「順序の概念について」[2]を著し、系列の生成を通じてこの考えの基礎を探求した。彼は1903年の『数学の諸原理』第IV部でこのトピックに戻った。ラッセルは二項関係 aRb が 逆関係が反対方向を持つ a から b へと進む向きを持ち、向きは「順序と系列の源である」と述べた。（p 95）彼はイマヌエル・カント[3]が「論理的対立と正と負の対立の違いを認識していた」ことを認めている。彼はカントが「非対称関係の論理的重要性に最初に注意を向けた」としてカントに貢献を帰した。

「ポセット」という用語は半順序集合の略語としてガーレット・バーコフの影響力ある著書『格子理論』第2版に帰されている。テンプレート:Sfn[4]

関連項目

注釈

テンプレート:脚注ヘルプ テンプレート:Reflist

参考文献

外部リンク

テンプレート:Wiktionary

テンプレート:集合論 テンプレート:順序論

  1. ↑ テンプレート:Citation
  2. ↑ Bertrand Russell (1901) Mind 10(2)
  3. ↑ Immanuel Kant (1763) Versuch den Begriff der negativen Grosse in die Weltweisheit einzufuhren
  4. ↑ テンプレート:Cite web
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=順序論&oldid=14240」から取得