Axiomes de Peano

Apprendre encore plus Il a été suggéré que les preuves impliquant l’addition de Nombres naturels soient fusionnées dans cet article. ( Discuter ) Proposé depuis janvier 2022.

En logique mathématique , les axiomes de Peano , également connus sous le nom d’ axiomes de Dedekind-Peano ou de 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 inchangés dans un certain nombre d’ investigations métamathématiques , y compris la recherche sur des 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’aux travaux 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 fondamentaux sur l’ opération successeur et l’induction . ^[1] En 1881, Charles Sanders Peirce a fourni une axiomatisation de l’arithmétique des Nombres naturels. ^[2] 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 la forme d’un 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 suivantes 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». ^[3] Les trois axiomes suivants sont des déclarations du premier ordre sur les Nombres naturels exprimant les propriétés fondamentales de l’opération successeur. Le neuvième axiome final est un énoncé de second ordre du principe d’induction mathématique sur les Nombres naturels, ce qui rend cette formulation proche de l’ arithmétique de second ordre . Un système de premier ordre plus faible appelé arithmétique de Peanoest 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 historique du second ordre

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 qu’il ait été la genèse de la notation moderne pour l’appartenance à un ensemble (∈, qui vient du ε de Peano) et l’ implication (⊃, qui vient du ‘ C’.) Peano a maintenu 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. ^[4] Peano n’était pas au courant du travail de Frege et a recréé indépendamment son appareil logique basé sur le travail deBoole et Schroder . ^[5]

Les axiomes de Peano définissent les propriétés arithmétiques des Nombres naturels , généralement représentés comme un ensemble N ou N . {displaystyle mathbb{N} .} Les symboles non logiques pour les axiomes consistent en un symbole de constante 0 et un symbole de fonction unaire S .

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

1. 0 est un nombre naturel.

La formulation originale de Peano des axiomes utilisait 1 au lieu de 0 comme “premier” nombre naturel, ^[6] tandis que les axiomes de Formulario mathematico incluent zéro. ^[7]

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. ^[5]

1. Pour tout nombre naturel x , x = x . Autrement dit, l’égalité est réflexive .
2. Pour tous les Nombres naturels x et y , si x = y , alors y = x . Autrement dit, l’égalité est symétrique .
3. Pour tous les Nombres naturels x , y et z , si x = y et y = z , alors x = z . Autrement dit, l’égalité est transitive .
4. Pour tout a et b , si b est un entier naturel et a = b , alors a est aussi un entier naturel. Autrement dit, 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 nombre naturel n , S ( n ) est un nombre naturel. Autrement dit, 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 ) . Autrement dit, S est une injection .
3. Pour tout nombre naturel n , S ( n ) = 0 est faux. Autrement dit, il n’y a pas de nombre naturel dont le successeur est 0.

La chaîne de dominos clairs, en commençant par le plus proche, peut représenter N , ^{[8] [9]} cependant, les axiomes 1–8 sont également satisfaits par l’ensemble de tous les dominos clairs et sombres. ^{[note 1]} Le 9ème axiome ( induction ) limite N à la chaîne de pièces légères (“pas de bric-à-brac”) car seuls les dominos légers tomberont lorsque le plus proche est renversé. ^[dix]

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. les Nombres naturels é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.

La notion intuitive que chaque nombre naturel peut être obtenu en appliquant le 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 prédicat unaire tel que :
   • φ (0) est vrai, et
   • pour tout 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 indiqué dans la section § L’arithmétique de Peano comme théorie du premier ordre ci- dessous.

Définition des opérations et des relations arithmétiques

Si nous utilisons l’Axiome d’induction du second ordre, il est possible de définir l’ addition , la multiplication et l’ordre total (linéaire) sur N directement à l’aide des axiomes. Cependant, avec l’induction du premier ordre, ce n’est pas possible ^{[ la citation nécessaire ]} et l’addition et la multiplication sont souvent ajoutées comme axiomes. 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 étant uniques en utilisant les axiomes de Peano.

Une addition

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

un + 0 = un , (1) un + S ( b ) = S ( a + b ) . (2) {displaystyle {begin{aligned}a+0&=a,&{textrm {(1)}}\a+S(b)&=S(a+b).&{textrm {(2) }}end{aligné}}}

Par example:

