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

EST training workshop, 5–9 septembre 2005, Fischbachau

Frank Wagner

21 septembre 2005

Chapitre 1

Langage et structure

En théorie des modèles on n’analyse pas une seule structure, comme les entiers où les complexes, mais on prend une classe de structures, et on cherche à déterminer les propriétés communes des structures dans cette classe. Pour exprimer une propriété, il nous faut d’abord un langage.

Définition 1.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.

En plus, on aura les variables, qui seront notés x, y, z, …, x_{0}, x_{1}, x_{2}, . . ..

Remarque 1.2 Une fonction d’arité 0 est une constante. Il y a deux relations d’arité 0 : la relation ⊤ qui est toujours vraie, et la relation ⊥ qui est toujours fausse.

Exemple 1.3 1. Le langage des ordres L_{ord} ne contient ni constantes ni

fonctions, mais deux relations binaires = et <.

2. Le langage des groupes L_{gp} contient une constante 1, une fonction unaire ^{−1}, une fonction binaire ∗, et une relation binaire =.

Définition 1.4 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.

Exemple 1.5 1. Les seuls termes de L_{ord} sont les variables ; les L_{ord}-

formules atomiques sont les égalités et les inégalités.

2. Parmi les termes de L_{gp}, il y a les produits des variables et leurs inverses (le produit vide étant égale à 1) ; en effet, modulo les lois de groupe chaque terme est équivalent à un tel produit. Donc les L_{gp}-formules atomiques sont les équations.

Lemme 1.6 [Lecture unique]

1. Soit t un L-terme. Alors soit t est une constante ou une variable (uniquement déterminée), soit il y a une fonction f d’arité n, et des Ltermes t_{n}, …, t_{n}, uniquement déterminés, tels que t est f(t_{1}, …, t_{n}).

2. Soit φ une L-formule. Alors φ tombe dans un (et un seul) des cas suivants :

(a) φ est atomique et il y a une relation R d’arité n, et des L-termes t_{n}, …, t_{n}, uniquement déterminés, tels que φ est R(t_{1}, …, t_{n}),

(b) Il y a une formule ψ uniquement déterminée telle que φ est ¬ψ.

(c) Il y a deux formules ψ_{1} et ψ_{2} uniquement déterminées telles que φ est (ψ_{1} ∧ ψ_{2}).

(d) Il y a deux formules ψ_{1} et ψ_{2} uniquement déterminées telles que φ est (ψ_{1} ∨ ψ_{2}).

(e) Il y a une formule ψ et une variable x uniquement déterminées telles que φ est ∃xψ.

(f) Il y a une formule ψ et une variable x uniquement déterminées telles que φ est ∀xψ.

Démonstration : Par récurrence sur la construction du terme et de la formule.

Maintenant que l’on a fixé la syntaxe, il nous faut des objets.

Définition 1.7 Une L-structure 𝔐 est un ensemble M, le domaine, 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 𝔐 et M, c et c^{𝔐}, f et f^{𝔐}, et R et R^{𝔐}.

Définition 1.8 Soit 𝔐 une L-structure. Si m̄ est un uple d’éléments de M et x̄ est un uple de variables (de la même longueur) dans un terme t(x̄), on peut substituer m̄ pour toutes les occurences de x̄ dans t et obtenir un terme t(m̄), un terme à paramètres m̄. Nous allons définir l’interprétation t^{𝔐} d’un terme t à paramètres dans 𝔐 clos (sans variable) récursivement par :

– l’interprétation d’une constante c est c^{𝔐}; l’interprétation d’un paramètre m est m.

– si f ∈ F est une fonction n-aire et t_{1}, …, t_{n} sont des termes à paramètres, alors f(t_{1}, …, t_{n})^{𝔐} = f^{𝔐}(t_{1}^{𝔐}, …, t_{n}^{𝔐}).

