Petit défi en arithmétique formelle (Peano)

**Médiat** · 09/02/2012, 09h14

Bonjour,
Petit défi :
Soit $\text{[math]}$ un modèle dénombrable, non standard de l'arithmétique de Peano (AP). Il est bien connu que le type d'ordre de $\text{[math]}$ est $\text{[math]}$ , où l'ordre sur $\text{[math]}$ est l'ordre lexicographique.
Soit $\text{[math]}$ , $\text{[math]}$ est donc de la forme $\text{[math]}$ , nous noterons $\text{[math]}$ (c'est à dire le nombre rationnel qui identifie la "fibre" dans laquelle se trouve $\text{[math]}$ .
Soit $\text{[math]}$ la suite définie (pour $\text{[math]}$ ) par $\text{[math]}$

1) Montrer que $\text{[math]}$ est strictement croissante.
2) Montrer que $\text{[math]}$ est bornée.
3) Montrer que $\text{[math]}$ n'a pas de limite.

Rappel : $\text{[math]}$ est définie dans AP par $\text{[math]}$
$\text{[math]}$ et $\text{[math]}$ appartiennent à la même fibre si et seulement si $\text{[math]}$

Amusez-vous bien.

**Médiat** · 10/02/2012, 05h16

Trop difficile ?

inviteaf1870ed · 10/02/2012, 10h54

Je ne comprends même pas la question

**Médiat** · 10/02/2012, 11h21

Bonjour

Arrgh ! Je n'avais anticipé cette hypothèse.

Il ne faut pas avoir peur, il suffit de connaître :

1) Quelques petites choses sur l'arithmétique de Peano (et j'ai rappelé le point le plus utilisé qui est la définition de <).
2) Rien sur les modèles non standard à part ce qui est dans l'énoncé (sur le type d'ordre, et l'appartenance à une même fibre (une même copie de $\text{[math]}$ )
3) Pour la question 3 il est nécessaire de connaître un théorème important de AP, mais on en reparlera quand les question 1 et 2 seront résolues

Bien sur, je suis ouvert à toutes questions.

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

inviteaf1870ed · 10/02/2012, 12h13

Le z qui apparait dans la définition de < doit être positif, ou bien ?

**Médiat** · 10/02/2012, 12h42

Dans l'arithmétique de Peano, tous les éléments sont plus grands que 0, donc pas de problème.

