順序論

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

順序論は、バイナリ関係を使用して順序の直感的な概念を調査する数学の一分野です。これは、「これはそれよりも小さい」または「これはその前にある」などのステートメントを記述するための正式なフレームワークを提供します。この記事では、フィールドを紹介し、基本的な定義を提供します。順序論の用語のリストは、順序論の用語集にあります。

背景と動機

注文は数学やコンピュータサイエンスのような関連分野のいたるところにあります小学校でよく議論される最初の順序は、自然数の標準的な順序です。たとえば、「2は3未満」、「10は5より大きい」、「トムのCookieはサリーより少ないですか?」などです。この直感的な概念は、整数実数など、他ののセットの順序に拡張できます別の数よりも大きいまたは小さいという考えは、一般に、数体系(記数法と比較)の基本的な直感の1つです(ただし、通常、実際の違いにも関心があります)順序によって与えられていない2つの数字の)。順序付けの他のよく知られた例は、辞書内の単語のアルファベット順と、人々のグループ内 の直系の降下の系図的特性です。

順序の概念は非常に一般的であり、シーケンスまたは相対的な量の即時の直感的な感覚を持つコンテキストを超えて拡張されます。他のコンテキストでは、注文は封じ込めまたは特殊化の概念を取り込む場合があります。抽象的には、このタイプの順序はサブセットの関係になります。たとえば、「小児科医医師です」、「は単なる特殊な楕円です」などです。

自然数の「未満」や単語のアルファベット順など、一部の順序には特別な特性があります。各要素は他の要素と比較できます。つまり、小さい(早い)、大きい(遅い)、またはと同じ。ただし、他の多くの注文はそうではありません。たとえば、セットのコレクションのサブセットの順序を考えてみます。鳥のセットと犬のセットはどちらも動物のセットのサブセットですが、鳥も犬も他方のサブセットを構成していません。比較できない要素が存在する「サブセットの」関係のような順序は、半順序と呼ばれます。要素のすべてのペアが比較可能な注文は、合計注文です。

順序論は、一般的な設定でそのような例から生じる順序の直感をキャプチャします。これは、関係≤が数学的な順序でなければならないというプロパティを指定することによって実現されます。このより抽象的なアプローチは、特定の順序の詳細に焦点を当てることなく、一般的な設定で多数の定理を導き出すことができるため、非常に理にかなっています。これらの洞察は、抽象度の低い多くのアプリケーションに簡単に転送できます。

注文の幅広い実用的な使用法に駆り立てられて、多数の特別な種類の注文セットが定義されており、そのうちのいくつかは独自の数学分野に成長しています。さらに、順序論は、それ自体をさまざまなクラスの順序関係に限定するのではなく、それらの間の適切な機能も考慮します。関数の順序論的特性の簡単な例は、単調関数が頻繁に見つかる 分析から得られます。

基本的な定義

このセクションでは、集合論算術、および二項関係の概念に基づいて順序集合を紹介します

半順序集合

注文は特別なバイナリ関係です。Pが集合であり、≤がPの関係あると仮定します(「集合の関係」は「その住民の関係」を意味すると解釈されます)。次に、≤は、反射的反対称的、推移的である場合、つまりPのすべてのab、およびcに対して、次のようになります。

