Isomorphisme entre deux modèles de l'arithmétique (2nd ordre)

[nash06]

Bonjour à tous,

J'essaie de montrer (en logique du 2nd ordre) que si on considère un langage constitué d'un symbole de constante c, d'une symbole de fonction unaire S, et deux symboles de fonction binaire + et . on a isomorphisme entre tous les modèles qui satisfont "l'ensemble des formules closes du second ordre satisfaites dans N" où N est la L-structure constituée des entiers naturels avec c=0, et l'interprétation usuelle de fonctions successeurs, addition et multiplication.


Plus précisément, je me suis dit que si je prends un modèle N' de cette théorie, je peux montrer qu'il est isomorphe à N en montrant que N est isomorphe à une sous-structure Ñ' de N' et ensuite utiliser l'axiome d'induction pour montrer que N' est réduit à Ñ'.

Le problème c'est que je sèche un peu pour construire l'isomorphisme entre N et Ñ'.

En effet, si je définis par exemple f(0)=c et f(S(n))=S(f(n)), je n'arrive pas à démontrer que f(x+y)=f(x)+f(y) et f(x.y)=f(x).f(y).


Après, je n'arrive pas à voir si je n'y arrive pas juste parce que je ne vois pas un truc évident ou bien si j'essaie simplement de démontrer un truc impossible à démontrer.


Bref, si quelqu'un avait la gentillesse de me débloquer là-dessus, ce serait vraiment sympa !
Merci d'avance
-----

[Médiat]

Bonjour,

Par récurrence sur y, cela devrait marcher ...

[nash06]

Ah oui effectivement, je crois que je cherchais des choses trop compliquées là où il fallait regarder au plus simple . Merci beaucoup !

[nash06]

Encore une petite chose. J'ai une petite difficulté pour prouver l'injectivité de cette fonction. En fait, j'y arrive en supposant le langage égalitaire (en raisonnant par l'absurde, j'arrive au fait qu'il y a un x de Ñ' tel que S(x)=c, et si le langage est égalitaire on peut écrire une formule qui dise que c'est impossible).

Mais a priori, dans mon énoncé le langage n'est pas égalitaire. Y a-t-il un moyen de prouver l'injectivité de cette fonction f dans le cas d'un langage réduit à {c,S,+,.} ?

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Etes vous sûr que votre langage n'est pas égalitaire ? Sinon comment exprimez-vous les propriétés de S ?

[nash06]

Etes vous sûr que votre langage n'est pas égalitaire ? Sinon comment exprimez-vous les propriétés de S ?

Eh bien... dans l'énoncé il n'est pas précisé que le langage est égalitaire, mais bon, ça peut être un oubli de l'énoncé peut-être. Pour la deuxième partie de votre question, je ne comprends pas bien. S est interprétée dans N comme la fonction successeur usuelle. Y a-t-il besoin d'exprimer des propriétés d'une telle fonction pour qu'elle existe ?

[Médiat]

Pour la deuxième partie de votre question, je ne comprends pas bien. S est interprétée dans N comme la fonction successeur usuelle. Y a-t-il besoin d'exprimer des propriétés d'une telle fonction pour qu'elle existe ?

Vous avez parfaitement raison, mais si vous ne pouvez exprimer les propriétés de S, vous ne pourrez faire aucune démonstration.

[nash06]

Ah oui je crois que je vois. Est-ce que ça voudrait dire que sans égalité on ne peut pas prouver que les deux modèles sont isomorphes ?

[Médiat]

Bonjour,

J'ai un peu réfléchi à votre question, sous réserve de vérifications il me semble que démontrer qu'une application entre deux modèles dont vous ne connaissez que ce qui en fait des modèles utilise forcément l'égalité du langage pour l'injectivité, puisque pour déduire quoi que ce soit de , vous ne pouvez utiliser que les éléments du langage.

Quand les deux modèles sont connus, le problème est différent, par exemple, pour montrer que est un isomorphisme de dans pour langage réduit à (<), il n'est pas utile d'utiliser l'égalité du langage ni même le < du langage, les propriétés connues de sont suffisantes.

[nash06]

Bonjour,

Effectivement la première partie de votre réponse semble assez logique. En tout cas, merci pour toutes vos réponses.