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

mardi 30 septembre 2003

Une loi zéro-un

On fixe une signature τ. Pour une classe K de τ-structures on note L_{n}(K) le nombre de structures de K de domaine {1, …, n}. On note L_{n}(φ) le nombre de modèles de φ de domaine {1, …, n}, et L_{n}(τ) le nombre de τ-structures de domaine {1, …, n}. Pour K une classe de τ-structures, on définit l_{n}(K) = L_{n}(K)/L_{n}(τ). On définit de même l_{n}(φ) = L_{n}(φ)/L_{n}(τ). On pose l(φ) = lim_{n→∞}l_{n}(φ) si elle existe. On dit qu’un ensemble de formules Ψ vérifie la loi zéro-un étiquetée si pour toute formule φ ∈ Ψ on a l(φ) = 0 ou l(φ) = 1.

Question 1. – A-t-on une loi zéro-un dans les cas suivants ?

a) τ = {P, c}, avec P unaire et c une constante, et Ψ = FO.

b) τ = {f}, avec f symbole de fonction unaire, et Ψ = FO.

c) τ = ∅ et Ψ = L_{∞ω}.

Question 2. – Soit τ une signature relationnelle finie.

a) Écrire les axiomes d’extension : ils expriment que pour tout ensemble de r éléments distincts, il existe un autre élément qui vérifie les relations unaires que l’on souhaite, et entretient exactement les relations que l’on veut avec les r autres points. On note T la théorie composée de tous les axiomes d’extension (pour tout r).

b) Montrer que tout modèle de T est infini. Montrer que T a un modèle dénombrable.

c) Montrer que T n’a qu’un seul modèle dénombrable (à isomorphisme près).

d) Une autre construction de cette structure est la suivante – on le fait pour un graphe uniquement et on l’admet dans le cas gnral. Soit ℕ l’ensemble des sommets. Pour chaque paire {i, j} avec i ≠ j, on tire à pile ou face si on place une arête entre i et j, tous les tirages étant indépendants. Montrer que le graphe obtenu vérifie tous les axiomes d’extension avec probabilité 1. Ceci justifie le nom de graphe (ou τ-structure) aléatoire.

Question 3. – Soit τ une signature relationnelle finie.

a) Montrer que tout axiome d’extension φ vérifie l(φ) = 1.

b) En déduire que pour la signature τ, la logique du premier ordre vérifie la loi zéro-un.