Arithmétique de Peano du premier ordre

[Merlin95]

Je me lance : dans le but de définir un ordre sur n élements. On compte le nombre de permutations de n élements, ca donne n! A noter que je ne souhaite pas associer le symbole de constante 0 au nombre 0 qui d'ailleurs n'existe pas forcément. De plus je vois un premier piège ne doit-il pas aussi avoir le symbole de constante 1 dans le langage. Je me réponds il suffit de définir 1 comme s(0). C'est bon ?
-----

[Deedee81]

Que signifie "majorant", tu veux dire "un majorant au nombre de structures" ? C'est ça ?

Cette question ne nécessite aucune connaissance particulière en logique.

Holà, ça me parrait bien compliqué quand même. A moins que cette fonction unaire et les deux binaires peuvent être quelconques ? Dans ce cas l'ensemble de ces structures a le cardinal des réels.... si je ne me trompe pas. Sinon je ne vois pas.

Croisement. Merlin, tu répondais aussi à la question ? on n'a pas compris la même chose visiblement

[Merlin95]

Oui en effet, mais je n'ai pas assimilé dans ma réponse la multiplication. Tu as sans doute raison c'est pas aussi 'simple'.

[Médiat]

Que signifie "majorant", tu veux dire "un majorant au nombre de structures" ? C'est ça ?

Oui

Holà, ça me parrait bien compliqué quand même. A moins que cette fonction unaire et les deux binaires peuvent être quelconques ? Dans ce cas l'ensemble de ces structures a le cardinal des réels.... si je ne me trompe pas.

C'est bien cela : le nombre d'application d'un ensemble de cardinal dans un ensemble de cardinal est

Tu vois, rien de particulier

[Médiat]

Je me lance : dans le but de définir un ordre sur n élements.

Ce n'est pas la question, car on ne tient pas compte des axiomes.

[Deedee81]

Tu vois, rien de particulier

Me sens moins bête

[Médiat]

Maintenant il va falloir trouver un minorant, c'est moins évident, je donnerai des pistes plus tard ...

[Merlin95]

Ce n'est pas la question, car on ne tient pas compte des axiomes.

Je sais quil y a un résultat 2^n (qui a une démonstration par récurrence d'ailleurs) mais bon.

Vous voulez dire que si on a les éléments 3,5,8,9 par exemple on autorise que :
3+8 = 5
Et
3*8 = 9
(Ou encore même 3*8=5)

Par exemple ?

En gros on s'en fout de + et * ?

[Médiat]

Oui, car on ne cherche pas des modèles, mais des structures qui interprètent le langage (ce qui nous donne un majorant simple à trouver)

[Merlin95]

Ok merci je comprends et même de s on s'en fout un peu (pour l'instant) ?

[Médiat]

Oui, absolument.

Pour résumer :

Il y a façons de choisir qui interprète
Il y a façons de choisir
Il y a façons de choisir
Il y a façons de choisir
Soit façons de choisir une structure

Certaines ne sont pas des modèles, certaines sont isomorphes, mais nous avons un majorant

J'attends des suggestions sur "comment trouver un "bon" minorant" (aucun calcul, aucune formule, juste des idées

[Deedee81]

Maintenant il va falloir trouver un minorant, c'est moins évident, je donnerai des pistes plus tard ...

Toujours sans contrainte ??? Là je vois pas (enfin, à part la même réponse)

[Médiat]

Là c'est un minorant du nombre de modèles, et ma 1ère question est "comment on fait" (sans le faire)

[Deedee81]

Là c'est un minorant du nombre de modèles, et ma 1ère question est "comment on fait" (sans le faire)

D'accord, moins trivial tout de même !

[Médiat]

Pour être honnête je n'attends pas de réponse, à part de connaisseurs, c'est pourquoi la question est juste "comment (quel type d'arguments) peut-on affirmer qu'il y a au moins modèles non isomorphes entre eux"

[Merlin95]

Maintenant avec les axiomes , c'est ça ?

[Merlin95]

On écrit chaque axiome pour un x pour s deux x pour ×, 2 x pour *. Et on multiplie par n pour +, par C^2_n pour * et +. En très gros.

Mais on parle de quels axiomes (de Peano ou mais ils sont pas en nombre infinis (schéma quoi), où alors on se place dans le cas infini maintenant ?) ?

[Merlin95]

On écrit chaque axiome pour un x pour s deux x pour ×, 2 x pour *. Et on multiplie par n pour +, par C^2_n pour * et +. En très gros.

Oubliez ça c'est trop flou.

[Médiat]

Maintenant avec les axiomes , c'est ça ?