a≤a (再帰
a≤bかつb≤a場合a = b 反対称_
a≤bかつb≤c場合 a≤c 推移_

半順序のセットは、半順序セットポセット、または意図された意味が明確な場合は単に順序セットと呼ばれます。これらの特性をチェックすることにより、自然数整数有理数実数のよく知られた次数がすべて上記の意味での次数であることがすぐにわかります。ただし、これらの例には、任意の2つの要素が比較可能であるという追加の特性があります。つまりPのすべてのabについて、次のようになります。

a≤bまたはb≤a_ _ _ _

このプロパティを持つ部分的な注文は、全順序と呼ばれます。これらのオーダーは、線形オーダーまたはチェーンと呼ばれることもあります多くのよく知られた順序は線形ですが、セットのサブセット順序は、これが当てはまらない例を示しています。別の例は、分割可能性(または「is-a- factor - of」)関係|によって与えられます。2つの自然数nmについて、 n |と書きます。nがmを除算する場合はm 残りなし。これにより半順序が生成されることが簡単にわかります。単位元=は、任意のセットで、2つの異なる要素ごとに比較できない半順序でもあります。これは、半順序と同値関係の両方である唯一の関係でもあります。ポセットの多くの高度なプロパティは、主に非線形次数にとって興味深いものです。

ポセットの視覚化

60のすべての除数のセットのハッセ図、分割可能性によって半順序

ハッセ図は、半順序の要素と関係を視覚的に表すことができます。これらは頂点がポセットの要素であり、順序関係がエッジと頂点の相対的な位置の両方によって示されるグラフ描画です。順序はボトムアップで描画されます。要素xがyよりも小さい(先行する)場合、 xからyへのパスが存在します。それは上向きです。多くの場合、要素を接続するエッジが互いに交差する必要がありますが、要素をエッジ内に配置してはなりません。有益な演習は、13以下の自然数のセットのハッセ図を描くことです。分割関係)。

一部の無限集合でさえ、有限のサブオーダーに省略記号(...)を重ね合わせることで図解できます。これは自然数ではうまく機能しますが、0を超える直接の後継がない実数では失敗します。ただし、非常に多くの場合、同様の種類の図に関連する直感を得ることができます[漠然とした]

注文内の特別な要素

半順序集合では、特別な役割を果たすいくつかの要素が存在する場合があります。最も基本的な例は、半順序集合の最小要素によって与えられます。たとえば、1は正の整数の最小要素であり、空のセットはサブセットの順序で最小のセットです。正式には、要素mは、次の場合に最小要素です。

m≤a、次数すべての要素aに対して。

表記0は、数値が関係していない場合でも、最小要素に対して頻繁に検出されます。ただし、一連の番号の順序では、番号0が常に最小であるとは限らないため、この表記は不適切またはあいまいな場合があります。例は、上記の分割可能次数|で示されます。ここで、1は、他のすべての数値を分割するため、最小要素です。対照的に、0は他のすべての数値で割った数値です。したがって、それは秩序の最大の要素です。最小要素と最大要素のその他のよくある用語は、、またはゼロ単位です。

実数の例が示すように、最小要素と最大要素は存在しない可能性があります。しかし、それらが存在する場合、それらは常に一意です。対照的に、分割可能性の関係を考えてみましょう。セット{2,3,4,5,6}。このセットには上も下もありませんが、要素2、3、および5には下に要素がなく、4、5、および6には上に要素がありません。このような要素は、それぞれ最小および最大と呼ばれます。正式には、要素mは次の場合 に最小になります。

a≤mは、次数すべての要素aに対してa = mを意味します。

≤を≥と交換すると、最大性の定義が得られます例が示すように、多くの最大要素が存在する可能性があり、一部の要素は最大と最小の両方である可能性があります(たとえば上記の5)。ただし、最小の要素がある場合、それは注文の唯一の最小要素です。繰り返しますが、無限ポセットでは、最大要素が常に存在するとは限りません。サブセットの包含順に並べられた、特定の無限セットのすべての有限サブセットのセットは、多くの反例の1つを提供します。特定の条件下で最大要素の存在を保証するための重要なツールは、ツォルンの補題です。

半順序集合のサブセットは、順序を継承します。自然数のサブセット{2,3,4,5,6}を、誘導された分割可能順序で検討することにより、これをすでに適用しました。現在、順序の一部のサブセットに関して特別な半順序集合の要素もあります。これは、上限の定義につながりますある半順序集合PのサブセットSが与えられると、 Sの上限はSのすべての要素の上にあるPの要素bです正式には、これは

s≤b Sすべてs

