Axiomes de Peano - Peano axioms

En logique mathématique , les axiomes de Peano , également connus sous le nom d' axiomes Dedekind-Peano ou postulats de Peano , sont des axiomes pour les nombres naturels présentés par le mathématicien italien du XIXe siècle Giuseppe Peano . Ces axiomes ont été utilisés presque sans changement dans un certain nombre d' enquêtes métamathématiques , y compris la recherche sur les questions fondamentales de savoir si la théorie des nombres est cohérente et complète .

La nécessité de formaliser l' arithmétique n'a pas été bien appréciée jusqu'au travail d' Hermann Grassmann , qui a montré dans les années 1860 que de nombreux faits en arithmétique pouvaient être dérivés de faits plus basiques sur l' opération successeur et l' induction . En 1881, Charles Sanders Peirce a fourni une axiomatisation de l'arithmétique des nombres naturels. En 1888, Richard Dedekind proposa une autre axiomatisation de l'arithmétique des nombres naturels, et en 1889, Peano en publia une version simplifiée sous forme de recueil d'axiomes dans son livre, Les principes de l'arithmétique présentés par une nouvelle méthode ( Latin : Arithmetices principia, nova methodo exposita ).

Les neuf axiomes de Peano contiennent trois types d'énoncés. Le premier axiome affirme l'existence d'au moins un membre de l'ensemble des nombres naturels. Les quatre suivants sont des déclarations générales sur l' égalité ; dans les traitements modernes, ceux-ci ne sont souvent pas considérés comme faisant partie des axiomes de Peano, mais plutôt comme des axiomes de la "logique sous-jacente". Les trois prochains axiomes sont des énoncés de premier ordre sur les nombres naturels exprimant les propriétés fondamentales de l'opération successeur. Le neuvième, dernier axiome est un énoncé du second ordre du principe d'induction mathématique sur les nombres naturels. Un système de premier ordre plus faible appelé arithmétique de Peano est obtenu en ajoutant explicitement les symboles d'opération d'addition et de multiplication et en remplaçant l' axiome d' induction du second ordre par un schéma d'axiome du premier ordre .

Formulation

Lorsque Peano a formulé ses axiomes, le langage de la logique mathématique en était à ses balbutiements. Le système de notation logique qu'il a créé pour présenter les axiomes ne s'est pas avéré populaire, bien que ce soit la genèse de la notation moderne pour l' appartenance à un ensemble (∈, qui vient du ε de Peano) et l' implication (⊃, qui vient du ' inversé de Peano C'.) Peano maintenait une distinction claire entre les symboles mathématiques et logiques, ce qui n'était pas encore courant en mathématiques; une telle séparation avait été introduite pour la première fois dans le Begriffsschrift de Gottlob Frege , publié en 1879. Peano n'était pas au courant du travail de Frege et a recréé indépendamment son appareil logique basé sur le travail de Boole et Schröder .

Les axiomes de Peano définissent les propriétés arithmétiques des nombres naturels , généralement représentés par un ensemble N ou Les symboles non logiques des axiomes se composent d'un symbole constant 0 et d'un symbole de fonction unaire S .

Le premier axiome énonce que la constante 0 est un nombre naturel :

  1. 0 est un nombre naturel.

Les quatre axiomes suivants décrivent la relation d' égalité . Puisqu'ils sont logiquement valides dans la logique du premier ordre avec égalité, ils ne sont pas considérés comme faisant partie des « axiomes de Peano » dans les traitements modernes.

  1. Pour tout entier naturel x , x = x . C'est-à-dire que l'égalité est réflexive .
  2. Pour tous les nombres naturels x et y , si x = y , alors y = x . C'est-à-dire que l'égalité est symétrique .
  3. Pour tous les nombres naturels x , y et z , si x = y et y = z , alors x = z . C'est-à-dire que l'égalité est transitive .
  4. Pour tout a et b , si b est un nombre naturel et a = b , alors a est également un nombre naturel. C'est-à-dire que les nombres naturels sont fermés par égalité.

