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.
}
{} {}
<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2014) | >> |
---|