下限も、順序を逆にすることで定義されます。たとえば、-5は、整数のサブセットとしての自然数の下限です。セットのセットが与えられると、サブセットの順序付けの下でのこれらのセットの上限は、それらの集合によって与えられます。実際、この上限は非常に特殊です。これは、すべてのセットを含む最小のセットです。したがって、集合のセットの最小の上限が見つかりました。この概念は、上限または結合とも呼ばれ、集合Sの場合、 sup(S)またはその最小の上限のために。逆に、最大の下限はinfimumまたはmeetとして知られており、inf(S)またはこれらの概念は、順序論の多くのアプリケーションで重要な役割を果たします。2つの要素xyの場合、1つは次のようにも記述します。それぞれsup({ xy })とinf({ xy })の場合。

たとえば、1は、整数のサブセットとしての正の整数の最小値です。

別の例として、関係|をもう一度考えてみましょう。自然数について。2つの数値の最小公倍数は、両方で除算された最小の数値、つまり最小公倍数です。次に、最大公約数は最大公約数によって与えられます。

二元性

以前の定義では、以前の定義の順序を逆にするだけで概念を定義できることによく気づきました。これは、「最小」と「最大」、「最小」と「最大」、「上限」と「下限」などの場合です。これは順序論の一般的な状況です。特定の順序は、ハッセ図を上から下に絵で反転させて、方向を交換するだけで反転できます。これにより、いわゆるデュアルインバース、または逆の順序が生成されます。

すべての順序論的定義には二重性があります。それは、定義を逆の順序に適用することによって得られる概念です。すべての概念は対称であるため、この操作は半順序の定理を保持します。与えられた数学的結果に対して、順序を逆にしてすべての定義をそれらの双対で置き換えることができ、別の有効な定理を得ることができます。1つの価格で2つの定理が得られるため、これは重要で便利です。いくつかの詳細と例は、順序論の二重性に関する記事にあります。

新しい注文の作成

与えられた注文から注文を作成する方法はたくさんあります。二重注文はその一例です。もう1つの重要な構造は、要素のペアの積順序と一緒に取られた、2つの半順序集合のデカルト積です。順序付けは、 a≤bかつx≤yの場合(およびその場合のみ)、a x ≤(by )によって定義されます(この定義では、関係記号≤には3つの異なる意味があることに注意してください。)非交和2つの半順序集合は、順序構築のもう1つの典型的な例であり、順序は元の順序の(互いに素な)和集合にすぎません。

すべての半順序≤はb≤aではなくa≤b場合にa < bを定義することにより、いわゆる厳密な順序<を生じさせますこの変換は、a < bまたはa = bの場合、 a≤bを設定することで反転できます2つの概念は同等ですが、状況によっては、一方が他方よりも操作しやすい場合があります。

注文間の機能

2つのセットの順序関係に関連する特定の追加プロパティを持つ半順序セット間の関数を検討することは合理的です。このコンテキストで発生する最も基本的な条件は単調性です。Pのa≤bがQのf a≤fb 意味する場合ポセットPからポセットQへの関数f単調、または順序保存です。(厳密には、ここでの2つの関係は、異なるセットに適用されるため、異なります。)この含意の逆は、順序を反映する関数、つまり、fa ) ≤f b)がa≤b意味する上記の関数fにつながります一方、a≤bがfa)≥f b 意味する場合、関数は順序反転またはアンチトーンである可能性もあります

順序埋め込みは、注文を保持し、注文を反映する注文間関数fです。これらの定義の例は簡単に見つかります。たとえば、自然数をその後継にマッピングする関数は、自然数に関して明らかに単調です。離散順序からの関数、つまり恒等式順序「=」で順序付けられたセットからの関数も単調です。各自然数を対応する実数にマッピングすると、順序埋め込みの例が示されます。べき集合集合補集合は、アンチトーン関数の例です。

