Kurs:Einführung in die mathematische Logik/13/Klausur mit Lösungen/latex

Aus Wikiversity

%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 }