Théorie des Modèles et la Propriété d’Indépendance

EST training workshop, 5–9 séptembre 2005

Frank Wagner

Institut Camille Jordan Université Lyon 1 21, avenue Claude Bernard 69622 Villeurbanne cedex France

    wagner@math.univ-lyon1.fr
http://igd.univ-lyon1.fr/home/wagner/fowaf.html

1. Langage et structure

Définition 1. Un langage L est l’union (disjointe) d’un ensemble C de symboles de constantes, d’un ensemble F de symboles de fonctions, et d’un ensemble R de symboles de relations. A chaque f ∈ F et chaque R ∈ R est associé un entier, l’arité, qui indique le nombre d’arguments.

Définition 2. Soit L un langage. La collection des L-termes est défini récursivement par : • toute constante et toute variable est un L-terme.

• si f ∈ F est une fonction n-aire et t_{1}, …, t_{n} sont des L-termes, alors f(t_{1}, …, t_{n}) est un L-terme. Une L-formule atomique est une expression de la forme R(t_{1}, …, t_{n}), où R ∈ R est une relation n-aire et t_{1}, …, t_{n} sont des L-termes. La collection des L-formules est défini récursivement par :

• une L-formule atomique est une L-formule.

• si φ et ψ sont des L-formules, leurs combinaisons booléennes (φ ∧ ψ) (conjonction, et), (φ ∨ ψ) (disjonction, ou) et ¬φ (négation, non) sont des L-formules.

• si φ est une L-formule et x est une variable, les quantifications ∀xφ (universelle, quel que soit) et ∃xφ (existentielle, il y a) sont des L-formules. Les occurrences de la variable x dans ces formules sont liées à ce quanteur ∀ ou ∃ (sauf si elles sont déjà liées à un quanteur dans φ). Une variable qui n’est pas liée est libre.

Un énoncé, ou une formule close, est une formule sans variable libre.

Lemme 3. [Lecture unique] Tout terme et toute formule se construit de manière unique.

Définition 4. Soit L un langage. Une L-structure 𝔐 est un ensemble M, le domaine de 𝔐, et • pour chaque symbole c ∈ C un élément c^{𝔐} ∈ M.

• pour chaque symbole f ∈ F d’arité n une fonction f^{𝔐} : M^{n} → M.

• pour chaque symbole R ∈ R d’arité n un sous-ensemble R^{𝔐} de M^{n}.

Souvent on confond M et 𝔐, c et c^{𝔐}, f et f^{𝔐}, et R et R^{𝔐}. L’interprétation t(m̄)^{𝔐} d’un terme t(x̄) à paramètres m̄ dans une structure 𝔐 est défini itérativement.

Définition 5. La satisfaction d’une formule close avec paramètres dans 𝔐 récursivement par : • si φ(m̄) est R(t_{1}(m̄), …, t_{n}(m̄)) est une formule atomique, où R ∈ R est une relation n-aire et t_{1}, …, t_{n} sont des termes, alors φ(m̄) est satisfaite dans 𝔐 si (t_{1}(m̄)^{𝔐}, …, t_{n}(m̄)^{𝔐}) ∈ R^{𝔐}.

• si φ est (φ_{1} ∧ φ_{2}), alors φ est satisfaite dans 𝔐 si φ_{1} et φ_{2} sont satisfaites dans 𝔐.

• si φ est (φ_{1} ∨ φ_{2}), alors φ est satisfaite dans 𝔐 si φ_{1} ou φ_{2} (ou bien les deux) est satisfaite dans 𝔐.

• si φ est ¬ψ, alors φ est satisfaite dans 𝔐 si ψ n’est pas satisfaite dans 𝔐.

• si φ est ∀xψ(x), alors φ est satisfaite dans 𝔐 si pour tout m ∈ M la formule ψ(m) est satisfaite dans 𝔐.

• si φ est ∃xψ(x), alors φ est satisfaite dans 𝔐 s’il y a un m ∈ M tel que ψ(m) est satisfaite dans 𝔐.

Si φ(m̄) est satisfaite (ou vraie) dans 𝔐, on le dénote par 𝔐 ⊧ φ(m̄) ; on dit également que m̄ satisfait (ou réalise) φ(x̄) dans 𝔐, et on écrit m̄ ⊧_{𝔐} φ(x̄). On pose φ^{𝔐} = {m̄ ∈ M^{|x̄|} : 𝔐 ⊧ φ(m̄)}.

Convention 6. L’égalité fera partie de tous les langages, et sera toujours interpretée par la vraie égalité.

Si Φ est un ensemble d’énoncés et 𝔐 une L-structure, on écrit 𝔐 ⊧ Φ si 𝔐 ⊧ φ pour tout φ ∈ Φ ; on dit que 𝔐 est un modèle de Φ.

Définition 7. Soient Φ un ensemble de L-énoncés, et φ(x̄) et ψ(x̄) deux L-formules. On dit que φ(x̄) implique ψ(x̄) modulo Φ si pour tout modèle 𝔐 de Φ et tout m̄ ∈ M, si 𝔐 ⊧ φ(m̄), alors 𝔐 ⊧ ψ(m̄). Deux formules φ(x̄) et ψ(x̄) sont équivalentes modulo Φ si φ implique ψ et ψ implique φ modulo Φ.

Si Φ est vide, il est omis.

Lemme 8. Pour toutes φ et ψ, les formules suivantes sont équivalentes :

• φ et ¬¬φ.

• ¬(φ ∧ ψ) et (¬φ ∨ ¬ψ), ainsi que ¬(φ ∨ ψ) et (¬φ ∧ ¬ψ) (de Morgan).

• ∀x¬φ et ¬∃xφ, ainsi que ∃x¬φ et ¬∀xφ.

Corollaire 9. Toute formule est équivalente à une formule qui n’utilise qu’un des deux connecteurs booléens, et qu’un des deux quanteurs.

Nous utiliserons aussi les abbréviations suivantes : (φ → ψ) pour (¬φ ∨ ψ), et (φ ↔ ψ) pour ((φ → ψ) ∧ (ψ → φ)). A partir d’ici on va supprimer les parenthèses superflues. On notera ⋀_{i≤n} φ_{i} une conjonction φ_{0} ∧ ⋯ ∧ φ_{n}, et ⋁_{i≤n} φ_{i} une disjonction φ_{0} ∨ ⋯ ∨ φ_{n}.

