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

mardi 7 octobre 2003

Loi zéro-un non-étiquetée

On veut maintenant prouver une loi zéro-un où on compte les structures à isomorphisme près. On note U_{n}(K) (U_{n}(τ), U_{n}(φ)) le nombre de structures de K (de τ-structres, de modèles de φ) de taille n, à isomorphisme près. On pose u(K) = lim_{n→∞}U_{n}(K)/U_{n}(τ) si elle existe. On définit de même u(φ) ainsi que les versions conditionnelles u_{n}(K|H) = U_{n}(K ∩H)/U_{n}(H) et u(K|H) sa limite éventuelle.

Question 1. – Une structure est dite rigide si elle n’a pas d’automorphisme non trivial. On note R la classe des structures rigides.

a) Donner une relation entre U_{n}(K) et L_{n}(K) dans le cas général, dans le cas où K ⊂ R et dans le cas où K ⊂ R^{c}.

b) Montrer que pour toute classe H on a u_{n}(R|H) ⩽ l_{n}(R|H).

c) Soit H, K deux classes de structures. Montrer que si u(R|H) = 1 alors l(K|H) = u(K|H).

d) Soit H une classe de structures. Montrer que u(R|H) = 1 si et seulement si

lim_{n→∞} \frac{L_{n}(H)}{U_{n}(H) · n!} = 1.

Question 2. – Soit τ une signature relationnelle contenant une relation d’arité au moins 2. On veut montrer que u(R|τ) = 1. On suppose pour simplifier que τ possède une relation binaire.

a) Pourquoi suffit-il de traiter le cas où τ est composée d’une relation binaire uniquement ? On considère maintenant τ = {E} avec E binaire.

b) Pour ρ ∈ S_{n}, on note I(ρ) le nombre de graphes à n sommets étiquetés invariants sous l’action de ρ. Montrer que

U_{n}(τ) = \frac{1}{n!} ∑_{ρ∈S_{n}} I(ρ).

c) Pour une permutation ρ, on note c(ρ) le nombre de cycles de ρ et s(ρ) le nombre de points non fixés par ρ. Soit ρ ∈ S_{n}; montrer que c(ρ) ⩽ n − s(ρ)/2.

d) Pour ρ ∈ S_{n}, on note ρ̃ la permutation de {1, …, n}^{2} définie par ρ̃((i, j)) = (ρ(i), ρ(j)). Evaluer I(ρ) en fonction de c(ρ̃).

e) Montrer que ∑_{ρ∈S_{n}\{Id}} 2^{c(ρ̃)−n^{2}} → 0.

f) En déduire la loi zéro-un non-étiquetée dans ce cas.

Question 3. – Reste le cas où τ est composée de relations unaires uniquement.

a) Les τ-structures sont-elles presque sûrement rigides ?

b) Montrer que toute formule du premier ordre sur τ est équivalente à une combinaison booléenne de formules de la forme ∃^{=l}x ψ(x) où ψ(x) est une conjonction de τ-formules atomiques (on pourra commencer par le montrer pour les formules de Hintikka).

c) En deduire la loi zéro-un non-étiquetée.