a + 1 = a + S ( 0 ) by definition = S ( a + 0 ) using (2) = S ( a ) , using (1) a + 2 = a + S ( 1 ) by definition = S ( a + 1 ) using (2) = S ( S ( a ) ) using a + 1 = S ( a ) a + 3 = a + S ( 2 ) by definition = S ( a + 2 ) using (2) = S ( S ( S ( a ) ) ) using a + 2 = S ( S ( a ) ) etc. {displaystyle {begin{aligned}a+1&=a+S(0)&{mbox{by definition}}\&=S(a+0)&{mbox{using (2)}} &=S(a),&{mbox{utilisant (1)}}\\a+2&=a+S(1)&{mbox{par définition}}\&=S(a+ 1)&{mbox{en utilisant (2)}}\&=S(S(a))&{mbox{en utilisant }}a+1=S(a)\\a+3&=a+ S(2)&{mbox{par définition}}\&=S(a+2)&{mbox{utilisant (2)}}\&=S(S(S(a)))&{ mbox{using }}a+2=S(S(a))\{text{etc.}}&\end{aligned}}}

La structure ( N , +) est un monoïde Commutatif d’élément d’identité 0. ( N , +) est aussi un magma annulatif , et donc plongeable dans un groupe . Le plus petit groupe incorporant N est les nombres 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:

a ⋅ 0 = 0 , a ⋅ S ( b ) = a + ( a ⋅ b ) . {displaystyle {begin{aligned}acdot 0&=0,\acdot S(b)&=a+(acdot b).end{aligned}}}

Il est facile de voir que S ( 0 ) {displaystyle S(0)} (ou “1”, dans le langage familier de la représentation décimale ) est l’ identité multiplicative à droite :

a ⋅ S ( 0 ) = a + ( a ⋅ 0 ) = a + 0 = a {displaystyle acdot S(0)=a+(acdot 0)=a+0=a}

Montrer que S ( 0 ) {displaystyle S(0)} est également l’identité multiplicative à gauche nécessite l’Axiome d’induction en raison de la façon dont la multiplication est définie :

• S ( 0 ) {displaystyle S(0)} est l’identité à gauche de 0 : S ( 0 ) ⋅ 0 = 0 {displaystyle S(0)cdot 0=0} .
• Si S ( 0 ) {displaystyle S(0)} est l’identité de gauche de a {displaystyle a} (C’est S ( 0 ) ⋅ a = a {displaystyle S(0)cdot a=a} ), alors S ( 0 ) {displaystyle S(0)} est aussi l’identité gauche de S ( a ) {displaystyle S(a)} : S ( 0 ) ⋅ S ( a ) = S ( 0 ) + S ( 0 ) ⋅ a = S ( 0 ) + a = a + S ( 0 ) = S ( a + 0 ) = S ( a ) {displaystyle S(0)cdot S(a)=S(0)+S(0)cdot a=S(0)+a=a+S(0)=S(a+0)=S( un)} .

Donc, par l’Axiome d’induction S ( 0 ) {displaystyle S(0)} 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 :

a ⋅ ( b + c ) = ( a ⋅ b ) + ( a ⋅ c ) {displaystyle acdot (b+c)=(acdot b)+(acdot c)} .

Ainsi, ( N , + , 0 , ⋅ , S ( 0 ) ) {displaystyle (mathbb {N} ,+,0,cdot ,S(0))} 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 , b ∈ N , a ≤ b si et seulement s’il existe un c ∈ N tel que a + c = b .

Cette relation est stable par addition et multiplication : pour un , b , c ∈ N {displaystyle a,b,cin mathbb {N} } , si a ≤ b , alors :

• a + c ≤ b + c , et
• une · c ≤ b · c .

Ainsi, la structure ( N , +, ·, 1, 0, ≤) est un semi- anneau ordonné ; car il n’y a pas de nombre 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 vrai, et
• pour tout n , k ∈ N , si k ≤ n implique que φ ( k ) est vrai, alors φ ( S ( n )) est vrai,

