Cours 9 : Deuxième théorème d’incomplétude de Gödel, Jeux d’Ehrenfreucht-Fraïssé

Introduction

  • La preuve que si les fonctions récursives sont représentables, alors la théorie est indécidable :

    \[P = \lbrace (n, m) \mid \text{ il existe } x \text{ tq } n = ⟨𝜑(x)⟩ \text{ et } T\vDash 𝜑(\overline{n}) \rbrace\]

    Problème : quand on demande “P est-il récursif ?” dans la preuve ⟶ trop fort.

  • NB : La preuve originale de Gödel utilise la

$𝜔$-cohérence :

si pour tout $n∈ℕ$, $T \vDash 𝜑(\overline{n})$, alors $T \not\vDash ∃z; ¬ 𝜑(z)$

On va faire dans ce cours une preuve plus générale, qui n’exigea pas la $𝜔$-complétude.

Jeux d’Ehrenfreucht-Fraïssé

Expressivité de la logique du premier ordre (pour nous), des logiques modales, etc…

Soient deux $F, P$-structures $S_1, S_2$ isomorphes.

alors $S_1$ et $S_2$ sont élémentairement équivalentes $S_1 ≡ S_2$ :

elles satisfont les mêmes formules : pour toute $𝜑$ close, \(S_1 \vDash 𝜑 ⟺ S_2 \vDash 𝜑\)

Mais la réciroque n’est pas vraie (cf. $ℚ$ et $ℝ$) ⟶ on voudrait une notion algébrique qui capture cette notion d’élémentaire équivalence.

Isomoprhisme partiel :

isomorphisme pour un sous-ensemble fini des domaines (isomorphismes de domaines finis)

⟶ tous les isomorphismes partiels peuvent se prolonger en d’autres isomorphismes partiels.

Isomorphismes partiels

  • Jeux : arène sur deux structures $S_1, S_2$

  • Deux joueurs : S(poiler) et D(uplicator)

  • $n$ rounds

  • $S$ choisit des éléments arbitrairement

    • objectif de $D$ : construire un isomorphisme partiel
    • objectif de $S$ : bloquer $D$ ⟶ pas d’isomorphisme partiel possible

Th principal : les structures sont élémentairement équivalentes ssi le Duplicator a une stratégie gagnante

i.e : le Duplicator peut toujours entretenir un isomorphisme partiel

Isomorphisme partiel de $S_1$ dans $S_2$ :

c’est une fonction injective $h: D_{S_1} ⟶ D_{S_2}$ tq

  • $Dom(h) ≝ \lbrace a_1, ⋯, a_n \rbrace$ est fini

  • pour tous $a, a_{j_1}, ⋯, a_{j_m} ∈ Dom(h)$,

    \[a =_{S_1} f^{S_1} (a_{j_1}, ⋯, a_{j_n}) \text{ ssi } h(a) =_{S_2} f^{S_2}(h(a_{j_1}, ⋯, h(a_{j_n})))\]

  • pour tout $P ∈ ℙ$ d’arité $m$ et pour tous $a, a_{j_1}, ⋯, a_{j_m} ∈ \lbrace a_1, ⋯, a_n \rbrace$,

    \[P^{S_1} (a_{j_1}, ⋯, a_{j_n}) \text{ ssi } P^{S_2}(h(a_{j_1}, ⋯, h(a_{j_n})))\]

Ex 1 :

\[ℙ ≝ \lbrace =, R(2) \rbrace\]

$S_1, S_2$ des graphes : $S_1$ est un graphe orienté de sommets $a, b, c, d$, $S_2$ le graphe non orienté (orienté dans les deux sens) obtenu à partir de $S_1$.

$S_1$ :

  digraph {
    rankdir=TB;
    a -> b, d;
    c -> a;
    d -> c;
    b -> c, d;
  }

$S_2$ :

  graph {
    rankdir=TB;
    a -- b, d;
    c -- a;
    d -- c;
    b -- c, d;
  }

  • Isomorphisme partiel de domaine à un élément : $a ⟶_h a$

  • Isomorphisme partiel de domaine à deux éléments : il n’y en a pas (aucun sommet n’est relié à un autre dans les deux sens dans $S_2$) :

    • dans $S_2$ : si $s_1 ≠s_2$ : \(R^{S_2}(s_1, s_2) \text{ et } R^{S_2}(s_2, s_1)\)

    • alors que dans $S_1$ : on n’a pas :

    \[R^{S_2}(h(s_1), h(s_2)) \text{ et } R^{S_2}(h(s_2), h(s_1))\]