重要な問題は、2つの順序が「本質的に等しい」場合、つまり要素の名前を変更するまで同じである場合です。順序同型は、そのような名前変更を定義する関数です。順序同型は、単調逆関数を持つ単調全単射関数です。これは、全射順序埋め込みであることに相当します。したがって、順序埋め込みのイメージfP)は常にPと同型であり、これは「埋め込み」という用語を正当化します。

より複雑なタイプの関数は、いわゆるガロア接続によって与えられます。単調ガロア接続は、互いに「完全に」逆ではないが、それでも密接な関係を持っている、逆方向の2つの関数のペアで構成されているため、順序同型の一般化と見なすことができます。

半順序集合上の別の特殊なタイプの自己マップは、単調であるだけでなくべき等である閉包作用素、つまりfx= f f x )、および広範囲(またはインフレ)、つまりx≤fx)。これらは、数学に現れるあらゆる種類の「クロージャー」に多くの用途があります。

単なる順序関係と互換性があることに加えて、ポセット間の関数は、特別な要素や構造に関してもうまく動作する可能性があります。たとえば、最小要素を持つ半順序集合について話す場合、この要素を保持する単調関数、つまり最小要素を最小要素にマップする単調関数のみを検討するのが合理的と思われる場合があります。バイナリインフィマ∧が存在する場合、合理的なプロパティは、すべてのxyについて、 f(x∧y)= fx∧fy要求することです。これらのすべてのプロパティ、および実際にはさらに多くのプロパティは、制限保持関数のラベルの下でコンパイルできます。

最後に、ビューを反転して、順序の関数から関数の順序に切り替えることができます実際、2つの半順序集合PQの間の関数は、点ごとの順序で並べ替えることができます2つの関数fgについてPのすべての要素xに対してf x ≤g x の場合、 f≤gになります。これは、たとえば、関数空間が重要な役割を果たす 領域理論で発生します。

特別な種類の注文

順序論で研究されている構造の多くは、さらなる特性を持つ順序関係を採用しています。実際、半順序ではない一部の関係でさえ、特に興味深いものです。主に予約注文の概念について言及する必要があります。プレオーダーは、反射的で推移的な関係ですが、必ずしも反対称である必要はありません。各事前順序は、要素間に同値関係を引き起こします。ここで、 a≤bおよびb≤a場合aはb同等です。この関係に関して同等であるすべての要素を識別することにより、予約注文を注文に変えることができます。

注文のアイテムの数値データから、いくつかのタイプの注文を定義できます。合計注文は、各アイテムに個別の実数を付け、数値比較を使用してアイテムを注文することで得られます。代わりに、個別のアイテムが等しい数値スコアを持つことが許可されている場合、厳密な弱順序が取得されます。比較する前に2つのスコアを固定のしきい値で区切る必要があると、準順序の概念が導き出されますが、しきい値をアイテムごとに変更できるようにすると、区間順序が生成されます。

追加の単純だが有用なプロパティは、いわゆる十分な根拠につながり、空でないサブセットはすべて最小限の要素を持ちます。線形から半順序への適切な順序を一般化すると、空でないすべてのサブセットに有限数の最小要素がある場合 、セットは部分的に適切に順序付けられます。

特定のセットのinfimasupremaの存在が保証されている場合、他の多くのタイプの注文が発生します。通常、注文の 完全性と呼ばれるこの側面に焦点を当てると、次のようになります。

ただし、さらに先に進むことができます。すべての有限の空でないインフィマが存在する場合、∧は普遍代数の意味での完全な二項演算と見なすことができますしたがって、ラティスでは、2つの操作∧と∨が使用可能であり、1つは次のようなIDを与えることによって新しいプロパティを定義できます。