alors pour tout n ∈ N , φ ( 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 au raisonnement sur l’ordre ≤. Par exemple, pour montrer que les naturels sont bien ordonnés – chaque sous- ensemble non vide de N a un plus petit élément – on peut raisonner comme suit. Soit un X ⊆ N non vide donné et supposons que X n’a ​​pas de moindre élément.

• Puisque 0 est le plus petit élément de N , il faut que 0 ∉ X .
• Pour tout n ∈ N , supposons que pour tout k ≤ n , k ∉ X . Alors S ( n ) ∉ X , car sinon ce serait le plus petit élément de X .

Ainsi, par le principe d’induction forte, pour tout n ∈ N , n ∉ X . Ainsi, X ∩ N = ∅ , ce qui contredit X étant un sous-ensemble non vide de N . Ainsi X a un plus petit élément.

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 : N → N 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 quelconques 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 _A → N _B satisfaisant

f ( 0 A ) = 0 B f ( S A ( n ) ) = S B ( f ( n ) ) {displaystyle {begin{aligné}f(0_{A})&=0_{B}\f(S_{A}(n))&=S_{B}(f(n))end{aligné }}}

et c’est une bijection . Cela signifie que les axiomes de Peano du second ordre sont catégoriques . (Ce n’est pas le cas avec toute reformulation de premier ordre des axiomes de Peano, ci-dessous.)

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 . ^[11] La construction standard des naturels, due à John von Neumann , part d’une définition de 0 comme ensemble vide, ∅, et d’un opérateur s sur des ensembles définis comme :

s ( a ) = a ∪ { a } {displaystyle s(a)=acup {a}}

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 qui lui sont inférieurs :

0 = ∅ 1 = s ( 0 ) = s ( ∅ ) = ∅ ∪ { ∅ } = { ∅ } = { 0 } 2 = s ( 1 ) = s ( { 0 } ) = { 0 } ∪ { { 0 } } = { 0 , { 0 } } = { 0 , 1 } 3 = s ( 2 ) = s ( { 0 , 1 } ) = { 0 , 1 } ∪ { { 0 , 1 } } = { 0 , 1 , { 0 , 1 } } = { 0 , 1 , 2 } {displaystyle {begin{aligned}0&=emptyset \1&=s(0)=s(emptyset )=emptyset cup {emptyset }={emptyset }={0 }\2&=s(1)=s({0})={0}cup {{0}}={0,{0}}={ 0,1}\3&=s(2)=s({0,1})={0,1}cup {{0,1}}={0, 1,{0,1}}={0,1,2}end{aligné}}}

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

L’arithmétique de Peano est équicohérente avec plusieurs systèmes faibles de la théorie des ensembles. ^[12] Un tel système est ZFC avec l’ axiome d’infini remplacé par sa négation. Un autre système de ce type consiste en la 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é qui vaut pour l’ensemble vide et vaut pour une adjonction chaque fois qu’elle vaut pour l’adjonction doit tenir 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 d’ Objet terminal 1 _C , et définissons la catégorie des systèmes unaires pointés , US ₁ ( C ) comme suit :

• Les objets de US ₁ ( C ) sont des triplets ( X , 0 _X , S _X ) où X est un objet de C , et 0 _X : 1 _C → X et S _X : X → X sont des C -morphismes.
• Un morphisme φ : ( X , 0 _X , S _X ) → ( Y , 0 _Y , S _Y ) est un C -morphisme φ : X → Y avec φ 0 _X = 0 _Y et φ S _X = S _Y φ .

On dit alors que C satisfait les axiomes de Dedekind–Peano si US ₁ ( C ) a un objet initial ; cet objet initial est connu sous le nom d’ objet de nombre naturel en C . Si ( N , 0, S ) est cet objet initial, et ( X , 0 _X , S _X ) est n’importe quel autre objet, alors l’unique application u : ( N , 0, S ) → ( X , 0 _X , S _X ) est telle que

tu ( 0 ) = 0 X , tu ( S X ) = S X ( tu X ) . {displaystyle {begin{aligned}u(0)&=0_{X},\u(Sx)&=S_{X}(ux).end{aligned}}}

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

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”. ^[13] 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. ^[14] En 1900, David Hilbert a posé le problème de prouver leur cohérence en utilisant uniquement des méthodes finitistes comme le deuxième de ses vingt-trois problèmes . ^[15] En 1931, Kurt Godela 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. ^[16]

Bien qu’il soit largement affirmé que le théorème de Gödel exclut la possibilité d’une Preuve de cohérence finitiste pour l’arithmétique de Peano, cela dépend exactement de ce que l’on entend par une preuve finitiste. Gödel lui-même a souligné la possibilité de donner une Preuve de cohérence finitiste de l’arithmétique de Peano ou de systèmes plus forts en utilisant des méthodes finitistes 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 à l’aide de la théorie des types . ^[17] En 1936, Gerhard Gentzen a donné une preuve de la consistance des axiomes de Peano, en utilisant l’induction transfinie jusqu’à un ordinal appelé ε ₀ . ^[18]Gentzen a expliqué: “Le but du présent article est de prouver la cohérence de la théorie élémentaire des nombres ou, plutôt, de réduire la question de la cohérence à certains principes fondamentaux”. La preuve de Gentzen est sans doute finitiste, puisque l’ordinal transfini ε ₀ 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 constitué des 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 finitiste, 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 de 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érificationqui sont similaires à PA mais ont une soustraction et une division au lieu d’une addition et d’une 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 de prouver que toutes sont vraies Π 1 {style d’affichage Pi _{1}} 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”). ^[19]

