Proposition 1Arithmétique dans PA

Lois de l'addition et de la multiplication dans l'arithmétique de Peano

Les conventions sont celles de Récurrence dans PA. Une chaîne $t_0 = t_1 = \cdots = t_n$ , sous des hypothèses données, signifie que chaque égalité $t_{i-1} = t_i$ est démontrable sous ces hypothèses : instance d'un axiome ou d'une égalité déjà établie, hypothèse, ou leur image par la congruence $t = u \to r[t/v] = r[u/v]$ , qui remplace un sous-terme par un terme égal. La transitivité et la symétrie de l'égalité (Calcul à variables libres, (vi)) donnent alors $t_0 = t_n$ .

Énoncé

Pour tous termes $t$ , $u$ et $r$ :

(i) Addition. $\vdash_{\mathsf{PA}} 0 + t = t$ , $\vdash_{\mathsf{PA}} S\,t + u = S(t + u)$ , $\vdash_{\mathsf{PA}} S\,t = t + S\,0$ , $\vdash_{\mathsf{PA}} t + u = u + t$ et $\vdash_{\mathsf{PA}} t + u + r = t + (u + r)$ .

(ii) Simplification. $\vdash_{\mathsf{PA}} t + r = u + r \to t = u$ et $\vdash_{\mathsf{PA}} t + u = 0 \to (t = 0 \wedge u = 0)$ .

(iii) Multiplication. $\vdash_{\mathsf{PA}} 0 \times t = 0$ , $\vdash_{\mathsf{PA}} t \times S\,0 = t$ , $\vdash_{\mathsf{PA}} S\,t \times u = t \times u + u$ , $\vdash_{\mathsf{PA}} t \times u = u \times t$ , $\vdash_{\mathsf{PA}} t \times (u + r) = t \times u + t \times r$ , $\vdash_{\mathsf{PA}} (t + u) \times r = t \times r + u \times r$ et $\vdash_{\mathsf{PA}} (t \times u) \times r = t \times (u \times r)$ .

(iv) $\vdash_{\mathsf{PA}} t \times S\,r = u \times S\,r \to t = u$ et $\vdash_{\mathsf{PA}} t \times u = 0 \to (t = 0 \vee u = 0)$ .

Démonstration

Toutes ces formules sont sans quantificateur. Il suffit donc de les démontrer quand $t$ , $u$ et $r$ sont trois variables distinctes $x$ , $y$ et $z$ : le point (ii) de Calcul à variables libres donne ensuite le cas de termes quelconques. Chaque récurrence est celle du point (iii) de Récurrence dans PA, avec $\Gamma$ vide ; on indique la variable de récurrence, les autres étant des paramètres.

(i) $0 + x = x$ , par récurrence sur $x$ . Le cas $0$ est l'instance $0 + 0 = 0$ de $\mathrm Q_4$ . Sous l'hypothèse $0 + x = x$ , la chaîne $0 + S\,x = S(0 + x) = S\,x$ emploie $\mathrm Q_5$ puis l'hypothèse.

$S\,x + y = S(x + y)$ , par récurrence sur $y$ . Pour $0$ : $S\,x + 0 = S\,x = S(x + 0)$ , par $\mathrm Q_4$ deux fois. Sous l'hypothèse $S\,x + y = S(x + y)$ : $S\,x + S\,y = S(S\,x + y) = S\,S(x + y) = S(x + S\,y)$ , par $\mathrm Q_5$ , l'hypothèse et $\mathrm Q_5$ .

$S\,x = x + S\,0$ , sans récurrence : $x + S\,0 = S(x + 0) = S\,x$ , par $\mathrm Q_5$ et $\mathrm Q_4$ .

$x + y = y + x$ , par récurrence sur $y$ . Pour $0$ : $x + 0 = x = 0 + x$ , par $\mathrm Q_4$ et le premier calcul. Sous l'hypothèse $x + y = y + x$ : $x + S\,y = S(x + y) = S(y + x) = S\,y + x$ , par $\mathrm Q_5$ , l'hypothèse et le deuxième calcul, appliqué aux variables $y$ et $x$ .

