超限帰納法

$X$が整列集合とし,${\cal P}(x)$は関係式とします。

$$(\forall x)\{ (x \in X)~and~ (\forall y: y \in X ~and~ y<x) ({\cal P}(y)) \Rightarrow {\cal P}(x) \}$$

が成立つとき

$$(\forall x)\{(x \in X) \Rightarrow {\cal P}(x) \}$$

が成立ちます。これを自然数での数学的帰納法になぞらえて超限帰納法と呼びます。 [証明] 前半の関係式

$$(\forall x)\{ (x \in X)~and~ (\forall y: y \in X ~and~ y<x) ({\cal P}(y)) \Rightarrow {\cal P}(x) \}$$

が成立してかつ

$$(\forall x)\{(x \in X) \Rightarrow {\cal P}(x) \}$$

が成立たないとします。

$$not (\forall x)\{(x \in X) \Rightarrow {\cal P}(x) \} \Leftrightarrow (\exists x)\{(x \in X) ~and~ not {\cal P}(x) \}$$

ですから

$$(\exists x)\{(x \in X) ~and~ not {\cal P}(x) \}$$

が成立ち,集合

$${\cal Y}={x\vert(x \in X) ~and~ not {\cal P}(x)}$$

が空集合でないことになります。 すると$X$は整列集合でしたから ${\cal Y}\subseteq X$には最小元 $x \in {\cal Y}$が存在します。

しかし,任意の$y \in X,y< x$については $not (y \in {\cal Y})$ゆえ, ${\cal P}(y)$が成立します。すると仮定した前半の関係式から, ${\cal P}(x)$が成立ちこれは $x \in {\cal Y}$に矛盾します。 [証明終]

順序集合$X$で,

$$YがXの切片 \stackrel{def}{\Leftrightarrow} (\forall y \in Y)(\forall x \in X)(x \le y \Rightarrow x \in Y)$$

$X \in X$について

$$(\leftarrow,x):=\{y\vert y \in X ~and~ y \le x ~and~ y \ne y \}$$

$X$を整列順序集合とするとき：

$$Y \subseteq X,~Y \ne X,~YがXの切片 \iff (\exists x)(x \in X ~and~ Y=(\leftarrow,x))$$

[証明]

$$Y \subseteq X,~Y \ne X,~YがXの切片$$

とすると：

$$X \setminus Y \ne \phi$$

$X$は整列順序集合だから

$$m=\min \{ X \setminus Y \}$$

が存在する。

$m \le x$のとき,$x \in Y$とすると$Y$が$Xの切片$だから $m \in Y$となり,矛盾。よって$x \notin Y$
よって,

$$[m,\rightarrow)=\{x\vert x \in X ~and~ m \le x\} \subseteq X \setminus Y$$

$x \notin X \setminus Y$とすると

$$m=\min X \setminus Y$$

$$m \le x~~i.e. x \in [m,\rightarrow)$$

よって

$$[m,\rightarrow)=X \setminus Y$$

ゆえに,

$$Y=(\leftarrow,m)$$

逆に, $(\leftarrow,m)$ が$X$の切片で $(\leftarrow,m) \ne X$は明らか。

[証明終]

$X$を整列順序集合とするとき：

$$\begin{eqnarray*} &&x \in X \mapsto (\leftarrow,x) \in {\cal S}(X) \\ &&{\cal S}(X)=\{ Y \vert Y \subseteq X~and~ YがXの切片~and~ Y \ne X \} \end{eqnarray*}$$

は整列順序について同型。

$$\{Y:Y \subseteq X ~and~X の切片 \}={\cal S}(X) \bigcup \{ X\}$$

は整列順序集合

[証明]

$x,y \in X$を任意にとるとき,

$x \le y$から

$$z \in (\leftarrow,x) \Rightarrow z \le x \Rightarrow z \le y \Rightarrow z \in (\leftarrow,x)$$

で

$$(\leftarrow,x) \subseteq (\leftarrow,y)$$

従って

$$x \le y \Rightarrow (\leftarrow,x) \subseteq (\leftarrow,y)$$

$x \le y ~and~ x \ne y$のとき

$$(\leftarrow,x)=(\leftarrow,y)$$

とすると

$$[x, \rightarrow) =[y, \rightarrow)$$

から

$$x \le y~and~ y \le x$$

よって

$$x=y$$

となり矛盾。よって,

$$(\leftarrow,x)　\subseteq (\leftarrow,y) ~and ~(\leftarrow,x)　\ne (\leftarrow,y)$$

従って

$$x < \Rightarrow (\leftarrow,x) \subseteq (\leftarrow,y)~and ~(\leftarrow,x)　\ne (\leftarrow,y)$$

よって

$$\begin{eqnarray*} &&x \in X \mapsto (\leftarrow,x) \in {\cal S}(X) \\ &&{\cal S}(X)=\{ Y \vert Y \subseteq X~and~ YがXの切片~and~ Y \ne X \} \end{eqnarray*}$$

は整列順序について同型。

$$\{Y:Y \subseteq X ~and~X の切片 \}={\cal S}(X) \bigcup \{ X\}$$

が整列順序集合であることも明らか。（$X$を最大元として${\cal S}(X)$に加える。）