Savoir & Culture

Je ne suis pas sûr qu'il reste beaucoup de logiciens sur ce forum, néanmoins je tente ma chance !

J'essaie de classifier les modèles de $T=Th(\mathbb{N}, s,0)$, la théorie des ensembles naturels avec la fonction successeur (plus précisément, l'ensemble des phrases du premier ordre sur la signature $\{s,0\}$ étant vraies dans $\mathbb{N}$).

Il est facile de montrer que si $\mathcal{M}$ est un modèle de $T$, alors sa fonction $s^{\mathcal{M}}$ doit être injective et presque surjective (dans le sens où tous les éléments sauf $0^\mathcal{M}$ ont un antécédent).

Ainsi, on en déduit qu'à isomorphisme près, $\mathcal{M}$ est nécessairement de la forme $\mathcal{M}_\kappa$, consistant en une copie de $\mathbb{N}$ ainsi que de $\kappa$ copies de $\mathbb{Z}$, l'ensemble des entiers relatifs, $\kappa$ étant un cardinal.

Il reste maintenant à prouver que chaque $\mathcal{M}_\kappa$ est effectivement un modèle de $T$, c'est-à-dire qu'il vérifie exactement les mêmes phrases (du premier ordre) que $\mathbb{N}$.

Alors, les logiciens qui passeront ici vont immédiatement penser "Ben oui, c'est évident, en utilisant les jeux d'Ehrenfeucht-Fraïssé.. !", et je suis d'accord : c'est évident quand on utilise les jeux d'Ehrenfeucht-Fraïssé, et donc on a notre classification. Terminé.

SAUF QUE il se trouve que j'ai trouvé cet exercice dans un livre, et que celui-ci ne mentionne à aucun moment les jeux d'EF. Je me dis donc qu'il doit exister un autre argument, possiblement très élégant.

En particulier, je me suis dit qu'on pouvait certainement montrer que $\mathbb{N}$ était une sous-structure élémentaire de $\mathcal{M}_\kappa$, via le test de Tarski-Vaught.

Supposons que $\varphi(x,y)$ soit une formule du premier ordre et $n$ un entier naturel tel que $\mathcal{M}_\kappa\vDash\varphi(n,a)$, où $a$ est un élement de $\mathcal{M}_\kappa$, et essayons donc de montrer qu'il existe en fait un $a$ dans $\mathbb{N}$ tel que que cela est aussi vrai.

(Oui, je sais, dans le test de TV, $x$ n'est pas seulement une variable, mais un tuple de variable, mais ce n'est pas grave ici, le raisonnement se généraliserait.)

En remplaçant dans $\varphi$ la variable $x$ par le terme $s(s(\cdots s(0) \cdots))$, où $s$ apparaît $n$ fois, alors on obtient une formule $\psi_n(y)$ tel que $\mathcal{M}_\kappa$ vérifie la phrase $\exists y.~\psi_n(y)$.

Et ensuite... ?? Où que je veuille aller ensuite, j'utilise de force les jeux d'EF... L'auteur du livre aurait-il oublié de les mentionner ?!

La bise.

Dans quel bouquin as-tu trouvé ton exercice ?

Models of Peano Arithmetic, de Richard Kaye.

C'est le dernier exercice du premier chapitre, dans l'édition de 2011.

C'est d'ailleurs un livre passionant !, pour peu qu'on ait un attrait pour ce genre de sujet.

Bon, je crois que j'ai trouvé une preuve qui n'utilise pas EF. Je regarderai les détails ce soir, pour vérifier qu'il n'y a pas d'erreur, et si c'est bien le cas, alors je la posterai ici.

Nonobstant, elle ne m'avance pas beaucoup, car elle fait appel à un lemme reliant FO et la notion d'isomorphisme, et cela non plus n'apparaît pas dans le livre.

Le 15 octobre 2022 à 15:25:26 :
Bon, je crois que j'ai trouvé une preuve qui n'utilise pas EF. Je regarderai les détails ce soir, pour vérifier qu'il n'y a pas d'erreur, et si c'est bien le cas, alors je la posterai ici.

Nonobstant, elle ne m'avance pas beaucoup, car elle fait appel à un lemme reliant FO et la notion d'isomorphisme, et cela non plus n'apparaît pas dans le livre.

"FO" pour "First Order" ?

Oui pardon.

