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

自然数の帰納的表記

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

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

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

このとき $X = \{ s^n(0) \mid n \in \mathbb{N} \}$ をおくと $X$ は上の条件を満たすので $X = N$ となります。よって

$N = \{ s^n(0) \mid n \in \mathbb{N} \}$

となります。

さらに $s$ は

(条件2) $s^m(0) = s^n(0) \iff m = n$

を満たすとします。

$N$ は自然数全体を表す集合と考えられます。これは自然数の定義だと考えると $\mathbb{N}$ が出てくるのはおかしいですが、ここでは数学的帰納法に関する記法を考えることが目的なので今はこのまま議論を進めます。この件は後で検討します。

$N$ の順序を

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

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

このとき
(条件3) $\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$

よって(条件1)より $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$ の最小元となります。[証明終わり]