順序集合 ハッセ図

ウィキペディア

順序集合

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/15 07:39 UTC 版)

ハッセ図

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

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

頂点：P の元

a ∈ P から b ∈ P への辺がある ⇔ a < b であり、しかも a < c < b を満たす c ∈ P が存在しない

（すなわち b は a を被覆している）

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

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

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

a < b ⇔ a から b への道がある

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

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

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

• x が A の上界 (upper bound) であるとは、A の任意の元 y に対して y ≤ x となること。
• x が A の上限 (supremum) あるいは最小上界 (least upper bound) であるとは、x が A の上界全体の集合の最小元となること。これは存在すれば一意的に決まり、sup A あるいは lub A と表される。
• x が A の最大元 (maximum element) であるとは、x は A の元であり、かつ x は A の上界であること。これは存在すれば一意的に決まり、max A で表される。
• x が A の極大元 (maximal element) であるとは、x は A の元であり、かつ y > x を満たす y ∈ A が存在しないこと。

• x が A の下界 (lower bound) であるとは、A の任意の元 y に対して y ≥ x となること。
• x が A の下限 (infimum) あるいは最大下界 (greatest lower bound) であるとは、x が A の下界全体の集合の最大元となること。これは存在すれば一意的に決まり、inf A あるいは glb A と表される。
• x が A の最小元 (minimum element) であるとは、x は A の元であり、かつ x は A の下界であること。これは存在すれば一意的に決まり、min A で表される。
• x が A の極小元 (minimal element) であるとは、x は A の元であり、かつ y < x を満たす y ∈ A が存在しないこと。

上界および上限の定義において、 x が必ずしも A の元であるとは限らない、ことには注意が必要である。左閉右開の半開区間 $[a,b)$

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

整除性によって順序付けられた非負整数のハッセ図

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

写像と順序

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

定義

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

• f: S → T が順序を保つ(order-preserving)（同調 (isotone) とも）とは、

任意の x, y ∈ S に対して x ≤ y ⇒ f(x) ≤ f (y)

• f: S → T が順序を逆にする（order-reversing）とは、

任意の x, y ∈ S に対して x ≤ y ⇒ f (x) ≥ f (y)

• 上の2つを合わせて単調 (monotone) 写像という。
• f が順序を反映する (order-reflecting) とは、

任意の x, y ∈ S に対して f (x) ≤ f (y) ⇒ x ≤ y

• f が順序埋め込みであるとは、

任意の x, y ∈ S に対して x ≤ y ⇔ f (x) ≤ f (y)

• f が順序同型写像であるとは、f が順序埋め込みな全単射であることをいう。

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

性質

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

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

具体例

順序を保つが順序を反映しない写像 (f(u) ≤ f(v) だが u ≤ v でない)

120 の約数全体の成す半順序集合（整除関係で順序を入れる）と {2, 3, 4, 5, 8} の整除関係で閉じた部分集合族（包含関係で順序を入れる）との間の順序同型

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