TD 11 : Exemples, Herbrand

EX 1. Théories cohérentes

1. Récursive et complète : Th des ordres denses, aithmétique de Presburger

2. Récursive et incomplète : Th. de l’égalité

3. Non récursive et complète : $Th(ℕ)$

4. Non récursive et incomplète : Peano

EX 2

1.

\[𝛷_1 ≝ \lbrace ∃x_1, \ldots, x_n, ∀y_1,\ldots, y_n. 𝜑 \mid 𝜑 ∈ 𝛷_0, fv(𝜑) ⊆ \lbrace x_1, \ldots, x_n, y_1, \ldots, y_m \rbrace\rbrace\]

Si $𝜑 ∈ 𝛷_1$ est satisfaisable :

\[Sk(𝜑) ≝ 𝜓 = ∀y_1, \ldots, y_m. 𝜓[x_1 \mapsto a_1, \ldots, x_n \mapsto a_m]\]

alors elle a un modèle de Herbrand.

Or, l’ensemble des termes clos $\lbrace a_1, \ldots, a_n \rbrace$ est fini, donc $𝜑$ a un modèle.

Or, on peut montrer que tout modèle satisfaisant $𝜓$ satisfait aussi $𝜑$ (cf. démonstration de la Skolémisation).

2.