ペアノの公理から「足し算」を作る｜自然数上の加法の構成
ペアノの公理から自然数上の足し算を構成する。
ペアノの公理とは
https://sorai-note.com/math/200403/
集合 $\NN$ とその要素 $0 \in \NN$ と写像 $s: \NN \rightarrow \NN$ の組 $(\NN, 0, s)$ で
$\NN$ の部分集合 $A$ が
を共に満たせば $A = \NN$
を満たすものをペアノシステムと呼ぶ。
今日はそこから「足し算」を構成するね
ペアノの公理と数学的帰納法
各 $n \in \NN$ に対する命題 $P(n)$ が2条件
を満たせば、各 $n \in \NN$ に対し $P(n)$ は真である。
$A = \iset{n \in \NN}{ P(n) }$ とする。
$0 \in A$ であることは Base Case から分かる。
$s[A] \subseteq A$ であること、すなわち各 $n \in A$ に対し $s(n) \in A$ であることは Induction Step からわかる。
従って (P3) より $A = \NN$ であり、各 $n \in \NN$ に対し $P(n)$ が成り立つ。
$\NN = \cbr{0} \cup s[\NN]$ であり、$\cbr{0} \cap s[\NN] = \varnothing$ である。
各 $n \in \NN$ に対し $n \in \cbr{0} \cup s[\NN]$ であることを $n$ についての数学的帰納法で示す。
$0 \in \cbr{0} \cup s[\NN]$ は自明。
$n \in \cbr{0} \cup s[\NN]$ とすると $s(n) \in s[\NN] \subseteq \cbr{0} \cup s[\NN]$ である。
(P2) から自明。
きっちり分けられることがわかった
ペアノの公理から加法を構成する
写像 $+: \NN \times \NN \rightarrow \NN$ で
を満たすものが存在する。
「$n + m$ が定義されてたら $n + s(m)$ を $s(n + m)$ で定義」
「再帰的定義」をちゃんと正当化するのは
実はわりと大変で
とりあえず今日は
加法の再帰的定義の正当化だけ
帰納法で直接やっちゃおう
集合 $X, Y$ に対し $X$ から $Y$ への写像全体の集合を $\mathcal{M}(X, Y)$ と書く。
写像 $F: \NN \rightarrow \mathcal{M}(\NN, \NN)$ で
を満たすものが存在する。
$+: \NN \times \NN \rightarrow \NN$ は
$n + m = F(n)(m)$ とすればいい
各 $n \in \NN$ に対し、次の2条件を満たす写像 $f: \NN \rightarrow \NN$ が唯一つ存在する。
$F = \iset{(n, f)}{f \text{ は(i)${}_n$,(ii)を満たす}}$
で写像 $F$ を作れる
$f$ の一意性も示さなきゃいけないわけか
一意性示さなくても
条件を満たす写像列 $\cbr{f_n}_{n \in \NN}$ を取って
$F(n) = f_n$ で終わりだけど
まず各 $n$ に対し (i’)$_{n}$, (ii’) を満たす $f$ が存在することを $n$ についての数学的帰納法で示す。
写像 $f$ を $f(m) = m$ で定めれば、これは (i’)$_{0}$ も (ii’) も満たす。
(i’)$_{n}$, (ii’) を満たす写像 $f$ が存在するとき、写像 $f_+$ を $$f_+(m) = s(f(m))$$ で定め、これが (i’)$_{s(n)}$ と (ii’) を満たす写像であることを確かめる。
$f_+$ が (i’)$_{s(n)}$ を満たすことは $$f_+(0) = s(f(0)) = s(n)$$ から分かる。 $f_+$ が (ii’) を満たすことは \begin{align*} f_+(s(m)) &= s(f(s(m))) \\&= s(s(f(m))) \\&= s(f_+(m)) \end{align*} から分かる。
次に一意性をしめす。$n$ を固定し $f_1, f_2$ がともに (i)${_n}$, (ii) を満たすとする。各 $m \in \NN$ に対し $f_1(m) = f_2(m)$ であることを $m$ についての数学的帰納法で示す。
どちらも (i)${_n}$ を満たすので $f_1(0) = n = f_2(0)$ である。
$f_1(m) = f_2(m)$ であるとすると、どちらも (ii) を満たすので $$f_1(s(m)) = s(f_1(m)) = s(f_2(m)) = f_2(s(m))$$ である。
加法の一意性の証明
写像 $+: \NN \times \NN \rightarrow \NN$ で
を満たすものは唯一つ。
(I), (II) を共に満たす2つの写像 $+, \mathrel{\dot{+}}$ を任意に取る。このとき
各 $n, m \in \NN$ に対し $n + m = n \mathrel{\dot{+}} m$
となることを $m$ についての数学的帰納法で示す。
$+$ も $\mathrel{\dot{+}}$ も (I) を満たすので $n + 0 = n = n \mathrel{\dot{+}} 0$ である。
$n + m = n \mathrel{\dot{+}} m$ であるとする。$+$ も $\mathrel{\dot{+}}$ も (II) を満たすので $$n + s(m) = s(n + m) = s( n \mathrel{\dot{+}} m) = n \mathrel{\dot{+}} s(m)$$ である。
1+1=2 の証明
加法の可換モノイド性
つまり $(\NN, +)$ が可換モノイドってことを確認しよう
集合 $X$ と写像 ${}\cdot{}: X \times X \rightarrow X$ の組 $(X, {}\cdot{})$ が
ある $e \in X$ が存在して、各 $x \in X$ に対し
$x \cdot e = e \cdot x = x$
各 $x, y, z \in X$ に対し、 $$x \cdot (y \cdot z) = (x \cdot y) \cdot z$$
を満たすとき $(X, {}\cdot{})$ はモノイドであるといい、更に
各 $x, y \in X$ に対し、 $$x \cdot y = y \cdot x$$
も満たすとき $(X, {}\cdot{})$ は可換モノイドであるという。
$0$ は $(\NN, +)$ の単位元である。すなわち、各 $n \in \NN$ に対し $$n + 0 = 0 + n = n$$ が成り立つ。
$n + 0 = n$ は自明。$0 + n = n$ を $n$ についての数学的帰納法で示す。
(I) より $0 + 0 = 0$ である。
$0 + n = n$ であるとする。このとき (II) より $$0 + s(n) = s(0 + n) = s(n)$$ となる。
……の前に一つ補題を
各 $n, m \in \NN$ に対し $$s(n + m) = s(n) + m$$ が成り立つ。
$m$ についての数学的帰納法で示す。
(I) より $s(n + 0) = s(n) = s(n) + 0$ である。
$s(n + m) = s(n) + m$ であるとする。このとき \begin{align*} s(n + s(m)) &= s(s(n + m)) \\&= s(s(n) + m) \\&= s(n) + s(m) \end{align*} を得る。
$(\NN, +)$ は可換性を持つ。すなわち各 $n, m \in \NN$ に対し $$n + m = m + n$$ が成り立つ。
$m$ についての数学的帰納法で示す。
$0$ は $(\NN, +)$ の単位元なので（命題２） $n + 0 = 0 + n$ である。
$n + m = m + n$ であるとすると、補題も用いて \begin{align*} n + s(m) &= s(n + m) \\&= s(m + n) \\&= s(m) + n \end{align*} を得る。
$(\NN, +)$ は結合性を持つ。すなわち各 $n, m, \ell \in \NN$ に対し $$(n + m) + \ell = n + (m + \ell)$$ が成り立つ。
$\ell$ についての数学的帰納法で示す。
$0$ は $(\NN, +)$ の単位元なので（命題２） $$(n + m) + 0 = n + m = n + (m + 0)$$ である。
$(n + m) + \ell = n + (m + \ell)$ であるとする。このとき \begin{align*} (n + m) + s(\ell) &= s((n + m) + \ell) \\&= s(n + (m + \ell)) \\&= n + s(m + \ell) \\&= n + (m + s(\ell)) \end{align*} である。
$(\NN, +)$ は可換モノイドである。
その他の性質
自然数 $n, m$ が $n + m = 0$ を満たすならば $n = m = 0$ である。
もし $m \neq 0$ ならば、$m = s(k) \ (k \in \NN)$ と表すことで $$n + m = n + s(k) = s(n + k) \neq 0$$ となる。つまり $n + m = 0$ ならば $m = 0$ であり、このとき $n = 0$ である。
自然数 $n, k_1, k_2$ が $n + k_1 = n + k_2$ を満たすならば $k_1 = k_2$ である。
$n$ についての数学的帰納法で示す。
$0 + k_1 = k_1$ と $0 + k_2 = k_2$ より従う。
$s(n) + k_1 = s(n) + k_2$ とすると $s(n + k_1) = s(n + k_2)$ であり、$s$ の単射性より $n + k_1 = n + k_2$ を得る。よって帰納法の仮定より $k_1 = k_2$ である。
自然数 $n, m$ に対し、$n + k = m$ となる $k \in \NN$ は存在すれば唯一つである。
$n + k_1 = m$ かつ $n + k_2 = m$ ならば $n + k_1 = n + k_2$ となり $k_1 = k_2$ である。
自然数 $n, k$ に対し、$n + k = n$ ならば $k = 0$ である。
$n + k = n + 0$ より $k = 0$ となる。
