L'arithmétique de ℕ

Toutes les preuves sont des récurrences sur la dernière variable (Récurrence), à partir des quatre égalités qui définissent les opérations (Addition, multiplication).

(i) L'associativité $(k + m) + n = k + (m + n)$ se démontre par récurrence sur $n$ : pour $n = 0$, les deux membres valent $k + m$, et $$\begin{aligned} (k + m) + S(n) &= S((k+m)+n) \\ &= S(k + (m+n)) \\ &= k + S(m+n) \\ &= k + (m + S(n)). \end{aligned}$$

On montre $0 + n = n$ par récurrence sur $n$ : $0 + 0 = 0$ et $0 + S(n) = S(0 + n) = S(n)$. Puis $S(m) + n = S(m + n)$, encore par récurrence sur $n$ : pour $n = 0$ les deux membres valent $S(m)$, et $$\begin{aligned} S(m) + S(n) &= S(S(m) + n) \\ &= S(S(m + n)) \\ &= S(m + S(n)). \end{aligned}$$ La commutativité $m + n = n + m$ s'en déduit par récurrence sur $n$, puisque $$\begin{aligned} m + S(n) &= S(m + n) \\ &= S(n + m) = S(n) + m. \end{aligned}$$

Pour la simplification, récurrence sur $p$ : si $m + S(p) = n + S(p)$, alors $S(m + p) = S(n + p)$, d'où $m + p = n + p$ par injectivité de $S$ (Axiomes de Peano), puis $m = n$.

Enfin, si $n \neq 0$, alors $n = S(n')$ (Axiomes de Peano), et $m + n = S(m + n') \neq 0$ ; donc $m + n = 0$ impose $n = 0$, puis $m = m + 0 = 0$.

(ii) On montre successivement, par récurrence sur la dernière variable : la distributivité à gauche $m(n + p) = mn + mp$, car $$\begin{aligned} m(n + S(p)) &= m\,S(n + p) \\ &= m(n + p) + m \\ &= mn + mp + m \\ &= mn + m\,S(p) ; \end{aligned}$$ l'associativité $(mn)p = m(np)$, car $$\begin{aligned} (mn)S(p) &= (mn)p + mn \\ &= m(np) + mn \\ &= m(np + n) = m(n\,S(p)) ; \end{aligned}$$ les égalités $0 \cdot n = 0$ et $S(m)\,n = mn + n$, la seconde par récurrence sur $n$, puisque $$\begin{aligned} S(m)\,S(n) &= S(m)\,n + S(m) \\ &= mn + n + m + 1 \end{aligned}$$ et $m\,S(n) + S(n) = mn + m + n + 1$ ; puis la commutativité, par récurrence sur $n$ : $m \cdot 0 = 0 = 0 \cdot m$ et $$\begin{aligned} m\,S(n) &= mn + m \\ &= nm + m = S(n)\,m. \end{aligned}$$

La distributivité à droite s'en déduit, et $1 \cdot n = n \cdot 1 = n$. Si $n \neq 0$, alors $n = S(n')$ (Axiomes de Peano) ; si de plus $mn = 0$, alors $mn' + m = 0$, donc $m = 0$ par (i).

(iii) Récurrence sur $n$. Pour $n = 0$ : $m \leqslant 0$ équivaut à $m = 0$, et $m + k = 0$ aussi, par (i).

Supposons le résultat vrai pour $n$. Comme $S(n) = n \cup \{n\}$, on a, pour l'ordre défini au nœud Bon ordre sur ℕ, $m \leqslant S(n)$ si et seulement si $m \leqslant n$ ou $m = S(n)$. Si $m + k = n$, alors $m + S(k) = S(n)$ ; si $m = S(n)$, $k = 0$ convient.

Réciproquement, si $m + k = S(n)$, ou bien $k = 0$ et $m = S(n)$, ou bien $k \neq 0$, donc $k = S(k')$ (Axiomes de Peano), et $S(m + k') = S(n)$ donne $m + k' = n$, donc $m \leqslant n$. L'unicité de $k$ est la simplification de (i), et $k = 0$ équivaut à $m = n$.

(iv) Si $m + k = n$, alors $(m + p) + k = n + p$ et $mp + kp = np$, par commutativité, associativité et distributivité. Si de plus $k \neq 0$ et $p \neq 0$, alors $kp \neq 0$ par (ii), et les inégalités sont strictes par (iii).