TD11 – Arithmétique de Peano et induction

Arithmétique de Peano

Rappel : L’arithmétique de Peano est une théorie des nombres écrite avec le langage ( est un opérateur unaire, interprété comme « successeur »), et définie par les axiomes

Fondation Injectivité Neutre
Addition Nilpotence    
Distributivité Induction

est un prédicat quelconque

  1. Démontrer la formule .
  2. Démontrer que l’addition est commutative.
  3. Démontrer la formule .
  4. Donner une définition pour «  est inférieur ou égal à  » basée sur l’arithmétique de Péano.
  5. Prouver que la relation ainsi définie est un ordre.
  6. Prouver que est le plus petit élément et que est le plus petit élément plus grand que .
  7. Prouver que cet ordre est total (i.e. que ou pour tout ).
  8. Prouver le schéma de induction forte:

Preuves par induction

Démontrer (par induction) les propriétés suivantes.

  1. Pour tout entier , est divisible par 6 ;
  2. Pour tout entier , est divisible par 3 ;
  3. pour tout  ;
  4. pour tout .

Quels axiomes de Peano avez-vous utilisé pour la preuve ?

Induction forte

Rappel : On dit qu’une preuve utilise l’induction forte lorsque le pas inductif a la forme , plutôt que . Autrement dit, on utilise comme hypothèse de récurrence le fait que la propriété est vraie pour tous les entiers plus petits que , plutôt que seulement pour .

  1. Prouver par induction forte que tout entier peut être exprimé sous la forme avec et des entiers positifs.

Bons ordres

Rappel : un ordre sur un ensemble est bien fondé si tout sous-ensemble de contient (au moins) un élément minimal (i.e., un élément n’ayant pas d’élément plus petit que lui dans le sous-ensemble). De façon équivalente, un ordre est bien fondé s’il n’existe pas de chaîne strictement décroissante infinie. On ordre total et bien fondé est dit un bon ordre.

Dire si les ordres suivants sont bien fondés et/ou des bons ordres :

  1. L’ordre usuel sur les nombres naturels ;
  2. L’ordre usuel sur les nombres rationnels ;
  3. L’ordre sur (les paires de naturels) défini par si et seulement si et  ;
  4. L’ordre alphabétique sur les mots ;
  5. Un ordre quelconque sur un ensemble fini.