L’arithmétique de Peano comme théorie du premier ordre

Tous les axiomes de Peano à l’exception du neuvième axiome (l’Axiome d’induction) sont des énoncés en logique du premier ordre . ^[20] 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 ci-dessus est du second ordre , puisqu’il quantifie sur des prédicats (de manière équivalente, des ensembles de Nombres naturels plutôt que des Nombres naturels). Comme alternative, on peut considérer un schéma d’axiome d’induction du 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. ^[21]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 d’axiomes suivante (ainsi que les axiomes d’égalité habituels), qui contient six des sept axiomes de l’arithmétique de Robinson , est suffisante à cette fin : ^[22]

• ∀ X ( 0 ≠ S ( x ) ) {displaystyle forall x (0neq S(x))}
• ∀ x , y ( S ( x ) = S ( y ) ⇒ x = y ) {displaystyle forall x,y (S(x)=S(y)Rightarrow x=y)}
• ∀ x ( x + 0 = x ) {displaystyle forall x (x+0=x)}
• ∀ x , y ( x + S ( y ) = S ( x + y ) ) {displaystyle forall x,y (x+S(y)=S(x+y))}
• ∀ x ( x ⋅ 0 = 0 ) {displaystyle forall x (xcdot 0=0)}
• ∀ x , y ( x ⋅ S ( y ) = x ⋅ y + x ) {displaystyle forall x,y (xcdot S(y)=xcdot y+x)}

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 récursivement énumérable d’ axiomes . Pour chaque formule φ ( x , y ₁ , …, y _k ) dans le langage de l’arithmétique de Peano, l’ Axiome d’induction du premier ordre pour φ est la phrase

∀ y ̄ ( ( φ ( 0 , y ̄ ) ∧ ∀ x ( φ ( x , y ̄ ) ⇒ φ ( S ( x ) , y ̄ ) ) ) ⇒ ∀ x φ ( x , y ̄ ) ) {displaystyle forall {bar {y}}{Bigg (}{bigg (}varphi (0,{bar {y}})land forall x{Big (}varphi (x, {bar {y}})Rightarrow varphi (S(x),{bar {y}}){Big )}{bigg )}Rightarrow forall xvarphi (x,{bar { y}}){Bigg )}}

où y ̄ {displaystyle {bar {y}}} est une abréviation pour y ₁ ,…, y _k . Le schéma d’induction du premier ordre inclut chaque instance de l’Axiome d’induction du premier ordre ; c’est-à-dire qu’il inclut l’Axiome d’induction pour chaque 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. ^[23]

