エレファントな整数論(21) - エレファント・コンピューティング調査報告

「エレファントな整数論(3)」で書いたような内容ですが、また書き直していきます。

全射・単射・有限集合

$X, Y$ を集合、 $f: X \to Y$ を写像とします。任意の $x_1, x_2 \in X$ に対して $f(x_1) = f(x_2)$ ならば $x_1 = x_2$ であるとき、 $f$ を単射と呼びます。任意の $y \in Y$ に対して $y = f(x)$ となる $x \in X$ が存在するとき、 $f$ を全射と呼びます。 $f$ が全射かつ単射であるとき全単射と呼びます。

$f$ が全単射であるとき、 $f$ は全射なので $y \in Y$ に対して $y = f(x)$ となる $x$ が存在し、 $f$ は単射なのでこの $x$ は一意的となります。よって $g: Y \to X$ を $g(y) = x$ と定義することができます。 $g \circ f = 1_X$ ( $X$ の恒等写像)、 $f \circ g = 1_Y$ ( $Y$ の恒等写像)となります。 $g$ を $f$ の逆写像と呼び $f^{-1}$ と書きます。

集合 $X$ に対して以下の条件(F1)が成り立つとき、 $X$ を有限集合と呼びます。有限集合でないとき無限集合と呼びます。

(F1) 集合 $X$ が、任意の写像 $f: X \to X$ に対して $f$ が単射ならば $f$ は全射である

(F1)は以下の(F2)と同値となります。

(F2) 集合 $X$ が、任意の写像 $f: X \to X$ に対して $f$ が全射ならば $f$ は単射である

[証明] $(F1) \Longrightarrow (F2):$ (F1)を仮定し、 $f: X \to X$ を全射とします。(選択公理より) $g: X \to X$ を $g(x) \in f^{-1}(x)$ となるように定義することができます。 $g$ は単射となり、(F1)より全単射となります。よって $f = g^{-1}$ は全単射となります。

$(F2) \Longrightarrow (F1):$ (F2)を仮定し、 $f: X \to X$ を単射とします。 $g: X \to X$ を $x \in f(X)$ のとき $g(x) \in f^{-1}(x)$ となるように定義することができます。 $x \notin f(X)$ のときは $g(x)$ 任意の $X$ の元とします。 $g$ は全射となり、(F2)より全単射となります。よって $f = g^{-1}$ は全単射となります。[証明終わり]

順序関係

集合 $O$ 上の二項関係 $\le$ が

反射律: 任意の $x \in O$ に対して $x \le x$
推移律: 任意の $x , y, z \in O$ に対して $x \le y \le z$ ならば $x \le z$

を満たすとき前順序と呼びます。さらに

反対称律: 任意の $x , y \in O$ に対して $x \le y$ かつ $y \le x$ ならば $x = y$

を満たすとき半順序と呼びます。単に順序という場合は半順序のことを表すとします。さらに

任意の $x , y \in O$ に対して $x \le y$ または $y \le x$

を満たすとき全順序と呼びます。

$x \le y$ を $y \ge x$ と書くこともできます。 $x \le y$ かつ $x \ne y$ のとき $x < y$ 、 $x \ge y$ かつ $x \ne y$ のとき $x > y$ と書きます。

集合 $O$ 上の二項関係 $\le$ が前順序のとき二項関係 $\cong$ を
$x \cong y \iff x \le y \ かつ \ y \le x$
とおくと

反射律: 任意の $x \in O$ に対して $x \cong x$
推移律: 任意の $x , y, z \in O$ に対して $x \cong y \cong z$ ならば $x \cong z$
対称律: 任意の $x , y \in O$ に対して $x \cong y$ ならば $y \cong x$

を満たすので同値関係となります。この同値関係による同値類の全体を $\bar{O}$ とおきます。 $x \in O$ を含む同値類を $\bar{x}$ とおきます。

