Théorème d'Ehrenfeucht-Mostowski — Les-mathematiques.net The most powerful custom community solution in the world

Théorème d'Ehrenfeucht-Mostowski

Salut à tous,

J'ai pas mal de problèmes avec la preuve ci-dessous. Pour tout dire je l'ai pompée sur des notes de cours prises il y a quelques années par un étudiant qui visiblement ,n'était pas très zélé en théorie des modèles (mais je ne le suis guère non plus). Venons-en au fait.

Théorème (Ehrenfeucht-Mostowski) : Soit $T$ une $\mathscr L$-théorie du premier ordre qui admet au moins un modèle infini. Alors, pour tout ordre total $(X,<)$, il existe un modèle $\mathscr U$ de $T$, contenant $X$, tel que $X$ soit un ensemble d'indiscernables pour $\mathscr U$.


Preuve : On étend le langage $\mathscr L$ en $\mathscr L'$ en ajoutant une constante $c_x$ pour tout $x \in X$. On construit une nouvelle théorie $T'$ obtenue comme la collection de tous les axiomes suivants :
$\to$ Tous les axiomes de $T$.
$\to$ Tous les axiomes du type $(x,y \in X \land x \neq y) \Rightarrow c_x \neq c_y$.
$\to$ Tous les axiomes de la forme
$$\varphi(c_{x_1},...,c_{x_n}) \Leftrightarrow \varphi(c_{y_1},...,c_{y_n}) \text{ pour } (x_i),(y_i) \in X, x_1<...<x_n,y_1<...<y_n$$
et $\varphi$ formule.
On va voir que $T'$ est consistante. Soit $T_0$ une partie finie de $T'$. On note $\mathscr L_0$ le langage de $T_0$, i.e. l'ensemble des symboles qui apparaissent dans $T_0$. Par ailleurs, soit $m$ le nombre (fini) de nouvelles constantes dans $\mathscr L_0$ : on les note $c_{a_1},...,c_{a_m}$ avec $a_1<...<a_m$.
Soit $\mathcal{M} = (M,...)$ un modèle infini de $T$. Sans perte de généralité, on peut supposer que $\omega \subseteq M$. Pour tout entier $k$, on pose
$$\Phi_k= \{\varphi : \exists x_1<...<x_k, \exists y_1<...<y_k, \text{"} \varphi(c_{x_1},...,c_{x_k}) \Leftrightarrow \varphi(c_{y_1},...,c_{y_k}) \text{"} \in T_0\}.$$
Enfin, on note $\Phi = \bigcup \limits_{k \in \omega} \Phi_k$. Il est clair que $\Phi$ est fini.
Pour $k \leq m$, on définit un coloriage $f_k : [\omega]^k \to \mathscr P(\Phi_k)$ en posant, pour
$n_1<...<n_k$ :
$$f_k(\{n_1,...,n_k\})= \{\varphi \in \Phi_k : \mathcal{M} \models \varphi(n_1,...,n_k)\}.$$
Par le théorème de Ramsey, il existe un sous-ensemble infini $H \subseteq \omega$ tel que $f \upharpoonright [H]^k$ soit constante égale à $\Phi_k$ pour tout $k$. On énumère alors $H$ dans l'ordre croissant : $H=\{n_1,...,n_j,...\}$. Soit
$$\mathcal{M}_0 = \left \langle \mathcal{M}, (c_{a_i}^{\mathcal{M}_0}=n_i)_{i=1,...,m} \right \rangle.$$
$\mathcal{M_0}$ est un modèle de $T_0$, et donc $T_0$ est consistante. Par compacité, $T'$ elle-même est consistante.

Soit $\mathcal{N}=(N,...)$ un modèle de $T'$. On peut écrire $X= \{c_x^{\mathcal{N}} : x \in X\}$, où on a interprété les $c_x$ par des éléments $c_x^{\mathcal{N}}$ de $X$ avec la condition $c_x^{\mathcal{N}} < c_y^{\mathcal{N}} \Leftrightarrow x<y$. Alors, $X$ est un ensemble infini d'indiscernables pour $\mathcal{N}$, et donc le réduit de $\mathcal{N}$ au langage $\mathscr L$ est un modèle de $T$ pour lequel $X$ est un ensemble d'indiscernables.



Ce que je ne comprends pas c'est la phrase qui commence par "Par le théorème de Ramsey". Il y a 2 trucs qui me gênent :
1) Dans la mesure où $\mathscr P(\Phi_k)$ est fini, il me semble qu'on n'a pas besoin de Ramsey, le principe des tiroirs suffit. (Bon, ça, c'est un détail).
2) Beaucoup plus grave : je suis d'accord pour l'existence d'un ensemble homogène infini, mais pourquoi diable la constante serait-elle forcément égale à $\Phi_k$ tout entier ?

Merci d'avance

Martial

Réponses

  • Le point 1) est vraiment une application du théorème de Ramsey, pas seulement le principe des tiroirs. Certes $[\omega]^k$ est infini et $\mathcal P(\Phi_k)$ est fini, donc $f$ est constante sur une partie infinie de $[\omega]^k$, mais qu'est-ce qui te garantit qu'une telle partie est de la forme $[H]^k$ ?

    Pour le point 2) je n'en ai aucune idée.
  • @Poirot : bien joué, merci ! C'est le genre de subtilités qui n'a aucun mal à m'échapper...
  • Bon, j'ai un peu avancé mais ce n'est pas encore ça. En fait la même preuve figure dans Kanamori, page 100. Je recopie le passage qui m'intéresse, en adaptant les notations pour qu'elles correspondent à ce que j'ai écrit ci-dessus :

    "Comme $T_0$ est fini, l'image de $f_k$ est finie, donc en appliquant $m$ fois le théorème de Ramsey il existe $H \in [\omega]^{\omega}$ qui est homogène pour chaque $f_k$". (Jusque là, OK).

    "Hence, $\mathcal{M}$ satisfies $T_0$ with any $m$ elements of $\{a_i : i \in H\}$ assigned to the new constants appearing in $T_0$ in corresponding increasing order".

    C'est cette dernière phrase qui me pose problème : que veut-il dire exactement ?
  • C'est la définition du fait que $f_k$ est constante sur $[H]^k$ pour tout $k \leq m$.
  • @Poirot : oui, tu as raison, c'est trivial, merci. Maintenant ce que je me demande c'est comment traduire ça proprement en français :

    "Donc, $\mathcal{M}$ satisfait $T_0$ : il suffit d'interpréter chacune des $m$ nouvelles constantes apparaissant dans $T_0$ par n'importe quels $m$ éléments de $\{a_i \mid i \in H\}$ en respectant l'ordre."

    Ça te paraît tenir la route ?
  • Ça me paraît très bien comme ça.
  • Merci Poirot, tu me rassures. Finalement je crois que pour mon paragraphe sur $0^{\#}$ je vais suivre Kanamori, ça me paraît plus sûr. Et au besoin j'irai chercher le reste de l'information dans le Jech, le Dehornoy, le Cantor's Attic et toutim.

    Pour la petite histoire, il y a une série de 4 volumes sur zero-sharp, disponibles seulement en allemand, dont voici la liste des auteurs : René Daumal, René Crevel, Michel Carrouges, Harry Mathews et Georges Perec.

    Trouver l'erreur !
  • Bientôt un 5ème volume de Martial L. ? :-D
  • @Poirot : un 5ème volume, peut-être, mais pas en allemand, lol.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!