1. ∀ x , y , z ( ( x + y ) + z = x + ( y + z ) ) {displaystyle forall x,y,z ((x+y)+z=x+(y+z))} , c’est-à-dire que l’addition est associative .
2. ∀ x , y ( x + y = y + x ) {displaystyle forall x,y (x+y=y+x)} , c’est-à-dire que l’addition est commutative .
3. ∀ x , y , z ( ( x ⋅ y ) ⋅ z = x ⋅ ( y ⋅ z ) ) {displaystyle forall x,y,z ((xcdot y)cdot z=xcdot (ycdot z))} , c’est-à-dire que la multiplication est associative.
4. ∀ x , y ( x ⋅ y = y ⋅ x ) {displaystyle forall x,y (xcdot y=ycdot x)} , c’est-à-dire que la multiplication est commutative.
5. ∀ x , y , z ( x ⋅ ( y + z ) = ( x ⋅ y ) + ( x ⋅ z ) ) {displaystyle forall x,y,z (xcdot (y+z)=(xcdot y)+(xcdot z))} , c’est-à-dire que la multiplication se répartit sur l’addition.
6. ∀ x ( x + 0 = x ∧ x ⋅ 0 = 0 ) {displaystyle forall x (x+0=xland xcdot 0=0)} , c’est-à-dire que zéro est une identité pour l’addition, et un élément absorbant pour la multiplication (en fait superflu ^{[note 2]} ).
7. ∀ x ( x ⋅ 1 = X ) {displaystyle forall x (xcdot 1=x)} , c’est-à-dire, un est une identité pour la multiplication.
8. ∀ X , y , z ( X < y ∧ y < z ⇒ X < z ) {displaystyle forall x,y,z (x<yland y<zRightarrow x<z)} , c’est-à-dire que l’opérateur ‘<‘ est transitif .
9. ∀ X ( ¬ ( X < X ) ) {displaystyle forall x (neg (x<x))} , c’est-à-dire que l’opérateur ‘<‘ est irréflexif .
10. ∀ X , y ( X < y ∨ X = y ∨ y < X ) {displaystyle forall x,y (x<ylor x=ylor y<x)} , c’est-à-dire que l’ordre satisfait la trichotomie .
11. ∀ X , y , z ( X < y ⇒ X + z < y + z ) {displaystyle forall x,y,z (x<yRightarrow x+z<y+z)} , c’est-à-dire que l’ordre est conservé sous ajout d’un même élément.
12. ∀ X , y , z ( 0 < z ∧ X < y ⇒ X ⋅ z < y ⋅ z ) {displaystyle forall x,y,z (0<zland x<yRightarrow xcdot z<ycdot z)} , c’est-à-dire que l’ordre est conservé sous multiplication par le même élément positif.
13. ∀ X , y ( X < y ⇒ ∃ z ( X + z = y ) ) {displaystyle forall x,y (x<yRightarrow exists z (x+z=y))} , c’est-à-dire étant donné deux éléments distincts, le plus grand est le plus petit plus un autre élément.
14. 0 < 1 ∧ ∀ X ( X > 0 ⇒ X ≥ 1 ) {displaystyle 0<1land forall x (x>0Rightarrow xgeq 1)} , 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. ∀ X ( X ≥ 0 ) {displaystyle forall x (xgeq 0)} , c’est-à-dire que zéro est l’élément minimum.

La théorie définie par ces axiomes est appelée 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 M {displaystyle M} satisfaisant cette théorie a un segment initial (ordonné par ≤ {displaystyle leq} ) isomorphe à N {displaystyle mathbb {N} } . 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 .

Indécidabilité et incomplétude

Selon les théorèmes d’incomplétude de Gödel , la théorie de PA (si elle est cohérente) est incomplète. Par conséquent, il existe des phrases de logique du premier ordre (FOL) qui sont vraies dans le modèle standard de PA mais qui ne sont pas une conséquence de l’axiomatisation FOL. Une incomplétude essentielle apparaît déjà pour les théories avec des axiomes plus faibles, comme l’ arithmétique de Robinson .

Étroitement lié au résultat d’incomplétude ci-dessus (via le théorème de complétude de Gödel pour FOL), il s’ensuit qu’il n’y a pas d’ algorithme pour décider si une phrase FOL donnée est une conséquence d’une axiomatisation de premier ordre de l’arithmétique de Peano ou non. PA est donc un exemple de théorie indécidable . L’indécidabilité survient déjà pour les phrases existentielles de PA , en raison de la réponse négative au dixième problème de Hilbert , dont la preuve implique que tous les ensembles dénombrables calculables sont des ensembles diophantiens , et donc définissables par des formules existentiellement quantifiées (à variables libres) de PA . Formules de PAavec un rang de quantificateur plus élevé (plus d’alternances de quantificateurs) que les formules existentielles sont plus expressives et définissent des ensembles dans les niveaux supérieurs de la hiérarchie arithmétique .

Modèles non standard

Bien que les Nombres naturels usuels 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 être exclue en logique du premier ordre. ^[24] 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 (du second ordre), qui n’ont qu’un seul modèle, à isomorphisme près. ^[25] Ceci illustre une façon dont le système de premier ordre PA est plus faible que les axiomes de Peano de second 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égoricité 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 un 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 de premier ordre de la théorie des ensembles.

Il est naturel de se demander si un modèle dénombrable non standard 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 dénombrable non standard de PA dans lequel l’opération d’addition ou de multiplication est calculable . ^[26] 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 dénombrable non standard de PA. Il n’y a qu’un seul type d’ordre possible d’un modèle non standard comptable. Soit ω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 dénombrable non standard de PA est ω + ζ · η , qui peut être visualisé comme une copie des Nombres naturels suivie d’un ordre linéaire dense de copies des nombres entiers.

Débordement

Une coupe dans un modèle non standard M est un sous-ensemble non vide C de M tel que C est fermé vers le bas ( x < y et y ∈ C ⇒ x ∈ C ) 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 ^[27] — Soit M un modèle non standard de PA et soit C une coupe propre de M . Supposer que un ̄ {displaystyle {bar {a}}} est un tuple d’éléments de M et φ ( x , a ̄ ) {displaystyle phi (x,{bar {a}})} est une formule dans le langage de l’arithmétique telle que