⟶ la formule $∀x≠y, R(x, y)$ est satisfaite dans $S_2$ mais pas dans $S_1$.

Ex 2 : La connexité des graphes n’est pas exprimable au premier ordre.

$S_1$ :

  digraph {
    rankdir=LR;
    c -> b -> a -> c;
    "c'" -> "b'" -> "a'" -> "c'";
  }

$S_2$ :

  digraph {
    rankdir=LR;
    c -> b -> a -> c;
  }

Qeustion : est-ce qu’il existe un isomorphisme partiel de domaine $a, a’$ ?

Non car on va envoyer $a$ et $a’$ sur deux éléments reliés entre eux dans $S_2$.

$S_1$ :

  digraph {
    rankdir=LR;
    c -> b -> a -> d -> c;
    "c'" -> "b'" -> "a'" -> "d'" -> "c'";
  }

$S_2$ :

  digraph {
    rankdir=LR;
    c -> b -> a -> d -> c;
  }

Isomorphisme partiel de domaine à deux éléments ? :

  • Oui : $a ⟶ a, a’ ⟶ d$
  • mais pas de domaine à trois éléments

Ex 3 :

  • $F = \lbrace 0(0), +(2) \rbrace$

  • $P = \lbrace = \rbrace$

  • $S_1 = ℤ$

  • $S_2 = ℝ$

  • $h(3)=4, h(4) =12$ ⟶ iso partiel
  • mais avec en plus $h(6)=8$ (valeur nécessaire à cause de $3+3$), on n’a plus un iso partiel : $8+4=12$ mais $6+3≠4$

Ex 4 :

$F = ∅, ℙ = \lbrace >(2), =(2) \rbrace$

  • $S_1 = ℚ, S_2 = ℝ$

Mq si $h : \lbrace a_1, ⋯, a_n\rbrace ⟶ \lbrace h(a_1), ⋯, h(a_n) \rbrace$ est un iso partiel, alors pour tout $a∈ℚ$, on peut prolonger $h$ à $a ≠ a_i$ (pour tout $i$).

  • Si $a< a_i$ pour tout $i$, on pose $h(a) = \min (h(a_i)) - 1$

  • Si $a >a_i$ pour tout $i$, on pose $h(a) = \max (h(a_i)) + 1$

  • Sinon : on pose $h = \frac{ \max \lbrace a_i \mid a_i < a \rbrace + \min \lbrace a_i \mid a_i > a \rbrace }{2}$

$m∈ℕ$

\[S_1 ≡_m S_2\]

ssi pour toute formule $𝜑$ de taille au plus $m$,

\[S_1 \vDash 𝜑 ⟺ S_2 \vDash 𝜑\]
\[S_1 ≃_m S_2\]

ssi pour toute formule $𝜑$ de rang au plus $m$,

\[S_1 \vDash 𝜑 ⟺ S_2 \vDash 𝜑\]
Rang de $𝜑$ :

nombre maximum de quantificateurs sur un chemin de l’arbre de $𝜑$

Lemme : \(S_1 ≡ S_2 \text{ ssi } S_1 ≃_m S_2 \text{ ssi } S_1 ≡_m S_2\)

formules plates :

  • $x = f(x_1, ⋯, x_n)$
  • $x = y$
  • $P(x_1, ⋯, x_n)$

Lemme : toute formule de taille $n$ est logiquement équivalente à une formule plate de rang au plus $n$

Lemme :

\(h : \underbrace{\lbrace a_1, ⋯ , a_n \rbrace}_{⊆ S_1} ⟶ D_{S_2}\) est un iso partiel ssi pour toute formule $𝜑$ atomique plate de var libres $x_1, ⋯, x_n$ :

\[S_1, \underbrace{\lbrace x_1 \mapsto a_1, ⋯, x_n \mapsto a_n \rbrace}_{𝜎_1} \vDash 𝜑 \\ \text{ ssi } S_2, \underbrace{\lbrace x_1 \mapsto h(a_1), ⋯, x_n \mapsto h(a_n) \rbrace}_{𝜎_2} \vDash 𝜑\]

Selon la structure de $𝜑$ plate :

  • si c’est une égalité de variables, le résultat découle de l’injectivité de $h$

  • si c’est une égalité variable-fonction, on conclut par déinition de l’iso partiel

  • idem pour les prédicats

Réciproquement : de même,

  • pour $𝜑 ≝ x_i = x_j$, on obtient $h$ injective

  • idem pour la suite

Jeux d’Ehrenfreucht-Fraïssé

  • $N$ : nombre de rondes fixé, ou choisi par le Spoiler.

