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

いったんできるだけ $\mathbb{N}$ を使わないように書き直します。これが意味があるかどうかはもう少し進めてみないとわかりません。

自然数の帰納的表記

$N$ を集合、 $0 \in N$ 、 $s: N \to N$ とし、 $N$ は
(N1)「 $X \subseteq N$ が

$0 \in X$ 、
$x \in X \implies s(x) \in X$

を満たすならば $X = N$ 」であるとします。

$N = \{ s^n(0) \mid n \in \mathbb{N} \}$ となるので $s$ が

$s^m(0) = s^n(0) \iff m = n$

を満たすとすると、 $N$ の順序を

$s^m(0) \le s^n(0) \iff m \le n$

と定義すると全順序集合になります。

後で自然数の定義をしようとしているので、ここで $\mathbb{N}$ が出てくるのは良くないのですが、何かの記法がないと書くことができません。そこで $x$ に $s$ を $0$ 回以上有限回適用したもの全体の集合を $s^*(x)$ と表すことにします。この書き方は自然数の性質を使っているわけではないので許すことにします。

$s^*(x)$ は(N2)

(N2-1) $x \in s^*(x)$
(N2-2) $y \in s^*(x) \implies s(y) \in s^*(x)$
(N2-3) $x \notin s^*(s(x))$
(N2-4) $y \in s^*(x), \ z \in s^*(y) \implies z \in s^*(x)$
(N2-5) $y \notin s^*(x) \implies x \in s^*(y)$

を満たすものとします。

すると(N2-1)、(N2-2) から $s^*(0)$ は(N1)の $X$ の条件を満たすので(N1)より $N = s^*(0)$ となって

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

と定義すると(N2-1)、(N2-3)、(N2-4)、(N2-5)より

$x \le x$
$x \le y, \ y \le x \implies x = y$
$x \le y, \ y \le z \implies x \le z$
$x \not\le y \implies y \le x$

となって、 $N$ は順序 $\le$ によって全順序集合になります。

このとき
(N3) $\varnothing \ne X \subseteq N$ とすると $X$ は最小元を持ちます。

[証明] $\varnothing \ne X \subseteq N$ とし

$Y = \{ y \in N \mid 任意の \ x \in X \ に対して \ y \le x \}$

とおくと

$0 \in Y$
$x \in X$ が存在し $s(x) \notin Y$ なので $Y \ne N$

よって(N1)より $y \in Y$ 、 $s(y) \notin Y$ となる $y$ が存在します。すなわち

(1) 任意の $x \in X$ に対して $y \le x$
(2) ある $x \in X$ が存在して $s(y) \not\le x$

となる $y$ が存在します。 $N$ は全順序集合なので (2) より $x < s(y)$ 、よって $x \le y$ となり、(1) より $y \le x$ なので $y = x \in X$ となります。よって (1) より $y$ は $X$ の最小元となります。[証明終わり]