Mathematische Logik/Gemischte Definitionsabfrage/5/Aufgabe/Lösung

1. Die zugehörige Interpretation ${}I=I^{\lambda }$ wird rekursiv über den Aufbau der Sprache wie folgt festgelegt.
   1. ${}I(v)=\lambda (v)$ für jede Aussagenvariable ${}v\in V$.
   2. Bei ${}\alpha =\neg (\beta )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0\,,\\0,{\text{ falls }}I(\beta )=1\,.\end{cases}}\,$

   3. Bei ${}\alpha =(\beta )\wedge (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )=1\,,\\0{\text{ sonst}}\,.\end{cases}}\,$

   4. Bei ${}\alpha =(\beta )\vee (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=1{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=I(\gamma )=0\,.\end{cases}}\,$

   5. Bei ${}\alpha =(\beta )\rightarrow (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=1{\text{ und }}I(\gamma )=0\,.\end{cases}}\,$

   6. Bei ${}\alpha =(\beta )\leftrightarrow (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )\,,\\0,{\text{ falls }}I(\beta )\neq I(\gamma )\,.\end{cases}}\,$

2. Das Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.
   1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
   2. Zu jeder natürlichen Zahl ${}n\in \mathbb {N} _{+}$ eine Menge ${}R_{n}$ von ${}n$-stelligen Relationssymbolen.
   3. Die aussagenlogischen Junktoren

      $\neg ,\,\wedge ,\,\vee ,\,\rightarrow ,\,\leftrightarrow .$

   4. Das Gleichheitszeichen ${}=$.
   5. Die Quantoren ${}\forall$ und ${}\exists$.
   6. Klammern, also ${}($ und ${})$.
3. Man nennt eine weitere ${}S$-Struktur ${}M'$, die zu ${}M$ elementar äquivalent, aber nicht zu ${}M$ ${}S$-isomorph ist, ein Nichtstandardmodell von ${}M$.
4. Die Abbildung ${}F$ heißt arithmetisch repräsentierbar, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$-Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die Äquivalenz ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r+s})$ gilt.
5. Die Theorie ${}T$ heißt vollständig, wenn für jeden Satz ${}\alpha \in L_{0}^{S}$ gilt ${}\alpha \in T$ oder ${}\neg \alpha \in T$.
6. Die Menge ${}U_{\Gamma }$ aller ${}\Gamma$ umfassenden, (aussagenlogisch) maximal widerspruchsfreien Teilmengen

   ${}W\subseteq L\,$

   mit der durch

   $WRV{\text{ genau dann, wenn für jedes }}\alpha \in L{\text{ mit }}\alpha \in V{\text{ die Beziehung }}\Diamond \alpha \in W{\text{ gilt}}.$

   gegebenen Erreichbarkeitsrelation und der durch ${}W\vdash p$, wenn ${}p\in W$, festgelegten Belegung ${}\nu$ heißt das ${}\Gamma$-universelle modallogische Modell.

Zur gelösten Aufgabe