$x + y + z = x + (y + z)$ , par récurrence sur $z$ . Pour $0$ : $x + y + 0 = x + y = x + (y + 0)$ , par $\mathrm Q_4$ deux fois. Sous l'hypothèse : $x + y + S\,z = S(x + y + z) = S(x + (y + z)) = x + S(y + z) = x + (y + S\,z)$ , par $\mathrm Q_5$ , l'hypothèse, $\mathrm Q_5$ et $\mathrm Q_5$ .

(ii) $x + z = y + z \to x = y$ , par récurrence sur $z$ . Pour $0$ : sous l'hypothèse $x + 0 = y + 0$ , la chaîne $x = x + 0 = y + 0 = y$ conclut, et le théorème de la déduction donne la formule. Sous les hypothèses $x + z = y + z \to x = y$ et $x + S\,z = y + S\,z$ : la chaîne $S(x + z) = x + S\,z = y + S\,z = S(y + z)$ et l'instance $S(x + z) = S(y + z) \to x + z = y + z$ de $\mathrm Q_2$ donnent $x + z = y + z$ , puis $x = y$ par la première hypothèse ; le théorème de la déduction décharge la seconde.

$x + y = 0 \to (x = 0 \wedge y = 0)$ , sans récurrence. Soit $w$ une variable distincte de $x$ et de $y$ , et $C$ la formule $x = 0 \wedge y = 0$ . Sous les hypothèses $x + y = 0$ et $y = S\,w$ , la chaîne $S(x + w) = x + S\,w = x + y = 0$ contredit l'instance $\neg(S(x + w) = 0)$ de $\mathrm Q_1$ , et l'instance $P \to (\neg P \to Q)$ donne $C$ . La variable $w$ n'est libre ni dans $x + y = 0$ ni dans $C$ : l'élimination du point (i) de Récurrence dans PA donne $C$ sous les hypothèses $x + y = 0$ et $\exists w\, (y = S\,w)$ . Sous les hypothèses $x + y = 0$ et $y = 0$ , la chaîne $x = x + 0 = x + y = 0$ donne $x = 0$ , d'où $C$ . Le raisonnement par cas, avec l'instance $\neg(y = 0) \to \exists w\, (y = S\,w)$ de $\mathrm Q_3$ et la tautologie $(\neg A \to B) \to ((A \to C) \to ((B \to C) \to C))$ , donne $C$ sous la seule hypothèse $x + y = 0$ .

(iii) $0 \times x = 0$ , par récurrence sur $x$ . Pour $0$ , c'est $\mathrm Q_6$ . Sous l'hypothèse $0 \times x = 0$ : $0 \times S\,x = 0 \times x + 0 = 0 \times x = 0$ , par $\mathrm Q_7$ , $\mathrm Q_4$ et l'hypothèse.

$x \times S\,0 = x$ , sans récurrence : $x \times S\,0 = x \times 0 + x = 0 + x = x$ , par $\mathrm Q_7$ , $\mathrm Q_6$ et (i).

$S\,x \times y = x \times y + y$ , par récurrence sur $y$ . Pour $0$ : $S\,x \times 0 = 0 = x \times 0 = x \times 0 + 0$ , par $\mathrm Q_6$ deux fois et $\mathrm Q_4$ . Sous l'hypothèse $S\,x \times y = x \times y + y$ : $\begin{aligned} S\,x \times S\,y &= S\,x \times y + S\,x \\ &= x \times y + y + S\,x \\ &= x \times y + (y + S\,x) \\ &= x \times y + (x + S\,y) \\ &= x \times y + x + S\,y \\ &= x \times S\,y + S\,y, \end{aligned}$ par $\mathrm Q_7$ , l'hypothèse, l'associativité, l'égalité $y + S\,x = S(y + x) = S(x + y) = x + S\,y$ , tirée de $\mathrm Q_5$ et de la commutativité, l'associativité et $\mathrm Q_7$ .