Définition 10. Un ensemble Φ de L-énoncés élimine les quanteurs si modulo Φ toute formule est équivalente à une formule sans quanteurs.

Proposition 11. Pour qu’un ensemble Φ élimine les quanteurs, il suffit que toute formule de la forme ∃x φ(x), où φ est sans quanteurs, soit équivalente modulo Φ à une formule sans quanteurs.

2. Equivalence élémentaire et sous-structures élémentaires

Définition 12. Une L-théorie T est un ensemble consistant de L-énoncés (qui a un modèle) ; elle est complète si pour chaque énoncé φ soit tout modèle de T satisfait φ, soit tout modèle satisfait ¬φ.

Donc une L-théorie est complète si et seulement si pour tout L-énoncé φ, soit T ⊧ φ, soit T ⊧ ¬φ. Si 𝔐 est une L-structure et A un ensemble d’éléments dans M, la L(A)-théorie de 𝔐, notée Th(𝔐, A), est l’ensemble de tous les énoncés à paramètres dans A qui sont satisfaits par 𝔐. Il est évident que c’est une théorie complète. On pose Th(𝔐) := Th(𝔐, ∅).

Définition 13. Deux L-structures 𝔐 et 𝔑 sont élémentairement équivalentes, ce qui est noté 𝔐 ≡ 𝔑, si elles satisfont les mêmes énoncés.

Définition 14. Soient 𝔐 et 𝔑 deux L-structures. 𝔐 est une sous-structure de 𝔑, notée 𝔐 ⊆ 𝔑, si • M ⊆ N ;

• c^{M} = c^{N} pour tout c ∈ C ;

• f^{𝔐} = f^{𝔑} ↾_{M^{n}} pour tout f ∈ F n-aire, et tout n < ω ; et

• R^{𝔐} = R^{𝔑} ∩ M^{n} pour tout R ∈ R n-aire, et tout n < ω. 𝔐 est une sous-structure élémentaire de 𝔑 si pour toute énoncé φ(m̄) à paramètres dans 𝔐 on a 𝔐 ⊧ φ(m̄) si et seulement si 𝔑 ⊧ φ(m̄). On dénote cette condition par 𝔐 \underline{≺} 𝔑.

Si 𝔐 \underline{≺} 𝔑, on dit que 𝔑 est une extension élémentaire de 𝔐.

Remarque 15. Si M ⊆ N est un ensemble qui contient les constantes et est clos par toutes les fonctions, alors les restrictions à M des relations de 𝔑 y induisent une L-sous-structure 𝔐.

Lemme 16. Soit (𝔐_{i} : i < ω) une chaîne élémentaire de L-structures (𝔐_{i} \underline{≺} 𝔐_{i+1} pour tout i < ω). La réunion 𝔐 = ⋃_{i<ω} 𝔐_{i} est canoniquement une L-structure qui satisfait 𝔐_{i} \underline{≺} 𝔐 pour tout i < ω.

Démonstration : Soit M = ⋃_{i<ω}. On définit une L-structure 𝔐 sur M comme suit : • c^{𝔐} = c^{𝔐_{0}} pour tout c ∈ C ; on notera que 𝔐_{0} \underline{≺} 𝔐_{i} pour tout i < ω par l’exercice précédant, et donc c^{𝔐} = c^{𝔐_{i}} pour tout i < ω.

• f^{𝔐}(m̄) = f^{𝔐_{i}}(m̄) si m̄ ∈ M_{i}, pour tout f ∈ F (d’arité n, disons) ; comme f^{𝔐_{i}} = f^{𝔐_{j}} ↾ M_{i}^{n} pour i < j, ceci est bien défini et f^{𝔐_{i}} = f^{𝔐} ↾ M_{i}^{n} pour tout i < ω.

• R^{𝔐} = ⋃_{i<ω} R^{𝔐_{i}} pour tout R ∈ R (d’arité n, disons) ; comme R^{𝔐_{i}} = R^{𝔐_{j}} ∩ M_{i}^{n} pour i < j, ceci définit une relation sur M^{n} telle que R^{𝔐_{i}} = R^{𝔐} ∩ M_{i}^{n} pour tout i < ω.

Par construction 𝔐_{i} est une sous-structure de 𝔐 pour tout i < ω. Supposons que 𝔐 ⊧ ∃x φ(x, m̄), où φ(x, m̄) est une formule à paramètres dans 𝔐_{i}. Donc il y a m_{0} ∈ M tel que 𝔐 ⊧ φ(m_{0}, m̄), et il y a j ≥ i tel que m_{0} ∈ M_{j}. Par récurrence 𝔐_{j} ⊧ φ(m_{0}, m̄), d’où 𝔐_{j} ⊧ ∃x φ(x, m̄). Comme 𝔐_{i} \underline{≺} 𝔐_{j}, on a 𝔐_{i} ⊧ ∃x φ(x, m̄) ; ceci montre que l’inclusion est élémentaire. □

Proposition 17. Test de Tarski Soit 𝔐 une sous-structure de 𝔑. Alors 𝔐 \underline{≺} 𝔑 si et seulement si pour toute formule φ(x) à paramètres dans 𝔐, si 𝔑 ⊧ ∃x φ(x), alors il y a m ∈ 𝔐 tel que 𝔑 ⊧ φ(m).

Démonstration : Si 𝔐 \underline{≺} 𝔑 et 𝔑 ⊧ ∃x φ(x), alors 𝔐 ⊧ ∃x φ(x) et on trouve m ∈ M tel que 𝔐 ⊧ φ(m), d’où 𝔑 ⊧ φ(m). Pour le réciproque, nous supposerons que le critère soit satisfait. Nous démontrerons par induction sur le nombre de symboles logiques d’un énoncé φ à paramètres dans 𝔐 que 𝔐 ⊧ φ si et seulement 𝔑 ⊧ φ. Comme 𝔐 est une sous-structure de 𝔑, il suffit de traiter le cas d’un quanteur existentiel. Supposons donc que 𝔐 ⊧ ∃x φ(x, m̄). Alors il y a m_{0} ∈ 𝔐 tel que 𝔐 ⊧ φ(m_{0}, m̄). Par hypothèse de récurrence 𝔑 ⊧ φ(m_{0}, m̄), d’où 𝔑 ⊧ ∃x φ(x, m̄). Réciproquement, si 𝔑 ⊧ ∃x φ(x, m̄), alors par hypothèse il y a m_{0} ∈ 𝔐 tel que 𝔑 ⊧ φ(m_{0}, m̄). Par hypothèse de récurrence 𝔐 ⊧ φ(m_{0}, m̄), et 𝔐 ⊧ ∃x φ(x, m̄). □

