Cours 8 : Théories indécidables

Théories indécidables

On va montrer l’indécidabilité de l’arithmétique élémentaire, notée $Q$.

  • \[A_{eq} ⊆ Q\]
  • \[{\cal F} ≝ \lbrace 0, S, +, × \rbrace\]
  • \[P = \lbrace = \rbrace\]

Axiomes de $Q$ :

  • l’addition $+$ est définie en unaire par récurrence à droite

  • la multiplication $×$ est définie en unaire par récurrence à droite

  • $∀x, 0 ≠ S(x)$
  • $∀x,y, S(x) = S(y) ⟶ x=y$
  • $∀x, ∃y; \, (x≠0 ⟶ x=s(y))$

NB : $Q$ est incomplète :

$𝜑 ≝ ∀x. 0+x =x$ : ni $𝜑$, ni $¬𝜑$ n’est conséquence logique de $Q$ (il existe des modèles dans lequels $0$ n’est pas neutre à gauche)

Arithmétique de Peano :

$Q^+$, : c’est $Q$, plus : pour toute $𝜑$ à 1 var. libre :

\[∀x. (𝜑(0) ∧ 𝜑(x) ⟶ 𝜑(S(x))) ⟶ ∀x. 𝜑(x)\]

Problème central : comment “mimer” la récursion primitive en logique ?

Rappel :

on note $𝒞$ le plus petit ens. de fonctions des entiers dans les entiers tq :

  • $0∈𝒞$
  • la fonction identiquement nulle est dans $𝒞$
  • la projection sur la $i$-ème coordonnée est dans $𝒞$
  • la fonction successeur est dans $𝒞$

  • l’addition, la multiplication, et le test d’égalité aussi

  • $𝒞$ est clos par composition et minimisation

Th : $𝒞$ est l’ens. des fonctions récursives partielles

On code les entiers par les de manière usuelle : $n = S^n(0)$

$f: ℕ^k ⟶ ℕ^k$ est définissable dans $T$ :

si il existe $𝜑_f$ tq

  1. pour tous $n_1, ⋯, n_k∈ℕ$,

\(f(n_1, ⋯, n_k) = n \text{ entraîne } T\vDash 𝜑_f(n_1, ⋯, n_k, n)\)

  1. pour tous $n_1, ⋯, n_k∈ℕ$,

\(f(n_1, ⋯, n_k) ≠ n \text{ entraîne } T\vDash ¬ 𝜑_f(n_1, ⋯, n_k, n)\)

  1. pour tous $n_1, ⋯, n_k∈ℕ$,
\[f(n_1, ⋯, n_k) = n \text{ entraîne } T\vDash (∀ x. 𝜑_f(n_1, ⋯, n_k, x) ⟶ x=n)\]

NB : 2 est conséquence de 1 et 3 si la représentation des entiers est injective et $f$ est totale

Exs de modèles de $Q$

$M ≝ ℕ \sqcup \lbrace a, b \rbrace$

  • $S_M(a)=a$
  • $S_M(b)=b$
  • $n +_M a = a +_M n = a$
  • $n +_M b = a$

  • $b +_M n = b$

  • a b
  • a a a
    b b b

(col + ligne)

⟶ ni associativité, ni commutativité, ni élément neutre à gauche

Fonctions récursives représentables

Lemme : Si les fonctions récursives sont représentables dans $T$, alors $T$ est incohérente ou indécidable.

\[P ≝ \lbrace (n, m) ∈ℕ^2 \mid \text{ il existe } 𝜑 \text{ à une var. libre}, n = ⟨𝜑(x)⟩ \text{ et } T \vDash 𝜑(m) \rbrace\]

Si $T$ est récursive (= décidable), alors $P$ est récursif.

Par l’absurde : Si $T$ est cohérente et décidable

\[E = \lbrace n \mid (n, n) ∉ P \rbrace\]

$E$ est récursif.

Donc $E$ est représentable (hypothèse) : il existe $𝜑_E$ qui représente $E$ et tq :

  • $T \vDash 𝜑_E(n)$ si $n∈E$

  • $T\vDash ¬ 𝜑_E(n)$ si $n∉E$

\[⟨𝜑_E⟩∈E \text{ ssi } T \vDash 𝜑_E(⟨𝜑_E⟩)\]

donc

\[T \not\vDash 𝜑_E(⟨𝜑_E⟩) \text{ ssi } \\ (⟨𝜑_E⟩, ⟨𝜑_E⟩)∉P \text{ ssi } ⟨𝜑_E⟩∈E \\ \text{ ssi } T \vDash 𝜑_E(⟨𝜑_E⟩)\]

contradiction.

NB : l’énoncé “$P$ est récursif” n’est lui-même pas représentable en arithmétique, donc on va devoir refaire la preuve (preuve de Rosser) pour le th. d’incomplétude de Gödel

Th : La th. des entiers naturels $Th(ℕ, +, ×, =, ≥, 0, 1)$ n’est pas réc. én.

