Widerspruchsfreie entscheidbare Ausdrucksmenge/Repräsentierbare Relationen und Funktionen sind entscheidbar bzw. berechenbar/Aufgabe

Es sei $\Gamma \subseteq L^{\mathrm{a}\mathrm{r}}$ eine widerspruchsfreie und $R$-entscheidbare Ausdrucksmenge.

a) Zeige, dass jede in $\Gamma$ repräsentierbare Relation $R\subseteq {\mathbb{N}}^r$ $R$-entscheidbar ist.

b) Zeige, dass jede in $\Gamma$ repräsentierbare Abbildung

$\phi :{\mathbb{N}}^r⟶{\mathbb{N}}^s$

$R$-berechenbar ist.

Eine Lösung erstellen