Aller au contenu
Topos Uranos
Français

Opérations de base sur les entiers naturels et relations d’ordre

Résumé

Cette leçon définit l’addition, la multiplication et la puissance des entiers naturels à partir du successeur des axiomes de Peano, avec le théorème de récurrence, qui garantit que les définitions par récurrence déterminent une opération unique ; elle admet sa partie d’existence, démontre par récurrence sa partie d’unicité et en déduit les propriétés des opérations : commutativité, associativité, distributivité et simplification. Elle définit ensuite la relation d’ordre au moyen de l’addition, avec ses propriétés de trichotomie, de transitivité et de monotonie, ainsi que les opérations réciproques, la soustraction et la division, et les conditions dans lesquelles elles existent. Le principe de récurrence est l’instrument de toutes les démonstrations.

Objectifs d’apprentissage

  1. Énoncer le théorème de récurrence et écrire avec lui les définitions par récurrence de l’addition, de la multiplication et de la puissance des entiers naturels.
  2. Démontrer par récurrence des propriétés des opérations à partir de leurs définitions.
  3. Définir l’ordre des entiers naturels au moyen de l’addition et appliquer ses propriétés de trichotomie, de transitivité et de monotonie.
  4. Reconnaître quand la soustraction et la division de deux entiers naturels existent, et calculer avec elles sans sortir des entiers naturels.

L’addition

Les opérations sur les entiers naturels sont connues depuis l’école ; il s’agit ici de les fonder avec une précision mathématique. Dans la leçon sur les axiomes de Peano, les entiers naturels ont été définis à partir de 11 et de l’opération successeur, qui associe à chaque entier naturel nn le suivant, S(n)S(n). L’addition se définit à partir du successeur par deux règles : ajouter 11, c’est prendre le successeur, et ajouter le successeur de mm, c’est prendre le successeur de la somme avec mm.

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

Une définition de ce type est dite par récurrence : la première règle fixe la valeur pour 11 et la seconde ramène chaque cas au précédent. Or, que deux règles de ce genre définissent effectivement une opération renferme deux affirmations distinctes : qu’il existe une fonction qui les vérifie pour tous les entiers naturels (existence) et qu’il n’y a pas deux fonctions distinctes qui les vérifient (unicité). Les deux forment le théorème de récurrence, dû à Dedekind : ce cours admet la partie d’existence, comme on l’explique après l’encadré, et démontre celle d’unicité. On l’énonce sous une forme générale pour qu’il serve aussi à la multiplication, à la puissance et aux définitions par récurrence des leçons suivantes.

Fait admis (théorème de récurrence). Soient XX un ensemble et cc un élément de XX, et supposons donnée, pour chaque entier naturel nn, une règle gng_n qui associe à chaque élément de XX un élément de XX. Alors il existe une fonction ff de N\mathbb{N} dans XX telle que f(1)=cf(1) = c et f(S(n))=gn(f(n))f(S(n)) = g_n(f(n)) pour tout entier naturel nn, et cette fonction est unique.

L’existence est admise dans ce cours sans démonstration. Sa démonstration exige de construire la fonction ff comme un ensemble de couples : le plus petit ensemble de couples qui contient (1,c)(1, c) et qui, avec chaque couple (n,x)(n, x), contient (S(n),gn(x))(S(n), g_n(x)) ; puis de vérifier, par récurrence, qu’à chaque entier naturel y correspond un unique second élément. Cette construction relève de la théorie des ensembles et n’apporte rien à l’arithmétique qui suit. L’unicité, en revanche, est une conséquence directe du cinquième axiome de Peano.

LemmeUnicité de la fonction définie par récurrence

Si deux fonctions ff et hh de N\mathbb{N} dans XX vérifient les deux conditions du théorème de récurrence, alors elles sont égales. La figure représente les valeurs de l’une et de l’autre sur les premiers entiers naturels.

Démonstration

  1. A={n∈N:f(n)=h(n)}\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}

    Soit AA l’ensemble des entiers naturels en lesquels les deux fonctions coïncident. Il suffit de prouver que AA est l’ensemble de tous les entiers naturels.

  2. f(1)=c=h(1)f(1) = \resaltar{c} = h(1)

    L’entier 11 appartient à AA, parce que les deux fonctions valent cc en 11.

  3. f(S(k))=gk(f(k))=gk(h(k))=h(S(k))f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))

    Si kk appartient à AA, alors S(k)S(k) aussi : les deux fonctions appliquent la même règle gkg_k à la même valeur.

  4. A=N,(∀n∈N) (f(n)=h(n))A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))

    D’après le cinquième axiome de Peano, AA est l’ensemble de tous les entiers naturels : les deux fonctions sont égales.

L’addition s’obtient à partir du théorème en fixant le premier terme nn et en prenant X=NX = \mathbb{N}, c=S(n)c = S(n) et, pour tout mm, la règle gmg_m qui associe à chaque entier naturel son successeur : la fonction ff que fournit le théorème est celle qui associe à chaque mm le nombre n+mn + m, et les deux règles de l’addition sont les deux conditions du théorème. De même, avec c=nc = n et la règle qui ajoute nn, on obtient la multiplication, et avec c=bc = b et la règle qui multiplie par bb, la puissance. Ajouter mm revient, en définitive, à appliquer mm fois le successeur.

ExempleDeux plus deux font quatre

L’affirmation la plus connue de l’arithmétique est un théorème qui se démontre avec les deux règles de l’addition et les noms 2=S(1)2 = S(1), 3=S(2)3 = S(2) et 4=S(3)4 = S(3).

Démonstration

  1. 2+2=2+S(1)2 + 2 = 2 + S(1)

    Nous écrivons le second terme comme successeur de 11.

  2. 2+S(1)=S(2+1)2 + S(1) = S(2 + 1)

    D’après la deuxième règle, ajouter un successeur, c’est prendre le successeur de la somme.

  3. S(2+1)=S(S(2))S(2 + 1) = S(S(2))

    D’après la première règle, ajouter 11, c’est prendre le successeur.

  4. S(S(2))=S(3)=4S(S(2)) = S(3) = 4

    Comme S(2)=3S(2) = 3 et S(3)=4S(3) = 4, on obtient le résultat.

Des règles de l’addition se déduisent, par récurrence, ses propriétés. Pour tous les entiers naturels aa, bb et cc :

  1. Commutativité : a+b=b+aa + b = b + a.
  2. Associativité : (a+b)+c=a+(b+c)(a + b) + c = a + (b + c). C’est pourquoi on peut écrire a+b+ca + b + c sans parenthèses.
  3. Simplification : si a+c=b+ca + c = b + c, alors a=ba = b.

La commutativité a été démontrée dans le problème résolu 5 de la leçon sur les axiomes de Peano, et l’associativité y est l’un des problèmes proposés. La simplification est démontrée dans le problème résolu 1 de cette leçon.