Définition 18. Soit T une L-théorie. Pour chaque L-formule φ(x, ȳ) considérons un nouveau symbole de fonction f_{φ}(ȳ), et posons

L_{Skolem} = L ∪ {f_{φ} : φ une L-formule}.

La skolemisation T_{Skolem} de T est la théorie suivante :

T ∪ {∃x φ(x, ȳ) → φ(f_{φ}(ȳ), ȳ) : φ une L-formule}.

Les f_{φ} s’appellent fonctions de Skolem pour la théorie T.

Lemme 19. La skolemisation d’une théorie consistante est consistante. Plus précisement, tout modèle de T a une expansion à un modèle de T_{Skolem}.

Les fonctions de Skolem n’ont rien de canonique ; leur existence est une conséquence de l’axiome du choix. On appelle 𝔐_{Skolem} une skolemisation de 𝔐.

Lemme 20. Soit 𝔑 une structure, et A ⊆ N. La clôture M de A par toutes les constantes, toutes les fonctions dans F et toutes les fonctions de Skolem est une sous-structure élémentaire 𝔐 de 𝔑.

Corollaire 21. Löwenheim-Skolem descendant Soit 𝔑 une L-structure infinie, A ⊆ N, et λ un cardinal infini avec |A| + |L| ≤ λ ≤ |N|. Alors il y a une sous-strucure élémentaire 𝔐 \underline{≺} 𝔑 contenant A de cardinal λ.

Démonstration : On peut supposer que |A| = λ. Choisissons une skolemisation de 𝔑, et considérons la clôture M de A sous les fonctions de F et les fonctions de Skolem. Comme il y a |L| + ℵ_{0} formules et donc fonctions de Skolem, |M| = |A| = λ ; par le lemme précédent 𝔐 \underline{≺} 𝔑. □

3. La compacité

Théorème 22. Compacité Un ensemble d’énoncés finiment consistant est consistant.

Lemme 23. Si Φ est finiment consistant et φ est un énoncé, alors soit Φ ∪ {φ}, soit Φ ∪ {¬φ} est finiment consistent.

Lemme 24. La réunion d’une chaîne croissante d’ensembles d’énoncés Φ_{i} finiment consistants est finiment consistant.

Lemme 25. Tout ensemble Φ d’énoncés finiment consistant peut etre completé en un ensemble Φ̄ ⊇ Φ d’énoncés finiment consistant, tel que pour tout énoncé φ soit φ ∈ Φ̄, soit ¬φ ∈ Φ̄.

Démonstration : On énumère les L-énoncés comme φ_{0}, φ_{1}, φ_{2}, …, et on pose Φ_{0} := Φ. Supposons qu’on ait trouve Φ_{i} tel que pour tout j < i soit φ_{j} ∈ Φ_{i} soit ¬φ_{j} ∈ Φ_{i}. Alors par le lemme 23 soit Φ_{i} ∪ {φ_{i}}, soit Φ_{i} ∪ {¬φ_{i}} est finiment consistant, et on trouve Φ_{i+1}. Aux étapes limites, on prend la réunion ; à la fin la réunion de tous les Φ_{i} donne l’ensemble Φ̄ recherché. □

Lemme 26. Si Φ est finiment consistant, Φ_{Skolem} est finiment consistant.