Quand on dit que le type d'ordre est $\text{[math]}$ , cela veut dire que les éléments appartiennent, soit à $\text{[math]}$ , soit à $\text{[math]}$ (une union disjointe, donc), sur $\text{[math]}$ , l'ordre est l'ordre usuel, sur $\text{[math]}$ l'ordre est lexicographique (avec l'ordre usuel sur chaque coordonnées), et tous les éléments de $\text{[math]}$ sont plus petits que chaque éléments de $\text{[math]}$ .

$\text{[math]}$

A droite de l'accolade, il y a un "ou" entre chaque ligne.

invite14e03d2a · 12/02/2012, 13h27

Bonjour,

comment est définie l'addition sur $\text{[math]}$ ? Est-ce que sa restriction à $\text{[math]}$ est l'addition "usuelle"?

$\text{[math]}$ et $\text{[math]}$ appartiennent à la même fibre si et seulement si $\text{[math]}$

Doit-on identifier $\text{[math]}$ à $\text{[math]}$ dans $\text{[math]}$ ?

Merci

**Médiat** · 12/02/2012, 14h10

Bonjour,

Envoyé par taladris

comment est définie l'addition sur $\text{[math]}$ ? Est-ce que sa restriction à $\text{[math]}$ est l'addition "usuelle"?

Excellente question (celle que j'attendais en fait)

.
Non seulement ce n'est pas dans l'énoncé (car c'est inutile), mais en plus le théorème de Tennenbaum dit que l'on ne sait pas définir les opérations sur un modèle non standard (à part l'addition d'un entier relatif standard, qui se passe à l'intérieur d'une même fibre).

Envoyé par taladris

Doit-on identifier $\text{[math]}$ à $\text{[math]}$ dans $\text{[math]}$ ?

Je ne suis pas sur de bien comprendre la question, on peut identifier $\text{[math]}$ avec chacune des fibres (chacun des $\text{[math]}$ ), en tant qu'ensemble ordonné

invite14e03d2a · 12/02/2012, 14h28

Envoyé par Médiat

$\text{[math]}$ et $\text{[math]}$ appartiennent à la même fibre si et seulement si $\text{[math]}$

Je faisais référence à la propriété ci-dessus: a et b sont des éléments de $\text{[math]}$ et k un élément de $\text{[math]}$ . Je ne comprend comment additionner a et k sans identifier $\text{[math]}$ à une fibre. Mais votre réponse me fait penser que je n'ai pas les connaissances nécessaires pour participer (je pensais que la question était purement algébrique).

**Médiat** · 12/02/2012, 14h52

Envoyé par taladris

Je faisais référence à la propriété ci-dessus: a et b sont des éléments de $\text{[math]}$ et k un élément de $\text{[math]}$ . Je ne comprend comment additionner a et k sans identifier $\text{[math]}$ à une fibre. Mais votre réponse me fait penser que je n'ai pas les connaissances nécessaires pour participer (je pensais que la question était purement algébrique).

Je comprends mieux la question, et j'aurais sans doute été plus clair en écrivant :

$\text{[math]}$ et $\text{[math]}$ appartiennent à la même fibre si et seulement si $\text{[math]}$ ou encore si $\text{[math]}$ , c'est à dire si a et b sont dans la même composante connexe (au sens de s), comme cela est décrit dans le document http://forums.futura-sciences.com/ma...ml#post3879760

Envoyé par taladris

Mais votre réponse me fait penser que je n'ai pas les connaissances nécessaires pour participer (je pensais que la question était purement algébrique).

Je vous assure que vous avez toutes les connaissances nécessaires, l'intérêt de ce petit défi c'est qu'il faut jongler entre les axiomes de Peano et les propriétés du modèle (dont on ne connait bien que peu de choses, ce que j'ai déjà cité en fait).

inviteaf1870ed · 13/02/2012, 11h47

Bon je vais dire une énormité, mais au moins on aura peut être progressé un peu dans la compréhension du "monstre" de Médiat.

On prend a=(r,k) où r est un rationnel et k un élément de Z. Alors (n+1)a est de la forme (n+1)r+k', et comme (n+1)r est supérieur dans Q à nr, on a bien que la suite est croissante...Mais Mais Mais je ne comprends pas très bien ce qui se passe quand n est un multiple de q, car alors on tombe dans Z, qui est bien inférieur à QxZ ?

**Médiat** · 13/02/2012, 12h18

Envoyé par ericcc

Bon je vais dire une énormité, mais au moins on aura peut être progressé un peu dans la compréhension du "monstre" de Médiat.

Merci, c'est effectivement ainsi que l'on avancera.

Envoyé par ericcc

On prend a=(r,k) où r est un rationnel et k un élément de Z. Alors (n+1)a est de la forme (n+1)r+k'

Malheureusement non, car on ne sait pas à quoi ressemble la multiplication dans ce modèle (et même : on ne peut pas savoir).

Afin de faire disparaître toute peur devant ce "monstre" (

), je vous donne deux débuts de démonstration pour le point 1) :

1) Si on admet connaître un certain nombre de théorème de l'arithmétique de Peano (AP par la suite), on peut écrire tout simplement :

$\text{[math]}$ , or
$\text{[math]}$ définition de < dans AP (et $\text{[math]}$ )

Evidemment ceci n'est que le début de la démonstration, il en manque un bon morceau. De plus cette démonstration fait disparaître un peu le fait que la démonstration se fait dans AP, puisque la première ligne est tout bêtement la distributivité, valide dans tous les ensembles utilisés dans la définition du modèle.