Les axiomes restants définissent les propriétés arithmétiques des nombres naturels. Les naturels sont supposés fermés sous une fonction « successeur » à valeur unique S .

  1. Pour tout entier naturel n , S ( n ) est un entier naturel. C'est-à-dire que les nombres naturels sont fermés sous S .
  2. Pour tous les nombres naturels m et n , m = n si et seulement si S ( m ) = S ( n ) . C'est-à-dire que S est une injection .
  3. Pour tout entier naturel n , S ( n ) = 0 est faux. C'est-à-dire qu'il n'y a pas de nombre naturel dont le successeur est 0.

La formulation originale de Peano des axiomes utilisait 1 au lieu de 0 comme « premier » nombre naturel. Cependant, parce que 0 est l' identité additive en arithmétique, la plupart des formulations modernes des axiomes de Peano commencent à partir de 0.

La chaîne de dominos clairs, en commençant par le plus proche, peut représenter N , cependant, les axiomes 1 à 8 sont également satisfaits par l'ensemble de tous les dominos clairs et foncés. Le 9ème axiome ( induction ) limite N à la chaîne de pièces légères ("pas de déchets") car seuls les dominos légers tomberont lorsque le plus proche sera renversé.

Les axiomes 1, 6, 7, 8 définissent une représentation unaire de la notion intuitive de nombres naturels : le nombre 1 peut être défini comme S (0), 2 comme S ( S (0)), etc. Cependant, considérant la notion de nombres naturels comme étant définis par ces axiomes, les axiomes 1, 6, 7, 8 n'impliquent pas que la fonction successeur génère tous les nombres naturels différents de 0. Autrement dit, ils ne garantissent pas que tout nombre naturel autre que zéro doit succéder à un certain nombre. autre nombre naturel.

La notion intuitive que chaque nombre naturel peut être obtenu en appliquant successeur suffisamment souvent à zéro nécessite un axiome supplémentaire, qui est parfois appelé l' axiome d'induction .

  1. Si K est un ensemble tel que :
    • 0 est dans K , et
    • pour tout entier naturel n , n étant dans K implique que S ( n ) est dans K ,
    alors K contient tout entier naturel.

L'axiome d'induction est parfois énoncé sous la forme suivante :

  1. Si φ est un unaire prédicat tel que:
    • φ (0) est vraie, et
    • pour chaque nombre naturel n , φ ( n ) étant vrai implique que φ ( S ( n )) est vrai,
    alors φ ( n ) est vrai pour tout entier naturel n .

Dans la formulation originale de Peano, l'axiome d'induction est un axiome du second ordre . Il est maintenant courant de remplacer ce principe du second ordre par un schéma d'induction du premier ordre plus faible . Il existe des différences importantes entre les formulations du second ordre et du premier ordre, comme discuté dans la section § Théorie du premier ordre de l'arithmétique ci-dessous.

Arithmétique

Les axiomes de Peano peuvent être augmentés avec les opérations d' addition et de multiplication et l'ordre total (linéaire) habituel sur N . Les fonctions et relations respectives sont construites en théorie des ensembles ou en logique du second ordre , et peuvent être démontrées comme uniques à l'aide des axiomes de Peano.

Une addition

L'addition est une fonction qui mappe deux nombres naturels (deux éléments de N ) à un autre. Il est défini récursivement comme :

Par exemple:

La structure ( N , + ) est un monoïde commutatif d' élément d' identité 0. ( N , + ) est aussi un magma annulatif , et donc noyable dans un groupe . Le plus petit groupe englobant N est celui des entiers .

Multiplication

De même, la multiplication est une fonction mappant deux nombres naturels à un autre. Compte tenu de l'addition, il est défini récursivement comme :

Il est facile de voir que (ou "1", dans le langage familier de la représentation décimale ) est le droit multiplicatif identité :

Montrer que c'est aussi l'identité de gauche multiplicative nécessite l'axiome d'induction en raison de la façon dont la multiplication est définie :

  • est l'identité gauche de 0 : .
  • Si est l'identité gauche de (c'est-à-dire ), alors est aussi l'identité gauche de : .

Par conséquent, par l'axiome d'induction est l'identité multiplicative gauche de tous les nombres naturels. De plus, on peut montrer que la multiplication est commutative et se distribue sur l' addition :

