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$)

Leave a Comment