Donc l’interprétation associe à chaque terme clos (avec paramètres) un élément de M. De même, pour une formule φ(x̄), on peut substituer m̄ pour toutes les occurences libres de x̄ dans φ et obtenir une formule φ(m̄) avec paramètres. (Par unicité de lecture, la liberté d’une variable est uniquement déterminée.) Nous allons définir 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̄).

Remarque 1.9 C’est cette définition de la satisfaction qui donne le sens usuel au connecteurs booléens et au quanteurs. Avant, ce n’étaient que des symboles manipulés de manière purement syntactique. Notons également que la définition est possible grâce au lemme d’unicité de lecture.

Convention 1.10 Dans ce cours, l’égalité = fera partie de tous les langages, et sera toujours interpretée par la vraie égalité. (Si = n’est pas interpreté par la vrai égalité, mais on considère une structure où les axiomes habituels de l’égalité sont satisfaits — qu’elle soit une congruence pour toutes les fonctions et relations —, alors on pourra quotienter par = ; comme c’est une congruence, ça nous induit une L-structure sur l’ensemble des classes modulo =, qu’on peut substituer pour la structure originale.)

Exemple 1.11 Considérons une L_{ord}-structure 𝔐 satisfaisant :

1. ∀x ¬x < x.

2. ∀x ∀y ((x < y ∨ y < x) ∨ x = y).

3. ∀x ∀y ∀z ¬((x < y ∧ y < z) ∧ (z = x ∨ z < x)). Alors la relation <^{𝔐} est anti-réfléxive, totale, et transitive, donc un ordre total. L’orde est sans extrémité si 𝔐 satisfait

∀x ∃y ∃z (y < x ∧ x < z) ;

il est dense si 𝔐 satisfait

∀x∀y ((x = y ∨ y < x) ∨ ∃z (x < z ∧ z < y)).

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 1.12 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 Φ.

On a la même définition pour des ensembles de L-formules à la place de φ et de ψ. Si Φ est vide, il est omis.

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

– φ et ¬¬φ.

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

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

Démonstration : Par exemple, pour toute L-structure 𝔐 et tout m̄ dans 𝔐 on a

𝔐 ⊧ ¬¬φ(m̄) ⇔ 𝔐 |̸= ¬φ(m̄)
⇔ il n’est pas vrai que 𝔐 ⊧ ¬φ(m̄)
⇔ il n’est pas vrai que 𝔐 |̸= φ(m̄)
⇔ 𝔐 ⊧ φ(m̄).

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

Démonstration : Grâce au Lemme 1.13 on élimine itérativement un des connecteurs et un des quanteurs.

Nous utiliserons aussi les abbréviations suivantes : (φ → ψ) pour (¬φ ∨ ψ), et (φ ↔ ψ) pour ((φ → ψ) ∧ (ψ → φ)).

Exercice 1.15 Deux formules φ(x̄) et ψ(x̄) sont équivalentes si et seulement si ∀x̄ (φ(x̄) ↔ ψ(x̄)) est vrai dans toute L-structure.

Exercice 1.16 Dans une conjonction ou une disjonction de plusieurs arguments, φ_{0} ∧ ⋯ ∧ φ_{n} ou φ_{0} ∨ ⋯ ∨ φ_{n}, tout choix des parenthèses donne une formule équivalente.

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 1.17 Un ensemble Φ de L-énoncés élimine les quanteurs si modulo Φ toute formule est équivalente à une formule sans quanteurs.

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

Démonstration : Par récurrence sur le nombre de quanteurs.

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

Définition 2.1 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 ⊧ ¬φ.

Convention 2.2 Conformément a notre convention sur l’égalité, les axiomes habituels sur = feront partie de toute théorie.

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(𝔐, ∅).

Exemple 2.3 La théorie des ordres denses sans extrémité est une L_{ord}- théorie complète.

Le maximum que l’on peut dire dans notre langage d’une structure est sa théorie ; nous verrons plus tard que sauf si 𝔐 est fini, il est impossible que Th(𝔐) caractérise 𝔐 à isomorphisme près. Donc, on définit :

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