M ⊨ φ ( b , a ̄ ) {displaystyle MvDash phi (b,{bar {a}})} pour tout b ∈ C .

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

M ⊨ φ ( c , a ̄ ) . {displaystyle MvDash phi (c,{bar {a}}).}

Voir également

• Portail de la philosophie
• Portail des mathématiques

• Fondements des mathématiques
• Théorème de Frege
• Théorème de Goodstein
• Néo-logicisme
• Modèle non standard d’arithmétique
• Théorème de Paris-Harrington
• Arithmétique de Presburger
• Arithmétique de Robinson
• Arithmétique du second ordre
• Théorie typographique des nombres

Remarques

1. ^ L’ensemble non contigu satisfait l’axiome 1 car il a un élément 0, 2–5 car il n’affecte pas les relations d’égalité, 6 et 8 car toutes les pièces ont un successeur, à l’exception de l’élément zéro et de l’axiome 7 car il n’y a pas deux dominos renverser , ou sont renversés par, la même pièce.
2. ^ ” ∀ x ( x ⋅ 0 = 0 ) {displaystyle forall x (xcdot 0=0)} ” peut être prouvé à partir des autres axiomes (en logique du premier ordre) comme suit. Premièrement, x ⋅ 0 + x ⋅ 0 = x ⋅ ( 0 + 0 ) = x ⋅ 0 = x ⋅ 0 + 0 {displaystyle xcdot 0+xcdot 0=xcdot (0+0)=xcdot 0=xcdot 0+0} par distributivité et identité additive. Deuxièmement, x ⋅ 0 = 0 ∨ x ⋅ 0 > 0 {displaystyle xcdot 0=0lor xcdot 0>0} par l’axiome 15. Si x ⋅ 0 > 0 {displaystyle xcdot 0>0} alors x ⋅ 0 + x ⋅ 0 > x ⋅ 0 + 0 {displaystyle xcdot 0+xcdot 0>xcdot 0+0} par addition du même élément et commutativité, et donc x ⋅ 0 + 0 > x ⋅ 0 + 0 {displaystyle xcdot 0+0>xcdot 0+0} par substitution, contredisant l’irréflexivité. Donc ça doit être ça x ⋅ 0 = 0 {displaystyle xcdot 0=0} .

Références

Citations

1. ^ Grassmann 1861 .
2. ^ Peirce 1881 , Boucliers 1997
3. ^ van Heijenoort 1967 , p. 94.
4. ^ van Heijenoort 1967 , p. 2.
5. ^ ^{un b} van Heijenoort 1967 , p. 83.
6. ^ Peano 1889 , p. 1.
7. ^ Peano 1908 , p. 27.
8. ^ Matt DeVos, induction mathématique , Université Simon Fraser
9. ^ Gerardo con Diaz, Mathematical Induction Archivé le 2 mai 2013 à la Wayback Machine , Université de Harvard
10. ^ José Meseguer et Joseph A. Goguen (décembre 1986). ” Initialité, induction et contputabilité “. Dans Maurice Nivat et John C. Reynolds (éd.). Méthodes algébriques en sémantique (PDF) . Cambridge : Cambridge University Press. p. 459–541. ISBN 9780521267939.Ici : sect.2.3, p.464 et sect.4.1, p.471
11. ^ Suppes 1960 , Hatcher 2014
12. ^ Tarski & Givant 1987 , Section 7.6.
13. ^ Fritz 1952 , p. 137
    Une illustration de « l’interprétation » est la propre définition de Russell du « nombre cardinal ». Le système non interprété dans ce cas est les axiomes de Peano pour le système des nombres, dont les trois idées primitives et les cinq axiomes, pensait Peano, étaient suffisants pour permettre de dériver toutes les propriétés du système des Nombres naturels. En fait, soutient Russell, les axiomes de Peano définissent toute progression de la forme x 0 , x 1 , x 2 , … , x n , … {displaystyle x_{0},x_{1},x_{2},ldots ,x_{n},ldots } dont la série des Nombres naturels est un exemple.