$x \cong x'$ 、 $y \cong y'$ とします。 $x \le y$ ならば $x' \le x \le y \le y'$ より $x' \le y'$ 、 $x' \le y'$ ならば $x \le x' \le y' \le y$ より $x \le y$ となるので、

$x \le y \iff x' \le y'$

が成り立ちます。よって $\bar{O}$ に二項関係 $\leqq$ を $\bar{x} \leqq \bar{y} \iff x \le y$ と定義することができます。 $\leqq$ は半順序となります。

集合 $O$ 上の前順序 $\le$ に対して、

(WF1) $O$ の任意の空でない部分集合が極小元を持つ

が成り立つとき $\le$ は整礎(well-founded)であるといいます。(Wikipediaでは、二項関係に対して「整礎」が定義されています。また、半順序に対しても「整礎」が定義されています。ここでは、前順序に対して「整礎」を定義します。)

(WF1) は、以下の条件(WF2)と同値となります。

(WF2) $O$ の元からなる無限降下列が存在しない

[証明] (WF1)⇒(WF2): (WF1)を仮定します。 $x_1 > x_2 > x_3 > \cdots$ を $O$ の元の無限個の列とすると、(WF1)より $X = \{x_1, x_2, x_3, \cdots \}$ の極小元が存在します。極小元を $x_i$ とすると $x_i > x_{i+1}$ であり、これは $x_i$ が極小元であることに反します。よって(WF2)が成り立ちます。

(WF2)⇒(WF1): (WF1)が成り立たないと仮定します。極小元を持たない $O$ の空でない部分集合 $X$ が存在します。 $X$ は極小元を持たないので $x \in X$ に対して $x > y$ となる $y \in X$ が存在します。この $y$ を $y(x)$ と書くことにします。

$X$ は空でないので $x_1 \in X$ が存在します。 $x_{i+1} = y(x_i)$ と帰納的に定義すると $x_1 > x_2 > x_3 > \cdots$ という無限個の列が存在するので(WF2)が成り立ちません。[証明終わり]

$\le$ が全順序であるとき、整列順序と呼び、 $O$ を整列集合と呼びます。

写像と順序の関係

$M$ を集合、 $s: M \to M$ を写像とします。 $M$ の部分集合全体の集合を $\mathfrak{P}(M)$ とします。 $\bar{s}: \mathfrak{P}(M) \to \mathfrak{P}(M)$ を $\displaystyle \bar{s}(X) = \bigcup_{x \in X} \{s(x)\} = \{ s(x) \mid x \in X \}$ とします。

$\mathcal{R}_x = \{ X \in \mathfrak{P}(M) \mid x \in X \ かつ \ \bar{s}(X) \subseteq X \}$

とおきます。

$s^*: M \to \mathfrak{P}(M)$ を $x \in M$ に対して

$\displaystyle s^*(x) = \bigcap \mathcal{R}_x$

( $\mathcal{R}_x$ に属する $M$ の部分集合全体の共通部分)とおくと(これは $s^*(x) = \{x, s(x), s^2(x), \cdots \} = \{ s^n(x) \mid n \in \mathbb{N} \}$ を表すものとなります)

(O1-1) $x \in s^*(x)$
(O1-2) $\bar{s}(s^*(x)) \subseteq s^*(x)$

が成り立ちます。よって

(O1) $s^*(x) \in \mathcal{R}_x$

となります。また、

(O2) $X \in \mathcal{R}_x \implies s^*(x) \subseteq X$

が成り立ちます。また、(O1-1)、(O1-2)より

(O3) $s(x) \in s^*(x)$

が成り立ちます。以下の(O4)が成り立ちます。

(O4) $s^(x) \supseteq s^(y) \iff y \in s^*(x)$

[証明] $s^*(x) \supseteq s^*(y)$ とすると (O1-1)より $y \in s^*(y) \subseteq s^*(x)$ となります。