Exemple 2.5 ⟨ℚ, <⟩ ≡ ⟨ℝ, <⟩ et ⟨ℤ, <⟩ ≡ ⟨ℤ^{2}, <_{lex}⟩, où <_{lex} est l’ordre lexicographique. Par contre, ⟨ℕ, <⟩ ≢ ⟨ℤ, <⟩, comme l’énoncé ∃x ¬∃y y < x est vrai dans ℕ mais faux dans ℤ.

Exercice 2.6 Deux L-structures 𝔐 et 𝔑 sont élémentairement équivalentes si et seulement si Th(𝔐) = Th(𝔑).

Définition 2.7 Soit 𝔑 une L-structure. Une L-structure 𝔐 est une sousstructure 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 2.8 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 𝔐.

Exemple 2.9 ⟨ℚ, <⟩ \underline{≺} ⟨ℝ, <⟩ et ⟨\{0\} × ℤ, <_{lex}⟩ \underline{≺} ⟨ℤ^{2}, <_{lex}⟩. Par contre, ⟨2ℤ, <⟩ \underline{⊀} ⟨ℤ, <⟩; l’énoncé ∃x (0 < x ∧ x < 2) est faux dans 2ℤ mais vrai dans ℤ.

Exercice 2.10 Soit 𝔐 une sous-structure de 𝔑. Alors 𝔐 \underline{≺} 𝔑 si et seulement si Th(𝔐, M) = Th(𝔑, M).

Exercice 2.11 Soient 𝔐 ⊆ 𝔑 ⊆ 𝔑′ des L-structures.

1. Si 𝔐 \underline{≺} 𝔑 \underline{≺} 𝔑′, alors 𝔐 \underline{≺} 𝔑′.

2. Si 𝔐 \underline{≺} 𝔑′ et 𝔑 \underline{≺} 𝔑′, alors 𝔐 \underline{≺} 𝔑. Trouver un exemple avec 𝔐 \underline{≺} 𝔑′, 𝔐 \underline{≺} 𝔑, mais 𝔑 \underline{⊀} 𝔑′.

Lemme 2.12 Soit (𝔐_{i} : i < ω) une chaîne élémentaire de L-structures (𝔐_{i} \underline{≺} 𝔐_{i+1} pour tout i < ω). Alors 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 < ω.

Il s’en suit que 𝔐_{i} est une sous-structure de 𝔐 pour tout i < ω. Pour vérifier qu’elle soit élémentaire, il nous suffit de voir par récurrence sur le nombre de symboles logiques que les quanteurs existentiels sont préservés de la droite à la gauche. Supposons donc 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 hypothèse de récurrence 𝔐_{j} ⊧ φ(m_{0}, m̄), d’où 𝔐_{j} ⊧ ∃x φ(x, m̄). Comme 𝔐_{i} \underline{≺} 𝔐_{j}, on a 𝔐_{i} ⊧ ∃x φ(x, m̄).

Remarque 2.13 Plus généralement, pour φ(x̄) une formule avec paramètres dans une structure 𝔐, on pose φ^{𝔐} = {m̄ ∈ M^{|x̄|} : 𝔐 ⊧ φ(m̄)}.

Il n’est pas toujours facile de vérifier qu’une sous-structure est élémentaire, puisque l’on doit connaître la satisfaction des énoncés dans les deux structures. Voici un critère utile qui ne mentionne que la satisfaction dans la grande structure :

Proposition 2.14 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̄).

Mais comment peut-on trouver ce témoin m_{0} du test de Tarski ?

Définition 2.15 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.

Remarque 2.16 Pour être précis, on doit également inclure dans T_{Skolem} les énoncés précisant que l’égalité soit une congruence pour toutes les fonctions de Skolem ainsi introduits.

Lemme 2.17 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}.

Démonstration : Soit 𝔐 un modèle de T ; nous choisissons un élément m_{0} ∈ M et interprétons f_{φ} sur 𝔐 comme suivant :