$x \times y = y \times x$ , par récurrence sur $y$ . Pour $0$ : $x \times 0 = 0 = 0 \times x$ . Sous l'hypothèse : $x \times S\,y = x \times y + x = y \times x + x = S\,y \times x$ , par $\mathrm Q_7$ , l'hypothèse et le calcul précédent, appliqué aux variables $y$ et $x$ .

$x \times (y + z) = x \times y + x \times z$ , par récurrence sur $z$ . Pour $0$ : $x \times (y + 0) = x \times y = x \times y + 0 = x \times y + x \times 0$ , par $\mathrm Q_4$ deux fois et $\mathrm Q_6$ . Sous l'hypothèse : $\begin{aligned} x \times (y + S\,z) &= x \times S(y + z) \\ &= x \times (y + z) + x \\ &= x \times y + x \times z + x \\ &= x \times y + (x \times z + x) \\ &= x \times y + x \times S\,z, \end{aligned}$ par $\mathrm Q_5$ , $\mathrm Q_7$ , l'hypothèse, l'associativité et $\mathrm Q_7$ . La distributivité à droite s'en déduit : $(x + y) \times z = z \times (x + y) = z \times x + z \times y = x \times z + y \times z$ , par la commutativité trois fois.

$(x \times y) \times z = x \times (y \times z)$ , par récurrence sur $z$ . Pour $0$ : les deux membres valent $0$ , par trois instances de $\mathrm Q_6$ , $(x \times y) \times 0 = 0$ , $y \times 0 = 0$ sous la congruence, qui donne $x \times (y \times 0) = x \times 0$ , et $x \times 0 = 0$ . Sous l'hypothèse : $\begin{aligned} &(x \times y) \times S\,z \\ &\quad = (x \times y) \times z + x \times y \\ &\quad = x \times (y \times z) + x \times y \\ &\quad = x \times (y \times z + y) \\ &\quad = x \times (y \times S\,z), \end{aligned}$ par $\mathrm Q_7$ , l'hypothèse, la distributivité et $\mathrm Q_7$ .

(iv) $x \times S\,z = y \times S\,z \to x = y$ , par récurrence sur $x$ , appliquée à la formule $\varphi = \forall y\, (x \times S\,z = y \times S\,z \to x = y)$ . Soit $w$ une variable distincte de $x$ , $y$ et $z$ .

Pour $0$ : sous l'hypothèse $0 \times S\,z = y \times S\,z$ , la chaîne $y \times z + y = y \times S\,z = 0 \times S\,z = 0$ et (ii) donnent $y = 0$ , d'où $0 = y$ . Le théorème de la déduction et la généralisation en $y$ donnent $\vdash_{\mathsf{PA}} \varphi[0/x]$ .

Pas : sous les hypothèses $\varphi$ et $S\,x \times S\,z = y \times S\,z$ , montrons $S\,x = y$ . Sous l'hypothèse supplémentaire $y = 0$ , la chaîne $S(S\,x \times z + x) = S\,x \times z + S\,x = S\,x \times S\,z = y \times S\,z = 0 \times S\,z = 0$ , par $\mathrm Q_5$ , $\mathrm Q_7$ , l'hypothèse, le remplacement et (iii), contredit $\mathrm Q_1$ , et $S\,x = y$ s'en déduit. Sous l'hypothèse supplémentaire $y = S\,w$ , la chaîne $x \times S\,z + S\,z = S\,x \times S\,z = y \times S\,z = S\,w \times S\,z = w \times S\,z + S\,z$ , par (iii) deux fois, donne $x \times S\,z = w \times S\,z$ par (ii). L'axiome (2), avec le terme $w$ , donne $\varphi \to (x \times S\,z = w \times S\,z \to x = w)$ , d'où $x = w$ , puis $S\,x = S\,w = y$ . La variable $w$ n'est libre ni dans les hypothèses ni dans la conclusion : l'élimination et le raisonnement par cas sur l'instance de $\mathrm Q_3$ donnent $S\,x = y$ . Le théorème de la déduction décharge l'hypothèse $S\,x \times S\,z = y \times S\,z$ , et la généralisation en $y$ , qui n'est pas libre dans $\varphi$ , donne $\varphi[S\,x/x]$ . Le point (iii) de Récurrence dans PA donne $\vdash_{\mathsf{PA}} \varphi$ , et l'axiome (2), avec le terme $y$ , conclut.

