Kurs:Einführung in die mathematische Logik/13/Klausur mit Lösungen/latex
%Daten zur Institution
%\input{Dozentdaten}
%\renewcommand{\fachbereich}{Fachbereich}
%\renewcommand{\dozent}{Prof. Dr. . }
%Klausurdaten
\renewcommand{\klausurgebiet}{ }
\renewcommand{\klausurtyp}{ }
\renewcommand{\klausurdatum}{ . 20}
\klausurvorspann {\fachbereich} {\klausurdatum} {\dozent} {\klausurgebiet} {\klausurtyp}
%Daten für folgende Punktetabelle
\renewcommand{\aeins}{ 3 }
\renewcommand{\azwei}{ 3 }
\renewcommand{\adrei}{ 3 }
\renewcommand{\avier}{ 3 }
\renewcommand{\afuenf}{ 2 }
\renewcommand{\asechs}{ 4 }
\renewcommand{\asieben}{ 7 }
\renewcommand{\aacht}{ 3 }
\renewcommand{\aneun}{ 0 }
\renewcommand{\azehn}{ 2 }
\renewcommand{\aelf}{ 8 }
\renewcommand{\azwoelf}{ 0 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 11 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 0 }
\renewcommand{\aachtzehn}{ 49 }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellesiebzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Eine \stichwort {Wahrheitsbelegung} {} für eine Menge an Aussagenvariablen.
}{Eine
\stichwort {induktiv} {}
geordnete Menge
\mathl{(I,\preccurlyeq)}{.}
}{Das \stichwort {Alphabet einer Sprache erster Stufe} {.}
}{Die Eigenschaft einer Ausdrucksmenge
\mathl{\Gamma \subseteq L^S}{,}
\stichwort {Beispiele zu enthalten} {.}
}{Die \stichwort {Addition} {} in einem \definitionsverweis {Dedekind-Peano-Modell}{}{} $\N$.
}{Der \stichwort {modallogische Folgerungsbegriff} {.} }
}
{
\aufzaehlungsechs{Unter einer
Wahrheitsbelegung
versteht man eine
\definitionsverweis {Abbildung}{}{}
\maabbdisp {\lambda} {V} {\{0,1\}
} {.}
}{Eine
\definitionsverweis {geordnete Menge}{}{}
\mathl{(I,\preccurlyeq)}{} heißt
induktiv geordnet,
wenn jede
\definitionsverweis {total geordnete}{}{}
Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {obere Schranke}{}{}
in $I$ besitzt.
}{Das
Alphabet einer Sprache erster Stufe
umfasst die folgenden Daten.
\aufzaehlungsechs{Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
}{Zu jeder natürlichen Zahl
\mathl{n \in \N_+}{} eine Menge
\mathl{R_n}{} von $n$-stelligen Relationssymbolen.
}{Die aussagenlogischen Junktoren
\mathdisp {\neg, \, \wedge, \, \vee, \, \rightarrow , \, \leftrightarrow} { . }
}{Das Gleichheitszeichen
\mathl{=}{.}
}{Die Quantoren
\mathkor {} {\forall} {und} {\exists} {.}
}{Klammern, also $($ und $)$.
}
}{Man sagt, dass $\Gamma$ Beispiele enthält, wenn es für jeden Ausdruck der Form
\mathl{\exists x \alpha}{} aus
\mathl{L^S}{} einen
$S$-\definitionsverweis {Term}{}{}
$t$ derart gibt, dass
\mathdisp {\exists x \alpha \rightarrow \alpha { \frac{ t }{ x } }} { }
zu $\Gamma$ gehört.
}{Die Addition
\mathl{n+k}{} wird über die Addition
\mathl{\alpha_n}{} mit festem $n$ definiert, wobei $\alpha_n$ die eindeutig bestimmte Abbildung
\maabbeledisp {\alpha_n} {\N} {\N
} {k} { \alpha_n(k)
} {,}
ist, für die
\mathdisp {\alpha_n(0)=n \text{ und } \alpha_n(k') = ( \alpha_n(k))' \text{ für alle } k \in \N} { }
gilt.
}{Es sei $\Gamma$ eine Menge von
\definitionsverweis {modallogischen Ausdrücken}{}{}
und $\alpha$ ein modallogischer Ausdruck. Man sagt, dass $\alpha$ aus $\Gamma$
folgt,
wenn für jedes
\definitionsverweis {modallogische Modell}{}{}
\mathl{(M,R,\mu)}{} mit
\mathdisp {(M,R,\mu) \vDash \Gamma} { }
auch
\mathdisp {(M,R,\mu) \vDash \alpha} { }
gilt.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Das Wohlordnungsprinzip für erststufige Aussagen.}{Das \stichwort {Isomorphielemma} {.}}{/Fakt/Name}
}
{
\aufzaehlungdrei{In einem
\definitionsverweis {Peano-Halbring}{}{}
$M$ gilt für jeden Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^{\{0,1,+,\cdot \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in der freien Variablen $x$ die Aussage
\mathdisp {\exists x \alpha \rightarrow \exists y { \left( \alpha \frac{y}{x} \wedge \forall x { \left( \alpha \rightarrow x \geq y \right) } \right) }} { . }
}{Es seien
\mathkor {} {M} {und} {N} {}
\definitionsverweis {isomorphe}{}{}
$S$-\definitionsverweis {Strukturen}{}{}
über einem
\definitionsverweis {Symbolalphabet}{}{}
$S$. Dann sind
\mathkor {} {M} {und} {N} {}
\definitionsverweis {elementar äquivalent}{}{.}}{/Fakt}
}
\inputaufgabeklausurloesung
{3}
{
In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit $V$ \zusatzklammer {vordere Tafel} {} {,} $M$ \zusatzklammer {mittlere Tafel} {} {} und $H$ \zusatzklammer {hintere Tafel} {} {} bezeichnet. Aufgrund der Höhe des Gestells sind nur \zusatzklammer {maximal} {} {} zwei Tafeln gleichzeitig einsehbar. Die Lehrperson schreibt in der Vorlesung jede Tafel genau einmal voll. In welcher Reihenfolge \zusatzklammer {alle Möglichkeiten} {!} {} muss sie die Tafeln einsetzen, wenn beim Beschreiben einer Tafel stets die zuletzt beschriebene Tafel sichtbar sein soll.
}
{
Die Tafeln \mathkor {} {M} {und} {H} {} sind nicht gleichzeitig sichtbar, da \zusatzklammer {mindestens} {} {} eine davon durch $V$ verdeckt wird. Dagegen sind sowohl \mathkor {} {V} {und} {H} {} \zusatzklammer {$M$ wird hinter $V$ geschoben} {} {} als auch \mathkor {} {V} {und} {M} {} gleichzeitig einsehbar. Eine Beschreibungsreihenfolge erfüllt also genau dann die angegebene Bedingung, wenn \mathkor {} {M} {und} {H} {} nicht direkt hintereinander beschrieben werden. Dies wird genau dann erreicht, wenn $V$ als zweite Tafel beschrieben wird. Erlaubt sind also die beiden Reihenfolgen \mathkor {} {M-V-H} {und} {H-V-M} {.}
}
\inputaufgabeklausurloesung
{3}
{
Bei einem Zwei-Personen-Regel-Spiel \zusatzklammer {wie Schach} {} {} spielen zwei Personen \zusatzklammer {$A$ und $B$} {} {} nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für $A$ ist, da ist $A$ am Zug und kann $B$ schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge $S$ aller Stellungen eine Gewinnstellung für $A$ \zusatzklammer {mit $A$ am Zug} {} {} ist.
}
{
Wir definieren
\mavergleichskettedisp
{\vergleichskette
{G_0
}
{ =} { \text{jede Mattstellung für } A
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und rekursiv
\mavergleichskettedisp
{\vergleichskette
{G_n
}
{ \defeq} { { \left\{ s \in S \mid \text{ es gibt einen Zug für } A \text{ derart, dass für alle Züge von } B \text{ die entstehende Stellung zu } G_{n-1} \text{ gehört} \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Eine Gewinnstellung ist dann
\mavergleichskettedisp
{\vergleichskette
{G
}
{ =} { \bigcup_{n \in \N} G_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{2}
{
Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt. \wahrheitstabelledreieins{ } {\tabellenzeilevier {$ p $} {$ q $} {$ r $} {$? $} } {\tabellendoppelzeilevier {w} {w} {w} {f} {w} {w} {f} {f} } {\tabellendoppelzeilevier {w} {f} {w} {w} {w} {f} {f} {f} } {\tabellendoppelzeilevier {f} {w} {w} {f} {f} {w} {f} {f} } {\tabellendoppelzeilevier {f} {f} {w} {w} {f} {f} {f} {w} }
}
{
\mathdisp {\neg q \wedge { \left( \neg p \vee r \right) }} { . }
}
\inputaufgabeklausurloesung
{4}
{
Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer
\definitionsverweis {Aussagenvariablenmenge}{}{}
$V$. Zeige
\mavergleichskettedisp
{\vergleichskette
{ \Gamma^\vdash
}
{ =} { { \left( \Gamma^\vdash \right) }^\vdash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Die Inklusion
\mavergleichskettedisp
{\vergleichskette
{\Gamma^\vdash
}
{ \subseteq} { { \left( \Gamma^\vdash \right) }^\vdash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist wegen
\mathl{\vdash \alpha \rightarrow \alpha}{} klar. Es sei also
\mathl{{ \left( \alpha \in \Gamma^\vdash \right) }^\vdash}{.} Dies bedeutet, dass es Ausdrücke
\mathl{\alpha_1 , \ldots , \alpha_n \in \Gamma^\vdash}{} mit
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \alpha} { }
gibt. Für die einzelnen $\alpha_i$ gibt es
\mathl{\beta_{i1} , \ldots , \beta_{ik_i} \in \Gamma}{} mit
\mathdisp {\vdash \beta_{i1} \wedge \ldots \wedge \beta_{ik_i} \rightarrow \alpha_i} { }
für jedes $i$. Daraus ergibt sich mit Hilfe
\zusatzklammer {der Regelversion} {} {}
von
Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021)) (2)
\mathdisp {\vdash \beta_{11} \wedge \ldots \wedge \beta_{1k_1} \wedge \beta_{21} \wedge \ldots \wedge \beta_{2k_2} \wedge \ldots \wedge \beta_{n1} \wedge \ldots \wedge \beta_{nk_n} \rightarrow \alpha_1 \wedge \ldots \wedge \alpha_{n}} { . }
Mit der Kettenschlussregel ergibt sich daraus
\mathdisp {\vdash \beta_{11} \wedge \ldots \wedge \beta_{1k_1} \wedge \beta_{21} \wedge \ldots \wedge \beta_{2k_2} \wedge \ldots \wedge \beta_{n1} \wedge \ldots \wedge \beta_{nk_n} \rightarrow \alpha} { , }
was
\mathl{\alpha \in \Gamma^\vdash}{} bedeutet.
}
\inputaufgabeklausurloesung
{7}
{
Beweise den Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen im abzählbaren Fall.
}
{
Es sei
\mathbed {p_n} {}
{n \in \N_+} {}
{} {} {} {,}
eine
\zusatzklammer {surjektive, aber nicht notwendigerweise injektive} {} {}
Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass
\mavergleichskette
{\vergleichskette
{ \Gamma_0
}
{ \defeq }{ \Gamma^\vdash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
keinen Widerspruch enthält. Wir konstruieren eine
\zusatzklammer {endliche oder abzählbar unendliche} {} {}
Folge von aufsteigenden widerspruchsfreien Teilmengen
\mavergleichskette
{\vergleichskette
{\Gamma_n
}
{ \subseteq }{\Gamma_{n+1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei in $\Gamma_n$ für jede Variable
\mathbed {p_i} {}
{1 \leq i \leq n} {}
{} {} {} {,}
die Alternative entweder
\mavergleichskette
{\vergleichskette
{p_i
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{\neg p_i
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für $\Gamma_0$ ist dies richtig. Es sei
\mathl{\Gamma_n}{} schon konstruiert. Bei
\mavergleichskette
{\vergleichskette
{p_{n+1}
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{\neg p_{n+1}
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
setzen wir
\mavergleichskettedisp
{\vergleichskette
{\Gamma_{n+1}
}
{ \defeq} { \Gamma_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wegen der Widerspruchsfreiheit von $\Gamma_n$ können nicht sowohl
\mathkor {} {p_{n+1}} {als auch} {\neg p_{n+1}} {}
zu $\Gamma_n$ gehören. Wenn weder
\mathl{p_{n+1}}{} noch
\mathl{\neg p_{n+1}}{} zu $\Gamma_n$ gehören, so setzen wir
\mavergleichskettedisp
{\vergleichskette
{\Gamma_{n+1}
}
{ \defeq} { { \left( \Gamma_n \cup {p_{n+1} } \right) }^\vdash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {man könnte genauso gut
\mathl{\neg p_{n+1}}{} hinzunehmen} {} {.}
Nach Konstruktion ist
\mathl{\Gamma_{n+1}}{} abgeschlossen unter der Ableitungsbeziehung und erfüllt die
\zusatzklammer {Oder} {} {-}Alterna\-tive für alle Variablen
\mathbed {p_i} {}
{i \leq n +1} {}
{} {} {} {.}
Wenn
\mathl{\Gamma_{n+1}}{} widersprüchlich wäre, so gelte insbesondere
\mathl{\Gamma_n \cup \{ p_{n+1} \} \vdash \neg p_{n+1}}{.} Dann würde aber auch
\mathl{\Gamma_n \vdash p_{n+1} \rightarrow \neg p_{n+1}}{} gelten und somit nach der Fallunterscheidungsregel auch
\mathl{\Gamma_n \vdash \neg p_{n+1}}{,} also
\mavergleichskette
{\vergleichskette
{\neg p_{n+1}
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
im Widerspruch zu dem Fall, in dem wir uns befinden. Daher liegt für die Aussagenvariablen auch die Entweder-Oder-Alternative vor.
Mit dieser induktiven Definition setzen wir
\mavergleichskettedisp
{\vergleichskette
{\Gamma'
}
{ \defeq} { \bigcup_{n \in \N} \Gamma_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Menge $\Gamma'$ ist widerspruchsfrei, da andernfalls schon eines der $\Gamma_n$ einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen $\Gamma_n$ gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Alternative
\mathkor {} {p_n \in \Gamma'} {oder} {\neg p_n \in \Gamma'} {.}
Damit sind die Voraussetzungen von
Lemma 4.7 (Einführung in die mathematische Logik (Osnabrück 2021))
erfüllt und $\Gamma'$ ist maximal widerspruchsfrei.
}
\inputaufgabeklausurloesung
{3}
{
Es seien $x_1,x_2$ Variablen, $t_1,t_2$ Terme und $\alpha$ ein Ausdruck in einer
\definitionsverweis {prädikatenlogischen Sprache}{}{.}
Zeige, dass
\mathdisp {{ \left( \alpha { \frac{ t_1 }{ x_1 } } \right) } { \frac{ t_2 }{ x_2 } } \rightarrow \alpha { \frac{ t_1,t_2 }{ x_1,x_2 } }} { }
im Allgemeinen nicht allgemeingültig ist.
}
{
Für $\alpha$ betrachten wir den Ausdruck
\mathl{x_1=x_2}{} und wir setzen
\mavergleichskette
{\vergleichskette
{t_1
}
{ \defeq }{x_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{t_2
}
{ \defeq }{x_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist einerseits
\zusatzklammer {wir schreiben $\equiv$ für die Gleichheit von Ausdrücken} {} {}
\mavergleichskettealign
{\vergleichskettealign
{ { \left( \alpha { \frac{ t_1 }{ x_1 } } \right) } { \frac{ t_2 }{ x_2 } }
}
{ \equiv} { { \left( (x_1 = x_2) { \frac{ x_2 }{ x_1 } } \right) } { \frac{ x_1 }{ x_2 } }
}
{ \equiv} { { \left( x_2 = x_2 \right) } { \frac{ x_1 }{ x_2 } }
}
{ \equiv} { x_1 = x_1
}
{ } {
}
}
{}
{}{,}
was allgemeingültig ist, und andererseits
\mavergleichskettealign
{\vergleichskettealign
{ \alpha { \frac{ t_1,t_2 }{ x_1,x_2 } }
}
{ \equiv} { (x_1 = x_2) { \frac{ x_2,x_1 }{ x_1,x_2 } }
}
{ \equiv} { (x_1 { \frac{ x_2,x_1 }{ x_1,x_2 } } = x_2 { \frac{ x_2,x_1 }{ x_1,x_2 } })
}
{ \equiv} { x_2 = x_1
}
{ } {
}
}
{}
{}{,}
was nicht allgemeingültig ist. Somit ist
\mathdisp {x_1=x_1 \rightarrow x_2=x_1} { }
nicht allgemeingültig.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{2 (0.5+0.5+0.5+0.5)}
{
Wir zählen
\mathdisp {\text{ ich},\, \text{ Mama},\, \text{ Oma}, \, \text{Uroma}, \, \text{Ururoma}, \ldots} { . }
\aufzaehlungvier{Was ist die Mama der Urururoma?
}{Was ist die Uroma der Uroma?
}{Was ist die Oma der Oma der Oma?
}{Was ist die Ururoma der Uroma?
}
}
{
\aufzaehlungvier{Ururururoma. }{Ururururoma. }{Ururururoma. }{Urururururoma. }
}
\inputaufgabeklausurloesung
{8}
{
Beweise das Wohlordnungsprinzip für erststufige Aussagen für Peano-Halbringe.
}
{
Wir betrachten den Ausdruck
\mathdisp {\forall u { \left( \exists x { \left( \alpha \wedge x \leq u \right) } \rightarrow \exists y { \left( \alpha \frac{y}{x} \wedge \forall x { \left( \alpha \rightarrow x \geq y \right) } \right) } \right) }} { }
und wollen zeigen, dass er in jedem Peano-Halbring gilt. Dies zeigen wir unter Verwendung des Induktionsaxioms und fixieren einen Peano-Halbring $M$. Für
\mavergleichskette
{\vergleichskette
{u
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die Aussage richtig, da dann, falls der Vordersatz
\mathl{\exists x { \left( \alpha \wedge x \leq 0 \right) }}{} gilt, dann insbesondere
\mathl{\alpha \frac{0}{x}}{} in $M$ gilt und man im Nachsatz
\mavergleichskettedisp
{\vergleichskette
{y
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
nehmen kann, da ja $0$ das kleinste Element ist. Zum Beweis des Induktionsschrittes müssen wir die Gültigkeit von
\mathdisp {\forall u { \left( { \left( \exists x { \left( \alpha \wedge x \leq u \right) } \rightarrow \exists y { \left( \alpha \frac{y}{x} \wedge \forall x { \left( \alpha \rightarrow y \leq x \right) } \right) } \right) } \rightarrow { \left( \exists x { \left( \alpha \wedge x \leq u +1 \right) } \rightarrow \exists y { \left( \alpha \frac{y}{x} \wedge \forall x { \left( \alpha \rightarrow x \geq y \right) } \right) } \right) } \right) }} { }
zeigen. Es sei also die Aussage für ein bestimmtes
\mavergleichskette
{\vergleichskette
{u
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {also der Vordersatz links} {} {}
im Modell wahr. Wir müssen dann den Nachsatz, also die Aussage für
\mathl{u+1}{} als wahr erweisen. Es gelte also
\mathdisp {\exists x { \left( \alpha \wedge x \leq u+1 \right) }} { . }
Wenn sogar
\mathl{\exists x { \left( \alpha \wedge x \leq u \right) }}{} gilt, so sind wir nach Induktionsvoraussetzung fertig. Es gelte diese Aussage also nicht. Das bedeutet einerseits, dass der Ausdruck $\alpha$ für kein Element aus $M$ gilt, das kleiner als oder gleich $u$ ist, und andererseits, dass $\alpha$ gilt, wenn $x$ durch
\mathl{u+1}{} interpretiert wird. Somit gilt der Ausdruck
\mathdisp {\alpha \frac{u+1}{x} \wedge \forall x { \left( \alpha \rightarrow x \geq u+1 \right) }} { }
und damit
\mathdisp {\exists y { \left( \alpha \frac{y}{x} \wedge \forall x { \left( \alpha \rightarrow x \geq y \right) } \right) }} { . }
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{11 (2+2+4+1+2)}
{
Wir betrachten die Identität
\maabbdisp {\operatorname{Id}} {\N} {\N
} {}
und den Ausdruck
\mathl{x=y}{,} den wir mit $\psi$ bezeichnen. Es sei
\mavergleichskette
{\vergleichskette
{ \Gamma
}
{ \subseteq }{ L^{\rm Ar}
}
{ }{
}
{ }{
}
{ }{}
}
{}{}{}
die Ausdrucksmenge, die die Kommutativität und die Assoziativität der Addition besagt sowie, dass $0$ das neutrale Element der Addition ist.
\aufzaehlungfuenf{Zeige, dass der Graph der Identität durch $\psi$
\definitionsverweis {schwach repräsentierbar}{}{}
in $\Gamma$ ist.
}{Zeige, dass der Graph der Identität nicht
\definitionsverweis {repräsentierbar}{}{}
in $\Gamma$ ist.
}{Zeige, dass der Graph der Identität
\definitionsverweis {repräsentierbar}{}{}
in der Peano-Arithmetik ${\rm PA}$ ist.
}{Ist die Identität als Abbildung repräsentierbar in der Peano-Arithmetik?
}{Gilt
\mathdisp {\Gamma \vdash \exists ! y \psi (n, y)} { }
für jedes
\mathl{n \in \N}{}
\zusatzklammer {dabei werde $n$ durch eine $n$-fache Summe der $1$ mit sich in beliebiger Klammerung wiedergegeben} {} {?}
}
}
{
\aufzaehlungfuenf{Wenn eine Gleichheit
\mavergleichskettedisp
{\vergleichskette
{m
}
{ =} {n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
von natürlichen Zahlen vorliegt, so wird diese eine Zahl durch den einen Term
\mathl{1 + \cdots + 1}{} in
\mathl{L^{\rm Ar}}{} dargestellt. Wegen
Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021))
gilt
\mathdisp {\Gamma \vdash n=n} { . }
Wenn hingegen
\mathkor {} {m} {und} {n} {}
verschiedene natürliche Zahlen sind, so ist die Gleichheit
\mavergleichskette
{\vergleichskette
{m
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nicht aus $\Gamma$ ableitbar, da andernfalls wegen
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{\N^\vDash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Gleichheit auch in $\N$ gelten würde.
}{Seien
\mavergleichskettedisp
{\vergleichskette
{m
}
{ \neq} {n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
verschiedene natürliche Zahlen. Wir behaupten
\mathdisp {\Gamma \not\vdash m \neq n} { . }
Wäre das nämlich doch ableitbar, so müsste diese Ungleichheit in jedem Modell von $\Gamma$ gelten. Die Gültigkeit von $\Gamma$ in einem Modell bedeutet aber lediglich, dass ein kommutatives Monoid vorliegt. Da es auch das triviale Monoid
\mathl{\{0\}}{} gibt, in dem alle Elemente gleich sind, erhalten wir einen Widerspruch.
}{Bei gleichen Zahlen folgt die Ableitbarkeit nach Teil (1) sogar aus $\Gamma$, also erst recht aus der Peano-Arithmetik. Es seien also
\mavergleichskettedisp
{\vergleichskette
{m
}
{ \neq} {n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
verschiedene natürliche Zahlen. Es ist
\mathdisp {{\rm PA} \vdash \neg (m=n)} { }
zu zeigen. Wegen der
\zusatzklammer {ableitbaren} {} {}
Symmetrie des Gleichheitszeichens können wir
\mavergleichskettedisp
{\vergleichskette
{m
}
{ >} {n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
annehmen. Es sei
\mavergleichskettedisp
{\vergleichskette
{m
}
{ =} {k+n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mathl{k \in \N_+}{.} Nach
Axiom 12.11 (Einführung in die mathematische Logik (Osnabrück 2021))
(1)
ist
\mathdisp {{\rm PA} \vdash \neg (k=0)} { . }
Die Kontraposition zu
Axiom 12.11 (Einführung in die mathematische Logik (Osnabrück 2021))
(2)
liefert der Reihe nach
\mathdisp {{\rm PA} \vdash \neg (k+1=1)} { , }
\mathdisp {{\rm PA} \vdash \neg (k+2=2)} { , \ldots }
bis man schließlich bei
\mathdisp {{\rm PA} \vdash \neg (k+n=n)} { }
anlangt.
}{Die folgt aus Teil (5).
}{Das gilt, es ist
\mathdisp {\Gamma \vdash n=y \wedge n=z \rightarrow y=z} { }
für jedes
\mathl{n \in \N}{} zu zeigen. Dies ergibt sich aber einfach aus der
\zusatzklammer {ableitbaren} {} {}
Symmetrie und der Transitivität des Gleichheitszeichens.
}
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}