TD n^{o}1 – Complexité descriptive et théorie des modèles finis Natacha Portier

mardi 23 septembre 2003

Jeux d’Ehrenfeucht-Fraïssé

Les jeux sont une technique très utile pour montrer qu’on ne peut pas exprimer certaines propriétés dans une logique donnée. On s’intéresse ici à la logique du premier ordre. Soit τ une signature composée de constantes et de relations uniquement. Soient A et B deux τ-structures finies, de domaines A et B respectivement. Un jeu d’Ehrenfeucht-Fraïssé de longueur m ∈ ℕ se passe de la manière suivante. À chaque coup, le joueur 1 joue en premier et choisit soit un élément dans A, soit un élément dans B. Le joueur 2 doit alors choisir un élément dans l’autre structure. Appelons a_{i} ∈ A et b_{i} ∈ B les deux éléments choisis au coup i. À la fin de la partie, après m coups, le joueur 2 a gagné si et seulement si l’application a_{i} ↦ b_{i} est un isomorphisme partiel de τ-structures – c’est à dire si pour toute formule atomique ψ(x_{1}, …, x_{m}), A ⊧ ψ(a_{1}, …, a_{m}) si et seulement si B ⊧ ψ(b_{1}, …, b_{m}). Sinon c’est le joueur 2 qui gagne. L’idée est que le joueur 1 veut montrer que les structures A et B sont différentes, alors que le joueur 2 veut montrer qu’elles se ressemblent. Si le joueur 2 a une stratégie gagnante, on écrit A ≅_{m} B. On rappelle qu’on note A ≡_{m} B si A et B vérifient les mêmes formules de rang de quantification au plus m.

Théorème 1 (Ehrenfeucht-Fraïssé) Pour toutes τ-structures finies A et B, A ≡_{m} B si et seulement si A ≅_{m} B.

Question 1. – Applications du théorème 1.

1) Soit τ = ∅. On veut montrer qu’il n’existe pas de formule du premier ordre exprimant que le cardinal du domaine de la structure est pair.

a) Supposer par l’absurde qu’une telle formule existe. Appelons m son rang de quantification.

b) Choisir deux structures finies A et B avec |A| pair et |B| impair, et telles que A ≅_{m} B.

c) Conclure.

2) Soit τ = {<}, < binaire. On se restreint à la classe des structures totalement ordonnées par <. Montrer qu’il n’existe pas de formule du premier ordre exprimant que le cardinal du domaine de la structure est pair.

3) Soit τ = {E}, E binaire. On se restreint à la classe des graphes (E étant la relation d’adjacence). Montrer qu’on ne peut pas exprimer au premier ordre la connexité.

Question 2. – Démonstration du théorème 1.

1) Vérifier que A ≅_{m+1} B si et seulement si pour tout a ∈ A, il existe b ∈ B tel que (A, a) ≅_{m} (B, b) et pour tout b ∈ B, il existe a ∈ A tel que (A, a) ≅_{m} (B, b).

2) Montrer que A ≅_{m} B implique A ≡_{m} B.

3) On définit le type de m-isomorphisme φ_{A,ā}^{m} d’un uple (éventuellement vide) ā = (a_{1}, …, a_{s}) d’éléments de A dans la structure A par les formules suivantes (appelées formules de Hintikka). On pose v̄ = (v_{1}, …, v_{s}) et

φ_{A,ā}^{0}(v̄) := ⋀{φ(v̄) | φ atomique ou ¬atomique, A ⊧ φ(ā)}

et pour m > 0,

φ_{A,ā}^{m}(v̄) := ⋀_{a∈A} ∃v_{s+1}φ_{A,āa}^{m−1}(v̄, v_{s+1}) ∧ ∀v_{s+1} ⋁_{a∈A} φ_{A,āa}^{m−1}(v̄, v_{s+1}).

Vérifier que les formules φ_{A,ā}^{m} sont bien du premier ordre, et que le rang de quantification de φ_{A,ā}^{m} est m.

4) Pour ā ∈ A^{s} et b̄ ∈ B^{s} montrer, par récurrence sur m, que (A, ā) ≅_{m} (B, b̄) si et seulement si B ⊧ φ_{A,ā}^{m}(b̄).

5) En déduire que A ≡_{m} B implique A ≅_{m} B.