自然数の基本演算と順序関係

要約

この課では、ペアノの公理の後者から出発し、再帰定理を用いて自然数の加法、乗法、累乗を定義する。再帰定理は、再帰的定義がただ一つの演算を定めることを保証する。この課はその存在の部分を認め、一意性の部分を帰納法で証明し、演算の性質、すなわち交換法則、結合法則、分配法則、簡約法則を導く。続いて加法によって順序関係を定義し、その三分律、推移律、単調性を示し、さらに逆演算である減法と除法を、それらが存在する条件とともに定義する。数学的帰納法の原理がすべての証明の道具である。

学習目標

再帰定理を述べ、それを用いて自然数の加法、乗法、累乗の再帰的定義を書く。
演算の性質を、その定義から帰納法で証明する。
自然数の順序を加法によって定義し、その三分律、推移律、単調性を適用する。
二つの自然数の減法と除法がいつ可能かを見きわめ、自然数の範囲から出ることなくそれらを用いて計算する。

加法

自然数の演算は学校以来よく知られている。ここではそれを数学的な厳密さで基礎づけることが目的である。ペアノの公理の課では、 $1$ と後者をとる演算から自然数が定義された。この演算は各自然数 $n$ にその次の数 $S(n)$ を対応させる。加法は、後者から二つの規則によって定義される。 $1$ を加えることは後者をとることであり、 $m$ の後者を加えることは、 $m$ との和の後者をとることである。

n + 1 = S(n), \qquad n + S(m) = S(n + m)

このような定義を再帰的という。第一の規則が $1$ における値を定め、第二の規則が各場合を一つ前の場合に帰着させる。しかし、このような二つの規則が実際に一つの演算を定めるということには、二つの異なる主張が含まれている。すべての自然数についてそれらを満たす関数が存在すること（存在）と、それらを満たす相異なる二つの関数はないこと（一意性）である。両者を合わせたものが再帰定理であり、デデキントによる。このコースでは、枠のあとで説明するように存在の部分を認め、一意性の部分を証明する。定理は、乗法、累乗、そして以降の課の再帰的定義にも使えるように、一般的な形で述べる。

証明なしに認める事実（再帰定理）。 $X$ を集合、 $c$ を $X$ の元とし、各自然数 $n$ に対して規則 $g_n$ が与えられていて、それが $X$ の各元に $X$ の別の元を対応させるとする。このとき関数 $f$ （ $\mathbb{N}$ から $X$ への）であって、 $f(1) = c$ かつ $f(S(n)) = g_n(f(n))$ がすべての自然数 $n$ について成り立つものが存在し、その関数は一意である。

存在は、このコースでは証明なしに認める。その証明には、関数 $f$ を対の集合として構成すること、すなわち $(1, c)$ を含み、各対 $(n, x)$ とともに $(S(n), g_n(x))$ も含むような最小の対の集合として構成し、そのうえで、各自然数にそこで対応する第二成分がただ一つであることを帰納法で確かめることが必要である。この構成は集合論に属し、以下の算術には何も付け加えない。これに対して一意性は、ペアノの第五公理の直接の帰結である。

補題再帰によって定義される関数の一意性

二つの関数 $f$ と $h$ （ $\mathbb{N}$ から $X$ への）が再帰定理の二つの条件を満たすならば、それらは等しい。図は、最初のいくつかの自然数における両者の値を表している。

証明

$\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}$
$A$ を、二つの関数が一致する自然数の集合とする。 $A$ がすべての自然数の集合であることを示せばよい。
$f(1) = \resaltar{c} = h(1)$
$1$ は $A$ に属する。二つの関数はどちらも値 $c$ をとるからである（ $1$ において）。
$f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))$
$k$ が $A$ に属するならば、 $S(k)$ も属する。二つの関数は同じ値に同じ規則 $g_k$ を適用するからである。
$A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))$
ペアノの第五公理により、 $A$ はすべての自然数の集合である。二つの関数は等しい。

第一の加数 $n$ を固定し、 $X = \mathbb{N}$ 、 $c = S(n)$ 、そして各 $m$ に対して規則 $g_m$ （各自然数にその後者を対応させるもの）をとると、定理から加法が得られる。定理が与える関数 $f$ は、各 $m$ に数 $n + m$ を対応させる関数であり、加法の二つの規則は定理の二つの条件にほかならない。同様に、 $c = n$ と $n$ を加える規則とから乗法が、 $c = b$ と $b$ を掛ける規則とから累乗が得られる。結局、 $m$ を加えることは、後者をとる操作を $m$ 回適用することに等しい。

例二たす二は四

算術で最もよく知られた主張は一つの定理であり、加法の二つの規則と名前 $2 = S(1)$ 、 $3 = S(2)$ 、 $4 = S(3)$ によって証明される。

証明

$2 + 2 = 2 + S(1)$
第二の加数を $1$ の後者として書く。
$2 + S(1) = S(2 + 1)$
第二の規則により、後者を加えることは和の後者をとることである。
$S(2 + 1) = S(S(2))$
第一の規則により、 $1$ を加えることは後者をとることである。
$S(S(2)) = S(3) = 4$
$S(2) = 3$ かつ $S(3) = 4$ なので、結果が得られる。

加法の規則から、その性質が帰納法によって導かれる。すべての自然数 $a$ 、 $b$ 、 $c$ について：

交換法則： $a + b = b + a$ 。
結合法則： $(a + b) + c = a + (b + c)$ 。そのため、括弧なしで $a + b + c$ と書いてよい。
簡約法則： $a + c = b + c$ ならば $a = b$ 。

交換法則はペアノの公理の課の例題 5 で証明され、結合法則はそこで練習問題の一つになっている。簡約法則はこの課の例題 1 で証明する。