Construction de N par les axiomes de Peano

**Seirios** · 11/06/2009, 09h22

Bonjour à tous,

D'après ce que j'ai compris, l'on peut construire l'ensemble des entiers naturels par les axiomes de Peano, c'est-à-dire qu'il existe un triplet $\left(0, \mathbb{N},S)$ , avec 0 un élément de l'ensemble $\mathbb{N}$ et S une application injective de $\mathbb{N}$ dans $\mathbb{N}$ , telle que $Im(f)= \mathbb{N}^*$ (S est l'application succession) ; de plus, si 0 appartient à un ensemble A, et si $n \in A \to S(n) \in A$ , alors $A=\mathbb{N}$ .

Je suis d'accord que $\mathbb{N}$ répond à ses axiomes, mais est-il ainsi défini de manière unique ? Et S ne présuppose-t-elle une définition d'ordre dans $\mathbb{N}$ ?

Merci d'avance
Phys2

**Médiat** · 11/06/2009, 09h42

Envoyé par Phys2

Je suis d'accord que $\mathbb{N}$ répond à ses axiomes, mais est-il ainsi défini de manière unique ?

Oui ! (à isomorphisme près, bien sur), cela se démontre très facilement par un va et vient.

Envoyé par Phys2

Et S ne présuppose-t-elle une définition d'ordre dans $\mathbb{N}$ ?

Non, je ne vois pas où la relation d'ordre est utile.

Remarque 1 : il me semble que dans les axiomes de Peano, il y a les définitions de + et de x
Remarque 2 : la définition que tu donnes est du deuxième ordre, donc non soumise au théorème d'incomplétude de Gödel.

**Seirios** · 11/06/2009, 13h15

Non, je ne vois pas où la relation d'ordre est utile.

Je pense que la réponse à ma question vient de l'axiome de récurrence ; c'est lui qui permet de déterminer de manière unique l'application injective S (en plus de la caractéristique $Im(f)= \mathbb{N}^*$ ).

Remarque 1 : il me semble que dans les axiomes de Peano, il y a les définitions de + et de x

Dans mon document, l'addition et la multiplication, comme lois de composition interne à $\mathbb{N}$ , sont présentées juste après les axiomes de Peano, mais en sont détachées.

Oui ! (à isomorphisme près, bien sur), cela se démontre très facilement par un va et vient.

Comment retrouve-t-on exactement cette unicité ?

**Médiat** · 11/06/2009, 17h35

Envoyé par Phys2

Comment retrouve-t-on exactement cette unicité ?

Soit $(E, \, 0_E, \, s_E)$ et $(F, \, 0_F, \, s_F)$ deux modèles de tes axiomes.
On définit $f$ de la façon suivante :
$f(0_E) \, = \, 0_F$ et
$\forall x \in E (f(s_E(x))\, = \, s_F(f(x))$

On peut montrer facilement que $Dom(f) \, = \, E$ , puisque
$0_E \in Dom(f)$ et
$\forall x \in Dom(f) (f(s_E(x))\, = \, s_F(f(x))$ ce qui montre bien que $s_E(x) \in Dom(f)$ et par l'axiome de récurrence on conclut que $E \, = \, Dom(f)$

Pour montrer que $Im(f) = F$ c'est dans le même genre, pour l'injectivité, il faut considérer l'ensemble $A = \{x \mid \forall y \in E (x \, \neq\, y) \Rightarrow (f(x) \neq f(y))\}$ et appliquer la récurrence.

PS : il y a une chose essentielle que je n'ai pas dîte

A voir en vidéo sur Futura · Aujourd'hui

**Seirios** · 11/06/2009, 18h39

PS : il y a une chose essentielle que je n'ai pas dîte

L'idée générale ne serait-elle pas de montrer que f est un isomorphisme de E vers F ? (et dans ce cas il faudrait sans doute montrer que $f^{-1}$ est un morphisme de F vers E, par un raisonnement analogue)

**Médiat** · 11/06/2009, 19h03

Envoyé par Phys2

L'idée générale ne serait-elle pas de montrer que f est un isomorphisme de E vers F ?

Bien sur, mais ça, f le fait très bien sauf que je n'ai pas montré que f était bien une fonction (mais cela se fait de la même façon que les autres propriétés

Envoyé par Phys2

(et dans ce cas il faudrait sans doute montrer que $f^{-1}$ est un morphisme de F vers E, par un raisonnement analogue)

Si tu montres que f est
1) une fonction
2) de domaine E
3) surjective
4) injective
5) telle que y = s_E(x) ==> f(y) = s_F(f(x))
Alors tu auras bien montré que c'est un isomorphisme pour les structures considérées.