– Si 𝔐 ⊧ ∃x φ(x, m̄), on choisit m_{φ} ∈ M tel que 𝔐 ⊧ φ(m_{φ}, m̄) et met f_{φ}(m̄) = m_{φ}.

– Si 𝔐 ⊧ ¬∃x φ(x, m̄), alors f_{φ}(m̄) = m_{0}. Il est évident que cette structure 𝔐_{Skolem} satisfait 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 2.18 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 𝔑.

Démonstration : Comme M est clos par les fonctions dans F, il est une sous-structure ; si 𝔑 ⊧ ∃x p(x, m̄) avec m̄ ∈ M, alors f_{φ}(m̄) ∈ M est le témoin pour l’application du test de Tarski.

Corollaire 2.19 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{≺} 𝔑.

La compacité

Rappelons qu’un ensemble d’énoncés est consistant s’il a un modèle. On l’appellera finiment consistant si toutes ses parties finies ont un modèle.

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

Le réciproque est bien sûr évident.

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

Démonstration : Supposons que ni Φ ∪ {φ}, ni Φ ∪ {¬φ} soit finiment consistant. Donc il y a deux parties finies Φ_{0} et Φ_{1} de Φ, telles que ni Φ_{0}∪{φ}, ni Φ_{1} ∪ {¬φ} sont consistants. Soit 𝔐 un modèle de Φ_{0} ∪ Φ_{1}, qui existe par hypopthèse. Mais alors soit 𝔐 ⊧ φ et Φ_{0} ∪ {φ} est consistant, soit 𝔐 ⊧ ¬φ et Φ_{1} ∪ {¬φ} est consistant, contradiction.

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

Démonstration : Tout sous-ensemble fini de la réunion des Φ_{i} est déjà sous-ensemble de Φ_{i_{0}} pour i_{0} suffisamment grand, et a donc un modèle par hypothèse.

Remarque 3.4 Le lemme est valable pour toute chaî ne (Φ_{i} : i ∈ I) pour un ordre total (I, i) telle que i ≤ j implique Φ_{i} ⊆ Φ_{j}.

Lemme 3.5 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 3.2 soit Φ_{i} ∪ {φ_{i}}, soit Φ_{i} ∪ {¬φ_{i}} est finiment consistant, et on trouve Φ_{i+1}. Aux étapes limites, on prend la réunion des Φ_{i} précédents, ce qui est finiment consistant par le lemme 3.3. A la fin, la réunion de tous les Φ_{i} donne l’ensemble Φ̄ recherché.

Notons que si Φ est finiment consistant, il est impossible que φ et ¬φ soient simultanément dans Φ.

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

Démonstration : Si Φ_{0} est un sous-ensemble fini de Φ_{Skolem}, soit Φ_{1} := Φ_{0} ∩ Φ. Alors Φ_{0} ⊆ Φ_{1}_{Skolem}; par hypothèse Φ_{1} a un modèle 𝔐, qui a une expansion 𝔐_{Skolem} ⊧ Φ_{1}_{Skolem} par le lemme 2.17. Donc les parties finies de Φ_{Skolem} ont des modèles.

Démonstration du Théorème 3.1. 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 3.5 et 3.6, et Φ̃ est finiment consistant par le lemme 3.3. 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 va maintentant construire un modèle 𝔐 de Φ̃, et donc de Φ. Le domaine M est l’ensemble des L̃-termes clos, quotienté par l’égalité. On pose

– c^{𝔐} := c/=, pour toute constante c;

– f^{𝔐}(t_{1}/=, …, t_{n}/=) := f(t_{1}, …, t_{n})/=, pour toute fonction n-aire de L̃ (y inclus les fonctions de Skolem), 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. Ceci términe la demonstration du théorème de la compacité.

Exemple 3.7 Il n’y a pas d’ensemble Φ de L_{ord}-énoncés dont les modèles sont précisément les ordres finis.

Démonstration : Supposons que Φ est un tel ensemble, et considérons l’ensemble de L-énoncés Ψ suivant :

Φ ∪ {∃x_{1} ⋯ ∃x_{n} ⋀_{i<j} x_{i} ≠ x_{j} : n < ω}.