x∧  (y∨z)=(x∧y  ∨   x∧z  、すべてxyおよび z に対して

この状態は分配法則と呼ばれ、分配を生じさせます。順序論における分配法則に関する記事で説明されている他のいくつかの重要な分配法則があります代数演算と定義IDを介して指定されることが多いいくつかの追加の順序構造は次のとおりです。

どちらも、否定と呼ばれる新しい操作を導入します。両方の構造は数理論理学で役割を果たし、特にブール代数はコンピューターサイエンスで主要なアプリケーションを持っています。最後に、数学のさまざまな構造は、加算演算の定義を可能にする、 量子の場合のように、次数とさらに多くの代数演算を組み合わせます。

ポセットの他の多くの重要なプロパティが存在します。たとえば、半順序集合は、その中のすべての閉区[ ab ]が有限である場合、局所的に有限です。局所有限半順序集合は、隣接代数を生成します。これを使用して、有限有界半順序集合 のオイラー標数を定義できます。

順序集合のサブセット

順序集合では、指定された順序に基づいて、多くの種類の特別なサブセットを定義できます。簡単な例は上方セットです; つまり、順番にそれらの上にあるすべての要素を含むセット。正式には、半順序集合Pの集合Sの上部閉包集合{ x in P | Sにはy≤x }のyあります上方閉鎖に等しい集合は上方集合と呼ばれます。下位セットは二重に定義されます。

より複雑な下位サブセットは理想であり、要素の2つごとに理想内の上限があるという追加のプロパティがあります。それらの双対はフィルターによって与えられます。関連する概念は、有向サブセットの概念です。これは、理想のように有限サブセットの上限を含みますが、下限セットである必要はありません。さらに、それはしばしば事前注文されたセットに一般化されます。

サブポーズとして線形に順序付けられたサブセットは、チェーンと呼ばれます。反対の概念である反鎖は、2つの同等の要素を含まないサブセットです。つまり、それは個別の注文です。

関連する数学分野

ほとんどの数学分野は、いずれかの方法で順序を使用しますが、単なる適用をはるかに超えた関係を持ついくつかの理論もあります。順序論との主要な接点とともに、これらのいくつかを以下に示します。

普遍代数

すでに述べたように、普遍代数の方法と形式は、多くの順序論的考察にとって重要なツールです。特定の恒等式を満たす代数的構造の観点から順序を形式化することに加えて、代数への他の接続を確立することもできます。例は、ブール代数ブール環の間の対応によって与えられます。他の問題は、生成元の特定のセットに基づく自由束などの自由構造の存在に関係しています。さらに、閉包作用素は普遍代数の研究において重要です。

トポロジー

トポロジーでは、注文が非常に重要な役割を果たします。実際、開集合のコレクションは、完全な格子、より正確には完全なハイティング代数(または「フレーム」または「ロケール」)の古典的な例を提供します。フィルタネットは順序論に密接に関連する概念であり、セットの閉包作用素を使用してトポロジを定義できます。これらの関係を超えて、トポロジーは開集合格子の観点からのみ見ることができ、それは無意味なトポロジーの研究につながります。さらに、トポロジーの基礎となるセットの要素の自然な事前順序は、いわゆる特殊化順序によって与えられます、トポロジがT 0の場合、これは実際には半順序です。

逆に、順序論では、トポロジー結果を利用することがよくあります。トポロジーのオープンセットと見なすことができるオーダーのサブセットを定義するさまざまな方法があります。特殊化順序として≤を誘導するポセット(X、≤)のトポロジーを考慮すると、そのような最も優れたトポロジーは、すべての上方セットを開いたものとして与えられるアレクサンドロフトポロジーです。逆に、特殊化順序を誘発する最も粗いトポロジーは、主イデアルの補集合(つまり、いくつかのxに対して{ y in X | y≤x }形式のセット)を持つ上位トポロジーです。サブベースさらに、特殊化順序≤のトポロジは順序が一貫している可能性があります。これは、それらの開集合が(≤に関して)「有向supremaによってアクセスできない」ことを意味します。最高の順序の一貫したトポロジーはスコットトポロジーであり、これはアレクサンドロフトポロジーよりも粗いです。この精神における3番目の重要なトポロジーは、ローソントポロジーですこれらのトポロジーと順序論の概念の間には密接な関係があります。たとえば、関数は、スコットトポロジーに関して連続である場合にのみ、有向超越を保持します(このため、この順序論的特性はスコット連続とも呼ばれます)。

圏論

ハッセ図を使用した順序の視覚化には、簡単な一般化があります。大きい要素のに小さい要素を表示する代わりに、グラフのエッジに方向を指定することで順序の方向を表すこともできます。このように、各次数は有向非巡回グラフと同等であることがわかります。ここで、ノードは半順序集合の要素であり a≤bの場合に限り、aからbへの有向パスがあります非周期的であるという要件を取り除くことで、すべての予約注文を取得することもできます。

すべての推移的なエッジを備えている場合、これらのグラフは、要素がオブジェクトであり、2つの要素間の射の各セットが最大でシングルトンである特別なカテゴリになります。注文間の関数は、カテゴリ間のファンクターになります。順序論の多くのアイデアは、小さな圏論の概念にすぎません。たとえば、最小と上限は単なるカテゴリ積です。より一般的には、カテゴリの制限(またはそれぞれcolimit )の抽象的な概念の下でinfimaとsupremaをキャプチャできます。カテゴリのアイデアが発生するもう1つの場所は、(単調な)ガロア接続の概念です。これは、随伴関手のペアとまったく同じです。

しかし、圏論は、より大規模な順序論にも影響を及ぼします。上記のように適切な機能を持つ半順序集合のクラスは、興味深いカテゴリを形成します。多くの場合、製品注文のように、カテゴリの観点から注文の構成を述べることもできます。順序のカテゴリが他のカテゴリとカテゴリ的に同等であることがわかった場合、たとえば位相空間など、さらに洞察が得られます。この一連の研究は、ストーン双対性のラベルの下で収集されることが多いさまざまな表現定理につながります。

歴史

前に説明したように、注文は数学の至る所にあります。ただし、半順序の最も初期の明示的な言及は、おそらく19世紀以前には見られないでしょう。この文脈では、ジョージ・ブールの作品は非常に重要です。さらに、チャールズ・サンダース・パースリヒャルト・デーデキンドエルンスト・シュレーダーの作品も順序論の概念を考慮しています。

順序幾何学への貢献者は1961年の教科書に記載されていました:

測定を参照せずに秩序の幾何学を開発できることを最初に指摘したのは1882年のパッシュでした。彼の公理体系は、ペアノ(1889)、ヒルベルト(1899)、ヴェブレン(1904)によって徐々に改善されました。

—  HSMコクセター、幾何学入門

1901年、バートランドラッセルは、「秩序の概念について」[2]を書き、シリーズの生成を通じてアイデアの基礎を探りました彼は数学の原則(1903)のパートIVのトピックに戻りました。ラッセルは、二元関係 aRbはaからbに進む意味を持ち逆関係は反対の意味を持ち、意味は「秩序と級数の源である」と述べました。(p 95)彼はイマヌエル・カントを認めている[3]「論理的な反対とポジティブとネガティブの反対の違いを知っていた」。彼は、「非対称関係の論理的重要性に最初に注意を向けた」ので、カントは称賛に値すると書いた。

半順序集合の略語としてのポセットという用語は、彼の影響力のある本LatticeTheoryの第2版でGarrettBirkhoffによって造られました。[4] [5]

も参照してください

メモ

  1. ^ Roller、Martin A.(1998)、Pocセット、中央値代数および群作用。 ダンウッディの構造とサゲエフの定理(PDF)の拡張研究、サウサンプトンプレプリントアーカイブ、2016年3月4日にオリジナル(PDF)からアーカイブ、2015 1月18日取得
  2. ^ バートランドラッセル(1901)マインド10(2)
  3. ^ Immanuel Kant(1763) Versuch den Begriff dernegativen Grosse in die Weltweisheit einzufuhren
  4. ^ Birkhoff 1940、p。1.1。
  5. ^ 「数学の単語(P)のいくつかの最も初期の既知の使用法」jeff560.tripod.com

参考文献

外部リンク