14. ^ Gris 2013 , p. 133
    Alors Poincaré s’est tourné pour voir si le logicisme pouvait générer l’arithmétique, plus précisément, l’arithmétique des ordinaux. Couturat, dit Poincaré, avait accepté les axiomes de Peano comme définition d’un nombre. Mais cela ne suffira pas. On ne peut pas montrer que les axiomes sont exempts de contradiction en en trouvant des exemples, et toute tentative de montrer qu’ils étaient exempts de contradiction en examinant la totalité de leurs implications nécessiterait le principe même d’induction mathématique que Couturat croyait qu’ils impliquaient. Car (dans un autre passage extrait de S&M) soit on supposait le principe pour le prouver, ce qui prouverait seulement que s’il est vrai il n’est pas contradictoire, ce qui ne dit rien ; ou on a utilisé le principe sous une autre forme que celle énoncée, auquel cas on doit montrer que le nombre d’étapes dans une’
15. ^ Hibert 1902 .
16. ^ Godel 1931 .
17. ^ Godel 1958
18. ^ Gentzen 1936
19. ^ Willard 2001 .
20. ^ Partée, Ter Meulen & Wall 2012 , p. 215.
21. ^ Harsanyi (1983) .
22. ^ Mendelson 1997 , p. 155. sfn error: no target: CITEREFMendelson1997 (help)
23. ^ Kaye 1991 , p. 16-18.
24. ^ Hermes 1973 , VI.4.3, présentant un théorème de Thoralf Skolem
25. ^ Hermès 1973 , VI.3.1.
26. ^ Kaye 1991 , section 11.3.
27. ^ Kaye 1991 , pp. 70ff..

Sources

• Davis, Martin (1974). Calculabilité. Notes de Barry Jacobs . Institut Courant des sciences mathématiques , Université de New York .
• Dedekind, Richard (1888). Was sind und was sollen die Zahlen? [ Quels sont et quels devraient être les chiffres ? ] (PDF) . Voireg . Récupéré le 4 juillet 2016 .
  • Deux traductions anglaises :
    • Beman, Wooster, Aspérule (1901). Essais sur la théorie des nombres (PDF) . Douvres .
    • En ligneEwald, William B. (1996). De Kant à Hilbert : un livre source sur les fondements des mathématiques . Presse universitaire d’Oxford . pp. 787–832. ISBN 9780198532712.