Comme la th. est complète (cf. cours précédent), elle est récursivement én. ssi elle est réc. (on fait tourner les machines de Turing sur $𝜑$ et $¬𝜑$ en parallèle), dont par le lemme précédent, l suffit de montrer (comme elle est cohérente : elle a un modèle, la structure elle-même), que les fonctions réc. y sont représentables.

Il suffit donc de mq que

  • $+, ×, =, ⋯$ sont représentables

  • les fonctions représentables sont closes par composition et minimisation

Let’s go :

Les fonctions de base sont trivialement représentables :

  • $n = 1 + ⋯ + 1$ ($n$ fois)
  • $𝜑_+(x, y, z) ≝ z = x+y$
  • $𝜑_0(x) ≝ x=0$
  • $𝜑_z(x,y) ≝ y=0$

NB : on a pris la théorie de la structure, donc on n’a plus le problème des modèles pathologiques comme avant avec la théorie de l’arithmétique élémentaire : $T \vDash 𝜑 \text{ ssi } ℕ \vDash 𝜑$

Clôture par composition :
  • $f_1, ⋯, f_k$ représentables de $ℕ^n⟶ℕ$ par $𝜑_{f_1}, ⋯, 𝜑_{f_k}$
  • $g$ représentable de $ℕ^n⟶ℕ$ par $𝜑_g$
\[f(n_1, ⋯, n_m) = g(f_1(n_1, ⋯, n_m), ⋯, f_k(n_1, ⋯, n_m)) \\ 𝜑_f(x_1, ⋯, x_m, x) ≝ ∃y_1, ⋯, y_k. 𝜑_{f_1}(x_1, ⋯, x_m, y_1) ∧ ⋯ ∧ 𝜑_{f_k}(x_1, ⋯, x_m, y_k) \\ ∧ 𝜑_g(y_1, ⋯, y_m, x)\]
  1. $f(n_1, ⋯, n_m) = n$

Mq $T \vDash 𝜑_f(n_1, n_m, n)$

Mq

  • $T \vDash 𝜑_{f_1}(n_1, ⋯, n_m, f_1(n_1, ⋯, n_m))$
  • $\vdots$
  • $T \vDash 𝜑_{f_k}(n_1, ⋯, n_m, f_k(n_1, ⋯, n_m))$
  • $T \vDash 𝜑_g(f_1(n_1, ⋯, n_m), ⋯, f_k(n_1, ⋯, n_m), n)$
  1. $f(n_1, ⋯, n_m) ≠ n$

Mq $T \vDash ¬ 𝜑_f(n_1, n_m, n)$

Mq \(T \vDash ∀y_1, ⋯, y_k. ¬𝜑_{f_1}(x_1, ⋯, x_m, y_1) ∨ ⋯ ∨ ¬ 𝜑_{f_k}(x_1, ⋯, x_m, y_k) \\ ∨ ¬ 𝜑_g(y_1, ⋯, y_m, x)\)

  • Comme les $f_i$ sont représentables, par la propriété 3 :

    \[T \vDash ∀y_i, 𝜑_{f_i}(n_1, ⋯, n_m, y_i) ⟶ y_i = f_i(n_1, ⋯, n_m)\]

Mq \(T \vDash ∀y_1, ⋯, y_k. y_1 ≠ f_1(n_1, ⋯, n_m) ∨ ⋯ ∨ y_k ≠ f_k(n_1, ⋯, n_m) \\ ∨ ¬ 𝜑_g(y_1, ⋯, y_m, x)\)

c’est la contraposée de la propriété 2 de “$g$ est représentable”.

  1. $T \vDash ∀x. 𝜑_f(n_1, ⋯, n_m, x)⟶x=f(n_1, ⋯, n_m)$

Par propriété 3 de $𝜑_{f_1}, ⋯, 𝜑_{f_k}$ et $𝜑_g$

Clôture par minimisation :

$f$ représentée par $𝜑_f$

\[g(n_1, ⋯, n_m) ≝ \min \lbrace n \mid f(n_1, ⋯, n_k, n) = 0 \rbrace \\ 𝜑_g(x_1, ⋯, x_k, x) ≝ 𝜑_f(x_1, ⋯, x_k, x, 0) ∧ ∀y. (𝜑_f(x_1, ⋯, x_k, y, 0) ⟶ y≥x)\]

où $x≥y ≝ ∃z. x = y+z$

On va utiliser à fond la spécificité de la théorie des entiers naturels : il suffit de montrer que

\[ℕ \vDash 𝜑_g(n_1, ⋯, n_k, g(n_1, ⋯, n_k))\]

cela se fait simplement, puisque $y$ (quantifié dans la formule du dessus) est un entier (ce qu’on ne peut pas supposer avec une théorie plus générale (ex: l’arithmétique élémentaire $Q$)!).

