TD 10 : Cohérence, récursivité, complétude, argument diagonal

Théories & Gödel

Th : Si $T = Th(A)$ est

• réc. axiomatisable
• complète

Question : $𝛷 ∈ T$ ?

• $𝛷 \text{ ou } ¬𝛷 ∈T$ par complétude

for (p,q) ∈ ℕ^2:
  A_p = {𝜙_1, ⋯, 𝜙_n ∈ A}
  B_q = {𝜓_1, ⋯, 𝜓_q ∈ Th(A_p)}

Une première boucle énumère les sous-ensembles finis de $A$ de taille $p$ croissante.

Dans une seconde boucle imbriquée, on énumère l’ensemble des conséquences logiques (en $p$ étapes, pour un parcours en largeur) de chaque ensemble fini, et on sélectionne les preuves dont les feuilles sont des axiomes.

Comme en tout on énumère $T = Th(A)$, on va finir par y trouver $𝜑$ ou $¬𝜑$.

• $A_q$ : ensemble d’axiomes ($Axioms$ est réc. én. par hypothèse)
• $B_q$ : ensemble des conséquences logiques dont les preuves se font à partir des axiomes.

Le système d’inférence est correct et complet, et l’ensemble des règles d’inférence est récursif :

\[A_1, ⋯, A_p \vDash 𝜙 \\ ⟺ A_1, ⋯, A_p \vdash 𝜙\]

---

Deuxième méthode :

\[T \vDash 𝜑 ⟺ T ∪ \lbrace ¬ 𝜑 \rbrace \vDash \bot\]

et par complétude réfutationnelle :

\[T ∪ \lbrace ¬ 𝜑 \rbrace \vdash \bot\]

Et on fait ça parallèlement pour $𝜑$ et $¬𝜑$ : en va dériver $\bot$ pour l’une ou l’autre par complétude.

---

EX 1.

1.

Récursive et complète :

• $TO$ : théorie des ordres denses (et total)

  • cohérence : $(ℚ, ≤, =)$ en est un modèle, donc la théorie est cohérente (c’est une équivalence).

  • complète : élimination des quantificateurs ⟹ on se ramène à des formules sans variables (i.e propositionnelles), c’est-à-dire $\top$ ou $\bot$, lesquelles sont réc. et complètes, donc $TO$ est réc. et complète.

NB : Peano contient $Q$, dont n’est pas réc.

2.

Récursive et incomplète :

• Théorie de l’égalité

  • cohérente : $ℕ$ ou un singleton en est un modèle.
  • récursive : on rajoute des prédicats $E_n$ “avoir $n$ éléments” (extension conservative) : l’extension conservative admet l’élimination des quantificateurs ⟶ l’extension est réc. ⟹ la théorie est réc. (ne marche pas pour la complétude !).
  • incomplète : $∀x,y. x=y$ : un modèle avec une seule classe d’éq. VS un modèle avec deux classes d’éq.

3.

Pas récursivement énumérable et complète :

On veut une théorie qui soit suffisamment expressive pour représenter les fonction récursives (donc la théorie est non réc.), et qui soit la théorie d’un modèle pour être complète (contrairement à l’arithmétique de Peano).

• $Th((ℕ, +, ×, 0, 1))$

  • cohérente et complète : c’est la théorie d’une structure : complétude car la fonction $M \vDash \bullet$ est une fonction totale à valeur dans $\lbrace Vrai, Faux \rbrace$.

  • si elle était réc. én., elle serait réc. axiomatisable et donc réc. car elle est en plus complète. Mais ce n’est pas le cas car les fonctions réc. y sont représentables (donc elle n’est pas réc.).

4.

• $Th(ℕ)∪ \lbrace ∀x, f(x) ⟹ g(x)\rbrace$

  • pas réc. én. car c’était déjà le cas de $Th(ℕ)$
  • plus complet car les nouveaux symboles de fonction $f$ et $g$ peuvent être interprétées n’importe comment.

• $Th(ℕ) ∩ \lbrace 𝛷 \mid ∃n∈ℕ, ⟨𝛷⟩=n \text{ et } ∃M \text{ T.M tq } ⟨M⟩ = n \text{ et } M \text{ termine }\rbrace$

NB : enlever une formule $𝜑$ d’une théorie de structure la rend incomplète car on ne peut plus dès lors montrer ni $T \vDash 𝜑$ ni $T \vDash ¬ 𝜑$ (ce n’était pas le cas avant).

EX 2.

1.

\[R = \lbrace ⟨𝜑(x)⟩ \mid 𝒜 \vDash 𝜑(\overline{⟨𝜑(x)⟩})\rbrace\]

Si $R$ était récursif, alors comme les fonctions récursives sont représentables dans l’arithmétique élémentaire, il existerait une formule $𝜑_R(x)$ représentant ce prédicat.

De même, il existerait une formule $𝜑_{¬R}(x)$ représentant le prédicat $¬R$.

Alors

\[⟨𝜑_{¬ R}⟩ ∈ R ⟺ 𝒜 \vDash 𝜑_R(\overline{⟨𝜑_{¬R}⟩}) \\ ⟺ 𝒜 \not\vDash 𝜑_{¬R}(\overline{⟨𝜑_{¬ R}⟩}) \\ ⟺ ⟨𝜑_{¬ R}⟩ ∉ R\]

Absurde.

EX 3.

1.

\[𝕸 ≝ (ℤ ∪ \lbrace +∞ \rbrace, succ, pred, +∞, =)\]

est clairement un modèle de $T$, donc $T$ est cohérente.

2.

Pour montrer le caractère récursif de $T$, il suffit de montrer qu’une extension conservative de $T$ admet l’élimination des quantificateurs.

Montrons que pour toute $𝜑$ universellement quantifiée et tout $x$, il existe $𝜓$ sans quantificateurs telle que

\[𝕸 \vDash ∃x. 𝜑 \longleftrightarrow 𝜓\]

Quitte à mettre $𝜑$ en forme DNF, on se ramène à une $𝜑$ de la forme :

\[𝜑 = \bigwedge_{k} f^{k} (x_i) = x \\ ∧ \bigwedge_{k} x ≠ f^{k} (x_i) \\ ∧ \bigwedge_{k} x = x_i \\ ∧ \bigwedge_{k} x ≠ x_i\]

car

• $f$ et $g$ sont des bijections réciproques
• ont peut rajouter des $f$ par bijectivité de $f$
• $a$ est un point fixe de $f$ et $g$

quitte à remplacer $x$ par ses valeurs potentielles, on peut se ramener à

\[𝜑 = \bigwedge_{k} x ≠ f^k(x_i) \\ ∧ \bigwedge_{k} x ≠ x_i\]

Or, cette formule est vraie (équivalente à $\top$) car il y a une infinité d’éléments dans le domaine.

Donc comme la théorie admet l’élimination des quantificateurs, elle est récursive et complète.

(les $a≠a$ sont équivalents à $\bot$)