Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Arbeitsblatt 22/latex

\setcounter{section}{22}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Zeige, dass eine \definitionsverweis {widersprüchliche}{}{} Ausdrucksmenge
\mathl{\Gamma \subseteq L^{\rm Ar}}{} \definitionsverweis {Repräsentierungen}{}{} erlaubt.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\Gamma \subseteq L^{\rm ar}}{} eine Ausdrucksmenge, die \definitionsverweis {Repräsentierungen erlaube}{}{.} Zeige, dass jede größere Ausdrucksmenge
\mathl{\Gamma' \supseteq \Gamma}{} ebenfalls Repräsentierungen erlaubt.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\Gamma \subseteq L^{\rm ar}}{} eine \definitionsverweis {widerspruchsfreie}{}{} und $R$-\definitionsverweis {entscheidbare}{}{} Ausdrucksmenge.

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

b) Zeige, dass jede in $\Gamma$ \definitionsverweis {repräsentierbare Abbildung}{}{} \maabbdisp {\varphi} {\N^r} {\N^s } {} $R$-\definitionsverweis {berechenbar}{}{} ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige, dass in der \definitionsverweis {erststufigen Peano-Arithmetik}{}{} die Addition von natürlichen Zahlen \definitionsverweis {repräsentierbar}{}{} ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge ohne freie Variablen und
\mathl{R \subseteq \N}{} eine Relation. Es seien
\mathl{\alpha, \beta \in L^{\rm Ar}}{} Ausdrücke in einer freien Variablen $x$. Zeige, dass aus
\mathdisp {\Gamma \vdash \alpha \leftrightarrow \beta} { }
folgt, dass $\alpha$ in $\Gamma$ die Relation $R$ genau dann \definitionsverweis {repräsentiert}{}{,} wenn
\mathl{\beta}{} in $\Gamma$ die Relation $R$ repräsentiert.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge und
\mathl{R \subseteq \N}{} eine Relation. Es seien
\mathl{\alpha, \beta \in L^{\rm Ar}}{} Ausdrücke in einer freien Variablen $x$. Zeige, dass aus
\mathdisp {\Gamma \vdash \alpha \leftrightarrow \beta} { }

\betonung{nicht}{} folgt, dass $\alpha$ in $\Gamma$ die Relation $R$ genau dann \definitionsverweis {repräsentiert}{}{,} wenn
\mathl{\beta}{} in $\Gamma$ die Relation $R$ repräsentiert.

}
{} {}