.

Ainsi, est un semi- anneau commutatif .

Inégalités

La relation d' ordre total habituelle sur les nombres naturels peut être définie comme suit, en supposant que 0 est un nombre naturel :

Pour tout a , bN , ab si et seulement s'il existe un certain cN tel que a + c = b .

Cette relation est stable par addition et multiplication : pour , si ab , alors :

  • a + cb + c , et
  • un · cb · c .

Ainsi, la structure ( N , +, ·, 1, 0, ≤) est un semi-anneau ordonné ; car il n'y a pas d'entier naturel entre 0 et 1, c'est un semi-anneau ordonné discret.

L'axiome d'induction est parfois énoncé sous la forme suivante qui utilise une hypothèse plus forte, en utilisant la relation d'ordre « ≤ » :

Pour tout prédicat φ , si
  • φ (0) est vraie, et
  • pour chaque n , kN , si kn implique que φ ( k ) est vrai, alors φ ( S ( n )) est vrai,
alors pour tout nN , φ ( n ) est vrai.

Cette forme de l'axiome d'induction, appelée induction forte , est une conséquence de la formulation standard, mais est souvent mieux adaptée pour raisonner sur l'ordre ≤. Par exemple, pour montrer que les naturels sont bien ordonnés — chaque sous- ensemble non vide de N a un moindre élément — on peut raisonner comme suit. Soit un XN non vide et supposons que X n'a pas le moindre élément.

  • Parce que 0 est le plus petit élément de N , il doit s'agir de 0 X .
  • Pour tout nN , supposons que pour chaque kn , kX . Alors S ( n ) X , car sinon ce serait le moindre élément de X .

Ainsi, le principe d'induction forte, pour chaque nN , nX . Ainsi, XN = ∅ , ce qui contredit X étant un sous-ensemble non vide de N . Ainsi X a un moindre élément.

Théorie du premier ordre de l'arithmétique

Tous les axiomes de Peano, à l'exception du neuvième axiome (l'axiome d'induction) sont des énoncés en logique du premier ordre . Les opérations arithmétiques d'addition et de multiplication et la relation d'ordre peuvent également être définies à l'aide d'axiomes du premier ordre. L'axiome d'induction est de second ordre , puisqu'il quantifie sur des prédicats (de manière équivalente, des ensembles de nombres naturels plutôt que de nombres naturels), mais il peut être transformé en un schéma d'axiome d'induction de premier ordre . Un tel schéma comprend un axiome par prédicat définissable dans le langage du premier ordre de l'arithmétique de Peano, ce qui le rend plus faible que l'axiome du second ordre. La raison pour laquelle il est plus faible est que le nombre de prédicats dans le langage du premier ordre est dénombrable, alors que le nombre d'ensembles de nombres naturels est indénombrable. Ainsi, il existe des ensembles qui ne peuvent pas être décrits en langage du premier ordre (en fait, la plupart des ensembles ont cette propriété).

Les axiomatisations du premier ordre de l'arithmétique de Peano ont une autre limitation technique. Dans la logique du second ordre, il est possible de définir les opérations d'addition et de multiplication à partir de l' opération successeur , mais cela ne peut pas être fait dans le cadre plus restrictif de la logique du premier ordre. Par conséquent, les opérations d'addition et de multiplication sont directement incluses dans la signature de l'arithmétique de Peano, et des axiomes sont inclus qui relient les trois opérations les unes aux autres.

La liste suivante d'axiomes (ainsi que les axiomes d'égalité habituels), qui contient six des sept axiomes de l' arithmétique de Robinson , est suffisante à cette fin :

En plus de cette liste d'axiomes numériques, l'arithmétique de Peano contient le schéma d'induction, qui consiste en un ensemble d' axiomes récursivement énumérables . Pour chaque formule φ ( x , y 1 , ..., y k ) dans le langage de l'arithmétique de Peano, l' axiome d'induction du premier ordre pour φ est la phrase

où est une abréviation pour y 1 ,..., y k . Le premier ordre schéma d'induction comprend toutes les occurrences du premier ordre axiome d'induction, qui est, elle comprend l'axiome d'induction pour toute formule φ .