Le point 5 est acquis par construction, je t'ai montré la démonstration pour le point 2 (et le point 3 est similaire) et le point 4, reste le point 1.

**Seirios** · 11/06/2009, 20h53

Il y a juste un détail que je ne comprends pas : je sais que le fait qu'il existe un isomorphisme entre deux structures permet d'avoir des propriétés similaires, mais qu'en est-il vraiment, c'est une relation qui reste encore floue pour moi ?

**Médiat** · 12/06/2009, 05h43

Envoyé par Phys2

Il y a juste un détail que je ne comprends pas : je sais que le fait qu'il existe un isomorphisme entre deux structures permet d'avoir des propriétés similaires, mais qu'en est-il vraiment, c'est une relation qui reste encore floue pour moi ?

Deux structures isomorphes sont plus que similaires, elles sont identiques aux noms près.

En utilisant la même notation qu'au message #3 (et en ne considérant que des langages avec égalité) :

$(\mathbb{Z}/2\mathbb{Z}, \, \times)$ est isomorphe à $(\{V, \, F\}, \wedge)$ ( $\wedge$ est le connecteur logique "et"), l'isomorphisme étant facile à trouver.
Un exemple plus simple :
$(\mathbb{N})$ et $(\mathbb{Q}^+)$ sont isomorphes.

Dans les deux exemples précédents, il est facile de voir que l'on peut passer d'une structure à l'autre simplement en changeant les noms des objets.

**Seirios** · 12/06/2009, 12h04

Voici donc le raisonnement que j'ai pu faire :

