Mathematische Logik/Gemischte Satzabfrage/20/Aufgabe/Lösung

1. Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$-Term und ${}\alpha$ ein ${}U$-Ausdruck. Es seien zwei ${}S$-Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Dann gelten folgende Aussagen.
   1. Es ist ${}I_{1}(t)=I_{2}(t)$.
   2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$.
2. In einem Peano-Halbring ${}M$ gilt für jedes ${}x\in M$ die Eigenschaft: Entweder ist ${}x=0$ oder es gibt ein ${}u\in M$ mit ${}x=u+1$.
3. Die Menge

   ${\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(0){\text{ hält an}}\right\}}$

   ist nicht

   ${}R$-entscheidbar.

Zur gelösten Aufgabe