$x \in M$ に対して $X = \{ y \in s^*(x) \mid s^*(x) \supseteq s^*(y) \}$ とおきます。 $x \in X$ 、 $\bar{s}(X) \subseteq X$ となるので $X \in \mathcal{R}_x$ となります。よって $s^*(x) = \bigcap \mathcal{R}_x \subseteq X$ となります。

$y \in s^*(x)$ とすると $y \in s^*(x) \subseteq X$ となるので $s^*(x) \supseteq s^*(y)$ となります。[証明終わり]

(O5) $s^(x) = \{x\} \cup s^(s(x))$

[証明] $(\subseteq) :$ (O1-1)より $x \in s^*(x)$ 、(O1-2)、(O3)より $s^*(s(X)) \subseteq s^*(x)$ となるので成り立ちます。

$(\supseteq) :$ $X = \{x\} \cup s^*(s(x))$ とおきます。 $x \in X$ 、 $\bar{s}(X) \subseteq X$ となるので $X \in \mathcal{R}_x$ となります。よって $s^*(x) = \bigcap \mathcal{R}_x \subseteq X$ となります。[証明終わり]

(O6) $\bar{s}(s^(x)) = s^(s(x))$

[証明] $(\subseteq) :$ (O5)より $\bar{s}(s^*(x)) \subseteq \{s(x)\} \cup \bar{s}(s^*(s(x))) \subseteq s^*(s(x))$ となるので成り立ちます。

$(\supseteq) :$ $X = \bar{s}(s^*(x))$ とおきます。 $s(x) \in X$ 、 $\bar{s}(X) \subseteq X$ となるので $X \in \mathcal{R}_{s(x)}$ となります。よって $s^*(s(x)) = \bigcap \mathcal{R}_{s(x)} \subseteq X$ となります。[証明終わり]

$x, y \in M$ に対して

$x \le y \iff s^*(x) \supseteq s^*(y)$

と定義すると $\supseteq$ が前順序であることから $\le$ は前順序となります。定義と(O4)より

(O7) $x \le y \iff y \in s^*(x)$

が成り立ちます。(O3)、(O7)より

(O8) $x \le s(x)$

が成り立ちます。

$x_0 \in M$ をとり $N = s^*(x_0)$ とおきます。

(帰納法) $N \in \mathcal{R}_{x_0}$ となるので $x \in N$ に関する条件 $p(x)$ が

$p(x_0)$
$p(x) \implies p(s(x))$

を満たすならば任意の $x \in N$ に対して $p(x)$ が成り立ちます。

写像の分類

以下の条件を考えます。

$(N_1)$ 任意の $x \in N$ に対して $s(x) \ne x$
$(N_2)$ 任意の $x \in N$ に対して $s(x) \ne x_0$
$(N_3)$ $N$ 上で $s$ は単射
$(N_4)$ $N$ 上で $\le$ は全順序
$(N_5)$ $N$ は無限集合

これらの条件により以下の表のようにタイプ $T_1$ から $T_5$ に分類することができます。

タイプ	$N_1$	$N_2$	$N_3$	$N_4$	$N_5$	図式
$T_1 = N_1 \land N_2 \land N_3$	○	○	○	○	○	$0 \to 1 \to \cdots$
$T_2 = N_1 \land N_2 \land \neg N_3$	○	○	×	×	×	$0 \to 1 \to \cdots \to n \to \cdots \to n$
$T_3 = N_1 \land \neg N_2$	○	×	○	×	×	$0 \to 1 \to \cdots \to 0$
$T_4 = \neg N_1 \land N_2$	×	○	×	○	×	$0 \to 1 \to \cdots \to n \to n$
$T_5 = \neg N_1 \land \neg N_2$	×	×	○	○	×	$0 \to 0$

この表は「○」のところは成り立ち、「×」のところは成り立たないことを表しています。「図式」のところは各タイプの意味を表すものが書かれています。タイプ $T_1$ が自然数を表すものとなります。この表が成り立つことを次回以降示していきたいのですが、この表は自然数の定義となるものなので、自然数を使わない形で示していく予定です。