Oui

On écrit chaque axiome pour un x pour s deux x pour ×, 2 x pour *

Je n'ai pas compris

. Et on multiplie par n pour +, par C^2_n pour * et +. En très gros.

C'est quoi n ?

Mais on parle de quels axiomes (de Peano ou mais ils sont pas en nombre infinis (schéma quoi), où alors on se place dans le cas infini maintenant ?) ?

On parle de tous les axiomes de Peano, puisque chaque modèle les vérifient tous

[Tryss2]

Axiomes de Peano — Wikipédia (wikipedia.org) l'axiome 2

Qui n'est pas le même dans la version anglaise de la page... du coup, il serait intéressant d'écrire explicitement de quels "Axiomes de Peano on parle" exactement.

[Médiat]

Il s'agit de l'axiome qui dit que seul 0 n'est pas successeur, , le wiki anglais ne le prend pas dans la liste d'axiomes car c'est une conséquence triviale des autres axiomes sur s et du schéma de récurrence, cela revient donc exactement au même.

[Merlin95]

Mais on parle de modèles infinis ou finis j'ai pas assimilé ce point.

[Médiat]

Des modèles finis de AP cela n'existe pas (axiomes de s)

[Merlin95]

Ha oui en effet

[Merlin95]

Si IN est un modèle tout modèle dénombrable non fini peut se mettre en bijection avec IN donc l'application entre l'ensemble de départ et d'arrivée est aussi une bijection. Je tente mais jai p-e pas compris un truc sûrement. Ça me dérangerait un peu il faut démontrer que IN est un modèle c'est p-e pas facile..

[Médiat]

Si IN est un modèle tout modèle dénombrable non fini peut se mettre en bijection avec IN donc l'application entre l'ensemble de départ et d'arrivée est aussi une bijection. Je tente mais jai p-e pas compris un truc sûrement. Ça me dérangerait un peu il faut démontrer que IN est un modèle c'est p-e pas facile..

Tous les ensembles dénombrables peuvent être mis en bijection, par définition ; quant à démontrer que IN est un modèle : renoncez !

[Merlin95]

Pk ? C'est impossible (aujourdhui et/ou à votre connaissance ou catégoriquement) ou très très difficile ?

[Médiat]

On ne sait pas si AP est consistant, donc on ne sait pas si elle a un modèle

[Médiat]

Bonjour,

Quelques explications afin de mettre un peu de glace sur des neurones en surchauffe :

La première idée qui pourrait venir pour compter les modèles dénombrables est de faire un peu comme le calcul de majorant, c'est à dire de compter de combien de façons on peut construire + (pour commencer) tout en s'assurant que deux solutions ne sont pas isomorphes, ceux qui ont essayé cette piste ont dus se rendre compte de la difficulté, qu'ils se rassurent, leurs compétences ne sont pas en jeu :

Théorème de Tennenbaum :
Il n'existe pas de modèle non-standard de l'arithmétique qui soit récursif.

C'est à dire où + et x soit définissable par un humain.

Heureusement il y a une autre technique : construire des ensembles de formules isoconsistants avec AP tels qu'un modèle qui les vérifie et un qui ne les vérifie pas ne puissent être isomorphes.

Je donne un exemple (déjà vu), pour alléger le texte, à partir de maintenant je suppose que AP est consistante (plus la peine de préciser isoconsistante avec AP, consistant suffit)

Pour tout entier standard on note la formule :
La théorie

Nous devons montrer que est consistante, pour cela on va utiliser le théorème de compacité (si toute partie finie d'un ensemble de formules est consistante, alors tout l'ensemble est consistant)

Une partie finie de , contient un n maximal (il n'y a qu'un nombre fini de ), il est clair que IN vérifie cette partie (n+1 par exemple), qui est donc consistante, donc est consistante, donc elle a un modèle qui ne peut pas être IN car dit qu'il existe un élément strictement plus grand que tous les éléments de IN, il ne peuvent être isomorphes, aucun élément de IN ne pouvant avoir pour image un élément plus grand que tous ses éléments.

Je viens de calculer un premier minorant : il y a au moins 2 modèles, mais bien sûr on peut faire beaucoup mieux, il faut trouver des ensembles de formules ...

[gg0]

Bonjour Médiat.

Je ne comprends pas ce passage : " dit qu'il existe un élément strictement plus grand que tous les éléments de IN". Je ne lis pas ainsi, puisque elle dit seulement que pour chaque n, il y a un majorant strict. C'est d'ailleurs ce que tu as employé pour prouver "que IN vérifie cette partie".

Cordialement.