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

jeudi 25 septembre 2003

La logique du premier ordre exprime des propriétés locales

Pour une structure relationnelle finie A de domaine A, on définit le graphe de Gaifman associé G(A) = (A, E) de la manière suivante : (x, y) ∈ E si x et y appartiennent à un même uple d’une relation de A. On note d la distance dans ce graphe, et S(a, r) la boule de centre a et de rayon r.

Question 1. – Soit A et B deux structures relationnelles finies, m un entier et e un majorant strict des cardinaux des boules de rayons 3^{m} de ces deux structures. On suppose que pour tout type t de 3^{m}-boule, si A et B n’ont pas le même nombre de boules de types t, alors elles en ont toutes deux plus de m · e. Montrer que A ≡_{m} B (théorème de Hanf).

Question 2. – En déduire (à nouveau) que la connexité d’un graphe fini ne s’exprime pas au premier ordre.

Question 3. – On veut montrer que la connexité des graphes finis ne s’exprime pas par une formule du type ∃P_{1} … ∃P_{r}ψ où les P_{i} sont des relations unaires et ψ du premier ordre sur le langage augmenté de P_{1}, …, P_{r}.

a) On considère la signature τ = {E, P_{1}, …, P_{r}}. On note C_{l} le cycle de longueur l. Soit m ⩾ 0. Montrer qu’il existe l_{0} tel que pour tout l ⩾ l_{0}, dans toute τ-structure de la forme (C_{l}, P_{1}, …, P_{r}) il existe a, b ∈ C_{l} tels que les boules S(a, 3^{m}) et S(b, 3^{m}) sont disjointes et isomorphes.

b) Conclure.

Question 4. – Montrer que la connexité s’exprime par une formule du type ∀P ψ, avec P unaire et ψ du premier ordre.

Question 5. – Montrer que la connexité s’exprime par une formule du type ∀x∀y∃P ψ, avec P unaire et ψ du premier ordre.