Pour tout sous-ensemble fini Ψ_{0} de Ψ soit n_{0} maximal tel que Ψ_{0} contient l’énoncé ∃x_{1} ⋯ ∃x_{n} ⋀_{i<j} x_{i} ≠ x_{j}, et soit 𝔐_{0} un ordre fini de cardinalité n_{0}.

Comme 𝔐_{0} ⊧ Φ et a n_{0} éléments, 𝔐_{0} ⊧ Ψ_{0}. Donc chaque sous-ensemble fini de Ψ a un modèle ; par compacité Ψ a un modèle 𝔐. Comme 𝔐 ⊧ Φ, il est un ordre fini. Mais 𝔐 a au moins n éléments pour chaque n < ω, contradiction.

Exercice 3.8 Démontrer qu’il n’y a pas d’ensemble Φ(x) de L_{gp}-formules tel que dans tout groupe G un élément g satisfait Φ(x) si et seulement si l’ordre de g est fini.

Maintenant nous allons voir que l’équivalence élémentaire ne peut pas déterminer le cardinal d’une L-structure, sauf si elle est finie.

Lemme 3.9 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 3.10 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 3.9 on trouve 𝔑′ \underline{≻} 𝔐 de cardinal au moins λ; par Löwenheim-Skolem descendant il y a 𝔑 \underline{≺} 𝔑′ contenant 𝔐 de cardinal λ, et 𝔐 \underline{≺} 𝔑.

Types

Définition 4.1 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.

Exercice 4.2 Si p est un type en x̄ sur A, alors pour toute formule φ(x̄) à paramètres dans A soit φ ∈ p, soit ¬φ ∈ p.

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.

Exemple 4.3 Dans la théorie des ordres denses, un 1-type sur A correspond à la coupure qu’il détermine dans A.

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 ouvert-fermés. Le théorème de compacité implique que c’est un espace compact.

Proposition 4.4 Soit 𝔐 une L-structure, A ⊆ M et p(x̄) ∈ S_{n}(A). Alors il y a 𝔑 ≻ 𝔐 et c̄ ∈ N tel que p = tp(c̄/A). Deux uples ā et ā′ on même type sur A si et seulement s’il y a 𝔑 ≻ 𝔐 et un automorphisme de 𝔑 qui fixe A et envoie ā à ā′.

Démonstration : Toute partie finie de Th(𝔐, M) ∪ p(c̄) (où c̄ sont des nouvelles constantes) est satisfaite dans 𝔐. Par compacité il y a un modèle 𝔑 de Th(𝔐, M) ∪ p(c̄) ; comme l’application M ∋ m ↦ m^{𝔑} est élémentaire, on peut considérer 𝔑 comme extension élémentaire de 𝔐. On pose ā = c̄^{𝔑}; il est évident que tp(ā/A) = p(x̄). Maintenant 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 𝔑 = ⋃_{i<ω} 𝔐_{i} sera une extension élémentaire de 𝔐, et σ = ⋃_{i<ω} σ_{i} sera un automorphisme de 𝔑 qui fixe A et envoie ā à ā′.

Lemme 4.5 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. Il nous faut voir que la théorie Φ suivante est consistante :

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 4.5 d’abord à 𝔐_{0} et σ_{0} pour obtenir 𝔐_{1} et σ_{1}, ensuite à 𝔐_{1} et σ_{1}^{−1} pour obtenir 𝔐_{2} et σ_{2}^{−1}, etc.

Nous avons vu qu’on peut toujour trouver un modèle qui réalise un type. Mais est-ce qu’on peut en trouver un qui ne le réalise pas ?

Définition 4.6 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.

Une reformulation nous donne : φ(x̄) isole tp(ā/A) si et seulement si Th(𝔐, A)∪ {φ(ā)} ⊧ Th(𝔐, Aā)}. Il est évident qu’un type principal est réalisé dans chaque modèle contenant A, comme ∃x̄ φ(x̄) fait partie de Th(𝔐, A). Pour le réciproque, il faut que L(A) soit dénombrable.