Soient $(E,0_E,S_E)$ et $(F,0_F,S_F)$ deux structures répondants aux axiomes de Peano, et f une application définie par : $\{ \array{ f(0_E)=0_F \\ f(S_E(x))=S_F(f(x))}$ .

Montrons tout d'abord que f est bien une fonction. Si $x=x'=0_E$ , alors $f(x)=f(x')=0_F$ . Supposons par la suite que $(x=x') \Rightarrow (f(x)=f(x'))$ ; comme $(x=x') \Leftrightarrow (s_E(x)=s_E(x'))$ et $(f(x)=f(x')) \Leftrightarrow (S_F(f(x))=S_F(f(x')))$ , on a $(S_E(x)=S_E(x')) \Rightarrow (S_F(f(x))=S_F(f(x')))$ , soit $(S_E(x)=S_E(x')) \Rightarrow (f(S_E(x))=f(S_E(x')))$ . Par l'axiome de récurrence, la propriété $(x=x') \Rightarrow (f(x)=f(x'))$ est vraie pour tout $x \in E$ , donc f est bien une fonction.

Ensuite, montrons que $Dom(f)=E$ . Par la définition de f, $0_E \in Dom(f)$ . Ensuite, si $x \in Dom(f)$ , alors $f(S_E(x))=S_F(f(x))$ existe et $S_E(x) \in Dom(f)$ . Par l'axiome de récurrence, $\forall x \in E, \ x \in Dom(f)$ , d'où $Dom(f)=E$ puisque par construction $Dom(f) \subset E$ .

Montrons que f est injective. Soit l'ensemble $A= \{ x \ | \ \forall y \in E, \ (x \neq y) \Rightarrow (f(x) \neq f(y)) \}$ ; on a $\forall y \in E \ | \ y \neq 0, \ f(0_E)=0_F$ et $S_F(f(y)) \neq 0_F$ puisque $0_E$ n'a pas de prédécesseur. Donc $0_E \in A$ . Supposons $\forall y \in E, \ (y \neq x) \Rightarrow f(y) \neq f(x)$ ; comme $(x \neq y) \Leftrightarrow (S_E(y) \neq S_E(x))$ et $(f(x) \neq f(y)) \Leftrightarrow (S_F(f(x)) \neq S_F(f(y)))$ puisque $S_F \ \ et \ \ S_E$ sont injectives, alors $\forall y \in E- \{ 0_E \}, \ (y \neq S_E(x)) \Rightarrow (f(y) \neq f(S_E(x)))$ . Donc $(x \in A) \Rightarrow (S_E(x) \in A)$ , d'où $A=E$ . Donc f est injective, puisque $\left( (x \neq y) \Rightarrow (f(x) \neq f(y)) \right) \Leftrightarrow \left( (f(x)=f(y)) \Rightarrow (x=y) \right)$ .

Montrons que f est surjective ; pour cela, puisque nous savons que f est injective, montrons simplement que $Im(f)=F$ . Il est immédiat que $0_F \in Im(f)$ . Supposons que $f(x) \in Im(f)$ ; nous avons $S_E(x) \in Dom(f), \ donc \ f(S_E(x))= f(S_F(x)) \in Im(f)$ . Par l'axiome de récurrence, $Im(f)=F$ .

On notera également que par construction, f est un morphisme.

Au final, nous avons montrer que f était une fonction, un morphisme de surcroît, que $Dom(f)=E$ et que f était injective et surjective. Par conséquent, f est un isomorphisme de E vers F, et E et F sont isomorphes. Q.E.D.

Finalement, nous montrons que si E et F satisfont aux axiomes de Peano, alors ils sont isomorphes. Donc les axiomes de Peano définissent tous les ensembles isomorphes avec $\mathbb{N}$ , comme lui-même ou bien $\mathbb{Q}^+$ , c'est-à-dire de manière générale, tous les ensembles dénombrables, non ?

**Médiat** · 12/06/2009, 13h07

Envoyé par Phys2

Donc les axiomes de Peano définissent tous les ensembles isomorphes avec $\mathbb{N}$ , comme lui-même ou bien $\mathbb{Q}^+$ , c'est-à-dire de manière générale, tous les ensembles dénombrables, non ?

Je regarderai le reste plus tard, mais ceci est faux (ce n'est pas ce que j'ai écrit), je te laisse réfléchir (la réponse est dans mon message précédent.

**Seirios** · 12/06/2009, 14h23

Envoyé par Phys2

Donc les axiomes de Peano définissent tous les ensembles isomorphes avec $\mathbb{N}$ , comme lui-même ou bien $\mathbb{Q}^+$ , c'est-à-dire de manière générale, tous les ensembles dénombrables, non ?

Une rectification tout de même, ce que j'ai écris est une absurdité logique : les axiomes de Peano ne définiraient pas tous les ensembles isomorphes avec $\mathbb{N}$ , mais définissent des ensembles qui sont isomorphes avec $\mathbb{N}$ (pas tous).

**Médiat** · 12/06/2009, 15h18

Envoyé par Phys2

Une rectification tout de même, ce que j'ai écris est une absurdité logique : les axiomes de Peano ne définiraient pas tous les ensembles isomorphes avec $\mathbb{N}$ , mais définissent des ensembles qui sont isomorphes avec $\mathbb{N}$ (pas tous).

Je répète que $(\mathbb{N})$ et $(\mathbb{Q}^+)$ sont isomorphes, pas $\mathbb{N}$ et $\mathbb{Q}^+$ (ce qui est au mieux un abus de langage au pire une ânerie).

Pour les axiomes de Peano, il faut se demander si
$(\mathbb{N}, \, 0_{\mathbb{N}}, \, s_{\mathbb{Q}})$ et $(\mathbb{Q}^+, \, 0_{\mathbb{Q}}, \, s_{\mathbb{Q}})$ sont isomorphes, pour la definition de $0_{\mathbb{N}}$ , $s_{\mathbb{N}}$ et $0_{\mathbb{Q}}$ , il n'y a pas d'ambiguité car il existe des candidats naturels, ce qui n'est pas le cas de $s_{\mathbb{Q}}$ (pas de notion naturelle de successeur dans $\mathbb{Q}$ , effectivement il y en a quand même, mais il faut l'expliciter pour savoir de quoi on parle.)

**Seirios** · 12/06/2009, 15h59

Envoyé par Médiat

Je répète que $(\mathbb{N})$ et $(\mathbb{Q}^+)$ sont isomorphes, pas $\mathbb{N}$ et $\mathbb{Q}^+$ (ce qui est au mieux un abus de langage au pire une ânerie).

Effectivement, puisqu'il est nécessaire d'associer aux ensembles une application pour pouvoir parler de morphisme.

Pour les axiomes de Peano, il faut se demander si
$(\mathbb{N}, \, 0_{\mathbb{N}}, \, s_{\mathbb{Q}})$ et $(\mathbb{Q}^+, \, 0_{\mathbb{Q}}, \, s_{\mathbb{Q}})$ sont isomorphes, pour la definition de $0_{\mathbb{N}}$ , $s_{\mathbb{N}}$ et $0_{\mathbb{Q}}$ , il n'y a pas d'ambiguité car il existe des candidats naturels, ce qui n'est pas le cas de $s_{\mathbb{Q}}$ (pas de notion naturelle de successeur dans $\mathbb{Q}$ , effectivement il y en a quand même, mais il faut l'expliciter pour savoir de quoi on parle.)

D'accord. Donc finalement, l'on peut construire l'ensemble $A= \{ x \ | x \in \mathbb{N},\ x \geq n, \ n \in \mathbb{N} \}$ , par exemple, grâce aux axiomes de Peano. A-t-on idée de l'ensemble des triplets $(A, 0_A, S_A)$ isomorphes avec $( \mathbb{N},0_{ \mathbb{N}},S_{ \mathbb{N}})$ ?

**Médiat** · 12/06/2009, 19h12

Envoyé par Phys2

Effectivement, puisqu'il est nécessaire d'associer aux ensembles une application pour pouvoir parler de morphisme.

Ce n'est pas encore tout à fait cela : pour parler de morphisme (je ne me place pas dans la théorie des catégories), il faut un langage ou, a minima, la signature d'un langage (je considère que parler de morphisme de corps est un abus de langage (pas grave), on devrait parler de morphisme du langage des corps (ou même, des anneaux, puisque c'est le même langage)) ; si je peux dire que $(\mathbb{N})$ est isomorphe à $(\mathbb{Q}^+)$ c'est parce que les parenthèses, qui dans tous mes messages sur ce fil permettaient de définir un ensemble et les interprétations, dans cet ensemble, des éléments du langage, indique que je me place dans le langage vide (à l'égalité près), autrement dit ici, un morphisme est juste une application et un isomorphisme une bijection.
Si on parle de $\mathbb{N}$ et de $\mathbb{Q}^+$ sans les parenthèses, c'est à dire sans préciser qu'il n'y a pas de symbole dans le langage, je ne sais pas de quoi on parle, est-ce que $\mathbb{N}$ est muni de la fonction successeur, de +, de x, de la relation de divisibilité, de la relation d'ordre etc. ???

Envoyé par Phys2

D'accord. Donc finalement, l'on peut construire l'ensemble $A= \{ x \ | x \in \mathbb{N},\ x \geq n, \ n \in \mathbb{N} \}$ , par exemple, grâce aux axiomes de Peano. A-t-on idée de l'ensemble des triplets $(A, 0_A, S_A)$ isomorphes avec $( \mathbb{N},0_{ \mathbb{N}},S_{ \mathbb{N}})$ ?

Deux façons de faire :
1) tu prends $(\mathbb{N}, 0_{\mathbb{N}}, S_{\mathbb{N}})$ , tu changes les noms et pof, tu as une structure isomorphe
2) Tu prends un ensemble dénombrable quelconque $A$ , il existe donc des bijections entre $\mathbb{N}$ et $A$ , soit $f$ l'une d'entre elles, $f(0)$ jouera le rôle de $0_A$ , et pour définir $s_A$ , on pose, $s_A(f(x)) \, = \, f(s_{\mathbb{N}}(x))$ . Comme f est une bijection, $s_A$ est bien entièrement définie.

Un mot de plus : la question intéressante qui n'est pas loin de la tienne est "A quoi ressemblent les différents modèles (non isomorphes) d'une théorie complète", mais la question "A quoi ressemblent les modèles isomorphes à tel modèle particulier" n'est pas très intéressante, parce que justement tous ces modèles sont essentiellement identiques.

**Seirios** · 16/06/2009, 20h32

Une petite question sur une remarque que j'avais laissée de côté :

Envoyé par Médiat

Remarque 2 : la définition que tu donnes est du deuxième ordre, donc non soumise au théorème d'incomplétude de Gödel.

A quoi correspond exactement une définition du deuxième ordre ?

**Médiat** · 16/06/2009, 20h46

Envoyé par Phys2

A quoi correspond exactement une définition du deuxième ordre ?

A une quantification sur les sous-ensembles.

**Médiat** · 17/06/2009, 05h45

Envoyé par Phys2

A quoi correspond exactement une définition du deuxième ordre ?

Je complète ma réponse précédente par une question :
Quelle est la différence fondamentale (quelles sont les différences fondamentales) entre
Pour tout ensemble $A$ tel que
$0 \in A$ et $n \in A \Rightarrow s(n) \in A$ alors $A = \mathbb{N}$

Pour toute formule $\Phi$ :
$\Phi(0)$ et $\forall x (\Phi(n) \Rightarrow \Phi(s(n))$ alors $\forall n \Phi(n)$

Que ceux qui savent ne répondent pas, l'intérêt est de creuser les raisons des mauvaises (ou incomplètes) réponses .

**Seirios** · 17/06/2009, 07h15

Envoyé par Médiat

Quelle est la différence fondamentale (quelles sont les différences fondamentales) entre
Pour tout ensemble $A$ tel que
$0 \in A$ et $n \in A \Rightarrow s(n) \in A$ alors $A = \mathbb{N}$

Pour toute formule $\Phi$ :
$\Phi(0)$ et $\forall x (\Phi(n) \Rightarrow \Phi(s(n))$ alors $\forall n \Phi(n)$

C'est la différence entre l'axiome de réccurrence et le principe même ; déjà, l'on utilise pas les mêmes notions, puisque l'on utilise pour le premier la notion d'ensemble, et pour le second la notion de formule, mais l'un découle de l'autre. Ensuite, je ne sais pas quoi ajouter d'autre...

invitec317278e · 17/06/2009, 08h06

Envoyé par Médiat

Je complète ma réponse précédente par une question :
Quelle est la différence fondamentale (quelles sont les différences fondamentales) entre
Pour tout ensemble $A$ tel que
$0 \in A$ et $n \in A \Rightarrow s(n) \in A$ alors $A = \mathbb{N}$

Pour toute formule $\Phi$ :
$\Phi(0)$ et $\forall x (\Phi(n) \Rightarrow \Phi(s(n))$ alors $\forall n \Phi(n)$

Que ceux qui savent ne répondent pas, l'intérêt est de creuser les raisons des mauvaises (ou incomplètes) réponses .

ya des "quelque soi" dans l'un et pas dans l'autre ?

**Médiat** · 17/06/2009, 08h13

Envoyé par Phys2

utilise pour le premier la notion d'ensemble, et pour le second la notion de formule

C'est pas faux, mais en quoi est-ce fondamental ?

Envoyé par Phys2

l'un découle de l'autre

Je ne suis pas sur de comprendre ce que tu veux dire (et au moins une interprétation me forcerait à dire que c'est faux

).

Envoyé par Thorin

ya des "quelque soi" dans l'un et pas dans l'autre ?

Non, j'ai repris la définition telle qu'elle a été donnée par Phys2, mais j'aurais pu ajouter le quantificateur sur n, dans le premier énoncé, sans rien changer (ce que l'on appelle la généralisation).

J'en profite pour rectifier une faute de frappe : dans l'énoncé avec la formule, le premier quantificateur devrait porter sur n et non sur x.

**Seirios** · 17/06/2009, 08h45

Je ne suis pas sur de comprendre ce que tu veux dire (et au moins une interprétation me forcerait à dire que c'est faux

).

Ici, le principe de récurrence se déduit de l'axiome.

C'est pas faux, mais en quoi est-ce fondamental ?

Si l'on déduit le principe de récurence de l'axiome de récurrence, et non l'inverse (ce dont je ne suis pas certain, mais a priori je ne vois pas comment l'on pourrait procéder), alors l'utilisation d'ensembles doit avoir une portée plus générale, plus fondamentale.

**Médiat** · 17/06/2009, 17h34

Envoyé par Phys2

Ici, le principe de récurrence se déduit de l'axiome.

C'est exact ; on peut noter que ce que tu appelles le principe de récurrence est en fait un schéma d'axiomes, ce qui sous-entend que l'on peut écrire tous les axiomes (au moins ceux dont on a besoin), alors qu'on ne peut faire de même pour les sous-ensembles.

Envoyé par Phys2

Si l'on déduit le principe de récurence de l'axiome de récurrence, et non l'inverse (ce dont je ne suis pas certain, mais a priori je ne vois pas comment l'on pourrait procéder), alors l'utilisation d'ensembles doit avoir une portée plus générale, plus fondamentale.

Oui encore, mais on peut creuser un peu plus : même en ajoutant au langage une infinité de symboles de constantes (1 pour chaque entier), il n'est pas possible d'écrire un schéma d'axiomes qui soit équivalent à l'axiome du 2^nd ordre.

Une piste pour mieux comprendre : $\aleph_0 < 2^{\aleph_0}$

Construction de N par les axiomes de Peano

Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Re : Construction de N par les axiomes de Peano

Discussions similaires

liste des axiomes

axiomes de MQ

Axiomes des tribus

Differentiation de la serie de Peano Baker et recurrence

[Logique] Axiomes et conséquences