順序集合 ハッセ図

順序集合

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/01/02 20:55 UTC 版)

ハッセ図

三元集合 {x, y, z}部分集合の全体を包含関係を順序とする順序集合とみたときのハッセ図

P を有限集合とし、「<」を P 上の狭義の半順序とするとき、以下のようにして P を自然に単純有向グラフとみなせる:

頂点:P の元
aP から bP への辺がある⇔ a < b であり、しかも a < c < b を満たす cP が存在しない。(すなわち ba を被覆している)。

この有向グラフを図示したものをハッセ図という。

ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。 例えばこの図で {x}{x, y, z} は比較可能だが、{x}{y} は比較不能である。また一元集合の族 {{x}, {y}, {z}} は反鎖である。さらに {x}{x, z} によって被覆されるが、{x, y, z} には被覆されない。

なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に (V, E) を閉路を持たない有限な単純有向グラフとすると、V 上に以下の順序を入れる事で V を半順序集合とみなせる:

a < ba から b への道がある。

したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。

上界、最大、極大、上限、上方集合

P半順序集合とし、A をその部分集合とし、xPとする。このとき上界、最大、極大、上限の概念、およびこれらの双対概念である下界、最小、極小、下限は以下のように定義される:

定義

  • xA上界resp. 下界): yA : yx (resp. yx)
  • xA上限(resp. 下限): x は集合 {yP | yA の上界(resp. 下界)} の最小元(resp. 最大元)
  • xA最大元(resp. 最小元): xA の元でしかも xA の上界(resp. 下界)である
  • xA極大元(resp. 極小元): xA の元でしかも y > x (resp. y < x) を満たす yA が存在しない

上界および上限の定義において、 xA に必ずしも属しているとは限らない、ことには注意が必要である。

極大元の概念と最大元の概念は以下の点で異なる。まず xA の極大元であるとは、A の元は「x 以下である」か、もしくは「x とは大小が比較不能である」かのいずれかである事を意味する。一方 xA の最大元であるとは A の元は常に x 以下である事を意味する(このとき xA の任意の元と比較が可能である)。したがって最大元は必ず極大元であるが、極大元は必ずしも最大元であるとは限らない。

さらに AP上方集合英語版(resp. 下方集合)であるとは、任意の aA x > a (resp. x < a) を満たす任意の P の元に対しxA となることをいう。

具体例

三元集合の冪集合のハッセ図から最大元と最小元を取り除いたもの。この図の一番上の行にある各元がこの半順序の極大元であり、一番下の行の各元は極小元である。最大元と最小元はない。集合 {x, y} は元の族 {{x}, {y}} に対する上界を与える。
整除性によって順序付けられた非負整数のハッセ図

正整数全体の成す集合を整除関係で順序付ける時、1 は任意の正整数を割り切るという意味において 1 は最小元である。しかしこの半順序集合には最大元は存在しない(任意の正整数の倍数としての 0 を追加して考えたとするならば、それが最大元になる)。この半順序集合には極大元も存在しない。実際、任意の元 g はそれとは異なる例えば 2g を割り切るから g は極大ではありえない。この半順序集合から最小元である 1 を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関して 60 は部分集合 {2, 3, 5, 10} の上界(上限ではない)を与えるが、1 は除かれているので下界は持たない。他方、2 の冪全体の成す部分集合に対して 2 はその下界(これは下限でもある)を与えるが、上界は存在しない。

写像と順序

順序に関する写像の概念に以下のものがある:

定義

S, T を順序集合とし、f: ST を写像とする。このとき

  • f: ST順序を保つ英語版(order-preserving)(同調 (isotone)とも)とは、任意の x, yS に対して xyf(x) ≤ f (y) である事を言う。
  • f: ST順序を逆にするorder-reversing英語版)とは、任意の x, yS に対して xyf (x) ≥ f (y) である事を言う。
  • 上の2つを合わせて単調 (monotone) 写像と言う。
  • f順序を反映する (order-reflecting) とは任意の x, yS に対して f (x) ≤ f (y) ⇒ xy であることを言う。
  • f順序埋め込み英語版であるとは、任意の x, yS に対し xyf (x) ≤ f (y) である事を言う。
  • f順序同型写像英語版であるとは、f が順序埋め込みな全単射である事を言う。

f: ST が順序埋め込みであるとき、Sf によって T に(順序集合として)埋め込まれるという。 また順序同型 f: ST が存在するとき、ST順序同型あるいは単に同型であるという。

性質

上で述べた概念は以下の性質を満たす:

  • 順序を反映する写像は単射である。実際 f(x) = f(y) ⇒f(x) ≤ f(y) かつ f(x) ≥ f(y) ⇒ xy かつ xyx = y である。
  • f が順序埋め込みである必要十分条件は f が順序を保存し、しかも順序を反映する事である。また全単射 f: ST とその逆関数 f−1: TS が順序同型なら f, f −1 は順序同型である。
  • 順序を保つ写像と順序を保つ写像の合成は順序を保つ。 順序を反映する写像と順序を反映する写像の合成も順序を反映する。

具体例

順序を保つが順序を反映しない写像 (f(u)≤f(v) だが uv でない)
120 の約数全体の成す半順序集合(整除関係で順序を入れる)と {2,3,4,5,8} の整除関係で閉じた部分集合族(包含関係で順序を入れる)との間の順序同型

自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 f: NP(N) を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である(すなわち、xy を割るならば x の各素因数は y の素因数にもなる)が単射ではない(例えば 126 もこの写像で {2, 3} に写る)し、順序を反映もしない(例えば 126 を割らない)。少し設定を変えて、各自然数にその素冪因子英語版の集合を対応させる写像 g: NP(N) を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない(実際、たとえば単元集合 {4} に写る数は無い)が終域g値域 g(N) に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な分配束英語版と呼ばれる半順序集合のクラスに対して一般化することができる(バーコフの表現定理英語版の項を参照)。


  1. ^ 原理的には半順序集合であっても同様の概念を定義できるが、本稿の英語版をはじめ、筆者が調べた範囲では全順序集合に対してのみorder topologyを定義している為、ここでは全順序のみに話を限定した。
  2. ^ 実数体でなくとも上極限位相と下極限位相を考える事ができるが、これも実数体以外に対してこれらの位相を定義した文献が見つけられなかったので、ここでは実数体のみを対象にした。
  3. ^ Ward, L. E. Jr (1954年). “Partially Ordered Topological Spaces”. Proceedings of the American Mathematical Society 5 (1): 144–161. doi:10.1090/S0002-9939-1954-0063016-5. 
  4. ^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8. 





順序集合と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「順序集合」の関連用語

順序集合のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



順序集合のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの順序集合 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2019 Weblio RSS