• Fritz, Charles A., Jr. (1952). La construction du monde extérieur de Bertrand Russell . New York, Humanities Press.
• Gentzen, Gerhard (1936). Réimprimé en traduction anglaise dans ses œuvres rassemblées de 1969 , ME Szabo, éd. “Die Widerspruchsfreiheit der reinen Zahlentheorie”. Annales Mathématiques . 112 : 132–213. doi : 10.1007/bf01565428 . S2CID 122719892 .
• Godel, Kurt (1931). Voir On Formally Undecidable Propositions of Principia Mathematica and Related Systems pour plus de détails sur les traductions en anglais. “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I” (PDF) . Monatshefte für Mathematik . 38 : 173–198. doi : 10.1007/bf01700692 . S2CID 197663120 . Archivé de l’original (PDF) le 2018-04-11 . Récupéré le 31/10/2013 .
• Godel, Kurt (1958). Réimprimé en traduction anglaise en 1990. Gödel’s Collected Works , Vol II. Solomon Feferman et al., éd. “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes” . Dialectique . Presse universitaire d’Oxford . 12 (3–4) : 280–287. doi : 10.1111/j.1746-8361.1958.tb01464.x .
• Grassmann, Hermann (1861). “Lehrbuch der Arithmetik” [Un tutoriel en arithmétique] (PDF) . Enslin. {{cite journal}}: Cite journal requires |journal= (help)
• Gray, Jérémy (2013). “L’essayiste” . Henri Poincaré : Une biographie scientifique . Presse de l’Université de Princeton . p. 133. ISBN 978-0-691-15271-4.
• En ligneHarsanyi, John C. (1983). “Les mathématiques, les faits empiriques et la nécessité logique”. Erkenntniss . 19 : 167–192. doi : 10.1007/978-94-015-7676-5_8 . ISBN 978-90-481-8389-0.
• Hatcher, William S. (2014) [1982]. Les fondements logiques des mathématiques . Elsevier. ISBN 978-1-4831-8963-5.Dérive les axiomes de Peano (appelés S ) de plusieurs théories axiomatiques des ensembles et de la théorie des catégories .
• Hermès, Hans (1973). Introduction à la logique mathématique . Hochschultext. Springer. ISBN 3540058192. ISSN 1431-4657 .
• Hilbert, David (1902). Traduit par Winton, Maby. “Mathematische Probleme” [Problèmes mathématiques]. Bulletin de l’American Mathematical Society . 8 (10): 437–479. doi : 10.1090/s0002-9904-1902-00923-3 .
• Kaye, Richard (1991). Modèles d’arithmétique de Peano . Presse universitaire d’Oxford . ISBN 0-19-853213-X.
• Landau, Edmond (1965). Grundlagen Der Analyse . Dérive les systèmes numériques de base des axiomes de Peano. Vocabulaire anglais/allemand inclus. Édition AMS Chelsea . ISBN 978-0-8284-0141-8.
• Mendelson, Elliott (2009). Introduction à la logique mathématique (5e éd.). Taylor et François. ISBN 9781584888765.
• Partée, Barbara; Ter Meulen, Alice ; Mur, Robert (2012). Méthodes mathématiques en linguistique . Springer. ISBN 978-94-009-2213-6.
• Peirce, CS (1881). “Sur la logique du nombre” . Journal américain de mathématiques . 4 (1): 85–95. doi : 10.2307/2369151 . JSTOR 2369151 . MR 1507856 .
• Boucliers, Paul (1997). “3. L’axiomatisation de Peirce de l’arithmétique” . Dans Houser, Nathan; Roberts, Don D.; Van Evra, James (éd.). Études sur la logique de Charles Sanders Peirce . Presse universitaire de l’Indiana. p. 43–52. ISBN 0-253-33020-3.
• Suppes, Patrick (1960). Théorie axiomatique des ensembles . Douvres . ISBN 0-486-61630-4.Dérive les axiomes de Peano de ZFC
• Tarski, Alfred ; Givant, Steven (1987). Une formalisation de la théorie des ensembles sans variables . Publications du colloque AMS. Vol. 41. Société mathématique américaine . ISBN 978-0-8218-1041-5.
• van Heijenoort, Jean (1967). De Frege à Godel: Un livre source en logique mathématique, 1879–1931 . Presse universitaire de Harvard. ISBN 9780674324497.
  • Contient les traductions des deux articles suivants, avec de précieux commentaires :
    • Dedekind, Richard (1890). Lettre à Keferstein . Dans. 100, il réaffirme et défend ses axiomes de 1888. pp. 98–103.
    • Peano, Giuseppe (1889). Arithmetices principia, nova methodo exposita [ Les principes de l’arithmétique, présentés par une nouvelle méthode ]. Un extrait du traité où Peano a présenté pour la première fois ses axiomes et défini de manière récursive les opérations arithmétiques. Frères Bocca. p. 83–97.
• Peano, Giuseppe (1908). Formulario Mathematico (éd. V). Turin, Bocca frères, Ch. Clausen. p. 27.
• Willard, Dan E. (2001). “Systèmes d’axiome autovérificateurs, théorème d’incomplétude et principes de réflexion associés” (PDF) . Le Journal de la logique symbolique . 66 (2): 536–596. doi : 10.2307/2695030 . JSTOR 2695030 . M. 1833464 .S2CID 2822314 .

Lectures complémentaires

• En ligneBuss, Samuel R. (1998). “Chapitre II: Théorie de la preuve du premier ordre de l’arithmétique”. Dans Buss, Samuel R. (éd.). Manuel de théorie de la preuve . New York : Elsevier. ISBN 0-444-89840-9.
• Takeuti, Gaisi (2013).Théorie de la preuve (deuxième éd.). Minéola, New York. ISBN 978-0486490731.
• Mendelson, Elliott (2009).Introduction à la logique mathématique (5e éd.). Taylor et François. ISBN 9781584888765.
• Raymond M. Smullyan (19 septembre 2013). Le livre de puzzle Godelian: Puzzles, paradoxes et preuves . Société de messagerie.ISBN 978-0-486-49705-1.

Liens externes

• Murzi, Mauro. “Henri Poincaré” . Encyclopédie Internet de la philosophie .Comprend une discussion de la critique de Poincaré des axiomes de Peano.
• Podnieks, Karlis (2015-01-25). “3. Arithmétique du premier ordre”. Qu’est-ce que les mathématiques : le théorème de Gödel et ses environs . p. 93–121.
• “Axiomes de Peano” , Encyclopédie des mathématiques , EMS Press , 2001 [1994]
• Weisstein, Eric W. “Axiomes de Peano” . MathWorld .
• En ligneBurris, Stanley N. (2001). “Qu’est-ce que les nombres, et quelle est leur signification ? : Dedekind” .Commentaire sur l’œuvre de Dedekind.

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