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
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
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour le point 2) je n'en ai aucune idée.
"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 ?
"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 ?
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 !