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

1. Es sei ${}\Gamma$ eine Menge an ${}S$-Ausdrücken (über einem Symbolalphabet ${}S$), die maximal widerspruchsfrei ist und Beispiele enthält. Dann ist die durch die kanonische Termidentifizierung gegebene Interpretation ein Modell für ${}\Gamma$.
2. 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.
3. Die Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht ${}R$-entscheidbar.

Zur gelösten Aufgabe