TD 12 : Argument diagonal, modèles non standards, classe de Bernays-Schönfinkel

EX 1

1.

\[R = \lbrace n ∈ ℕ \mid \text{ il existe } 𝜑(x) \text{ tq } n = ⟨𝜑(x)⟩ \text{ et } Q \vDash 𝜑(\overline{n}) \rbrace\] \[R = \lbrace ⟨𝜑(x)⟩ \mid Q \vDash 𝜑(\overline{⟨𝜑(x)⟩ }) \rbrace\]

Par l’absurde :

Si $R$ est récursif, on note $𝜑_R$ la formule qui représente $R$ (i.e.

\[\text{Si } n∈ R, \text{ alors } Q \vDash 𝜑_R(\overline{n})\\ \text{Si } n∉ R, \text{ alors } Q \vDash ¬𝜑_R(\overline{n})\]

) dans $Q$ (car les fonctions récursives sont représentables dans $Q$).

Alors

\[\begin{align*} Q \vDash 𝜑_R (\overline{⟨¬𝜑_R⟩} & ⟺ ⟨¬𝜑_R⟩∈ R &&\text{( ⟸ : par déf de } 𝜑_R(x) \text{ / ⟹ : par cohérence de } Q \text{, }\\ & &&\text{ et contraposée de la deuxième propriété de représentabilité)}\\ & ⟺ Q \vDash ¬ 𝜑_R (\overline{⟨¬𝜑_R⟩}) &&\text{(par déf de } R \text{)} \\ \end{align*}\]

Absurde.

2.

\[P = \lbrace ⟨𝜑(x)⟩ \mid 𝜑(x) \text{ représente dans } Q \text{ un prédicat récursif à 1 argument} \rbrace\]

Par l’absurde :

Si $P$ est récursif, on note $𝜑_P$ la formule qui représente $P$ (i.e.

\[\text{Si } n∈ P, \text{ alors } Q \vDash 𝜑_P(\overline{n})\\ \text{Si } n∉ P, \text{ alors } Q \vDash ¬𝜑_P(\overline{n})\]

) dans $Q$ (car les fonctions récursives sont représentables dans $Q$).

Alors en posant

\[P' = P ∩ R\]

si $P$ est récursif, $P’$ est récursif.

Mais $P’$ n’est pas récursif : en effet, il suffit de reprendre le raisonnement de la question précédente.

EX 2

1.

On prend le modèle $ℕ ∪ \lbrace 𝜔 \rbrace$ avec les opérations usuelles.

2.

Le modèle précédent convient. Il est non standard car non isomorphe (au sens des $F,P$-structures) à $ℕ$.

EX 3

Classe de Bernays-Schönfinkel :

\[BSC ≝ \lbrace ∃x_1, \ldots, x_n, ∀y_1, \ldots, y_n. 𝜓 \mid n,m∈ℕ, 𝜓 \text{ sans quantificateurs ni symboles de fonctions} \rbrace\]

La satisfiabilité de toute formule de $BSC$ est décidable :

En effet, pour toute $𝜑 ≝ ∃x_1, \ldots, x_n, ∀y_1, \ldots, y_n. 𝜓 ∈ BSC$, an mettant $𝜑$ sous forme normale négative $𝜑’$ et en la Skolémisant, on ne rajoute que des symboles de constantes (les quantificateurs $∃$ précèdent les $∀$).

Donc le domaine des modèles de Herbrand de $Sk(𝜑’)$ (ensemble des termes clos) est fini (constantes rajoutées + variables libres de $𝜑$), et l’ensemble des modèles de Herband de $Sk(𝜑’)$ est fini (il n’y a qu’un nombre fini d’interprétations possibles des prédicats apapraissant dans $𝜑$, puisqu’il y a un nombre fini de termes clos).

Or, $Sk(𝜑’)$ et $𝜑$ sont équisatisfaisables, et la satisfiabilité de $Sk(𝜑’)$ équivaut à sa satisfaisabilité par un modèle de Herbrand.

Donc $𝜑$ est satisfaisable ssi $Sk(𝜑’)$ est satisfaite par un modèle de Herband, lesquels sont en nombre fini : la satisfaisabilité de $𝜑$ est donc décidable, il suffit de calculer :

\[\bigvee_{H ∈ \underbrace{\lbrace \text{ modèles de Herbrand de } Sk(𝜑')\rbrace}_{\text{ ensemble fini}}} H \vDash Sk(𝜑')\]