Partiel – Complexité descriptive et théorie des modèles finis Natacha Portier

mardi 18 novembre 2003

Documents autorisés : notes de cours et de TD, pas de livre N’oubliez pas de rédiger !

Question 1. – Si A est un ensemble ordonné fini et l un entier, ◁^{l} A désigne l’union disjointe ordonnée de l copies de A. Considérons le langage relationnel constitué de la relation binaire <. Montrer que dans ce langage, pour tous les entiers m ≥ 1 et l, k > 2^{m} et tout ensemble ordonné A, on a ◁^{l} A ≅_{m}◁^{k} A.

Question 2. – Montrer le théorème suivant (Trahtenbrot) en utilisant une réduction du problème de l’arrêt :

Théorème 1 Il existe un vocabulaire τ tel que l’ensemble suivant ne soit pas décidable : Sat[τ] = {φ|φ est un énoncé du premier ordre sur le vocabulaire τ satisfiable par un modèle fini}

Question 3. – Soit p un réel strictement compris entre 0 et 1 et τ un vocabulaire relationnel. On construit une structure A de cardinal n sur τ de la manière suivante : pour tout symbole R de τ d’arité m et tout uple i_{1}...i_{m} de A, i_{1}...i_{m} ∈ R avec probabilité p. Soit l_{n}(φ) la probabilité qu’une formule φ soit satisfaite par une structure de cardinal n. Calculer pour tout axiome d’extension φ la limite éventuele de l_{n}(φ).