Axiomatisations équivalentes

Il existe de nombreuses axiomatisations différentes, mais équivalentes, de l'arithmétique de Peano. Alors que certaines axiomatisations, comme celle qui vient d'être décrite, utilisent une signature qui n'a que des symboles pour 0 et les opérations de successeur, d'addition et de multiplication, d'autres axiomatisations utilisent le langage des semi - anneaux ordonnés , y compris un symbole de relation d'ordre supplémentaire. Une telle axiomatisation commence par les axiomes suivants qui décrivent un semi-anneau ordonné discret.

  1. , c'est-à-dire que l'addition est associative .
  2. , c'est-à-dire que l'addition est commutative .
  3. , c'est-à-dire que la multiplication est associative.
  4. , c'est-à-dire que la multiplication est commutative.
  5. , c'est-à-dire que la multiplication se distribue sur l'addition.
  6. , c'est-à-dire que zéro est une identité pour l'addition, et un élément absorbant pour la multiplication (en fait superflu).
  7. , c'est-à-dire que l'un est une identité pour la multiplication.
  8. , c'est-à-dire que l'opérateur '<' est transitif .
  9. , c'est-à-dire que l'opérateur '<' est irréflexif .
  10. , c'est-à-dire que l'ordre satisfait à la trichotomie .
  11. , c'est-à-dire que l'ordre est conservé sous ajout du même élément.
  12. , c'est-à-dire que l'ordre est conservé sous multiplication par le même élément positif.
  13. , c'est-à-dire étant donné deux éléments distincts, le plus grand est le plus petit plus un autre élément.
  14. , c'est-à-dire que zéro et un sont distincts et qu'il n'y a aucun élément entre eux. En d'autres termes, 0 est couvert par 1, ce qui suggère que les nombres naturels sont discrets.
  15. , c'est-à-dire que zéro est l'élément minimum.

La théorie définie par ces axiomes est connue sous le nom de PA ; la théorie PA est obtenue en ajoutant le schéma d'induction du premier ordre. Une propriété importante de PA est que toute structure satisfaisant cette théorie a un segment initial (ordonné par ) isomorphe à . Les éléments de ce segment sont appelés éléments standard , tandis que les autres éléments sont appelés éléments non standard .

Des modèles

Un modèle des axiomes de Peano est un triplet ( N , 0, S ) , où N est un ensemble (nécessairement infini), 0 N et S : NN satisfait les axiomes ci-dessus. Dedekind a prouvé dans son livre de 1888, La nature et la signification des nombres ( allemand : Was sind und was sollen die Zahlen ? , c'est-à-dire, « Quels sont les nombres et à quoi servent-ils ? ») que deux modèles des axiomes de Peano ( y compris l'axiome d'induction du second ordre) sont isomorphes . En particulier, étant donné deux modèles ( N A , 0 A , S A ) et ( N B , 0 B , S B ) des axiomes de Peano, il existe un unique homomorphisme f  : N AN B satisfaisant

et c'est une bijection . Cela signifie que les axiomes de Peano de second ordre sont catégoriques . Ce n'est cependant pas le cas de toute reformulation de premier ordre des axiomes de Peano.

Modèles ensemblistes

Les axiomes de Peano peuvent être dérivés des constructions théoriques des ensembles des nombres naturels et des axiomes de la théorie des ensembles tels que ZF . La construction standard des naturels, due à John von Neumann , part d'une définition de 0 comme l'ensemble vide, , et d'un opérateur s sur les ensembles définis comme :

L'ensemble des nombres naturels N est défini comme l'intersection de tous les ensembles fermés sous s qui contiennent l'ensemble vide. Chaque nombre naturel est égal (en tant qu'ensemble) à l'ensemble des nombres naturels inférieur à lui :

etc. L'ensemble N avec 0 et la fonction successeur s  : NN satisfait les axiomes de Peano.