2) Le même début, en revenant aux axiomes de AP (et en notant $\text{[math]}$ la fonction successeur) :
$\text{[math]}$ par définition de 1
$\text{[math]}$ cf. ci-dessus
$\text{[math]}$ Axiome 2 de l'addition dans AP
$\text{[math]}$ Axiome 1 de l'addition dans AP
$\text{[math]}$ cf. ci-dessus
$\text{[math]}$ Axiome 2 de la multiplication dans AP
$\text{[math]}$ définition de < dans AP (et $\text{[math]}$ )

La suite est très "différente", mais pas plus compliquée.

**Médiat** · 14/02/2012, 14h40

Bonjour,

Allez je donne un coup de pouce :

On a démontré une relation entre $\text{[math]}$ et $\text{[math]}$ en n'utilisant que les axiomes de AP (aucune propriété particulière de $\text{[math]}$ ou de $\text{[math]}$ n'a été supposée), cette relation est donc vraie dans le modèle, mais comment l'écrire (la traduire), dans le modèle ?

inviteaf1870ed · 14/02/2012, 16h30

Si na<(n+1)a, en appliquant la définition, il existe k dans Z tel que (n+1)a=na+k, et d'après ta deuxième propriété na et (n+1)a appartiennent à la même fibre ???

**Médiat** · 14/02/2012, 18h05

Donc, on sait que $\text{[math]}$ , on sait aussi que $\text{[math]}$ et $\text{[math]}$ ne sont pas des entiers standard, puisque plus grand que $\text{[math]}$ qui n'est pas standard (ils ne sont pas dans $\text{[math]}$ , donc ils sont dans $\text{[math]}$ ), donc si vous regardez le message #6, vous saurez comment traduire, dans le modèle, que $\text{[math]}$ ...

inviteaf1870ed · 14/02/2012, 18h50

Bon je me lance (la persévérance est fille de l'ignorance

)

On sait que nos amis na et (n+1)a sont non standards, ils sont donc de la forme (A,P) avec A dans Q et P dans Z. En appliquant la définition de l'inégalité à na=(A,P) et (n+1)a=(B,M) on a soit que

A<B donc $\text{[math]}$
A=B et P<M donc $\text{[math]}$

et notre suite est croissante sans être strictement croissante

A moins que je ne me sois encore complètement gourré

**Médiat** · 14/02/2012, 19h27

Vous avez tout bon !

Vous avez démontré que $\text{[math]}$ , il ne vous reste plus qu'à démontrer que l'égalité est impossible.

Rappel $\text{[math]}$ veut très exactement dire que $\text{[math]}$ et $\text{[math]}$ sont dans la même fibre...

inviteaf1870ed · 14/02/2012, 19h59

Si ils sont dans la même fibre, ils sont séparés par un entier relatif k : (n+1)a=na+k.
Je suppose qu'un super raisonnement qui n'emploie aucune des opérations que l'on est tenté de faire (soustraction par exemple) aboutit à une "égalité" du genre k=a, qui est impossible car on est justement dans le cas non standard ?

**Médiat** · 14/02/2012, 20h14

Envoyé par ericcc

Si ils sont dans la même fibre, ils sont séparés par un entier relatif k : (n+1)a=na+k.

Parfait

Envoyé par ericcc

Je suppose qu'un super raisonnement qui n'emploie aucune des opérations que l'on est tenté de faire (soustraction par exemple) aboutit à une "égalité" du genre k=a, qui est impossible car on est justement dans le cas non standard ?

Parfaitement exact, le raisonnement en question est tout simplement la régularité de l'addition dans AP, pour la démonstration à partir de axiomes de AP, vous pouvez regarder les solutions : http://forums.futura-sciences.com/ma...ml#post3879760, exercice 12 T7 (si c'est démontrable dans Presburger, c'est a fortiori démontrable dans AP)

Comme vous le voyez, pour cette partie on a eu besoin de raisonner dans AP, puis dans le modèle, puis à nouveau dans AP et c'est là l'intérêt de "défi", en plus du côté étonnant du résultat.

**Médiat** · 15/02/2012, 19h29