Conséquence :

  • $Th(ℕ)$ n’a pas d’axiomisation réc.

Indécidabilité de l’arithmétique élémentaire $Q$

Le seul endroit où cela coincerait dans la démonstration précédente est la clôture par minimisation (en effet : on ne peut plus supposer que $y$ est un entier : il y a des aliens).

Propriétés des théories de l’arithmétique :

  • \((A_+) : T \vDash 𝜑_+(n, m, k)\) si $m+n=k$

  • \((A_{f+}) : T \vDash ∀x. (𝜑_+(n, m, k) ⟶ x=k)\) si $m+n=k$

  • $(A_×), (A_{f×})$ : idem

  • \(: T \vDash 𝜑_+(n, m, k)\) si $m+n=k$

  • \((A_=) : T \vDash m ≠ n\) si $m≠n$

  • \((A_≤) : T \vDash ∀x. (x≤n ⟶ x = 0 ∨ ⋯ ∨ x = n)\) si $n∈ℕ$

  • \[(A_{<>}) : T \vDash ∀x. (x ≤ n ∨ x > n)\]

avec

$x ≤ y ≝ ∃z. 𝜑_f(z, x, y)$

$x < z ≝ x ≤ y ∨∧ x≠y$

TH : Si les propriétés précédentes sont satisfaites par $T$, alors les fonctions réc. sont représentables dans $T$.

Clôture par minimisation des fonctions représentables.

\[g(n_1, ⋯, n_k) ≝ \min \lbrace n \mid f(n_1, ⋯, n_k, n) = 0 \rbrace\]

$𝜑_f$ représente $f$.

\[𝜑_g(x_1, ⋯, x_k, x) ≝ 𝜑_f(x_1, ⋯, x_k, x, 0) ∧ ∀y. (𝜑_f(x_1, ⋯, x_k, y, 0) ⟶ y≥x)\]
  1. Si $g(n_1, ⋯ , n_k) = n$

Mq \(T \vDash 𝜑_g(n_1, ⋯, n_k, n)\)

Mq \(T \vDash 𝜑_f(n_1, ⋯, n_k, n, 0) ∧ ∀y. (𝜑_f(n_1, ⋯, n_k, y, 0) ⟶ y≥n)\)

  • $T \vDash 𝜑_f(n_1, ⋯, n_k, n, 0)$ découle de la représentabilité de $f$

De plus :

  • \[(A_≤) : T \vDash ∀y (y≤n ⟶ y = 0 ∨ ⋯ ∨ y = n)\]
  • \[(A_{<>}) : T \vDash ∀y. (y ≤ n ∨ y > n)\]

Représentabilité de $f$ :

$T \vDash ¬ 𝜑_f(n_1, ⋯, n_k, m, 0)$ si $m<n$

donc :

\[T \vDash ∀y. (¬ 𝜑_f(n_1, ⋯, n_k, y, 0) ∨ y ≥ n)\]

3.

Mq \(T \vDash ∀x. (𝜑_g( n_1,⋯, n_k, x) ⟶ x = g(n_1, ⋯, n_k))\)

Par $A_{<>}$ :

Mq \(T \vDash ∀x. (x ≤ g(n_1, ⋯, n_k) ∧ 𝜑_g( n_1,⋯, n_k, x) ⟶ x = g(n_1, ⋯, n_k))\\ ∨ \Bigg(x > g(n_1, ⋯, n_k) ∧ 𝜑_g( n_1,⋯, n_k, x) ⟶ x = g(n_1, ⋯, n_k)\Bigg)\)

Th : Si $T$ contient $Q$, alors les fonctions récursives sont représentables.

  • $n = s^n(0)$
  • $𝜑_+(x, y, z) ≝ x+y=z$
  • $𝜑_×(x, y, z) ≝ x×y=z$

On démontre $(A_+)$ en montrant par réc sur $m$ que pour tous $n, m, k$ :

\[Q \vDash s^n(0) + s^m(0) = s^k(0)\]

$(A_{f_+})$ : On montre par récurrence sur $m$ que pour tous $n, m, k$ :

\[Q \vDash ∀x, s^n(0) + s^m(0) = x ⟶ x = s^{n+m}(0)\]

$(A_{<>})$ : on montre par réc sur $n$ que

\[Q \vDash ∀x. ((∃z, z+x = s^n(0) ∨ (∃z, z+s^n(0) = x))\]

$(A_{≤})$ : on montre par réc sur $n$ que

\[Q \vDash ∀x. (x ≤ s^n(0) ⟶ x = 0 ∨ ⋯ ∨ x = s^n(0))\]

Corollaire : Toute théorie qui contient l’arithmétique élémentaire $Q$ est incohérente ou indécidable, donc incomplète (car complète ⟹ décidable).

Remarques :

  • Si $T \supseteq Q$ et cohérente, alors $T$ est incomplète

  • 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 de Gödel utilise la

$𝜔$-cohérence :

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

Leave a comment