三元集合 {
x,
y,
z} の部分集合の全体を包含関係を順序とする順序集合とみたときのハッセ図
数学における（半）順序集合（はん-じゅんじょしゅうごう、英: [partially] ordered set, poset）とは整列、序列化、配列、順序付けといった直感的概念を定式化するものである。
目次
- 1 定義
- 1.1 半順序集合（poset）
- 1.2 鎖（chain）
- 1.3 同調写像（isotone map）
- 2 半順序集合に付与する性質
- 2.1 有界性（bounded）
- 2.2 完備性（complete）
- 2.2.1 連続写像（continuous map）
- 3 例
- 4 直積集合上の順序
- 5 位相空間の半順序と連続関数
- 6 整列集合
- 7 線型順序拡大
- 8 順序構造と位相構造
- 9 注記
- 10 参考文献
- 11 関連項目
定義[編集]
半順序集合（poset）[編集]
半順序集合（partially ordered set , poset）とは集合 P と P 上の２項関係 ≦ の組 ＜P ; ≦＞ のことであり、≦ は P の任意の元 a , b , c に対して以下の３条件を満たす[1]。
- 反射律（reflexivity）
- a ≦ a
|
- 推移律（transitivity）
- a ≦ b かつ b ≦ c ならば a ≦ c
|
- 反対称律（antisymmetry）
- a ≦ b かつ b ≦ a ならば a ＝ b
|
半順序関係（partial ordering relation）[2]と呼ばれるこの関係 a ≦ b （b は a を含む と読む）に対し、a < b とは a ≦ b かつ a ≠ b を意味する。さらに、a < b かつ a < x < b となる P の元 x が存在しないとき b は a を覆う（cover）と呼ぶ。
鎖（chain）[編集]
集合 C 上の半順序関係 ≦ が反射律、推移律及び反対称律に加えて以下の条件
- 線型律（linearity）
- C の任意の２元 a , b に対して、a ≦ b または b ≦ a
を満たすとき ＜C ; ≦＞ を鎖（chain）[3]と呼ぶ。
半順序集合の２つの元 a , b に対して、a ≦ b または b ≦ a が成り立つとき a と b は比較可能（comparable）であると言う。半順序集合においては任意の ２元は比較可能とは言えないが、鎖であれば任意の２元は比較可能である。
同調写像（isotone map）[編集]
二つの半順序集合 ＜P ; ≦1＞、＜Q ; ≦2＞ の間の写像 ψ : P → Q で任意の a , b ∈ P（ただし、a ≦1 b） に対して、
- a ≦1 b ならば ψ(a) ≦2 ψ(b)
が成り立つ、すなわち順序関係を保つものを同調写像（isotone map）、単調写像（monotone mapping）または順序保存写像（order-preserving map）と呼ぶ。
半順序集合に付与する性質[編集]
有界性（bounded）[編集]
半順序集合 ＜P ; ≦＞ の台集合 P の部分集合を S とする。任意の S の元 s に対して s ≦ b が成り立つ P の元 b を S の上界（じょうかい、upper bound）と呼ぶ。同様に任意の S の元 s に対して a ≦ s が成り立つ P の元 a を S の下界（かかい、lower bound）と呼ぶ。
部分集合 S が上界を持つとき S は上に有界であるという。同様に、下界を持つとき S は下に有界であるという。上下に有界であるときは、単に有界（bounded）という。
S の上界 l で、S 任意の上界 b に対して、l ≦ b が成り立つものを S の最小上界（lowest upper bound , l.u.b.）または上限（supremum）[4]、結び（join）などと呼び、それぞれ l.u.b.(S) , sup(S) , ∨(S) などと書く。 同様に、S の下界 g で、S の任意の下界 a に対して、a ≦ g が成り立つものを S の最大下界（greatest lower bound , g.l.b.）または下限（infimum）[5]、交わり（meet）などと呼び、それぞれ g.l.b.(S) , inf(S) , ∧(S) などと書く。
部分集合 S の上限（極大元）が S にも属する（a ∈ S）場合、S の最大元（maximum element）、ユニット（unit）、恒等元（identity）、トップ（top）などと呼びmax(S) , 1S（または単純に 1） , T などと書く[6]。 同様に、部分集合 S の下限（極小元）が S にも属する場合、S の最小元（minimum element）、ゼロ（zero）などと呼び min(S) , 0 , ⊥ , ボトム（bottom）などと書く。
完備性（complete）[編集]
半順序集合 ＜P ; ≦＞ の上界を持つ任意の部分集合が最小上界を持つとき完備（complete）もしくは完備半順序集合（complete partially ordered set）と呼ばれる[7]。＜P ; ≦＞ が完備半順序集合であれば、その定義から完備半束（complete lattice）＜P ; ≦ , ∨ , ∧＞ を構成できる。
連続写像（continuous map）[編集]
完備半順序集合 ＜P ; ≦P＞,＜Q ; ≦Q＞ 間の単調写像 f : P → Q が以下を満たすとき連続（continuous）または連続写像（continuous map）と呼ぶ
- P の任意の部分集合 S について、f(g.l.b.(S)) = g.l.b.(f(S)) かつf(l.u.b.(S)) = l.u.b.(f(S)) が成り立つ。
- （ただし、X が集合であるとき f(X) は {f(x) | x ∈ X} を意味する。）
例[編集]
- 都道府県の集合に人口の大小で順序を定めると前順序集合になる。特に人口の等しい都道府県が無ければ全順序集合になる。
- 自然数全体の集合 N、整数全体の集合 Z、有理数全体の集合 Q、実数全体の集合 R は通常の代数的な大小関係によって全順序集合になるが、複素数はそうではない。複素数全体の集合 C に R × R としての辞書式順序を定めたものは全順序集合であるが、この順序は複素数の乗法とは両立しない。
- 自然数全体の成す集合は整除関係を順序として半順序集合である。
- ある集合の冪集合は部分集合の包含関係を順序として半順序集合となる。これは一般には全順序ではない。例えば {1, 2, 3} の冪集合
について、たとえば {1, 2} と {2, 3} を考えれば、これらは比較不能である（{1, 2} ≤ {2, 3} でも {2, 3} ≤ {1, 2} でもない）。
- ベクトル空間の部分空間全体は包含関係で順序付けられた半順序集合である。
- 半順序集合 P に対し、P の元の列全体の成す集合は、列 a, b に対し、
と定めると半順序集合となる。
- 集合 X と半順序集合 P に対し、X から P への写像全体の成す写像空間は、ふたつの写像 f, g に対して、f ≤ g を X の任意の元 x に対して f(x) ≤ g(x) となることとして定義すると、半順序集合になる。
- 非循環有向グラフの頂点集合は、到達不可能性によって順序付けられる。
- 半順序集合における順序関係の向きが a < b > c < d ... というように交互に入れ替わる列をフェンスと呼ぶ。
- 有界半順序集合の例
- 自然数の間に順序 a ≤ b を a | b（a は b の約数）で定義する。集合 {a, b} の上界、下界はそれぞれ a と b の公倍数、公約数であり、上限、下限はそれぞれ最小公倍数、最大公約数である。{1, 2, ..., 10} の極大元は 6, 7, 8, 9, 10 であり、最大元は存在しない。最小元は 1 である。
- 集合 S を S = {m | ある自然数 n が存在して m = 2n} で定義して上と同じ順序を考えると、これは全順序集合になる。写像 f: S → N を f(2n) = n で与えると、これは順序同型になる。ただし、値域の自然数の順序には普通の大小関係を考える。
- S をある集合とし、そのべき集合 2S の間に包含関係による順序を考える。A, B を S のある部分集合とすると、{A, B} の上限、下限はそれぞれ A ∪ B、A ∩ B である。
- ある環の自明でないイデアル全体の集合に包含関係による順序を考える。極大イデアルはこの集合の極大元である。
直積集合上の順序[編集]
ふたつの半順序集合（の台集合）の直積集合上の半順序としては次の三種類が考えられる。
最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの半順序集合の直積に対しても同様に定義される。
体上の順序線型空間に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。
位相空間の半順序と連続関数[編集]
集合 X の冪集合 Pow(X) は集合演算としての結び ∪ と交わり ∩ について束（lattice）＜Pow(X) ; ∪ , ∩＞ をなす。 この部分束 ＜Open(X) ; ∪ , ∩＞ が以下を満たすとき、Open(X) を集合 X の開集合系と呼ぶ。なお、その組（X , Open(X)）を位相空間（topological space）と呼ぶ。
- Open(X) は Pow(X) の部分集合
- X ∈ Open(X) かつ Φ ∈ Open(X) （最大元、最小元の存在）
- 任意の２元 A , B ∈ Open(X) に対して、A ∩ B ∈ Open(X) （交わり演算としての ∩）
- 任意の集合族 Oα , Oβ , ... ∈ Open(X) （α ,β , ... ∈ I）に対して、 ∈ Open(X) （結び演算 ∪ について完備）
これはすなわち組 ＜Open(X) ; ∪ , ∩＞ は結び演算に関して完備な有界束であることに他ならない。ここで、
- A ⊂ B は A ∪ B = B を意味する
と定めるとき、半順序関係 ⊂ は集合間の包含関係に一致する。すなわち、＜Open(X) ; ∪ , ∩ , ⊂＞ は包含関係 ⊂ について上に完備な有界半順序集合となる。
整列集合[編集]
詳細は「整列集合」を参照
順序集合は、その任意の空でない部分集合が最小元を持つとき整列集合 (well-ordered set) であるという。また、その順序を整列順序 (well-order) という。定義からすぐに「整列集合は全順序集合である」ということが分かる。実際、任意の二つの元 a, b をとってきたとき、その二つの元のなす集合 {a, b} にも最小元があるから、a ≤ b か b ≤ a のどちらかが成り立つ。これは全順序であるということに他ならない。
- 自然数全体の集合 N は大小関係によって整列集合になる。
- 普通の大小関係において整数全体の集合 Z、有理数全体の集合 Q、実数全体の集合 R はそうではない。
- Z は 0 < -1 < 1 < -2 < 2 < -3 < 3 < … と順序を定めると整列集合になる。
- Q や R では（特に R では）、このような簡単な修正ではうまく行かない。
しかし、選択公理を仮定すると、次の整列可能定理 (well-ordering theorem、単に整列定理、ツェルメロの整列定理ともいう）が証明できる。
- 任意の集合は整列集合となるように順序を定めることができる。
逆に、整列可能定理を仮定して選択公理を証明することもできるので、整列可能定理は選択公理と同値であり、さらにはツォルンの補題などとも同値である。
線型順序拡大[編集]
全順序 T が半順序 P の線型拡大（あるいは線型拡張）であるとは、P において x ≤ y であるような二元については T においてもなお x ≤ y となっているときにいう。任意の半順序は全順序に拡張することができる（順序拡大原理[8]）。
計算機科学において、半順序の線型拡張を求めるアルゴリズムは位相ソート (topological sorting) と呼ばれる。
順序構造と位相構造[編集]
全順序集合には次のようにして自然に位相構造が定められる。これを順序位相 (order topology) という。例えば、通常の大小関係 ≤ によって実数全体の集合 R を全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。
(A, ≤) を一般の全順序集合とする。無限半開区間(-∞, b)および(a, +∞)全体を準開基とする位相が定まる。これを A の順序位相という。
P が半順序集合で位相空間の構造をも持つとき、慣習的に {(a, b) ∈ P × P | a ≤ b } が直積位相に関する閉部分集合であるものと仮定する。この仮定の下で、半順序関係は
が成り立つという意味で数列の極限に関してよく振舞う (well-behaved)（Deshpande (1968) を参照）。
注記[編集]
- ^ 半順序集合 ＜P ; ≦＞ の "≦" を "≧" で置き換えたもの ＜P ; ≧＞ もやはり半順序集合となる。
- ^ 反射律と推移律は成り立つが反対称律は成り立たないものは前順序集合（preordered set）と呼ばれる。推移律と反対称律によって半順序関係はいわゆる三竦みが起こらないことが保証されるが、前順序集合においては三竦みが起こりうる
- ^ 鎖のことを全順序集合（totally ordered set）または線型順序集合（linearly ordered set）とも呼ばれる。
- ^ 極大元（maximal element）とも呼ぶ。
- ^ 極小元（minimal element）とも呼ぶ。
- ^ 最大元（最小元）は存在すれば、反対称律から唯一つに定まる。
- ^
- 半順序集合 ＜P ; ≦＞ が完備である必要十分条件は、下界を持つ任意の部分集合が最大下界を持つことである
- （つまり、下界を持つ任意の部分集合が最大下界を持つことを完備の定義としてもよい）
証明
- （完備ならば下界を持つ任意の部分集合が最大下界を持つ）
- P の下界を持つ空でない任意の部分集合を U とする。さらに U の下界からなる集合を L とする。したがって、L は上界を持つ集合となり、完備であることから最小上界 u が存在する。u は L の上界であり、かつ最小のものであることから
- 任意の x ∈ L に対して x ≦ u かつ 任意の y ∈ U に対して u ≦ y
- が成り立つ。これは u が U の最大下界であることに他ならない。すなわち下界を持つ任意の部分集合が最大下界を持つ。
- （下界を持つ任意の部分集合が最大下界を持つならば完備）
- 上記の下界、最大下界を上界、最小上界に読み替えればよい。
- ^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8.
参考文献[編集]
- ガーレット・バーコフ, ソンダース・マクレーン 『現代代数学概論』 白水社、1967年、改訂第３版。
- 前田 周一郎 『束論と量子論理』 槙書店、1980年。
- Garrett Birkhoff (1979). Lattice Theory (3rd ed.).
- George Grätzer (1979). Universal Algebra (2nd ed.).
- George Grätzer (2003). General Lattice Theory (2nd ed.).
- George Grätzer (2011). Lattice Theory: Foundation.
- John L. Kelley (1975) [1955]. General topology. Graduate Texts in Mathematics, No. 27. Springer-Verlag, New York-Berlin. ISBN 978-0387901251. 日本語訳: 『位相空間論』 児玉之宏訳、吉岡書店〈数学叢書〉、1968年。
- E. H. Moore , H. L. Smith (1922), A General Theory of Limits, http://www.jstor.org/stable/pdfplus/2370388.pdf?acceptTC=true
関連項目[編集]