Pour $i$ allant de $1$ à $N$ :

  • $S$ choisit $a_i^j$ dans $S_j$
  • $D$ choisit $a_i^{3-j}$ dans $S_{3-j}$

On a une séquence $(a_1^1, a_1^2, ⋯ , a_N^1, a_N^2)$

$D$ gagne si

  • $a_1^1 \mapsto a_1^2$
  • $\vdots$
  • $a_N^1 \mapsto a_N^2$

est un isomorphe partiel.

Une stratégie de $D$ :

\[𝜎 : \bigcup\limits_{i=0}^{N-1} (D_{S_1}^i × D_{S_2}^i) × D_{S_j} ⟶ D_{S_{j-3}}\]
$𝜎$ est gagnante :

si pour tous $a_i^{j_i} ∈S_j$ :

\[a_1^{j_1}, 𝜎(a_1^{j_1}), a_2^{j_2}, 𝜎(a_1^{j_1}, 𝜎(a_1^{j_1}), a_2^{j_2}), \ldots\]

définit un iso partiel

Théorème d’Ehrenfreucht-Fraïssé

Th :

  • Si $D$ a une stratégie gagnante en $n$ rondes sur $S_1, S_2$, alors \(S_1 ≡_n S_2\)

  • Si $S_1 ≃_n S_2$, alors $D$ a une stratégie gagnante en $n$ rondes

1.

Le premier point se montre élémentairement par réc sur $𝜑$ plate.

On prend $𝜑$ plate et sans $∀$ (quitte à utiliser des doubles négations) et de rang inférieur à $N$ (lemme précédent sur les formules de taille inférieure à $N$).

On veut mq $S_1 ≡_N S_2$.

On montre par réc. sur $𝜑$ de var libres $x_1, ⋯ , x_k$ et de rang au plus $N-k$ que si $h$ est un iso partiel de domaine $\lbrace a_1, ⋯, a_k \rbrace$, alors :

\[S_1, \lbrace x_1 \mapsto a_1, ⋯ , x_k \mapsto a_k\rbrace \vDash 𝜑 \\ \text{ ssi } S_2, \lbrace x_1 \mapsto h(a_1), ⋯ , x_k \mapsto h(a_k) \rbrace \vDash 𝜑\]

En détails :

Soit $𝜑$ une formule de taille $n$ sans var. libres.

Mq \(S_1 \vDash 𝜑 \text{ ssi } S_2 \vDash 𝜑\)

Il suffit de mq que pour toute formule plate $𝜑$ de rang $n$ :

\[S_1 \vDash 𝜑 \text{ ssi } S_2 \vDash 𝜑\]

Sans perte de gén., on suppose que $𝜑$ ne contient pas de $∀$ (quitte à utiliser des doubles négations).

Par réc sur $\vert 𝜑 \vert$, pour tous $a_1, ⋯, a_k, b_1, ⋯, b_k$ joués suivant la stratégie de D.

Si $Var(𝜑) = \lbrace x_1, ⋯, x_k \rbrace$

\[S_1, \lbrace x_1 \mapsto a_1, ⋯ , x_k \mapsto a_k\rbrace \vDash 𝜑 \\ \text{ ssi } S_2, \lbrace x_1 \mapsto b_1, ⋯ , x_k \mapsto b_k \rbrace \vDash 𝜑\]

  • Cas de base : $𝜑$ formule atomique plate :

    Comme $h(a_i) = b_i$ définit un iso partiel, le résultat est acquis avec le lemme précédent (caractérisation des iso partiels)

  • Hérédité :

    • si $𝜑 = 𝜑_1 \star 𝜑_2$ : c’est immédiat par HR.

    • si $𝜑 = ∃x. 𝜓$ :

      Mq \(S_1, \lbrace x_1 \mapsto a_1, ⋯ , x_k \mapsto a_k\rbrace \vDash ∃x. 𝜓 \\ \text{ ssi il existe } a∈D_{S_1}; \; S_1, \lbrace x_1 \mapsto a_1, ⋯ , x_k \mapsto a_k, x \mapsto a \rbrace \vDash 𝜓\)

      Par la stratégie gagnant de D : il existe $b∈ D_{S_2}$ tq $(a_i \mapsto b_i, a \mapsto b)$ est un iso partiel. Puis, on conclut par HR.

2. Réciproque

On suppose que \(S_1 \vDash 𝜑 \text{ ssi } S_2 \vDash 𝜑\) pour une $𝜑$ tq $rg(𝜑)≤N$

