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

1. Ein Primzahlzwilling ist ein Paar bestehend aus ${}p$ und ${}p+2$, wobei diese beiden Zahlen Primzahlen sind.
2. Die Bestandteile einer Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.
   1. eine Variablenmenge ${}V$,
   2. eine Konstantenmenge ${}K$,
   3. zu jedem ${}n\in \mathbb {N} _{+}$ eine Menge ${}F_{n}$ von Funktionssymbolen.
3. Unter einer ${}S$-Struktur versteht man eine nichtleere Menge ${}M$ mit den folgenden Festlegungen.
   1. Für jede Konstante ${}c\in K$ ist ein Element ${}c^{M}\in M$ festgelegt.
   2. Zu jedem ${}n$-stelligen Funktionssymbol ${}f$ (aus ${}S$) ist eine ${}n$-stellige Funktion

      $f^{M}\colon M^{n}\longrightarrow M$

      festgelegt.

   3. Zu jedem ${}n$-stelligen Relationssymbol ${}R$ (aus ${}S$) ist eine ${}n$-stellige Relation

      $R^{M}\subseteq M^{n}$

      festgelegt.

4. Man nennt ${}\alpha$ allgemeingültig, wenn er in jeder ${}S$-Interpretation ${}I$ gilt.
5. Die Abbildung

   $\varphi \colon M\longrightarrow N$

   heißt ${}S$-Homomorphismus, wenn folgende Eigenschaften gelten.

   1. Für jede Konstante ${}c\in S$ ist

      ${}\varphi (c^{M})=c^{N}\,.$

   2. Für jedes ${}n$-stellige Funktionssymbol ${}f\in S$ ist

      ${}\varphi (f^{M}(m_{1},\ldots ,m_{n}))=f^{N}(\varphi (m_{1}),\ldots ,\varphi (m_{n}))\,$

      für alle ${}m_{1},\ldots ,m_{n}\in M$.

   3. Für jedes ${}n$-stellige Relationsymbol ${}R\in S$ impliziert die Gültigkeit von

      $R^{M}(m_{1},\ldots ,m_{n})$

      die Gültigkeit von

      $R^{N}(\varphi (m_{1}),\ldots ,\varphi (m_{n})).$

6. Die Relation ${}R\subseteq \mathbb {N} ^{r}$ heißt arithmetisch repräsentierbar, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$-Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die Äquivalenz ${}(n_{1},\ldots ,n_{r})\in R$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r})$ gilt.

Zur gelösten Aufgabe