Pour montrer que la suite est bornée, c'est très simple, il suffit d'imaginer (c'est assez naturel) un entier plus grand que tous les na pour n dans $\text{[math]}$

invite6acfe16b · 15/02/2012, 21h56

Bonjour,

J'ai l'impression que cette suite n'est pas bornée. En effet, je crois pouvoir prouver, mais je me trompe peut-être ,que $\text{[math]}$ tel que $\text{[math]}$ . Si m=0, il suffit de prendre n=1 et si c'est vrai pour m, alors c'est vrai pour m+1 en prenant le successeur du n qui marchait pour m.
Du coup, j'ai toujours un n tel que $\text{[math]}$ pour tout rationnel q.

Qu'est ce qui est faux la dedans ?

**Médiat** · 16/02/2012, 04h57

Bonjour, et merci de votre contribution.

Vous avez bien démontré que $\text{[math]}$ , si j'ajoute les ensembles d'appartenance des variables, on obtient : $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ , mais ce qu'il faudrait démontrer pour montrer que la suite n'est pas bornée c'est :
$\text{[math]}$ $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ , et là il est impossible^(*) d'utiliser une récurrence (généralement une bonne idée dans AP).

Je viens de relire le message #1, et j'avoue qu'il y a du "non-dit"

(quand on est trop habitué à certaines choses...), je ré-écris la définition de $\text{[math]}$ :
Soit $\text{[math]}$ la suite définie (pour $\text{[math]}$ $\text{[math]}$ ) par $\text{[math]}$ .

En effet une suite est une application de $\text{[math]}$ dans quelque chose, ici dans $\text{[math]}$ (ce qui montre bien que nous ne sommes pas entièrement dans la théorie AP).

(*) Impossible car la récurrence dans AP (du premier ordre^(**)) est restreinte aux formules du langage, et donc pour établir une récurrence pour une formule où l'une des variables est restreinte à $\text{[math]}$ , il faudrait que $\text{[math]}$ soit définissable, or justement on sait que non (la démonstration se trouve dans le document sur l'arithmétique déjà cité), c'est d'ailleurs à ce théorème que je faisais allusion dans le message #4, il sera donc encore utile.

(**) Nous sommes forcément au premier ordre car dans AP du deuxième ordre, il n'y a pas de modèle non-standard.

invite6acfe16b · 16/02/2012, 08h16

D'accord, donc $\text{[math]}$ . C'est effectivement le point qui me bloquait depuis le début.
Ensuite, il est facile de montrer que la suite est bornée puisque en choisissant n'importe quel $\text{[math]}$ on a $\text{[math]}$ et donc q est un majorant.

Je réfléchis à la suite, mais elle me semble contredire le fait que toute suite croissante bornée dans $\text{[math]}$ est convergente. Peut-être que le truc est que la suite ne converge pas dans $\text{[math]}$ mais quand même bien dans $\text{[math]}$ ?

invite6acfe16b · 16/02/2012, 08h26

Juste une précision, j'ai oublié de dire que le m de mon message précédent n'est évidemment pas dans $\text{[math]}$ , mais vous l'aviez tous deviné

**Médiat** · 16/02/2012, 08h34

Envoyé par Sylvestre

Ensuite, il est facile de montrer que la suite est bornée puisque en choisissant n'importe quel $\text{[math]}$ on a $\text{[math]}$ et donc q est un majorant.

C'est un peu rapide

.