Si $b_1, ⋯, b_n ∈ D_{S_2}$, on note $𝜙(b_1, ⋯, b_n) =$ formules plates atomiques et leur négation, avec $x_1, ⋯, x_n$ var libres qui sont satisfaites dans $S_2$ par $(x_1 \mapsto b_i)$

Cet ensemble est de taille finie : en $O(a^n)$ (où $a$ est l’arité maximale des fonctions et prédicats).

On pose :

\[𝜑_0^{b_1 ⋯ b_n} ≝ \bigwedge\limits_{𝜑 ∈ 𝜙(b_1, ⋯, b_n)} 𝜑\]

Exemples :

$ℚ, ℝ$, $ \lbrace= , > \rbrace$

\[𝜑_0^{1,2} ≝ x_1 = x_2 ∧ x_2 = x_2 ∧ x_2 > x_1 ∧ x_1 ≠ x_2 ∧ x_1 \not > x_2\] \[𝜑_{n+1}^{b_1 ⋯ b_n} ≝ \Bigg( ∀x_{n+1}. \, \bigvee\limits_{b ∈ D_{S_2}} 𝜑_{m}^{b_1 ⋯ b_n, b}(x_1, ⋯ , x_{n+1}) \Bigg) ∧ \Bigg( \, \bigwedge\limits_{b ∈ D_{S_2}} ∃x_{n+1}. 𝜑_{m}^{b_1 ⋯ b_n, b}(x_1, ⋯ , x_{n+1}) \Bigg)\]

L’ensemble

\[\lbrace 𝜑_{m}^{b_1 ⋯ b_n}(x_1, ⋯ , x_{n}) \mid b_i ∈ D_{S_2}, n,m∈ℕ \rbrace\]

est fini à éq. logique près.

Par réc sur $m$.

  • Si $m=0$ : l’ensemble est de card inférieur à $O(2^{\underbrace{a^n}_{≝ B(F, R)}})$

  • Pour $m+1$ :

    \(𝜑_{m+1}^{b_1 ⋯ b_n} \mapsto \lbrace 𝜑_m^{b_1 ⋯ b_n, b} \mid b ∈ D_{S_2} \rbrace\) est injective (la connaissance de l’ensemble nous donne la connaissance de la formule, par définition).

Donc

\[\vert \lbrace 𝜑_m^{b_1 ⋯ b_n} \mid b_i ∈ D_{S_2} \rbrace \vert ≤ 2^{2^{2^{\vdots^{2^{B(F, R)}}}}} \text{ avec une tour exponentielle de taille } m+1\]

En bref :

La stratégie de D est :

  1. choisir $a_n$ (resp. $b_n$) tq
\[S_1, \lbrace x_i \mapsto a_i \rbrace_i \vDash 𝜑_{N-n}^{b_1 ⋯ b_n}\]

invariant de $D$.

Puis on utilise la réciproque du lemme de caractérisation des iso partiels pour montrer qu’on obtient un iso partiel au bout de $n$ rounds.

NB :

  • quantificateur existentiel : choix du Spoiler dans $S_2$

  • quantificateur universel : choix du Spoiler dans $S_1$

Corollaire : $S_1$ et $S_2$ sont élémentairement équiv. ssi D a une stratégie gagnante pour un nb quelconque de tours.

Méthode pour mq qu’une théorie est complète

complétude d’une théorie ⟺ tous ses modèles sont élém. équivalents

Il suffit de montrer que D a une stratégie gagnante pour un nombre $n$ fixé de tours.

Application d’Ehrenfreucht-Fraïssé

Théorème :

$𝒫 = \lbrace =(2), R(2) \rbrace, F=∅$, il n’existe pas de formule du premier ordre satisfaite par tous les graphes connexes et par aucun graphe non connexe.

Mq pour tout $n∈ℕ$, il existe $S_1, S_2$ tq

  • $S_1$ connexe
  • $S_2$ non connexe
  • $S_1 ≡_n S_2$

$R_1 : \lbrace (s_i, s_{i+1}) \mid 1 ≤ i ≤ 2^n-1 \rbrace ∪ \lbrace (s_{2^n}, s_1) \rbrace$

$R_2$ : deux copies de $R_1$

Par le théorème d’EF, il suffit de mq $D$ a 1 stratégie gagnante en $n$ rondes.

On introduit une distance en deux sommets :

  • $d_1(s_i, s_j) = j - i + 2^n$ ($\mod 2^n$ dans $⟦1, 2^n⟧$)

  • $d_2(s_i^b, s_j^b) =$ idem

  • $d_2(s_i^1, s_j^2) = +∞$

Par réc sur $1≤k≤n$ ($a_1, b_1, ⋯, a_k, b_k$)

