Processing math: 0%

順序集合[ordered set,poset]

全順序集合[totally ordered set]

集合 $A$ 上の（半）順序（関係） （partial order） とは，

• 反射律: $a \leq a$
• 推移律: $a \leq b かつ b \leq c ならば a \leq c$
• 反対称律: $a \leq b かつ b \leq a ならば a = b$
• 完全律：$A$の任意の元 $a, b$ について $a \leq b$ か $b \leq a$ のどちらかが成り立つ事

が成立するような関係$\leq$のことを全順序集合（totally ordered set）といいます．

半順序集合（poset）

完全律のみが成り立たない場合は半順序集合[partially ordered set]といいます．

半順序集合は，partially ordered set を略して，poset とも言われます．

$a,b$ を正の整数としたとき, $\leq$ を $b$ が $a$ の倍数 $\Leftrightarrow$ $a \leq b$ と定義した場合は,2は3の倍数でもないこと,また,3は2の倍数でもなく,比較不可能ということになり全順序ではなく半順序になります.

順序型

順序集合 $M,N$ の各元の間に，前後の順序を保ったまま，1対1の対応が付けられるとき，順序集合 $M,N$ は同じ順序型を持つといい，$M,N$ は順序同型であるといいます．

整列（well-ordered）

順序集合 $M=(M,<)$ が，任意の空ではない　$A \subset M$ が最小元を持つことを，整列（well-ordered）といいます．

これは，$M$ が全順序集合であり，無限下降列を持たないことと同値です．

Mathematics is the language with which God has written the universe.