L'arithmétique de Peano est équicohérente avec plusieurs systèmes faibles de la théorie des ensembles. Un de ces systèmes est ZFC avec l' axiome de l'infini remplacé par sa négation. Un autre système de ce type consiste en une théorie générale des ensembles ( extensionnalité , existence de l' ensemble vide et axiome d' adjonction ), augmentée d' un schéma d' axiome indiquant qu'une propriété valable pour l' ensemble vide et valable pour une adjonction chaque fois qu'elle est valable pour l' adjonction doit être valable pour tous les ensembles.

Interprétation en théorie des catégories

Les axiomes de Peano peuvent également être compris en utilisant la théorie des catégories . Soit C une catégorie avec l' objet terminal 1 C , et définissons la catégorie des systèmes unaires pointés , US 1 ( C ) comme suit :

  • Les objets de US 1 ( C ) sont des triplets ( X , 0 X , S X )X est un objet de C , et 0 X  : 1 CX et S X  : XX sont des C -morphismes.
  • Un morphisme φ  : ( X , 0 X , S X ) → ( Y , 0 Y , S Y ) est un C -morphisme φ  : XY avec φ 0 X = 0 Y et φ S X = S Y φ .

On dit alors que C satisfait les axiomes de Dedekind-Peano si US 1 ( C ) a un objet initial ; cet objet initial est connu sous le nom d' objet entier naturel en C . Si ( N , 0, S ) est cet objet initial, et ( X , 0 X , S X ) est tout autre objet, alors l'unique application u  : ( N , 0, S ) → ( X , 0 X , S X ) est tel que

C'est précisément la définition récursive de 0 X et S X .

Modèles non standard

Bien que les nombres naturels habituels satisfassent les axiomes de PA , il existe également d'autres modèles (appelés « modèles non standard ») ; le théorème de compacité implique que l'existence d'éléments non standard ne peut pas être exclue en logique du premier ordre. Le théorème ascendant de Löwenheim-Skolem montre qu'il existe des modèles non standard de PA de toutes les cardinalités infinies. Ce n'est pas le cas pour les axiomes de Peano originaux (de second ordre), qui n'ont qu'un seul modèle, à isomorphisme près. Cela illustre une façon dont le système du premier ordre PA est plus faible que les axiomes de Peano du deuxième ordre.

Lorsqu'elle est interprétée comme une preuve au sein d'une théorie des ensembles du premier ordre , telle que ZFC , la preuve de catégorisation de Dedekind pour PA montre que chaque modèle de théorie des ensembles a un modèle unique des axiomes de Peano, jusqu'à l'isomorphisme, qui intègre comme segment initial de tous d'autres modèles d'AP contenus dans ce modèle de théorie des ensembles. Dans le modèle standard de la théorie des ensembles, ce plus petit modèle de PA est le modèle standard de PA ; cependant, dans un modèle non standard de théorie des ensembles, il peut s'agir d'un modèle non standard de PA. Cette situation ne peut être évitée avec aucune formalisation du premier ordre de la théorie des ensembles.

Il est naturel de se demander si un modèle non standard comptable peut être explicitement construit. La réponse est affirmative car Skolem en 1933 a fourni une construction explicite d'un tel modèle non standard . D'autre part, le théorème de Tennenbaum , prouvé en 1959, montre qu'il n'y a pas de modèle non standard dénombrable de PA dans lequel l'opération d'addition ou de multiplication est calculable . Ce résultat montre qu'il est difficile d'être complètement explicite dans la description des opérations d'addition et de multiplication d'un modèle non standard dénombrable de PA. Il n'y a qu'un seul type de commande possible d'un modèle non standard comptable. Soit ω le type d'ordre des nombres naturels, ζ le type d'ordre des entiers et η le type d'ordre des rationnels, le type d'ordre de tout modèle non standard dénombrable de PA est ω + ζ · η , qui peut être visualisé comme une copie des nombres naturels suivi d'un ordre linéaire dense des copies des nombres entiers.

Débordement

Une coupe dans un modèle non standard M est un sous - ensemble non vide C de M de sorte que C est fermé vers le bas ( x < y , et yCxC ) et C est fermé sous successeur. Une coupe propre est une coupe qui est un sous-ensemble propre de M . Chaque modèle non standard a de nombreuses coupes appropriées, dont une qui correspond aux nombres naturels standard. Cependant, le schéma d'induction dans l'arithmétique de Peano empêche toute coupe appropriée d'être définissable. Le lemme du débordement, prouvé pour la première fois par Abraham Robinson, formalise ce fait.

