Petit défi en arithmétique formelle (Peano)
Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 34

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



  1. #1
    Médiat

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


    ------

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

    1) Montrer que est strictement croissante.
    2) Montrer que est bornée.
    3) Montrer que n'a pas de limite.

    Rappel : est définie dans AP par
    et appartiennent à la même fibre si et seulement si

    Amusez-vous bien.

    -----
    Dernière modification par Médiat ; 09/02/2012 à 14h09. Motif: Ajout d'une précision.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  2. #2
    Médiat

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

    Trop difficile ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    ericcc

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

    Je ne comprends même pas la question

  4. #4
    Médiat

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

    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 )
    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.
    Dernière modification par Médiat ; 10/02/2012 à 11h24.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  5. A voir en vidéo sur Futura
  6. #5
    ericcc

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

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

  7. #6
    Médiat

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

    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 , cela veut dire que les éléments appartiennent, soit à , soit à (une union disjointe, donc), sur , l'ordre est l'ordre usuel, sur l'ordre est lexicographique (avec l'ordre usuel sur chaque coordonnées), et tous les éléments de sont plus petits que chaque éléments de .



    A droite de l'accolade, il y a un "ou" entre chaque ligne.
    Dernière modification par Médiat ; 11/02/2012 à 13h11. Motif: Latex
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  8. #7
    taladris

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

    Bonjour,

    comment est définie l'addition sur ? Est-ce que sa restriction à est l'addition "usuelle"?

    et appartiennent à la même fibre si et seulement si
    Doit-on identifier à dans ?

    Merci

  9. #8
    Médiat

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

    Bonjour,
    Citation Envoyé par taladris Voir le message
    comment est définie l'addition sur ? Est-ce que sa restriction à 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).

    Citation Envoyé par taladris Voir le message
    Doit-on identifier à dans ?
    Je ne suis pas sur de bien comprendre la question, on peut identifier avec chacune des fibres (chacun des ), en tant qu'ensemble ordonné
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  10. #9
    taladris

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

    Citation Envoyé par Médiat Voir le message
    et appartiennent à la même fibre si et seulement si
    Je faisais référence à la propriété ci-dessus: a et b sont des éléments de et k un élément de . Je ne comprend comment additionner a et k sans identifier à 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).

  11. #10
    Médiat

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

    Citation Envoyé par taladris Voir le message
    Je faisais référence à la propriété ci-dessus: a et b sont des éléments de et k un élément de . Je ne comprend comment additionner a et k sans identifier à 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 :

    et appartiennent à la même fibre si et seulement si ou encore si , 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

    Citation Envoyé par taladris Voir le message
    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).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  12. #11
    ericcc

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

    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 ?

  13. #12
    Médiat

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

    Citation Envoyé par ericcc Voir le message
    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.

    Citation Envoyé par ericcc Voir le message
    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 :

    , or
    définition de < dans AP (et )

    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 la fonction successeur) :
    par définition de 1
    cf. ci-dessus
    Axiome 2 de l'addition dans AP
    Axiome 1 de l'addition dans AP
    cf. ci-dessus
    Axiome 2 de la multiplication dans AP
    définition de < dans AP (et )

    La suite est très "différente", mais pas plus compliquée.
    Dernière modification par Médiat ; 13/02/2012 à 12h22.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #13
    Médiat

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

    Bonjour,

    Allez je donne un coup de pouce :

    On a démontré une relation entre et en n'utilisant que les axiomes de AP (aucune propriété particulière de ou de n'a été supposée), cette relation est donc vraie dans le modèle, mais comment l'écrire (la traduire), dans le modèle ?
    Dernière modification par Médiat ; 14/02/2012 à 15h06.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #14
    ericcc

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

    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 ???

  16. #15
    Médiat

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

    Donc, on sait que , on sait aussi que et ne sont pas des entiers standard, puisque plus grand que qui n'est pas standard (ils ne sont pas dans , donc ils sont dans ), donc si vous regardez le message #6, vous saurez comment traduire, dans le modèle, que ...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  17. #16
    ericcc

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

    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
    A=B et P<M donc

    et notre suite est croissante sans être strictement croissante

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

  18. #17
    Médiat

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



    Vous avez tout bon !

    Vous avez démontré que , il ne vous reste plus qu'à démontrer que l'égalité est impossible.

    Rappel veut très exactement dire que et sont dans la même fibre...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #18
    ericcc

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

    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 ?

  20. #19
    Médiat

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

    Citation Envoyé par ericcc Voir le message
    Si ils sont dans la même fibre, ils sont séparés par un entier relatif k : (n+1)a=na+k.
    Parfait

    Citation Envoyé par ericcc Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #20
    Médiat

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

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. #21
    Sylvestre

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

    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 tel que . 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 pour tout rationnel q.

    Qu'est ce qui est faux la dedans ?
    Dernière modification par Sylvestre ; 15/02/2012 à 21h58.
    Programming is understanding

  23. #22
    Médiat

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

    Bonjour, et merci de votre contribution.

    Vous avez bien démontré que , si j'ajoute les ensembles d'appartenance des variables, on obtient : , mais ce qu'il faudrait démontrer pour montrer que la suite n'est pas bornée c'est :
    , 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 :
    Soit la suite définie (pour ) par .

    En effet une suite est une application de dans quelque chose, ici dans (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 à , il faudrait que 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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  24. #23
    Sylvestre

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

    D'accord, donc . 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 on a 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 est convergente. Peut-être que le truc est que la suite ne converge pas dans mais quand même bien dans ?
    Programming is understanding

  25. #24
    Sylvestre

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

    Juste une précision, j'ai oublié de dire que le m de mon message précédent n'est évidemment pas dans , mais vous l'aviez tous deviné
    Programming is understanding

  26. #25
    Médiat

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

    Citation Envoyé par Sylvestre Voir le message
    Ensuite, il est facile de montrer que la suite est bornée puisque en choisissant n'importe quel on a et donc q est un majorant.
    C'est un peu rapide .

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


    Citation Envoyé par Sylvestre Voir le message
    Je réfléchis à la suite, mais elle me semble contredire le fait que toute suite croissante bornée dans est convergente. Peut-être que le truc est que la suite ne converge pas dans mais quand même bien dans ?
    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é).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #26
    Sylvestre

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

    Alors je vais essayer de faire plus de pas.

    Je veux montrer que . Je sais que donc il existe tel que et donc implique .

    Pour le point 2, il suffit d'utiliser le fait que l'ordre sur 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...)
    Programming is understanding

  28. #27
    Médiat

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

    Citation Envoyé par Sylvestre Voir le message
    Je veux montrer que . Je sais que donc il existe tel que et donc implique .

    Pour le point 2, il suffit d'utiliser le fait que l'ordre sur est lexicographique....)
    Excellent .

    Citation Envoyé par Sylvestre Voir le message
    Je réfléchis toujours au point 3 du problème initiale. ...)
    Il est plus compliqué, je suis ouvert à toutes questions.

    Citation Envoyé par Sylvestre Voir le message
    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 .
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  29. #28
    Sylvestre

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

    Par l'absurde, si la suite convergeait vers , on aurait que . L'égalité est impossible car les éléments de la suite sont tous dans des fibres différentes.
    Soit un élément quelconque de la fibre .
    Alors, on pourrait définir les éléments de comme étant tous les tels que , 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.
    Dernière modification par Sylvestre ; 16/02/2012 à 15h35.
    Programming is understanding

  30. #29
    Médiat

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

    Citation Envoyé par Sylvestre Voir le message
    Alors, on pourrait définir les éléments de comme étant tous les tels que , 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 .

    Citation Envoyé par Sylvestre Voir le message
    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 (on sait que tous les modèles non-standard ont un type d'ordre de la forme est un ordre total, dense, sans extrémités, donc était candidat).

    Je reviendrai sur d'autres aspects des modèles non-standard assez rapidement (sur ce même fil).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  31. #30
    Sylvestre

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

    Soit un élément non standard. On a . Donc, comme la limite de la suite est , nous avons , ce qui exclut tous les éléments non standards du critère.
    Programming is understanding

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Petit défi d'algèbre
    Par Seirios dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 25/01/2012, 20h16
  2. Les suites (un petit défi)
    Par invite8741c18e dans le forum Mathématiques du supérieur
    Réponses: 21
    Dernier message: 05/12/2008, 01h11
  3. Mouvements et référentiels : petit défi
    Par invite48c8c396 dans le forum Physique
    Réponses: 20
    Dernier message: 17/03/2005, 13h23
  4. petit défi
    Par invite4793bfc9 dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 11/02/2005, 17h04
  5. Petit défi!
    Par invitee42ad93f dans le forum Physique
    Réponses: 13
    Dernier message: 13/06/2004, 00h05