順序について

$X$ を集合とする. $X$ 上の二項関係とは次の写像である.

$ \rho : X \times X \rightarrow \{ T, F \} $

ここで集合 $ \{ T, F \} $ は真理値の集合を表す. $T$ が True, $F$ が False のつもりである. $ \{ 1, 0 \} $ で代用しても問題ない.

このような写像を定める代わりに, 直積集合 $X \times X$ の部分集合 $ R $ を定めてもよい. この場合, $X \times X$ における $ R $ の特性関数が上記の $ \rho $ に対応する. 以下では二項関係とは $ R $ のように, 直積集合の部分集合として定めることにする.

集合 $ X $ 上の半順序関係とは $X \times X$ の部分集合 $ R $ で以下の条件を満たすもののことである.

• $\forall x \in X, (x, x) \in R$
• $\forall x, y \in X ~ \{ (x, y), (y, x) \in R \Rightarrow x=y \}$
• $\forall x, y, z \in X ~ \{ (x, y), (y, z) \in R \Rightarrow (x, z) \in R \}$

通例, 半順序関係 $ R $ において $(x, y) \in R $ であることを $x \leqq y$ と書く. 半順序集合 $ X $ を $(X, \leqq)$ と書く.

例えば $X = \{ 1, 2 \}$ に対して $ R = \{ (1, 1), (2, 2) \} $ と定めると, これは $X$ 上の半順序関係となる. このとき $1 \leqq 2$ も $ 2 \leqq 1 $ も成立しないことに注意. 半順序関係ではこのように比較不可能な二元が存在しうる.

半順序集合 $(X, \leqq)$ で, 比較不可能な元たちが存在しないもの, すなわち

$\forall x, y \in X$ について $x \leqq y$ または $y \leqq x$

が満たされるようなものを特に全順序集合と呼ぶ.

空集合 $\emptyset$ 上にはただ一つの半順序 $R=\emptyset \subset \emptyset \times \emptyset$ が存在し, これによって $\emptyset$ は全順序集合となる. というのも, 半順序の定義は全称量化子 $\forall$ を用いて定められており, これは空集合上では常に真となるからである.

ちなみにこれを写像で表すと

$\rho : \emptyset \rightarrow \{ T, F \}$

という空写像に対応することになる. 終域 $ \{ T, F \} $ は一定なので, 空集合上の半順序はただ一つであることに矛盾しない.

半順序集合 $(X, \leqq)$ の部分集合 $A$ の上界とは $x \in X$ で

$\forall y \in A, y \leqq x$

を満たすもののことである. $x \in A$ である必要はない.

半順序集合 $(X, \leqq)$ であって, その任意の全順序な部分集合が上界を持つようなものを帰納的という.

$(X, \leqq)$ を帰納的な半順序集合とする. 先に述べたように空集合 $\emptyset$ は $X$ の全順序部分集合となる. すると帰納的であることの定義から $\emptyset$ の上界が存在しないといけない. したがって $X \neq \emptyset$ であることが導かれる.

Zornの補題は「帰納的半順序集合は極大元をもつ」と存在性を主張しているが, 帰納的という仮定がある時点で空集合ではないので問題ない.