TD 8 : Théories

EX 1

\[𝒜 = TO', 𝒫 ≝ \lbrace <, = \rbrace\]

Soit $𝜑$ sans quantif. en DNF.

$𝜑$ conjonction de formules atomiques, $x$ var.

Trouver $𝜓$ sans quantif. tq

\[𝒜 \vDash ∃x. 𝜑 \longleftrightarrow 𝜓\] \[𝜑 = 𝜑_{-x} ∧ \bigwedge\limits_{i∈I} x>x_i ∧ \bigwedge\limits_{j∈J} x_j>x ∧ \bigwedge\limits_{k∈K} x = x_k\]

$I∩J =∅$

$I ≠ ∅ \text{ et } J ≠∅$

\[𝜓 = \bigwedge\limits_{i, j} x_j > x_i\]

Soit $M \vDash 𝒜$ et $𝜎$ tq $M, 𝜎 \vDash 𝜓$.

\[M, 𝜎 ∪ \lbrace x \mapsto c \rbrace \vDash 𝜑\]

avec

  • $a = \min_j (x_j 𝜎)$
  • $b = \max_i (x_i 𝜎)$

alors $∃c; \; a>c>b$

\[M, 𝜎 \vDash ∃x. 𝜑\]

$I ≠ ∅ \text{ et } J =∅$

$NoMax = ∀x, ∃y. y>x$

\[𝜓 = \top\]

$I = ∅$

$∃Min = ∃x. ∀y. ¬(y<x)$

Attention : on ne peut plus éliminer les quantificateurs !

\[TO^+ \qquad 𝒫^+ = \lbrace = (2), > (2), \min (2) \rbrace\]

avec $\min(x) \longleftrightarrow ∀y. ¬(y <x)$

\[𝜓 = \bigwedge\limits_{j∈J} ¬ \min (x_j)\]

Enfin, on conclut par le fait qu’une formule sans variables et sans quantificateurs est une combinaison logique de “True” et “False” : la théorie $TO^+$ est décidable :

$TO’$ est complète

\[Th(TO') = Th(TO^+) ∩ \lbrace 𝜑 \mid \text{le prédicat min n'est pas dans } 𝜑 \rbrace\]

Rappel : $TO’$ est complète ssi pour toute formule $𝜑$,

\[TO' \vDash 𝜑 \text{ ou } TO' \vDash ¬ 𝜑\]

Soit $𝜑$ une formule sur ${\cal F}(F, P)$ close.

Pour $𝜓$ sans variable, on a :

\[TO^+ \vDash 𝜓 \text{ ou } TO^+ \vDash ¬ 𝜓 \quad (1)\]

Comme on peut appliquer l’élimination des quant. dans $TO^+$, il existe $𝜑’$ tq :

\[TO' \vDash 𝜑 \longleftrightarrow 𝜑'\]

et $𝜑’$ est sans variable.

Donc d’après $(1)$ :

\[TO^+ \vDash 𝜑' \text{ ou } TO^+ \vDash ¬ 𝜑' \quad (1)\]

d’où

\[TO^+ \vDash 𝜑 \text{ ou } TO^+ \vDash ¬ 𝜑 \quad (1)\]

et $TO^+$ est complète.

$ℚ^+$ et $ℝ^+$ sont des modèles de $TO’$ non isomorphes (car non équipotents).

EX 2

$M_1$ et $M_2$ sont élémentairement équivalents (él. éq.) ssi :
\[∀𝜙, M_1 \vDash 𝜙 \text{ ssi } M_1 \vDash 𝜙\]

Deux modèles d’une théorie complète sont élémentairement équivalents.

Si $M$ et $M’$ sont deux modèles de $T$ complète, et $𝜙$ une formule :

\[T \vDash 𝜙 \text{ ou } T \vDash ¬ 𝜙\]

Si $M_1 \vDash 𝜙$ : alors nécessairement $T \vDash 𝜙$ (car sinon $T \vDash ¬ 𝜙$, et $M_1 \vDash ¬𝜙$), et donc $M_1 \vDash 𝜙$.

On conclut par symétrie.

Toute théorie cohérente et complète possède une infinité de modèles non isomorphes et élémentairement équivalents.

\[∀𝜙, T \vDash 𝜙 ⟺ T \not\vDash ¬𝜙\]

Löwenheim-Skolem : si il y a un modèle infini, Si $T$ est cohérente et complète :

Or, $T$ est cohérente, donc il existe un modèle infini (on montre par contraposée que : il n’existe pas de modèle ⟹ non cohérente, puis : comme la formule est satisfaisable, elle a un modèle de Herbrand dénombrable).

NB :

  • $T$ cohérent : \(T \vDash 𝜙 ⟹ T \not\vDash ¬ 𝜙\)

  • $T$ complète : \(T \not\vDash 𝜙 ⟹ T \vDash ¬ 𝜙\)

Cohérence + Complétude : on a l’équivalence

Système de preuves

Correct : \(T \vdash 𝜙 ⟹ T \vDash 𝜙\)

Cohérence : Théorie ⟶ Modèle / Syntaxe ⟶ Sémantique

Complétude : \(T \vDash 𝜙 ⟹ T \vdash 𝜙\)

Complétude : Modèle ⟶ Théorie / Sémantique ⟶ Syntaxe

EX 2,5

Les assertions suivantes sont-elles vraies ou fausses ?

  1. \[Q = AE \vDash ∀x, ∀y. (x≤y ∧ y ≤ x) ⟶ x=y\]
  2. \[Q = AE \vDash ¬ \Big(∀x, ∀y. (x≤y ∧ y ≤ x) ⟶ x=y \Big)\]
  3. \[PA \vDash ∀x, ∀y. (x≤y ∧ y ≤ x) ⟶ x=y\]
  4. \[PA \vDash ¬ \Big(∀x, ∀y. (x≤y ∧ y ≤ x) ⟶ x=y \Big)\]

Donner un modèle de AE tq $≤$ n’est pas bien fondée.

1. FAUX

$M ≝ ℕ \sqcup \lbrace 𝜔_1, 𝜔_2 \rbrace$

  digraph {
    rankdir=BT;
    𝜔_1 -> 𝜔_1;
    𝜔_2 -> 𝜔_2;
    1 -> 2;
    2 -> 3;
    3 -> ⋯;
  }
\[n + 𝜔_i = 𝜔_i + n = 𝜔_i \\ 𝜔_1 + 𝜔_2 = 𝜔_2\\ 𝜔_2 + 𝜔_1 = 𝜔_1\\ 𝜔_i + 𝜔_i = 𝜔_i\\ 𝜔_1 × 𝜔_2 = 𝜔_2\\ 𝜔_2 × 𝜔_1 = 𝜔_1\\ 𝜔_i × 𝜔_i = 𝜔_i\\\]

Alors $ℕ \sqcup \lbrace a, b \rbrace$ est un modèle de $Q$, mais :

\[𝜔_1 ≤ 𝜔_2\\ 𝜔_2 ≤ 𝜔_1\]

mais

\[𝜔_1 ≠ 𝜔_2\]

2. FAUX

On prend $ℕ$ comme modèle.

3. VRAI

Soit $M$ un modèle tel que $M \vDash PA$.

Montrons que $M \vDash ∀x, ∀y. (x≤y ∧ y ≤ x) ⟶ x=y$.

On pose $𝛷_x(y) ≝ (x≤y ∧ y ≤ x) ⟶ x=y$

Pour tout $x$, on montre que :

\[M \vDash ∀y, 𝛷_x(y)\]

en montrant (ce qui est suffisant, par induction) que

\[M \vDash 𝛷_x(0) \text{ et } M \vDash ∀y, \; 𝛷_x(y) ⟶ 𝛷_x(s(y))\]

NB : Pour montrer $M \vDash 𝛷_x(0)$, il suffit de montrer que $M \vDash x ≤ 0 ⟶ x=0$, i.e $M \vDash ∃z. x + z = 0 ⟶ x=0$ : on fait un raisonnement par cas au niveau méta (de la sémantique) :

  • si $z_M = 0_M$ : c’est immédiat

  • sinon : $z_M = s_m(z’_M)$ pour un $z’_M$, ce qui n’est pas possible puisqu’alors $x_M + s_m(z’_M) = s_M(x_M + z’_M) = 0_M$ (ce qui contredit un des axiomes de $PA$)

De même, on pose $𝛹(x) ≝ ∀y, 𝛷_x(y)$

Et on montre par induction que :

\[M \vDash ∀x, 𝛹(x)\]

4. FAUX

M1 : On prend $ℕ$ comme modèle.

M2 : Comme $PA$ a un modèle donc est cohérente et par le point précédent : le résultat s’ensuit.

EX 4

  1. cohérente
  2. complète
  3. contient l’arithmétique élémentaire $Q$
  4. est récursivement axiomatisable (i.e il existe un ensemble d’axiomes récursif $A$ tel que $T = Th(A)$)

Les hypothèses de Gödel sont minimales : on peut donner des exemples de théories vérifiant :

1, 2, 3

$Th(ℕ)$

1, 2, 4

$TO$, ou n’importe quelle autre théorie décidable : Presburger, logique propositionnelle SAT (domaine : $\lbrace 0, 1 \rbrace$, que des symboles de prédicats $0$-aires, pas de symboles de fonctions)

1, 3, 4

$PA$ : Peano (vérifie le 3, car elle contient $Q$, qui elle même vérifie 3).

2, 3, 4

N’importe quelle théorie incohérente : ex : $Th(\bot)$ (on peut tout déduire du faux)

Leave a comment