公理的集合論における自然数の存在(その 7)

いよいよ自然数の演算を再現します。なお、公理的集合論においては、通常は集合を現すのにアルファベットの小文字を使用するのが慣わしですが、煩雑さを避けるため、大文字等も使用することにします。

帰納定理

定理(帰納定理)

$A\neq\emptyset$ とし、 $a\in A$ とする。さらに写像 $f:A\to A$ が与えられているとき、写像 $F:\omega\to A$ で、次の性質を満たすものが一意的に存在する。

$F(0)=a$

$F(n^+)=f(F(n))$

(証明)まず、「対応」 $F:\omega\to A$ で、上の条件を満たすものが存在することを示す。
$S=\{x\in\mathcal{P}(\omega\times a)|\langle 0,a\rangle\in x\wedge[\langle n,a\rangle\in x\to\langle n^+,f(a)\rangle\in x]\}$
とおく。明らかに $\omega\times A\in S$ だから $S\neq\emptyset$ 。故に $F=\cap S$ とおくと $F\in\mathcal{P}(\omega\times A)$ 、すなわち $F$ は $\omega$ から $A$ への対応で、 $\langle 0,a\rangle\in F$ かつ $\langle n,a\rangle\in F\to\langle n^+,f(a)\rangle\in F$ が成り立つ。
後は、 $F$ が写像であることを示せば、証明は完了する。実際、写像 $F':\omega\to A$ で、定理の性質を満たすものが存在すれば $F'\in S$ であるから $F=\cap S\subseteq F'$ となり、 $F$ が写像であれば、このことから $F=F'$ となる*1からである。
まず
$\langle n,\alpha\rangle\in x_0\leftrightarrow\langle n,\alpha\rangle=\langle 0,a\rangle\vee\langle n,\alpha\rangle\in(\omega\setminus\{0\})\times A$
を満たすものは $S$ の元である( $n^+\neq 0$ から直ちに確かめられる)。従って $F\subseteq x_0$ となり、 $F(0)=a$ がわかる。後は
$F(n)=\alpha\to F(n^+)=f(\alpha)$
を示せば、数学的帰納法によって $F$ は写像で、かつ定理の性質を満たすものとなることがわかる。
実際、 $f(\alpha)\in F(n^+)$ は明らかなので、 $\beta\in F(n^+),\beta\neq f(\alpha)$ として矛盾を導けばよい。
$y=F\setminus\{\langle n^+,\beta\rangle\}$
とおくと、 $y\in S$ である。実際 $\langle 0,a\rangle\in y$ は明らかだし
$\langle m,\gamma\rangle\in y\to\langle m^+,f(\gamma)\rangle\in y$
は次のように示される。
$m=n$ ならば、 $F(n)=\alpha$ によって $\gamma=\alpha$ となり、 $y$ の定義により $\langle n^+,f(\alpha)\rangle\in y$ 。 $m\neq n$ ならば $m^+\neq n^+$ であるから
$\langle m,\gamma\rangle\in F\to\langle m^+,f(\gamma)\rangle\in F\setminus\{\langle n^+,\beta\rangle\}=y$
だからである。従って $F$ の定義によって $F\subseteq y$ であるが、一方で $y\subset F$ であるから、これは矛盾である。
以上により帰納定理が証明されました。この定理を用いて、次回、和・積・べき乗の演算を定義することにします。

*1:一般に写像 $f,g:a\to b$ が $f\subseteq g$ を満たすなら、 $f=g$ が成り立ちます。このことは練習問題にしましょう。