Théorème 4.7 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.

Nous allons maintenant une méthode pour obtenir des types particuliers.

Définition 4.8 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 4.9 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 4.10 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 4.11 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.

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

Dans ce chapître, I sera toujours un ensemble infini totalement ordonné.

Définition 5.1 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 5.2 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).

Démonstration : Simple application de la compacité.

Pour construire des suites indiscernables, on a besoin d’un théorème combinatoire :

Théorème 5.3 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 sous-ensemble 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 sousensemble 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 5.4 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 5.5 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 5.6 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 j 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.

Démonstration : (1) ⇔ (3) et (5) ⇔ (6) suivent par compacité ; (3) ⇔ (4) par le théorème 5.4. (3) ⇒ (5) est immédiat. Supposons donc (5). Mais alors par indiscernabilité pour tout J ⊆ ω il existe b̄_{J} dans une extension élémentaire 𝔑 tel que 𝔑 ⊧ φ(ā_{i}, b̄_{J}) si et seulement si i ∈ J, contradiction. Enfin, pour montrer (1) ⇒ (2) (et donc le converse par symétrie), fixons n < ω et considérons une énumération (I_{i} : i < 2^{n}) des sous-ensembles de n. Soient (J_{j} : j < n) des sous-ensembles de 2^{n} tels que i ∈ J_{j} si et seulement si j ∈ I_{i}. Si (ā_{i} : i < 2^{n}) et (b̄_{J} : J ⊆ 2^{n}) témoignent de la propriété d’indépendance pour φ au niveau 2^{n}, alors (b̄_{J_{j}} : j < n) et (ā_{i} : i < 2^{n}) en témoignent pour φ^{∗}.

Corollaire 5.7 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émonstration : Si une formule φ(x̄) et sa négation est satisfaite par une infinité de ā_{i}, alors on trouve i_{0} < i_{1} < ⋯ telle que 𝔐 ⊧ φ(ā_{i_{j}}) si et seulement si j est pair, ce qui contredit le lemme 5.6. Ceci montre complétude et consistance.

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

Proposition 5.9 Si T a la propriété d’indépendance, alors il existe une formule φ(x, ȳ) qui l’a par rapport à T, où x est un singleton.

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. (Rappelons que pour un ordre J l’ordre J · ω est l’ordre sur J repété ω fois, et qu’un élément de J · ω est pair si sa coordonné dans J est pair.) Supposons qu’aucune formule ψ(x, ȳ) ait la propriété d’indépendance.

Lemme 5.10 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 5.6. 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 5.11 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 5.12 Si T est faiblement o-minimale, alors pour toute formule φ(x, ȳ) il xiste 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.

Démonstration : Sinon, par compacité il existe un modèle 𝔐 et b̄ ∈ M tel qu’il y ait a_{0} < a_{1} < a_{2} < ⋯ avec 𝔐 ⊧ φ(a, b̄) si et seulement si i est pair, contradiction à l’o-minimalité faible.

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

Démonstration : Par le lemme 5.12 une formule φ(x, ȳ) ne peut pas avoir la propriété d’indépendance.

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

Dans ce chapitre, nous démontrerons le théoremème suivant :

Théorème 6.1 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^{k}, 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 : Toutes les formules seront des L-formules, sauf mention du contraire. Pour une formule ψ(x̄, y) = ψ(x̄, y, c̄) avec paramètre c̄ ∈ N et |x̄| = k considérons l’ensemble

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

Lemme 6.2 Soit U un ultrafiltre sur M^{k} contenant X_{ψ}. Alors il existe une L(N)-formule φ 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 4.11 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. Nous prétondons que la suite (ā_{i}b_{i} : i ≤ ω) est indiscernable au dessus de 𝔐. En fait, 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),

où tp_{Δ}(ā/B) est l’ensemble des instances de formules dans Δ dans tp(ā/B). 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 5.6.

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 6.2 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.