数学において、有向集合(または有向前順序集合、フィルター集合)とは、すべての有限部分集合に上限が存在する前順序集合のことである。[ 1 ]言い換えれば、空でない前順序集合である。任意のそしてで存在するでとそして[ a ]有向集合の先行順序は方向と呼ばれます。
上記で定義された概念は、上向きの集合。下向きの有向集合は対称的に定義され、 [ 2 ]すべての有限部分集合には下限が。 [ 3 ]一部の著者(およびこの記事)は、特に断りがない限り、有向集合は上向きであると仮定します。他の著者は、集合が上向きと下向きの両方に有向である場合に限り、その集合を有向集合と呼びます。 [ 4 ]
有向集合は、空でない全順序集合の一般化である。つまり、すべての全順序集合は有向集合である(有向である必要のない半順序集合とは対照的である)。結合半束(半順序集合)も有向集合であるが、その逆は成り立たない。同様に、束は上方向と下方向の両方において有向集合である。
位相幾何学では、有向集合を用いてネットが定義され、ネットは数列を一般化し、解析学で用いられる様々な極限の概念を統一する。また、有向集合は抽象代数学や(より一般的には)圏論における直接極限を生み出す。
自然数の集合通常の命令では有向集合の最も重要な例の 1 つです。すべての全順序集合は有向集合であり、 も含まれます。そして
方向を持たない部分順序集合の(自明な)例としては、集合 がある。唯一の順序関係はそしてより些細ではない例としては、次のような「向かう実数」の例がある。「ただし、順序付けルールは同じ側の要素のペアにのみ適用されます。(つまり、要素を取る場合)の左側そしてその右側に、そして比較できない部分集合上限はありません。
抽象書き換えシステムが合流的であれば、その推移閉包は有向集合である。
させてそして有向集合である。すると、デカルト積集合は定義することで有向集合にすることができるかつその場合に限りそして積の順序に類似して、これはデカルト積の積の方向です。たとえば、集合自然数のペアは、定義することで有向集合にすることができる。かつその場合に限りそして
もしが実数である場合、集合定義することで有向集合に変換できるもし(つまり「より大きな」要素は) そして、実数はこれは、部分順序で も全順序でもない有向集合の例です。これは、すべてのペアに対して反対称性が破綻するためです。そしてから等距離どこそして反対側にある具体的には、これは次のような場合に起こります。本当のその場合そしてそれでもこの予約注文が定義されていたらの代わりにそうすれば、依然として有向集合を形成するが、今度は(唯一の)最大要素を持つことになる。具体的にはしかし、それでも部分順序付けはされません。この例は距離空間に一般化できます。定義によりまたは予約注文かつその場合に限り
要素予約注文したセットのは、すべての に対して であれば極大要素である。暗示する[ b ] すべての
最大要素を持つ任意の順序付き集合は、同じ順序を持つ有向集合である。例えば、半順序集合では要素のすべての下閉包。つまり、形式のすべての部分集合。どこ固定要素指示されている。
順序付けられた集合は、最大要素の集合(空集合である可能性もある)が最大要素の集合と等しい場合に限り、方向性を持つ。
部分集合包含関係二重の任意の集合族に対して半順序を定義する。空でない集合族は、半順序に関して有向集合である。(それぞれ、) は、そのメンバーの任意の 2 つの共通部分 (または和集合) が、ある第 3 メンバーを部分集合として含む (または部分集合として含む) 場合に限ります。記号で表すと、ファミリーは集合の方向は(それぞれ、) の場合に限り
または同等に、
これらの半順序を用いて、有向集合の重要な例を数多く定義することができる。例えば、定義によれば、プリフィルタまたはフィルタ基底は、半順序に関して有向集合である空でない集合族である。また、空集合も含まない(この条件は自明性を防ぐ。そうでなければ、空集合はに関して最大の要素となるからである)。) πシステム(空でない集合族であり、そのメンバーの任意の 2 つの共通部分に関して閉じている) は、 に関して有向集合である。すべてのλシステムは、すべてのフィルター、トポロジー、およびσ代数は、両方に関して有向集合である。そして
定義によれば、ネットは有向集合からの関数であり、数列は自然数からの関数である。すべてのシーケンスは、と
もし有向集合からの任意のネットすると任意のインデックスに対してセットは、開始家族すべての尾部は、 ;\,} 実際、それはプリフィルターです。
もしは位相空間であり、はポイントですすべての近隣の集合を記述することで、有向集合に変換できます。かつその場合に限りを含むすべてのそして:
セット集合のすべての有限部分集合のうちに関して指示されている任意の2つが与えられたので彼らの結婚は上限ですそしてでこの特定の有向集合は、和を定義するために使用されます。一般化された一連のインデックス付きの数値コレクション(あるいはより一般的には、位相ベクトル空間のベクトルなど、アーベル位相群の要素 の和)部分和のネットの極限としてつまり:
させて形式理論とは、特定の性質を持つ文の集合である(その詳細は、この主題に関する記事を参照)。例えば、一次理論(ツェルメロ・フレンケル集合論など)またはより単純な零次理論である可能性がある。前順序集合は有向集合です。そしてもし論理結合によって形成された文を表すそれからそしてどこ もしは、リンデンバウム・タルスキー代数に関連付けられています。それからこれは、半順序集合であり、かつ有向集合でもある。

有向集合は(結合)半束よりも一般的な概念です。すべての結合半束は有向集合であり、2つの要素の結合または最小上界が目的のものです。 しかし、逆は成り立たない。ビットごとに順序付けられた有向集合 {1000,0001,1101,1011,1111} を見ればわかる(例:保持するが、最後のビット1 > 0であるため、そうはなりません。ここで、{1000,0001}には3つの上限がありますが、最小上限はありません(図を参照)。(また、1111がない場合、この集合は有向集合ではないことに注意してください。)
有向集合における順序関係は反対称である必要はなく、したがって有向集合は必ずしも半順序ではない。しかし、有向集合という用語は半順序集合の文脈でも頻繁に使用される。この設定では、部分集合は半順序集合のは、同じ半順序に従って有向集合である場合、有向部分集合と呼ばれます。言い換えれば、空集合ではなく、すべての要素のペアに上限があります。ここで、 の要素の順序関係は、から継承されるそのため、反射律と推移律を明示的に要求する必要はない。
半順序集合の有向部分集合は、下方閉包である必要はありません。半順序集合の部分集合が有向であるのは、その下方閉包がイデアルである場合のみです。有向集合の定義は「上方有向」集合(すべての要素のペアに上限がある)に対するものですが、すべての要素のペアに共通の下限がある下方有向集合を定義することもできます。半順序集合の部分集合が下方有向であるのは、その上方閉包がフィルターである場合のみです。
有向部分集合は、有向完全半順序を研究する領域理論で使用されます。[ 5 ]これらは、すべての上向きの集合が最小上界を持つことが要求される半順序集合です。この文脈では、有向部分集合は再び収束列の一般化を提供します。