4.4 順序集合

反射的，反対称的かつ推移的である関係を半順序(partial order)とよぶ． 例題4.1より実数上の関係$\leqq$はこの３条件をみたすから半順序である． $R$が集合$P$上の半順序のとき，$P$と$R$を組にして考えた $(P,R)\strut$を 半順序集合(partially ordered set)とよぶ． 考えている半順序が明らかなときは，単に$P$を半順序集合とよぶこともある．

例 4.26   ${\cal P}\strut$を集合族とする． $x,y\in {\cal P}\strut$に対し， $x \leq y \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut x \subseteq y\strut$とすると 関係 $x\leq y\strut$は半順序であり， $({\cal P},\leq )\strut$は半順序集合である．

$(P,\preceq)\strut$を半順序集合とする．$P$の元$x,y\strut$は $x\preceq y\strut$または $y\preceq x\strut$ が成り立つとき比較可能 であるという．$P$の任意の元$x,y\strut$が比較可能であるとき， $(P,\preceq)\strut$は全順序集合 (totally ordered set)あるいは線形順序集合(linearly ordered set)とよばれる．$\leqq$を実数上の順序とすると， $(\mathbb{R}, \leqq)\strut$は全順序集合である．例4.26は全順序集合ではない．

$(P,\preceq)\strut$を半順序集合とする． $S\subseteq P , x\in S$に対し，$x$が$S$の極 小元であるとは， $\forall y \in S [ y\preceq x \rightarrow y=x]\strut$ をみたすときをいう．同様に $\forall y \in S [ y\succeq x \rightarrow y=x]\strut$ をみた すとき $x$ は$S$の極大元と よばれる．$P$の任意の空でない部分集合$S$が極小元をもつとき， $(P,\preceq)\strut$は 整礎集合（well-founded set） とよばれる．

定理 4.27  

全順序集合 $(P,\preceq)\strut$が整礎集合であるための必要十分条件は$P$の任意の空でな い部分集合$S$が最小元を もつことである．

証明： 全順序集合 $(P,\preceq)\strut$が整礎集合であるとする．$P$の任意の空でない部 分集合$S$は極小元をもつ． $S$はただ一つの極小元（すなわち最小元）をもつことを示す．$x$と$y\strut$を$S$の極小 元とする． $(P,\preceq)\strut$は全順序集合であるから， $x\preceq y \vee y\preceq x\strut$がなりた つ． $x\preceq y\strut$のときは，$y\strut$が極小元であることより$y=x\strut$となる．一方， $y\preceq x\strut$の場合も $x$が極小元であることより$x=y\strut$となる．よって，$S$は極小元をただひとつもつ， すなわち$S$は最小元をもつ． 逆は，定義より明らかである． $\Box$

整礎である全順序集合を整列集合とよぶ．

例 4.28  

1. $(\mathbb{N}, \leq )\strut$は全順序集合で任意の空でない部分集合$S$は最小元をもつ から整礎集合（整列集合）である．
2. $(\mathbb{Z}, \leq )\strut$は全順序集合であるが， $S=\mathbb{Z}$に最小元がないから整礎集合ではない．
3. $(\mathbb{R}, \leq )\strut$は全順序集合であるが， $S=\mathbb{R}$に最小元がないから整礎集合ではない．

問題 4.29   $(x,y),(u,v)\in \mathbb{N}\times\mathbb{N}\strut$に対し， $(x,y)\prec (u,v) \Leftrightarrow [x < u] \vee [x=u \wedge y < v]\strut$ とする．さらに， $(x,y)\preceq (u,v) \Leftrightarrow (x,y)=(u,v) \vee (x,y)\prec (u,v)\strut$とする． このとき，次の問に答えよ．

1. $(\mathbb{N}\times\mathbb{N},\preceq )\strut$は全順序集合であることを示せ．
2. $(\mathbb{N}\times\mathbb{N},\preceq )\strut$は整列集合であることを示せ．

定理 4.30  

$(P,\preceq)\strut$が整礎集合であるための必要十分条件は $(P,\preceq)\strut$が真の無限下降 列をもたないこと， すなわち $\{a_n\}\strut$が $a_1\succeq a_2 \succeq a_3 \succeq \cdots \succeq a_n \succeq \cdots \strut$をみ たすならば， ある番号$N$が存在して 任意の$n\geqq N$に対し， $a_n = a_N\strut$となることである．

証明： $(P,\preceq)\strut$を整礎集合とする． $\{a_n\}\strut$は $a_1\succeq a_2 \succeq a_3 \succeq \cdots \succeq a_n \succeq \cdots \strut$をみ たす点列とする． $S=\{a_n\vert n \in \mathbb{N}\}\strut$とおくと，これは$P$の空でない部分集合で$P$は整礎集合で あるから，極小元$x\in S$ をもつ．$S$の定義より，ある番号$N$があって， $x=a_N\strut$となる．このとき， $x=a_N\succeq a_{N+1} \succeq a_{N+2} \succeq \cdots \strut$であるが，$x$が極小元 であるから定義より $x=a_N=a_{N+1}=a_{N+2}=\cdots \strut$となる．逆に， $(P,\preceq)\strut$は無限下降列をもた ないとする． $S$を$P$の空でない部分集合とする．$S$が極小元を持たないと仮定する．このとき $\forall x\in S\exists y \in S [y\prec x]\strut$がなりたつから， $a_1\succ a_2 \succ a_3 \succ \cdots \succ a_n \succ \cdots \strut$となる真の無限 下降列が存在する ことになるが，これは $(P,\preceq)\strut$は無限下降列をもたないに反する． $\Box$

問題 4.31  

1. $x,y\in \mathbb{Z}\strut$に対し， $x \prec y \ \Leftrightarrow\ [x \geq 0 \,\wedge\,[y < 0 \,\vee\,[y \geq 0 \,\wedge\,x < y]]]\strut$とし， $x \preceq y \Leftrightarrow x=y \vee x\prec y$とすると $(\mathbb{Z},\preceq)\strut$は整礎集合であることを示せ．
2. 例の半順序集合 $({\cal P},\preceq)\strut$は ${\cal P}={\cal P}(\mathbb{N})\strut$ のときは，整礎集合ではないこと を示せ．

整礎集合 $(P,\preceq)\strut$に対しては次の帰納法が適用できる．

定理 4.32 (整礎集合上の帰納法)   $(P,\preceq)\strut$を整礎集合， $A(x)\strut$を$P$上の述語とする．このとき

$$\forall x\in P [\forall y\prec x [A(y)] \rightarrow A(x)] \rightarrow \forall x \in P [A(x)]\strut$$

が成り立つ．

証明： 対偶を証明する． $\exists x \in P [\neg A(x)]\strut$とする．このとき， $S=\{x\in P \vert \neg A(x)\}\strut$とおくと$S$は空でないから，$S$は極小元$x$をもつ． $x$は$S$の極小元であるから， $\forall y \in P [ y\prec x \rightarrow y\notin\strut S]\strut$が成り立つ． よって， $\forall y \in P [ y\prec x \rightarrow A(y)] \wedge \neg A(x)\strut$をみたす $x$が存在する ことになる． $\Box$

例 4.33  

$(\mathbb{N}, \leq )\strut$に対し，整礎集合上の帰納法を考えると

$$\forall x\in P [\forall y < x [A(y)] \rightarrow A(x)] \rightarrow \forall x \in P [A(x)]\strut$$

となるが，これは通常累積帰納法とよばれるものである．