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

1. Eine Primzahl der Form ${}2^{n}-1$ heißt Mersennesche Primzahl.
2. Die ${}S$-Ausdrücke werden folgendermaßen als gültig charakterisiert (dabei seien ${}s,t,t_{1},\ldots ,t_{n}$ Terme und ${}\alpha ,\beta$ Ausdrücke).
   1. ${}I\vDash s=t$, wenn ${}I(s)=I(t)$.
   2. ${}I\vDash Rt_{1}\ldots t_{n}$, wenn ${}(I(t_{1}),\ldots ,I(t_{n}))\in R^{M}$.
   3. ${}I\vDash \neg {\left(\alpha \right)}$, wenn nicht ${}I\vDash \alpha$ gilt.
   4. ${}I\vDash {\left(\alpha \right)}\wedge {\left(\beta \right)}$, wenn ${}I\vDash \alpha$ und ${}I\vDash \beta$ gilt.
   5. ${}I\vDash {\left(\alpha \right)}\rightarrow {\left(\beta \right)}$, wenn die Gültigkeit ${}I\vDash \alpha$ die Gültigkeit ${}I\vDash \beta$ impliziert.
   6. ${}I\vDash \exists x\alpha$, wenn es ein ${}m\in M$ gibt mit ${}I{\frac {m}{x}}\vDash \alpha$.
   7. ${}I\vDash \forall x\alpha$, wenn für alle ${}m\in M$ die Beziehung ${}I{\frac {m}{x}}\vDash \alpha$ gilt.

3. $\varphi \colon M\longrightarrow N$

   heißt ${}S$-Isomorphismus, wenn ${}\varphi$ bijektiv ist und sowohl ${}\varphi$ als auch die Umkehrabbildung ${}\varphi ^{-1}$ ein ${}S$-Homomorphismus ist.

4. Man sagt, dass ${}T$ ${}R$-aufzählbar ist, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei Eingabe von ${}0$ nach und nach genau die Zahlen aus ${}T$ ausdruckt.
5. Das modallogische Axiomenschema

   $\Box \alpha \rightarrow \Box \Box \alpha$

   nennt man Transitivitätsaxiom.

6. Die Gültigkeit wird rekursiv wie folgt definiert: Es sei der modallogische Ausdruck ${}\alpha$ schon für jeden Weltpunkt definiert. Dann setzt man für einen jeden Weltpunkt ${}w\in M$

   $w\vDash \Box \alpha$

   genau dann, wenn in jeder von ${}w$ aus erreichbaren Welt ${}v$ die Beziehung

   $v\vDash \alpha$

   gilt.

Zur gelösten Aufgabe