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

1. Die Teilmenge ${}\Gamma \subseteq L^{V}$ heißt maximal widerspruchsfrei, wenn ${}\Gamma$ widerspruchsfrei ist und jede echt größere Menge ${}\Gamma \subset \Gamma '$ widersprüchlich ist.
2. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
   1. Wenn ${}t_{1}$ und ${}t_{2}$ Terme sind, so ist

      $t_{1}=t_{2}$

      ein Ausdruck.
   2. Wenn ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind, so ist

      $Rt_{1}{\ldots }t_{n}$

      ein Ausdruck.

   3. Wenn ${}\alpha$ und ${}\beta$ Ausdrücke sind, so sind auch

      $\neg {\left(\alpha \right)},\,{\left(\alpha \right)}\wedge {\left(\beta \right)},\,{\left(\alpha \right)}\vee {\left(\beta \right)},\,{\left(\alpha \right)}\rightarrow {\left(\beta \right)},\,{\left(\alpha \right)}\leftrightarrow {\left(\beta \right)}$

      Ausdrücke.

   4. Wenn ${}\alpha$ ein Ausdruck ist und ${}x$ eine Variable, so sind auch

      $\forall x{\left(\alpha \right)}\,\,{\text{ und }}\,\,\exists x{\left(\alpha \right)}$

      Ausdrücke.

3. Die Terminterpretation ${}I(t)\in M$ wird induktiv über den Aufbau der Terme für jeden ${}S$-Term ${}t$ definiert.
   1. Für jede Konstante ${}c$ und jede Variable ${}x$ ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also ${}I(c)=c^{M}$ und ${}I(x)=x^{M}$.
   2. Wenn ${}t_{1},\ldots ,t_{n}$ Terme mit Interpretationen ${}I(t_{1}),\ldots ,I(t_{n})$ sind und wenn ${}f$ ein ${}n$-stelliges Funktionssymbol ist, so wird der Term ${}ft_{1}\ldots t_{n}$ als ${}f^{M}(I(t_{1}),\ldots ,I(t_{n}))$ interpretiert.
4. Unter einem atomaren Ausdruck versteht man Ausdrücke der Form ${}s=t$, wobei ${}s$ und ${}t$ Terme sind, und der Form ${}Rt_{1}\ldots t_{n}$, wobei ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind.
5. Die Funktion

   $F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N}$

   heißt ${}R$-berechenbar, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei jeder Eingabe ${}(r_{1},\ldots ,r_{k})$ (in den ersten ${}k$ Registern) anhält und ${}F(r_{1},\ldots ,r_{k})$ als (einzige) Ausgabe besitzt.

6. Unter dem Reflexivitätsaxiom versteht man das modallogische Axiomenschema

   $\Box \alpha \rightarrow \alpha .$

Zur gelösten Aufgabe