Lemme de débordement  —  Soit M un modèle non standard de PA et C une coupe propre de M . Supposons que soit un tuple d'éléments de M et une formule dans le langage de l'arithmétique telle que

pour tout bC .

Alors il y a un c dans M qui est plus grand que tout élément de C tel que

Cohérence

Lorsque les axiomes de Peano ont été proposés pour la première fois, Bertrand Russell et d'autres ont convenu que ces axiomes définissaient implicitement ce que nous entendons par un « nombre naturel ». Henri Poincaré était plus prudent, disant qu'ils ne définissaient les nombres naturels que s'ils étaient cohérents ; s'il existe une preuve qui part uniquement de ces axiomes et dérive une contradiction telle que 0 = 1, alors les axiomes sont incohérents et ne définissent rien. En 1900, David Hilbert a posé le problème de prouver leur cohérence en utilisant uniquement des méthodes finiistes comme le deuxième de ses vingt-trois problèmes . En 1931, Kurt Gödel a prouvé son deuxième théorème d'incomplétude , qui montre qu'une telle preuve de cohérence ne peut pas être formalisée dans l'arithmétique de Peano elle-même.

Bien qu'il soit largement affirmé que le théorème de Gödel exclut la possibilité d'une preuve de cohérence finiiste pour l'arithmétique de Peano, cela dépend exactement de ce que l'on entend par une preuve finiiste. Gödel lui-même a souligné la possibilité de donner une preuve de cohérence finiiste de l'arithmétique de Peano ou des systèmes plus forts en utilisant des méthodes finiistes qui ne sont pas formalisables dans l'arithmétique de Peano, et en 1958, Gödel a publié une méthode pour prouver la cohérence de l'arithmétique en utilisant la théorie des types . En 1936, Gerhard Gentzen a donné une preuve de la cohérence des axiomes de Peano, en utilisant l'induction transfinie jusqu'à un ordinal appelé ε 0 . Gentzen a expliqué : « Le but du présent article est de prouver la cohérence de la théorie des nombres élémentaires ou, plutôt, de réduire la question de la cohérence à certains principes fondamentaux ». La preuve de Gentzen est sans doute finiiste, puisque l'ordinal transfini 0 peut être codé en termes d'objets finis (par exemple, comme une machine de Turing décrivant un ordre approprié sur les entiers, ou plus abstraitement comme consistant en les arbres finis , convenablement ordonnés linéairement) . Que la preuve de Gentzen réponde ou non aux exigences envisagées par Hilbert n'est pas clair : il n'y a pas de définition généralement acceptée de ce que l'on entend exactement par une preuve finiiste, et Hilbert lui-même n'a jamais donné de définition précise.

La grande majorité des mathématiciens contemporains croient que les axiomes de Peano sont cohérents, s'appuyant soit sur l'intuition, soit sur l'acceptation d'une preuve de cohérence telle que la preuve de Gentzen . Un petit nombre de philosophes et de mathématiciens, dont certains prônent également l' ultrafinitisme , rejettent les axiomes de Peano car accepter les axiomes revient à accepter la collection infinie des nombres naturels. En particulier, l'addition (y compris la fonction successeur) et la multiplication sont supposées être totales . Curieusement, il existe des théories d'auto-vérification qui sont similaires à PA mais ont la soustraction et la division au lieu de l'addition et de la multiplication, qui sont axiomatisées de manière à éviter de prouver des phrases qui correspondent à la totalité de l'addition et de la multiplication, mais qui sont toujours capables pour prouver tous les vrais théorèmes de PA, et pourtant peut être étendu à une théorie cohérente qui prouve sa propre cohérence (énoncée comme la non-existence d'une preuve de style Hilbert de "0=1").

Voir également

Remarques

Les références

Citations

Sources

Lectures complémentaires

Liens externes

Cet article incorpore du matériel de PA sur PlanetMath , qui est sous licence Creative Commons Attribution/Share-Alike License .