利用者:I.hidekazu/半順序集合

半順序集合（はんじゅんじょしゅうごう、英: partially ordered set : poset）とは、順序関係を持つ集合を言う。

定義

半順序集合（partially ordered set : poset）

集合 P 上の関係を ≦ とする。a, b, c ∈ P に対して ≦ が以下

反射律（reflexivity）

全ての a ∈ P について a ≦ a

反対称律（antisymmetry）

a ≦ b かつ b ≦ a のとき a = b

推移律（transitivity）

a ≦ b かつ b ≦ c のとき a ≦ c

を満たすとき ≦ を半順序関係（partially ordered relation）と呼ぶ。さらに、半順序関係 ≦ を持つ集合 ＜P ; ≦＞ を半順序集合と呼ぶ。

半順序集合は任意の２元について比較可能（comparable）であるとは限らない。任意の２元について比較可能な半順序集合は鎖（chain）と呼ばれる。

鎖（chain）

半順序集合 ＜C ; ≦＞ が

線型律（linearity）

全ての a, b ∈ C に対して a ≦ b または b ≦ a

を満たすとき鎖（chain）または全順序集合（totally ordered set）、線型順序集合（linear ordered set）と呼ぶ。

ω鎖（ω-chain）

非負整数 0 ≦ 1 ≦ 2 ≦ ... は鎖を成す。この鎖を ω = ＜{ 0, 1 ,2, ... } ; ≦＞ で表しω鎖（ω-chain）と呼ぶ。

単調写像（monotone mapping）

半順序集合を ＜P ; ≦＞、＜Q ; ≦＞ とする。写像 f : P → Q が順序を保存するとき、すなわち a, b ∈ P について

a ≦ b のとき、f(a) ≦ f(b)

を満たすとき、f を単調写像（monotone mapping）、同調写像（isotone mapping）または順序保存写像（order preserving map）と呼ぶ。

半順序集合に付与する性質

有界性（bounded）

半順序集合を ＜P ; ≦＞ とする。1 ∈ P が P の最大元（さいだいげん、greatest element）であるとは、全ての a ∈ P について、a ≦ 1 を満たすものを言う。同様に、0 ∈ P が P の最小元（さいしょうげん、least element）であるとは、全ての a ∈ P について、0 ≦ a を満たすものを言う。

最大元 1 と最小元 0 を持つ半順序集合 ＜P ; ≦, 1, 0＞ を有界半順序集合（bounded poset）と呼ぶ。

上界（upper bound）と下界（lower bound）

P の部分集合を X とする。このとき、元 a ∈ P が X ⊆ P の上界（じょうかい、upper bound）であるとは、全ての x ∈ X について、x ≦ a を満たすものを言う。 同様に、元 b ∈ P が X ⊆ P の下界（かかい、lower bound）であるとは、全ての x ∈ X について、b ≦ x を満たすものを言う。

最小上界（least upper bound：l.u.b.）と最大下界（greatest lower bound：g.l.b.）

X の全ての上界 a ∈ P 及び全ての x ∈ X に対して、x ≦ l.u.b.(X) ≦ a を満たす X の上界 l.u.b.(X) ∈ P を X の最小上界（least upper bound : l.u.b.）と呼ぶ。同様に、X の全ての下界 b ∈ P 及び全ての x ∈ X に対して、b ≦ g.l.b.(X) ≦ x を満たす X の下界 g.l.b.(X) ∈ P を X の最大下界（greatest lower bound : g.l.b.）と呼ぶ。

文字通り、P の部分集合 X の最小上界は X の上界の中で最小のもので、順序関係を一意的に分解する。最大下界も同様である。

極大元（maximal element）と極小元（minimal element）

P の部分集合を X とする。このとき、元 s ∈ X が X ⊆ P の極大元（maximal element）であるとは、s ≦ p を満たす p ∈ P が存在しないものを言う。同様に、元 t ∈ X が X ⊆ P の極小元（minimal element）であるとは、p ≦ t を満たす p ∈ P が存在しないものを言う。

s が最大元であるならば s は極大元であり、同様に t が最小元であるならば t は極小元であるが、一般に逆は成り立たない。