Démonstration du Théorème 22. Soit Φ un ensemble de L-énoncés finiment consistant. On itère alternativement entre complétion et skolemisation : On pose Φ_{0} := Φ, Φ_{2i+1} := Φ̄_{2i} et Φ_{2i+2} := Φ_{2i+1}_{Skolem}. Soit Φ̃ := ⋃_{i<ω} Φ_{i}. Alors tous les Φ_{i} sont finiment consistants par les lemmes 25 et 26, et Φ̃ est finiment consistant par le lemme 24. En plus, Φ̃ est complètement skolemisé : pour toute formule φ(x, ȳ) dans son langage L̃ (qui est l’itération infinie des skolemisations) il y a une fonction f_{φ} telle que ∀ȳ [∃x φ(x, ȳ) → φ(f_{φ}(ȳ, ȳ)] est dans Φ̃. Et Φ̃ est complète : pour tout L̃-énoncé φ soit φ ∈ Φ̃, soit ¬φ ∈ Φ̃ (et jamais les deux).

On construit une L-structure 𝔐. Le domaine M est l’ensemble des L̃-termes clos, quotienté par l’égalité. • c^{𝔐} := c/=, pour toute constante c ;

• f^{𝔐}(t_{1}/=, …, t_{n}/=) := f(t_{1}, …, t_{n})/=, pour toute L̃-fonction n-aire et L̃-termes clos t_{1}, …, t_{n}.

• R^{𝔐} := {(t_{1}/=, …, t_{n}/=) ∈ M^{n} : R(t_{1}, …, t_{n}) ∈ Φ̃}, pour toute relation n-aire R. Comme Φ̃ implique que = est une congruence pour toutes les L̃-fonctions et L̃-relations, 𝔐 est bien défini. On va montrer par récurrence sur le nombre de symboles logiques que 𝔐 ⊧ φ(t̄/=) si et seulement si φ(t̄) ∈ Φ̃, pour tout L̃-énoncé φ(t̄), où t̄ sont des L̃-termes clos. On notera qu’en outre des paramètres t̄/= la formule φ peut contenir des L̃-termes clos (non quotientés par =). C’est par définition des R^{𝔐} si φ est atomique. Pour les connecteurs booléens, 𝔐 ⊧ ¬ψ si et seulement si 𝔐 |̸= ψ, si et seulement si ψ ∉ Φ̃, si et seulement si ¬ψ ∈ Φ̃ (la dernière équivalence est par complétude et consistance finie). Pour la conjonction, 𝔐 ⊧ φ_{1} ∧ φ_{2} si et seulement si 𝔐 ⊧ φ_{1} et 𝔐 ⊧ φ_{2}, si et seulement si φ_{1} ∈ Φ̃ et φ_{2} ∈ Φ̃. Par complétude et consistance finie le dernier est équivalent à φ_{1} ∧ φ_{2} ∈ Φ̃ ; le cas d’une disjonction est analogue. Il nous restent les énoncés φ de la forme ∃x ψ(x, t̄/=), pour des L̃-termes t̄. Si ∃x ψ(x, t̄) ∈ Φ̃, comme

∀ȳ [∃x ψ(x, ȳ) → ψ(f_{ψ}(ȳ), ȳ)]

est dans Φ̃, il est impossible par consistance finie que

¬ψ(f_{ψ}(t̄), t̄)

soit dans Φ̃. Par complétude, ψ(f_{ψ}(t̄), t̄) ∈ Φ̃ ; par hypothèse de récurrence 𝔐 ⊧ ψ(f_{ψ}(t̄/=), t̄/=), et donc 𝔐 ⊧ ∃x ψ(x, t̄/=). Réciproquement, si 𝔐 ⊧ ∃x ψ(x, t̄/=), alors il y a un L̃-terme clos t_{0} tel que 𝔐 ⊧ ψ(t_{0}/=, t̄/=). Par hypothèse de récurrence ψ(t_{0}, t̄) ∈ Φ̃ ; par consistance finie ¬∃x ψ(x, t̄) n’est pas dans Φ̃, et par complétude ∃x ψ(x, t̄) l’est. □

Lemme 27. Soit 𝔐 une L-structure infinie. Alors il y a 𝔑 \underline{≻} 𝔐 arbitrairement large.

Démonstration : Soit λ un cardinal arbitraire, {c_{i} : i < λ} des nouvelles constantes, et

Φ = Th(𝔐, M) ∪ {c_{i} ≠ c_{j} : i ≠ j}.

Alors chaque sous-ensemble fini de Φ ne mentionne qu’un nombre fini de constantes, que l’on peut interpréter dans 𝔐. Donc chaque sous-ensemble fini de Φ a un modèle ; par compacité il y a un modèle 𝔑 de Φ. Évidemment |𝔑| ≥ λ. En plus, on a une injection canonique de 𝔐 dans 𝔑, qui envoie un élément m ∈ 𝔐 sur la réalisation m^{𝔑} de sa constante dans 𝔑. Soit maintenant φ(m̄) ∈ L(m̄) pour un m̄ ∈ 𝔐. Alors

𝔐 ⊧ φ(m̄) ⇔ φ(m̄) ∈ Th(𝔐, M) ⇔ 𝔑 ⊧ φ(m̄),

donc l’inclusion est élémentaire. □

Corollaire 28. Löwenheim-Skolem ascendant Soit 𝔐 une L-structure infinie. Alors pour tout λ ≥ |L| + |M| il a une extension élémentaire 𝔑 \underline{≻} 𝔐 de cardinal λ.

Démonstration : Par le lemme 27 on trouve 𝔑′ \underline{≻} 𝔐 de cardinal au moins λ; par Löwenheim-Skolem descendant il y a 𝔑 \underline{≺} 𝔑′ contenant 𝔐 de cardinal λ, et 𝔐 \underline{≺} 𝔑. □

4. Types

Définition 29. Soit 𝔐 une L-structure, A ⊆ M et ā un uple dans M. Le type de ā sur A, noté tp(ā/A), est l’ensemble des L(A)-formules φ(x̄) satisfaites par ā dans 𝔐. Si A est vide, on l’omet et note tp(ā). Plus généralement, un n-type (complèt) sur A est un ensemble p(x̄) maximal de L(A)-formules avec variables libres x̄ = (x_{1}, …, x_{n}), tel que toute partie finie de p(x̄) est réalisée dans 𝔐 La famille des n-types sur A est noté S_{n}(A); on pose S(A) = ⋃_{n<ω} S_{n}(A). Nous allons également considerer des types en une infinité de variables.

Th(𝔐, A) fait partie de tout type sur A, et tp(ā/A) dépend du modèle ambiant 𝔐 ; il reste inchangé si on remplace 𝔐 par une extension élémentaire. Pour tout n l’espace des n-types sur A porte la topologie suivante : Un base pour les ouvert-fermés est donné par les ensembles

[φ] = {p ∈ S_{n}(A) : φ ∈ p}.

C’est donc une topologie totalement discontinu : deux point distincts peuvent être séparés par des ouvertfermés. Le théorème de compacité implique que c’est un espace compact.

Proposition 30. Si A ⊆ M et p(x̄) ∈ S_{n}(A), il y a 𝔑 ≻ 𝔐 et c̄ ∈ N tel que p = tp(c̄/A). tp(ā/A) = tp(ā′/A) ssi il y a 𝔑 ≻ 𝔐 et un automorphisme de 𝔑 qui fixe A et envoie ā sur ā′.

Démonstration : Th(𝔐, M) ∪ p(c̄) (où c̄ sont des nouvelles constantes) est finiment interprétable dans 𝔐. Par compacité il y a 𝔑 ⊧ Th(𝔐, M) ∪ p(c̄) ; on peut supposer 𝔐 \underline{≺} 𝔑. Alors c̄^{𝔑} ⊧_{𝔑} p. Soient ā et ā′ deux réalisations d’un type p(x̄) sur A dans une extension élémentaire 𝔐_{0} de 𝔐. Nous allons construire une suite 𝔐 ≺ 𝔐_{0} ≺ 𝔐_{1} ≺ ⋯ d’extensions élémentaires, et une chaîne σ_{0} ⊆ σ_{1} ⊆ ⋯ d’isomorphismes partiels élémentaires σ_{i} : 𝔐_{i} → 𝔐_{i}, telle que σ_{0} fixe A et envoie ā à ā′, et pour tout i < ω la domaine de σ_{2i+1} contient 𝔐_{2i} et l’image de σ_{2i+2} contient 𝔐_{2i+1}. Alors 𝔐 \underline{≺} ⋃_{i<ω} 𝔐_{i} =: 𝔑, et σ = ⋃_{i<ω} σ_{i} sera un automorphisme de 𝔑 qui fixe A et envoie ā sur ā′.

Lemme 31. Soit 𝔐 une L-structure et σ un L-morphisme élémentaire partiel de 𝔐. Alors il y a 𝔑 ≻ 𝔐 et un L-morphisme partiel τ de 𝔑 de domaine 𝔐 qui étend σ; en plus τ(𝔐) ≺ 𝔑.

Démonstration : Pour chaque m ∈ M soit m′ une nouvelle constante. Soit

Φ := Th(𝔐, M) ∪ {φ(m̄′, σ(n̄)) : 𝔐 ⊧ φ(m̄, n̄) et n̄ ∈ dom(σ)}.

Considérons une partie finie Φ_{0} de Φ qui contient des formules φ_{i}(m̄′_{i}, σ(n̄_{i})) pour i ≤ n. Alors 𝔐 ⊧ ⋀_{i≤n} φ_{i}(m̄_{i}, n̄_{i}) et 𝔐 ⊧ ∃_{i≤n}x̄_{i} ⋀_{i≤n} φ_{i}(x̄_{i}, n̄_{i}); comme σ est élémentaire, on a

𝔐 ⊧ ∃_{i≤n}x̄_{i} ⋀_{i≤n} φ_{i}(x̄_{i}, σ(n̄_{i})).

Donc, on peut modéliser Φ_{0} dans 𝔐. Par compacité on trouve un modèle 𝔑 de Φ, qui est une extension élémentaire de 𝔐; l’application τ : m ↦ (m′)^{𝔑} est une continuation élémentaire de σ sur 𝔐. Enfin, pour tout formule φ(τ(m̄)) à paramètres dans τ(𝔐)

𝔑 ⊧ φ(τ(m̄)) ⇔ 𝔑 ⊧ φ(m̄) ⇔ 𝔐 ⊧ φ(m̄) ⇔ τ(𝔐) ⊧ φ(τ(m̄)).

Maintenant on applique le lemme 31 d’abord à 𝔐_{0} et σ_{0} pour obtenir 𝔐_{1} et σ_{1}, ensuite à 𝔐_{1} et σ_{1}^{−1} pour obtenir 𝔐_{2} et σ_{2}^{−1}, etc. □

Définition 32. Un type p(x̄) sur A est principal, ou isolé, s’il y a une formule φ(x̄) dans p(x̄) telle que Th(𝔐, A) ∪ {φ(x̄)} ⊧ p(x̄). Dans ce cas, la formule φ(x̄) isole p(x̄) sur A.

Il est évident qu’un type principal est réalisé dans chaque modèle contenant A.

Théorème 33. Omission des types Soit 𝔐 une L-structure, A ⊆ M avec L(A) dénombrable, et p(x̄) ∈ S_{n}(A) non-isolé. Alors il y a un modèle de Th(𝔐, A) qui omet p.

Démonstration : Soit C = {c_{i} : i < ω} des nouvelles constantes. Nous allons construire une L(A ∪ C)-théorie consistante T étendant Th(𝔐, A) telle que pour chaque formule φ(x) il y a i_{φ} < ω tel que ∃xφ(x) → φ(c_{i_{φ}}) est dans T. Alors si 𝔑 est un modèle de T, alors {c_{i}^{𝔑} : i < ω} est une sous-structure de 𝔑, comme parmi les formules φ(x) se trouvent celles de la forme x = a pour toute constante a, et x = f(c̄) pour toute fonction f(x̄) ∈ F et c̄ ∈ C. Par le test de Tarski, l’inclusion est élémentaire, et {c_{i}^{𝔑} : i < ω} est un modèle de Th(𝔐, A); nous allons faire de manière qu’il omet p. Soit (φ_{i}(x) : 0 < i < ω) une énumération des L(A∪C)-formules avec une variable lible x, et (c̄_{i} : i < ω) une énumération des n-uples dans C. On pose T_{0} = ∅; si on a déjà construit T_{n} fini tel que Th(𝔐, A)∪T_{n} a un modèle, alors :

• Si n = 2m, soit i minimal tel que c_{i} ne figure pas dans T_{n}. On met T_{n+1} = T_{n} ∪ {∃xφ_{m}(x) → φ_{m}(c_{i})}; comme c_{i} ne figure pas dans Th(𝔐, A) ∪ T_{n}, il y a un modèle de Th(𝔐, A) ∪ T_{n+1}.

• Si n = 2m + 1, on considère l’uple c̄_{m}. Soient d̄ les constantes dans C − {c̄_{m}} qui figurent dans T_{n}, et ψ(c̄_{m}, d̄) l’énonce ⋀ T_{n}. Comme p(x̄) n’est pas principal,

Th(𝔐, A) ∪ {∃ȳ ψ(x̄, ȳ)} |̸= p(x̄)

et il y a un modèle 𝔐_{m} de Th(𝔐, A) ∪ {ψ(c̄_{m}, d̄)} tel que 𝔐_{m} |̸= p(c̄_{m}). Si ψ_{m}(x̄) ∈ tp(c̄_{m}/A) − p(x̄), alors T_{n+1} = T_{n} ∪ {ψ_{m}(c̄_{m})} a un modèle.

On pose T = ⋃_{n<ω} T_{n}. Alors T est consistant par compacité et étend Th(𝔐, A), les quanteurs existentiels on des témoins dans C, et aucun uple dans C réalise p. □

Définition 34. Soit I un ensemble infini. Un filtre sur I est une collection F de sous-ensembles de I telle que

• ∅ ∉ F,

• si X ∈ F et X ⊆ Y ⊆ I, alors Y ∈ F, et

• si X ∈ F et Y ∈ F, alors X ∩ Y ∈ F. Un ultrafiltre est un filtre maximal. Un filtre est principal s’il est de la forme {X ⊆ I : i ∈ X} pour un i ∈ I.

Par le lemme de Zorn tout filtre est contenu dans un ultrafiltre. Notons que si U est un ultrafiltre sur I et X ⊆ I, alors soit X ∈ U, soit I \ X ∈ U (sinon l’ensemble {Y ⊆ I : ∃ Z ∈ U Z ∩ X ⊆ Y } serait un filtre plus grand).

Remarque 35. Si p est un k-type sur un modèle 𝔐, alors la collection d’ensembles qui contiennent un sous-ensemble de la forme φ^{𝔐} pour une formule φ ∈ p est un filtre sur M^{k}.

Définition 36. Soient 𝔐 ≺ 𝔑 deux L-structures, A ⊇ M, et U un ultrafiltre U sur M^{k}. On pose lim_{U}(M^{k}/A) := {φ(x̄) ∈ L(A) : (φ^{𝔑} ∩ M^{k}) ∈ U}.

Lemme 37. lim_{U}(M/A) est un type complèt sur A. Il est finiment satisfaisable dans M (toute formule a une réalisation dans M).

Démonstration : Complétude et clôture par conjonctions finies suivent des propriétés analogues de l’ultrafiltre. Soit donc φ(x̄) une formule à paramètres dans A telle que (φ^{𝔐} ∩ M^{k}) ∈ U. Puisque tout ensemble dans U est non-vide, φ a une réalisation dans M. En particulier p est finiment réalise dans N, et est donc un type. □

5. Indiscernables et la Propriété d’Indépendance

Dans cette section I sera toujours un ensemble infini totalement ordonné.

Définition 38. Soit 𝔐 une structure, A ⊆ M, et (ā_{i} : i ∈ I) une suite d’uples de même longueur dans M. La suite est indiscernable sur A si pour chaque n < ω et tout i_{1} < ⋯ < i_{n} et j_{1} < ⋯ < j_{n} on a tp(ā_{i_{1}}, …, ā_{i_{n}}/A) = tp(ā_{j_{1}}, …, ā_{j_{n}}/A).

Lemme 39. Soit 𝔐 une structure, A ⊆ M, et (ā_{i} : i ∈ I) une suite indiscernable sur A. Alors pour tout ensemble ordonné J infini il y a 𝔑 ≻ 𝔐 et une suite indiscernable (ā′_{j} : j ∈ J) ⊂ N sur A dont les sous-suites finis ont même type sur A que les sous-suites finis de (ā_{i} : i ∈ I).

Théorème 40. Théorème de Ramsey Soit X un ensemble ordonné infini dont les n-uples croissants sont colorés en un nombre fini de couleurs. Alors il y a un sous-ensemble Y ⊆ X infini monochrome.

Démonstration : Par récurrence sur n, l’énoncé étant évident si n = 1. Considérons donc une coloration des (n + 1)-uples de X ; fixant x_{0} ∈ X on obtient par hypothèse de récurrence un sousensemble infini X_{0} ⊆ X − {x_{0}} et une couleur k_{0} < k tel que pour tout n-uple croissant x̄ de X_{0} le (n + 1)-uple x_{0}x̄ porte le même type d’ordre et la même couleur k_{0}. Récursivement on obtient une suite X = X_{−1} ⊇ X_{0} ⊇ X_{1} ⊇ ⋯ de sous-ensembles infinis, des éléments x_{i} ∈ X_{i−1} − X_{i}, et des couleurs k_{i}, tels que pour chaque n-uple croissant x̄ dans X_{i} le (n + 1)-uple x_{i}x̄ porte le même ordre et la même couleur k_{i}. Comme il n’y a qu’un nombre fini de couleurs, il y a un sous-ensemble infini I ⊆ ω et une couleur k′ tels que k_{i} = k′ pour tout i ∈ I. Alors l’ensemble {x_{i} : i ∈ I} sera monochrome. □

Théorème 41. Soit 𝔐 une structure, A ⊆ M, et (ā_{i} : i ∈ I) une suite infinie d’uples de même longueur dans M. Alors il y a une extension élémentaire 𝔑 ≻ 𝔐 et une suite indiscernable (ā′_{i} : i < ω) sur A dans 𝔑, telles que toute L(A)-formule φ(x̄_{i} : i < n) satisfaite par (ā′_{1}, …, ā′_{n}) est satisfaite par une n-sous-suite de (ā_{i} : i < ω).

Démonstration : Soit Δ = {φ_{i}(x̄_{1}, …, x̄_{n}) : i < k} un ensemble fini de L(A)-formules. Le théorème de Ramsey nous donne un sous-ensemble infini I_{Δ} ⊆ I tel que soit 𝔐 ⊧ φ_{i}(ā_{j_{1}}, …, ā_{j_{n}}) pour tous j_{1} < ⋯ < j_{n} dans I_{Δ}, soit 𝔐 ⊧ ¬φ_{i}(ā_{j_{1}}, …, ā_{j_{n}}) pour tous j_{1} < ⋯ < j_{n} dans I_{Δ}, comme satisfaction de ces formules nous donne une 2^{k}-coloration des n-uples dans (ā_{i} : i ∈ I). Donc, si (c̄_{i} : i < ω) sont des nouvelles constantes,

Th(𝔐, M) ∪ ⋃_{\begin{matrix}i_{1}<···<i_{n} \\ j_{1}<···<j_{n} \end{matrix}} \{φ(c̄_{i_{1}}, …, c̄_{i_{n}}) ↔ φ(c̄_{j_{1}}, …, c̄_{j_{n}}) : φ ∈ L(A)\}

∪ \{φ(c̄_{1}, …, c̄_{n}) : \begin{matrix}φ ∈ L(A), 𝔐 ⊧ φ(ā_{i_{1}}, …, ā_{i_{n}}) \\ pour tout i_{1} < ⋯ < i_{n} dans I \end{matrix} \}

est finiment réalisable dans 𝔐, et a un modèle 𝔑, extension élémentaire de 𝔐 ; on prend ā′_{i} = c̄_{i}^{𝔑} pour i < ω. □

Définition 42. Soit T und L-théorie et φ(x̄, ȳ) une formule. Alors φ a la propriété d’indépendance (par rapport à T) si pour tout n < ω il y a un modèle 𝔐 de T et deux suites (ā_{i} : i < n) et (b̄_{J} : J ⊆ n) dans 𝔐 telles que 𝔐 ⊧ φ(ā_{i}, b̄_{J}) si et seulement si i ∈ J. On dit que T a la propriété d’indépendance s’il y a une formule qui l’a par rapport à T.

Lemme 43. Soit T une théorie, et φ(x̄, ȳ) une formule. Sont équivalents :

(1) φ(x̄, ȳ) a la propriété d’indépendance par rapport à T.

(2) φ^{∗}(ȳ, x̄) := φ(x̄, ȳ) a la propriété d’indépendance par rapport à T.

(3) Pour tout ensemble ordonné I il y a un modèle 𝔐 de T telle qu’il y ait deux suites (ā_{i} : i ∈ I) et (b̄_{J} : J ⊆ I) avec 𝔐 ⊧ φ(ā_{i}, b̄_{J}) si et seulement si i ∈ J.

(4) L’énoncé précédent, avec en plus (ā_{i} : i ∈ I) indiscernable.

(5) Il existe une suite indiscernable (ā_{i} : i < ω) dans un modèle 𝔐 de T et b̄ ∈ 𝔐 tels que 𝔐 ⊧ φ(ā_{i}, b̄) si et seulement si i est pair.

(6) Pour tout n < ω il existe une suite indiscernable (ā_{i} : i < n) dans un modèle 𝔐 de T et b̄ ∈ 𝔐 tels que 𝔐 ⊧ φ(ā_{i}, b̄) si et seulement si i est pair.

Corollaire 44. Soit (ā_{i} : i < ω) une suite indiscernable sur ∅ dans un modèle 𝔐 d’une théorie sans la propriété d’indépendance. Alors l’ensemble des formules avec paramètres dans 𝔐 satisfaites par presque tous les ā_{i} forme un type complèt sur 𝔐.

Définition 45. Le type donné par le corollaire 44 s’appelle le type moyen av(ā_{i} : i < ω) de la suite.

Proposition 46. Si T a la propriété d’indépendance, il existe une formule φ(x, ȳ) qui l’a.

Démonstration : Soient dans un modèle 𝔐 une suite indiscernable (ā_{i} : i ∈ I), un élément b̄ = b_{0} … b_{k}, et une formule φ(x̄, ȳ), tels que I = ω^{n} et 𝔐 ⊧ φ(ā_{i}, b̄) si et seulement si i est pair. Supposons qu’aucune formule ψ(x, ȳ) n’ait la propriété d’indépendance.

Lemme 47. Pour toute formule ψ(x̄_{0}, …, x̄_{ℓ}, b_{k}) il existe un interval I_{ψ} = {x ∈ I : ω^{n−1} · j_{ψ} ≤ x < ω^{n−1} · (j_{ψ} + 1)} tel que (ā_{i} : i ∈ I_{ψ}) est ψ-indiscernable.

Démonstration : Sinon, pour tout j < ω on trouve

ω^{n−1} · j ≤ i_{j,0} < i_{j,1} < ⋯ < i_{j,ℓ} < ω^{n−1} · (j + 1)

tels que 𝔐 ⊧ ψ(ā_{i_{j,0}}, …, ā_{i_{j,ℓ}}, b_{k}) si et seulement si j est pair. Comme la suite (ā_{i_{j,0}} … ā_{i_{j,ℓ}} : j < ω) est indiscernable, ceci contredit le lemme 43. □ En itérant ce lemme on trouve un interval I′ de longueur ω dans I tel que (ā_{i} : i ∈ I′) est indiscernable par rapport à n formules avec paramètre b_{k}; par compacité on peux supposer qu’on trouve une telle sous-suite qui est indiscernable au dessus de b_{k}. Mais alors φ^{∗}(x̄y_{k}, y_{0} … y_{k−1}) := φ(x̄, y_{0} … y_{k}) a la propriété d’indépendance; la proposition suit par récurrence sur k. □

Définition 48. Une théorie T est faiblement o-minimale si son domaine est totalement ordonné, et tout sous-ensemble (unaire) dans tout modèle est une réunion finie d’ensembles définissables convexes.

Lemme 49. Si T est faiblement o-minimale, alors pour toute formule φ(x, ȳ) il existe n_{φ} < ω tel que tout ensemble défini par un instance φ(x, ā) avec a dans un modèle de T est réunion d’au plus n_{φ} ensembles convexes.

Proposition 50. Une théorie faiblement o-minimale n’a pas la propriété d’indépendance.

6. Expansions des théories sans la propriété d’indépendance

Théorème 51. Soit T une théorie dans un langage L sans la propriété d’indépendance, et 𝔐 ≺ 𝔑 deux modèles de T telle que 𝔑 réalise tout ω-type au dessus de M. Pour toute formule φ(x̄) avec paramètres dans 𝔑 on rajoute au langage un prédicat P_{φ}(x̄) interprété comme P_{φ}^{𝔐} = φ^{𝔑} ∩ M^{|x̄|}, pour former le langage L^{∗}. Alors l’expansion 𝔐^{∗} de 𝔐 comme L^{∗}-structure élimine les quanteurs. En particulier, 𝔐^{∗} n’a pas la propriété d’indépendance; si 𝔐 est faiblement o-minimal, 𝔐^{∗} l’est aussi.

Démonstration : Pour une formule ψ(x̄, y) = ψ(x̄, y, c̄) avec c̄ ∈ N et k = |x̄| considérons l’ensemble

X_{ψ} := {m̄ ∈ M^{k} : il existe m′ ∈ M tel que 𝔑 ⊧ ψ(m̄, m′)}.

Lemme 52. Soit U ∋ X_{ψ} un ultrafiltre sur M^{k}. Alors il existe φ ∈ L(N) avec P_{φ}^{𝔐} ⊆ X_{ψ} et P_{φ}^{𝔐} ∈ U.

Démonstration : Supposons que ψ donne lieu à un contre-exemple. Pour ā ∈ X_{ψ} soit bā ∈ M tel que 𝔑 ⊧ ψ(ā, bā), et soit U′ l’ultrafiltre sur M^{k+1} engendré par les ensembles {(ā, bā) : ā ∈ X ∩ X_{ψ}} pour X ∈ U. Pour i ≤ ω soit ā_{i}b_{i} ∈ 𝔑 (ou dans une extension élémentaire) une réalisation de lim_{U′}(M^{k+1}/M, ā_{j}b_{j} : j < i) ; par le lemme 37 c’est un type finiment satisfaisable dans M ; notons que chacun étend le type précédent, et que ā_{i} satisfait lim_{U}(M^{k}/M, ā_{j}b_{j} : j < i). Puisque 𝔑 réalise tous le types au dessus de M, on peut supposer que (ā_{i}b_{i} : i ≤ ω) ⊆ N. Montrons que la suite (ā_{i}b_{i} : i ≤ ω) est indiscernable au dessus de 𝔐 : Tous les uples satisfont le même type sur 𝔐 ; supposons que tous les n-uplets aient même type, et considérons 0 ≤ i_{0} < ⋯ < i_{n} ≤ ω et 0 ≤ j_{0} < ⋯ < j_{n} ≤ ω. On peut supposer que i_{n} = j_{n} =: i. Or, tp(ā_{i}b_{i}/M, ā_{j}b_{j} : j < i) est finiment satisfaisable dans 𝔐 ; s’il existait une formule φ telle que 𝔑 ⊧ φ(ā_{i_{ℓ}}b_{i_{ℓ}} : ℓ ≤ n) ∧ ¬φ(ā_{j_{ℓ}}b_{j_{ℓ}} : ℓ ≤ n), on pourrait remplacer ā_{i}b_{i} dans cette formule par un uple dans M, ce qui contredirait l’hypothèse de récurrence.

Ensuite, soit 𝔐′ ≺ 𝔑′ ⊧ T, et supposons que (c̄_{i} : i ≤ ω) ⊆ N′ est indiscernable sur M′ et pour tout i < ω on a d̄_{i} ∈ M′ qui réalise tp(c̄_{ω}/c̄_{j} : j < ω, d̄_{j} : j < i). Alors (c̄_{i} : i < ω)ˆ (d̄_{i} : i ∈ ω^{∗}) est indiscernable, où ω^{∗} est l’ordre inverse de ω. En fait, si (c̄_{i} : i < ω)ˆ (d̄_{i} : i = n, …, 0) est indiscernable, alors (c̄_{i} : i ≤ ω)ˆ (d̄_{i} : i = n, …, 0) l’est aussi par indiscernabilité de la suite (c̄_{i} : i ≤ ω) sur M′, et donc (c̄_{i} : i < ω)ˆ (d̄_{i} : i = n + 1, …, 0) est indiscernable. Par compacité dans le langage L(P) avec un nouveau prédicat P interpreté comme P^{𝔑′} := M′ (le fait que ce soit un modèle est sans importance) pour tout n_{1} < ω et ensemble fini Δ_{1} de L-formules il existe n_{2} < ω et un ensemble fini Δ_{2} de L-formules telle que si (ā′_{i}b′_{i} : i ≤ ω) ⊆ N′ est L-indiscernable sur M′ et pour tout i ≤ n_{1} on trouve dans M′ des uples

ā′′_{2i+1} ⊧ tp_{Δ_{2}}(ā′_{ω}/ā′_{j}b′_{j} : j < n_{2}, ā′′_{2j+1}ā′′_{2j}b′′_{2j} : j < i, ā′′_{2i}b′′_{2i}), et
ā′′_{2i}b′′_{2i} ⊧ tp_{Δ_{2}}(ā′_{ω}b′_{ω}/ā′_{j}b′_{j} : j < n_{2}, ā′′_{2j+1}ā′′_{2j}b′′_{2j} : j < i),

alors

(ā′_{i} : i < n_{1})ˆ (ā′′_{i} : i = n_{1}, …, 0), et
(ā′_{2i}a′_{2i+1}b′_{2i+1} : i < n_{1})ˆ (ā′′_{2i+1}ā′′_{2i}b′′_{2i} : i = n_{1}, …, 0)

sont Δ_{1}-indiscernables. Fixons un ensemble fini Δ de formules et un entier n < ω. Si B ⊂ M est fini, alors par satisfaisabilité finie on trouve āb ∈ M qui réalise tp_{Δ}(ā_{ω}b_{ω}/B, ā_{i}b_{i} : i < n). En particulier 𝔑 ⊧ ψ(ā, b). De l’autre coté, soit φ(x̄) = ⋀ tp_{Δ}(ā_{ω}/B, ā_{i}b_{i} : i < n). C’est une formule satisfaite par ā_{ω}, d’où P_{φ}^{𝔐} ∈ U. Par hypothèse P_{φ}^{𝔐} ⊈ X_{ψ} et il y a ā ∈ P_{φ}^{𝔐} \ X_{ψ}. Donc ā ⊧ tp_{Δ}(ā_{ω}/B, ā_{i}b_{i} : i < n), et pour tout b ∈ M on a 𝔑 ⊧ ¬ψ(ā, b).

Par compacité dans L(P) on trouve une extension L(P)-élémentaire 𝔑′, avec 𝔐′ := P^{𝔑′} ≺_{L} 𝔑′, et deux suites

(ā′_{i}b′_{i} : i < ω) ⊂ N′ et (ā′′_{2i+1}, ā′′_{2i}, b̄′′_{2i} : i < ω^{∗}) ⊂ M′

telles que

(ā′_{i} : i < ω)ˆ (ā′′_{i} : i < ω^{∗}), et
(ā′_{2i}a′_{2i+1}b′_{2i+1} : i < ω)ˆ (ā′′_{2i+1}ā′′_{2i}b′′_{2i} : i < ω^{∗})

sont L-indiscernables, 𝔑′ ⊧ ψ(ā′′_{2i}, b′′_{2i}) pour tout i < ω^{∗}, mais 𝔑′ ⊧ ¬ψ(ā′′_{2i+1}, b) pour tout b ∈ M′, et telle que 𝔐′ réalise tout L-type de longueur ω sur (ā′′_{i} : i < ω^{∗}). Puisque tp(ā′′_{i} : i < ω^{∗}) = tp(ā′′_{2i} : i < ω^{∗}), on trouve des éléments (b′′_{2i+1} : i < ω^{∗}) ⊂ M′ tels que (ā′′_{i}b′′_{i} : i < ω^{∗}) est indiscernable. Alors 𝔑′ ⊧ ψ(ā′′_{i}, b′′_{i}, c̄) si et seulement si i est pair, ce qui contredit le lemme 43. □ Supposons maintenant que X_{ψ} ne soit pas équivalente à une réunion finie de formules P_{φ}. Alors l’ensemble {M \ P_{φ}^{𝔐} : P_{φ}^{𝔐} ⊂ X_{ψ}} forme un filtre, qui est contenu dans un ultrafiltre U. Par le lemme 52 il existe une L-formule φ avec paramètres dans une extension élémentaire de 𝔑 telle que P_{φ}^{𝔐} ∈ U et P_{φ}^{𝔐} ⊆ X_{ψ}, contradiction. Donc toute L^{∗}-formule existentielle est équivalente à une L^{∗}-formule sans quanteurs, ce qui montre élimination des quanteurs. Mais une L^{∗}-formule sans quanteurs est équivalente à une L-formule avec des paramètres dans une extension élémentaire ; elle ne peut donc pas avoir la propriété d’indépendance ; si T est faiblement o-minimale, elle doit être une réunion finie et bornée d’ensembles convexes. □