Pareil j'imagine que "TV" ça correspond au test de Tarski-Vaught ! J'ai pensé un peu à ce genre de trucs puisque tu parles de "sous-structures élémentaires" (t'as aussi le théorème de réunion de chaînes de Tarski je crois) ... D'ailleurs, à cause de tous ces noms, je confonds parfois avec le test de Los-Vaught !

Oui, mais ça je l'ai défini dans mon post original.

Celui des chaînes de Tarski je ne connais pas nonobstant. Tu as un lien ?

Ayaaa il y a une erreur dans ma preuve. C'est pas possible.

Cependant, je vais quand même finir de la rédiger, car elle fonctionne tout de même lorsque $\kappa$ est infini, ce qui est curieux.

Bon, c'est parti. Montrons, sans utiliser les jeux d'Ehrenfeucht-Fraïssé, que $\mathcal{M}_\kappa$ est un modèle de $T=Th(\mathbb{N},s,0)$ lorsque $\kappa$ est un cardinal infini.

Déjà, on peut prouver que :

Lemme 1 : Il existe un cardinal $\kappa'\geq\kappa$ tel que $\mathcal{M}_\kappa'$, lui, est bien un modèle de $T$.

Preuve : On considère pour chaque $i\in\kappa$, un nouveau symbole $c_i$ de constante, et $T_\kappa$ la théorie $T\cup \bigcup_{i\in\kappa}A_i\cup\bigcup_{i\neq j\in\kappa}B_{i,j}$, où :
- pour chaque $i$, $A_i$ exprime que $c_i$ n'est pas un entier naturel standard, c'est l'ensemble des formules de la forme $\neg s(\cdots (s(0))= c_i$, où le symbole $s$ apparaît un certain nombre $n\in\mathbb{N}$ de fois;
- pour chaque $i,j$ distincts, $B_{i,j}$ exprime que $c_i$ et $c_j$ se trouvent dans différentes copies de $\mathbb{Z}$, c'est l'ensemble des formules d'une de ces deux formes : $\neg s(\cdots (s(c_i))= c_j$, ou $\neg s(\cdots (s(c_j))= c_i$, avec $s$ apparaît un certain nombre $n\in\mathbb{N}$ de fois.

Il est facile de voir qu'un sous-ensemble fini de $T_\kappa$ est satisfait dans $\mathbb{N}$, avec les $c_i$ étant interprétés en des entiers suffisamment espacés. Ainsi, par le théorème de compacité, $T_\kappa$ admet un modèle $\mathcal{M}$. Ce modèle $\mathcal{M}$ est bien un modèle de $T$ (car $T\subseteq T_\kappa$), et est donc nécessairement de la forme $\mathcal{M}_\kappa'$, avec $\kappa'$ un certain cardinal. De plus, $\mathcal{M}$ contenant au moins $\kappa'$ copies distinctes de $\mathbb{Z}$ (par construction), on a $\kappa\leq\kappa'$. $\Box$

Jusqu'à la fin de ce post, on considère donc un tel modèle $\mathcal{M}_\kappa'$ de $T$, où $\kappa'$ est un cardinal plus grand que $\kappa$. Notre modèle $\mathcal{M}_\kappa$ est une sous-structure de $\mathcal{M}_\kappa'$, il nous reste à prouver que c'est en fait une sous-structure élémentaire : elle satisfait exactement les mêmes phrases, c'est-à-dire $T$.

Maintenant, deuxième lemme important :

Lemme 2 : Soit $\varphi(x_0,\dots, x_{k-1},y)$ une formule, $a_0,\ldots, a_{k-1}$ $k$ éléments de $\mathcal{M}_\kappa'$, et $b,c$ deux éléments de $\mathcal{M}_\kappa'$ se trouvant dans une copie de $\mathbb{Z}$ ne comprenant aucun $a_i$. Alors on a $\mathcal{M}_\kappa'\vDash\varphi(a_0,\ldots,a_{k-1},b)$ si et seulement si $\mathcal{M}_\kappa'\vDash\varphi(a_0,\ldots,a_{k-1},c)$.

Preuve : Il suffit de remarquer qu'il existe un automorphisme de $\mathcal{M}_\kappa'$ envoyant $b$ sur $c$ et conservant les valeurs de chaque $a_i$. Ensuite, il est connu que FO (et même MSO) est invariant par automorphisme. $\Box$

Ce qui nous permet de prouver ce dernier lemme :

Lemme 3 : Soit $\varphi(x_0,\dots, x_{k-1},y)$ une formule $a_0,\ldots, a_{k-1}$ $k$ éléments de $\mathcal{M}_\kappa$. Alors on a l'implication suivante : s'il existe $b\in\mathcal{M}_\kappa'$ tel que $\mathcal{M}_\kappa'\vDash\varphi(a_0,\ldots,a_{k-1},b)$, alors il existe un $c\in\mathcal{M}_\kappa$ tel que $\mathcal{M}_\kappa'\vDash\varphi(a_0,\ldots,a_{k-1},c)$.

Preuve : Étant donné que $\mathcal{M}_\kappa$ admet une infinité de copies de $\mathbb{Z}$, il en existe bien une à laquelle n'appartient aucun des $a_i$. On peut prendre $c$ se trouvant dans une de ces copies, et conclure avec le Lemme 2. $\Box$

Ainsi, le test de Tarski-Vaught est satisfait pour $\mathcal{M}_\kappa\subseteq\mathcal{M}_\kappa'$, et on peut conclure.

Le 15 octobre 2022 à 22:24:10 :
Oui, mais ça je l'ai défini dans mon post original.

Celui des chaînes de Tarski je ne connais pas nonobstant. Tu as un lien ?

https://people.math.sc.eddu/mcnulty/762/modeltheory.pdf va en lecture 5 !

+ d'autres liens pépites avec tous les résultats de base en théorie des modèles pour la culture : http://www.math.toronto.edu/weiss/model_theory.pdf et un plus avancé : http://www.math.toronto.edu/rossman/hpt-jacm.pdf ... Les trucs de préservation ont un lien avec les formes de Herbrand/Skolem sûrement ...

(Dans mon post précédent, je voulais bien sûr écrire $\mathcal{M}_{\kappa'}$, et non pas $\mathcal{M}_\kappa'$.)

Bon, autre solution : montrer que $T$ admet l'élimination des quantificateurs (pas regardé dans tous les détails techniques, mais ça le fait). Ainsi, une formule $\exists y.~\varphi(x_0,\dots,x_{k-1},y)$ est équivalente à une formule $\psi(x_0,\dots,x_{k-1})$. Le test de TV est ainsi trivialement vérifié.

Mais bon, ça implique connaître la notion d'élimination des quantificateurs, pas idéal pour un DM.

Sapristi, ça veut dire que chaque sous-structure $\mathcal{M}$ d'une structure $\mathcal{N}$ satisfaisant une théorie décidable est en fait élémentaire ?! Bien ma grotte ?!

Merci pour les liens. Je vais particulièrement lire le dernier.

La pure théorie des modèles, c'est vraiment ma passion. J'aimerais bien faire de la recherche dessus, mais je ne saurais pas par où commencer. Je n'ai pas (encore) de contacts dans ce domaine.

Le 16 octobre 2022 à 13:08:03 :

Merci pour les liens. Je vais particulièrement lire le dernier.

La pure théorie des modèles, c'est vraiment ma passion. J'aimerais bien faire de la recherche dessus, mais je ne saurais pas par où commencer. Je n'ai pas (encore) de contacts dans ce domaine.

C'est un domaine ultra-vaste c'est vrai ! Même si dans le domaine de la "logique" c'est loin d'être ma partie préférée (trop de notions à retenir même si les raisonnements sont presque tlt les mêmes ...). Faudrait que t'arrives déjà à cibler une partie qui te fait vraiment kiffer et ensuite voir avec des profs de master qui travaillent dans la-dite partie s'ils peuvent t'encadrer !

... Je suis docteur...

(Mea culpa dans le post précédent : une théorie peut être décidable sans admettre l'élimination des quantificateurs.)

Le 16 octobre 2022 à 16:10:25 :
... Je suis docteur...

(Mea culpa dans le post précédent : une théorie peut être décidable sans admettre l'élimination des quantificateurs.)

Ah ...

J'ai trouvé.

Directement avec le test de Tarski-Vaught, et sans automorphisme !

Soit $\varphi(x_0,\ldots,x_{k-1},y)$ une formule, et soient $n_0,\ldots,n_{k-1}$ des entiers naturels. On suppose qu'il existe $a\in\mathcal{M}_\kappa$ tel que $\mathcal{M}_\kappa\vDash\varphi(n_0,\ldots,n_{k-1},a)$.

En réécrivant $\varphi$ en DNF, en remplaçant chaque variable $x_i$ par le terme $s(\cdots s(0))$ avec $n_i$ symboles, et enfin en simplifiant les $s$ des différentes égalités obtenues, on obtient que l'élément $a$ vérifie une certaine conjonction de formules atomiques de la forme $y = s(\cdots s(0))$ et $\neg y = s(\cdots s(0))$.

Si au moins un desdits atomes est de la première forme, alors $a$ est nécessairement un entier. Si en revanche tous les atomes sont de la seconde forme, alors la conjonction sera également vraie pour $n$ étant un nombre entier assez grand (typiquement, le maximum de $s$ apparaissant dans un des atomes, plus un).

Dans les deux cas, on est bon, et la satisfaction du test nous permet de conclure que $\mathbb{N}$ est une sous-structure élémentaire de $\mathcal{M}_\kappa$.

Ah mais non ayaaaa.

Ça marche seulement si $\varphi$ est sans quantificateur. Qu'est-ce qui m'a pris de passer outre ce détail ?!

Bon, ben, sans ça, on retombe à ma preuve d'élimination des quantificateurs. Tellement décevant sapristi.

Tu te souviens de la L-théorie des bijections sans cycles (où L est constitué d'un symbole de fonction 1-aire) khey ?

Non, c'est quoi ?