$x \times y = 0 \to (x = 0 \vee y = 0)$ , sans récurrence. Sous les hypothèses $x \times y = 0$ et $y = 0$ , la conclusion est immédiate. Sous les hypothèses $x \times y = 0$ et $y = S\,w$ , la chaîne $x \times w + x = x \times S\,w = x \times y = 0$ et (ii) donnent $x = 0$ . L'élimination de $w$ et le raisonnement par cas concluent comme en (ii).

□

Remarque

Les trois formules établies sans récurrence, $S\,t = t + S\,0$ et les secondes formules de (ii) et de (iv), sont démontrables dans $\mathsf Q$ , puisque leurs preuves n'emploient que ses axiomes. Les lois dont la preuve demande une récurrence, au contraire, ne le sont pas en général, alors que $\mathsf Q$ en démontre toutes les instances par des chiffres (Calculs dans Q, (i) et (ii)). Dans la structure $\mathcal M$ de la deuxième remarque de ce nœud, on a $0 + a = b \neq a$ ; $a + 0 = a$ et $0 + a = b$ , donc l'addition n'est pas commutative ; $(0 + 0) + a = b$ et $0 + (0 + a) = 0 + b = a$ , donc elle n'est pas associative ; $0 + a = 1 + a = b$ , donc elle n'est pas simplifiable. Pour la multiplication, $a \times S\,0 = b$ ; $1 \times a = a$ et $a \times 1 = b$ ; $(1 \times a) \times 1 = b$ et $1 \times (a \times 1) = a$ ; $1 \times (0 + a) = a$ et $1 \times 0 + 1 \times a = b$ ; enfin $1 \times S\,a = 2 \times S\,a = a$ , avec $1 \neq 2$ . Par le théorème de correction, $\mathsf Q$ ne démontre aucune de ces lois. Ces valeurs ont été vérifiées par un calcul sur la table de $\mathcal M$ ; les seules formules de l'énoncé qui y restent vraies sont les trois formules démontrables dans $\mathsf Q$ , $S\,t + u = S(t + u)$ et $0 \times t = 0$ , et $\mathcal M$ ne tranche pas pour ces deux dernières. Pour $0 \times t = 0$ , il suffit de modifier $\mathcal M$ en posant $0 \times a = a$ : les sept axiomes restent satisfaits, puisque $\mathrm Q_7$ en $x = 0$ , $y = a$ s'écrit $0 \times a = 0 \times a + 0$ et qu'aucun autre axiome ne fait intervenir $0 \times a$ , ce qu'a confirmé le même calcul ; cette structure réfute $0 \times t = 0$ .

Remarque

L'ordre des démonstrations n'est pas indifférent, et l'erreur la plus répandue est de tenter la commutativité d'emblée. Par récurrence sur $y$ , le cas $0$ demande $x + 0 = 0 + x$ , c'est-à-dire $0 + x = x$ , qui est déjà une récurrence, et le pas demande de faire passer $S$ à gauche, ce que fait la deuxième formule de (i), récurrence elle aussi. De même, la commutativité de la multiplication demande d'abord $0 \times x = 0$ et $S\,x \times y = x \times y + y$ : les axiomes ne calculent que sur le second argument, et presque chaque loi qui touche au premier coûte une récurrence ; $t + u = 0 \to (t = 0 \wedge u = 0)$ y échappe, parce qu'il suffit de décomposer $u$ .

Remarque

Hermann Grassmann a défini l'addition et la multiplication par récurrence et en a tiré les lois usuelles dans son Lehrbuch der Arithmetik (1861) ; Peano s'est largement servi de ce travail, comme le rapporte H. Wang (« The axiomatization of arithmetic », Journal of Symbolic Logic 22, 1957, p. 145-158). La différence est ici que chaque récurrence est une instance d'un schéma du premier ordre, appliquée dans un système formel.

Repose sur

Règles de démonstration dans l'arithmétique de Peano

Sert à

Ordre et quantifications bornées dans l'arithmétique de Peano