D'abord, comme vous l'avez précisé, vous devez choisir $\text{[math]}$ (je garde les variables m, n pour des entiers standard), ensuite il faut y aller par étape :
1) Démontrer $\text{[math]}$
2) En déduire $\text{[math]}$ (l'inégalité au sens large est suffisante).

Envoyé par Sylvestre

Je réfléchis à la suite, mais elle me semble contredire le fait que toute suite croissante bornée dans $\text{[math]}$ est convergente. Peut-être que le truc est que la suite ne converge pas dans $\text{[math]}$ mais quand même bien dans $\text{[math]}$ ?

Oui, c'est exactement cela (et c'est d'ailleurs le côté surprenant de ce résultat), d'ailleurs, vous êtes à deux doigts de démontrer un autre théorème concernant les modèles non-standard (si vous ne devinez pas lequel, j'en dirai plus, une fois ce premier théorème démontré).

invite6acfe16b · 16/02/2012, 08h47

Alors je vais essayer de faire plus de pas.

Je veux montrer que $\text{[math]}$ . Je sais que $\text{[math]}$ donc il existe $\text{[math]}$ tel que $\text{[math]}$ et donc $\text{[math]}$ implique $\text{[math]}$ .

Pour le point 2, il suffit d'utiliser le fait que l'ordre sur $\text{[math]}$ est lexicographique.

Je réfléchis toujours au point 3 du problème initiale.

PS: Je ne répondrai pas tout de suite, car je suis occupé à travailler aujourd'hui. (et oui, on ne peut pas toujours s'amuser à faire des maths...)

**Médiat** · 16/02/2012, 08h52

Envoyé par Sylvestre

Je veux montrer que $\text{[math]}$ . Je sais que $\text{[math]}$ donc il existe $\text{[math]}$ tel que $\text{[math]}$ et donc $\text{[math]}$ implique $\text{[math]}$ .

Pour le point 2, il suffit d'utiliser le fait que l'ordre sur $\text{[math]}$ est lexicographique....)

Excellent

.

Envoyé par Sylvestre

Je réfléchis toujours au point 3 du problème initiale. ...)

Il est plus compliqué, je suis ouvert à toutes questions.

Envoyé par Sylvestre

PS: Je ne répondrai pas tout de suite, car je suis occupé à travailler aujourd'hui. (et oui, on ne peut pas toujours s'amuser à faire des maths...)

La vie est mal faite

.

invite6acfe16b · 16/02/2012, 15h31

Par l'absurde, si la suite convergeait vers $\text{[math]}$ , on aurait que $\text{[math]}$ . L'égalité est impossible car les éléments de la suite sont tous dans des fibres différentes.
Soit $\text{[math]}$ un élément quelconque de la fibre $\text{[math]}$ .
Alors, on pourrait définir les éléments de $\text{[math]}$ comme étant tous les $\text{[math]}$ tels que $\text{[math]}$ , ce qui est impossible par le théorème que vous avez cité.

Ceci dit, je ne vois pas à quel autre théorème vous faites allusion.

**Médiat** · 16/02/2012, 15h53

Envoyé par Sylvestre

Alors, on pourrait définir les éléments de $\text{[math]}$ comme étant tous les $\text{[math]}$ tels que $\text{[math]}$ , ce qui est impossible par le théorème que vous avez cité.

C'est parfaitement exact, mais un peu rapide, il est clair que tous les entiers standard sont dans cet ensemble, qu'il ne contienne rien d'autre, mérite un peu de développements

.

Envoyé par Sylvestre

Ceci dit, je ne vois pas à quel autre théorème vous faites allusion.

En fait le théorème connu, et qui est un corrolaire immédiat de ce qui vient d'être dit, c'est qu'aucun modèle non-standard n'est de type d'ordre $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ (on sait que tous les modèles non-standard ont un type d'ordre de la forme $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ où $\text{[math]}$ est un ordre total, dense, sans extrémités, donc $\text{[math]}$ était candidat).

Je reviendrai sur d'autres aspects des modèles non-standard assez rapidement (sur ce même fil).

invite6acfe16b · 16/02/2012, 16h00

Soit $\text{[math]}$ un élément non standard. On a $\text{[math]}$ . Donc, comme la limite de la suite est $\text{[math]}$ , nous avons $\text{[math]}$ , ce qui exclut tous les éléments non standards du critère.

Petit défi en arithmétique formelle (Peano)

Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Re : Petit défi en arithmétique formelle (Peano)

Discussions similaires

Petit défi d'algèbre

Les suites (un petit défi)

Mouvements et référentiels : petit défi

petit défi

Petit défi!