順序集合
順序集合
定義《順序集合》
$A$ を集合とする.
- (1)
- $A$ における $2$ 項関係 $\leqq$ が次の (O1)～(O3) を満たすとき, $\leqq$ は $A$ における順序関係であるといい, $(A,\leqq )$ を順序集合と呼ぶ.
- (O1)
- 反射律: $A$ の任意の元 $a$ に対して, \[ a \leqq a.\]
- (O2)
- 反対称律: $A$ の任意の元 $a,$ $b$ に対して, \[ a \leqq b,\ b \leqq a \Longrightarrow a = b.\]
- (O3)
- 推移律: $A$ の任意の元 $a,$ $b,$ $c$ に対して, \[ a \leqq b,\ b \leqq c \Longrightarrow a \leqq c.\]
- (2)
- $(A,\leqq )$ を順序集合とする.
$\leqq$ が次の条件を満たすとき, $\leqq$ は全順序関係であるといい, $(A,\leqq )$ を全順序集合と呼ぶ.
- (O4)
- 全順序性: $A$ の任意の元 $a,$ $b$ に対して $a \leqq b,$ $b \leqq a$ の少なくとも一方が成り立つ.
例《順序集合》
- (1)
- 与えられた集合 $X$ に対して, $X$ の部分集合全体 ($X$ のべき集合) は包含関係 $\subset$ に関して順序集合をなすが, これは全順序集合でない.
- (2)
- 自然数全体 $\mathbb N,$ 整数全体 $\mathbb Z$ はそれぞれ整除関係 (割る, 割り切れるの関係) に関して順序集合をなすが, これは全順序集合でない.
- (3)
- 自然数全体 $\mathbb N,$ 整数全体 $\mathbb Z,$ 有理数全体 $\mathbb Q,$ 実数全体 $\mathbb R$ はそれぞれ大小関係に関して全順序集合をなす.
定義《最大元, 最小元》
$(A,\leqq )$ を順序集合, $S$ を $A$ の空でない部分集合とする.
- (1)
- $S$ の元 $M$ で, $S$ の任意の元 $s$ に対して $s \leqq M$ を満たすものが存在するとき, $M$ を $S$ の最大元と呼ぶ.
- (1)'
- $S$ の元 $m$ で, $S$ の任意の元 $s$ に対して $m \leqq s$ を満たすものが存在するとき, $m$ を $S$ の最小元と呼ぶ.
定義《整列集合》
$(A,\leqq )$ を全順序集合とする.
$A$ の空でない任意の部分集合 $S$ が $S$ において最小元をもつとき, $\leqq$ を整列順序と呼び, $(A,\leqq )$ を整列集合と呼ぶ.
例《整列集合》
- (1)
- 自然数全体 $\mathbb N$ は大小関係に関して整列集合をなす.
- (2)
- 整数全体 $\mathbb Z,$ 有理数全体 $\mathbb Q,$ 実数全体 $\mathbb R$ はそれぞれ大小関係に関して整列集合をなさない.