maintenons les invariants :

  1. \[∀i, j≤k, \text{ si } d_1(a_i, a_j) ≤ 2^{n-k} \text{ alors } d_2(b_i, b_j) = d_1(a_i, b_j)\]
  2. \[∀i, j≤k, d_1(a_i, a_j) > 2^{n-k} \text{ ssi } d_2(b_i, b_j) > 2^{n-k}\]
  1. Si S choisit $a_{k+1} ∈ D_{S_1}$.

Soit

  • $a_{i_0}$ tq $d_1(a_{i_0}, a_{k+1})$ minimal

  • $a_{j_0}$ tq $d_1(a_{k+1}, a_{j_0})$ minimal

D choisit $b_{k+1}$ tq

  • $d_2(b_{i_0}, b_{k+1}) = d_1(a_{i_0}, a_{k+1})$ si $d_1(a_{i_0}, a_{k+1}) ≤ d_1(a_{k+1}, a_{j_0})$

  • $d_2(b_{k+1}, b_{j_0}) = d_1(a_{k+1}, a_{j_0})$ sinon

Mq les invariants sont conservés.

  • $i, j ≠ k+1$ : invariants préservés

  • si $j = k+1$ et $d_1(a_i, a_{k+1}) ≤ 2^{n-k-1}$

\[\begin{cases} d_1(a_i, a_{k+1}) = d_1(a_i, a_{i_0}) + d_1(a_{i_0}, a_{k+1}) \\ i = i_0 \end{cases}\]

  • Sous-Cas : $d_1(a_{i_0}, a_{k+1}) ≤ d_1(a_{k+1}, a_{j_0})$

    alors \(d_1(a_i, a_{k+1}) = \underbrace{d_1(a_i, a_{i_0})}_{= d_2(b_i, b_{i_0}) \text{ par HR}} + d_2(b_{i_0}, b_{k+1}) = d_2(b_i, b_{k+1})\)

  • Sous-Cas : $d_1(a_{k+1}, a_{j_0}) ≤ d_1(a_{i_0}, a_{k+1})$

    alors \(d_1(a_{i_0}, a_{k+1}) + \underbrace{d_1(a_{k+1}, a_{j_0})}_{= d_2(b_{k+1}, b_{j_0})} = \underbrace{d_1(a_{i_0}, a_{j_0})}_{≤ 2^{n-k}} = d_2(b_{i_0}, b_{j_0})\)

    donc

    \[d_1(a_{i_0}, a_{k+1}) = d_2(b_{i_0}, b_{j_0}) - d_2(b_{k+1}, b_{j_0}) = d_2(b_{i_0}, b_{k+1})\]

  • Si $j=k+1$ et $d_1(a_i, a_{k+1}) > 2^{n-k-1}$

    • Sous Cas : $d_1(a_{i_0}, a_{k+1})> 2^{n-k-1}$

      2 sous cas :

      • $d_1(a_{i_0}, a_{k+1}) ≤ d_1(a_{k+1}, a_{j_0})$

        $d_1(a_{i_0}, a_{k+1}) = d_1(b_{i_0}, b_{k+1})$

      • $d_2(a_{i}, a_{k+1}) > 2^{n-k-1}$

        • $d_1(a_{i_0}, a_{k+1}) > d_1(a_{k+1}, a_{j_0}) > 2^{n-k-1}$

        • $d_1(a_{k+1}, a_{j_0}) ≤ 2^{n-k-1}$

          $d_2 = (b_{k+1}, b_{j_0}) = d_1(a_{k+1}, a_{j_0})$

          \[d_1(a_{i_0}, a_{j_0}) > 2^{n-k} \\ HR : d_2(b_{i_0}, b_{j_0}) > 2^{n-k} \\ d_2(b_{i_0}, b_{k+1}) > 2^{n-k-1} \\ d_2(b_{i}, b_{k+1}) > 2^{n-k-1}\]

Si S joue sur $S_2$, et choisit un élément dans la deuxième composante connexe (sachant qu’on n’a joué que dans la première jusqu’alors) :

Somme des $k$ intervalles entre les $a_i$ sur la première composante :

\[n_1 + ⋯ + n_k = 2^n\]

alors

\[∃i; \; n_i ≥ \frac{2^n}{k} > 2^{n-k} + 1\]

($k ≤ 2^{k-1}$)

et D choisit $a_{k+1}$ à distance $2^{n-k-1} + 1$ de $a_1$

Donc la stratégie de Duplicator maintient un isomorphisme partiel, puisque être en relation ⟺ être à une distance de 1.

Leave a comment