Kurs:Einführung in die mathematische Logik/8/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}{ 1 }
\renewcommand{\avier}{ 3 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 2 }
\renewcommand{\asieben}{ 4 }
\renewcommand{\aacht}{ 4 }
\renewcommand{\aneun}{ 8 }
\renewcommand{\azehn}{ 2 }
\renewcommand{\aelf}{ 2 }
\renewcommand{\azwoelf}{ 4 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 6 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 5 }
\renewcommand{\asiebzehn}{ 50 }
\renewcommand{\aachtzehn}{ }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellesechzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden
\zusatzklammer {kursiv gedruckten} {} {} Begriffe.
\aufzaehlungsechs{Eine
\stichwort {widersprüchliche} {}
Ausdrucksmenge
\mathl{\Gamma \subseteq L^V}{} in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$.
}{Die \stichwort {Produktmenge} {} aus zwei Mengen $L$ und $M$.
}{Die \stichwort {Ableitbarkeit} {} eines Ausdrucks $\alpha \in L^S$ im prädikatenlogischen Kalkül.
}{Die \stichwort {Repräsentierbarkeit} {} einer \definitionsverweis {Funktion}{}{} \maabbdisp {F} {\N^r} {\N^s } {} in einer Menge $\Gamma$ von \definitionsverweis {arithmetischen Ausdrücken}{}{.}
}{Das \definitionsverweis {modallogische}{}{} \stichwort {Möglichkeitsaxiom} {.}
}{Die \stichwort {Nachfolgermenge} {} in einem \definitionsverweis {gerichteten Graphen}{}{.} }
}
{
\aufzaehlungsechs{Die Ausdrucksmenge
\mathl{\Gamma}{} heißt
widersprüchlich,
wenn es einen Ausdruck
\mathl{\alpha \in L^V}{} mit
\mathkor {} {\Gamma \vdash \alpha} {und} {\Gamma \vdash \neg \alpha} {}
gibt.
}{Man nennt die Menge
\mavergleichskettedisp
{\vergleichskette
{ L \times M
}
{ =} { { \left\{ (x,y) \mid x \in L,\, y \in M \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die Produktmenge der Mengen
\mathkor {} {L} {und} {M} {.}
}{Der Ausdruck
\mathl{\alpha}{} heißt
ableitbar,
wenn er sich aus den Grundtautologien, also
\auflistungdrei{den aussagenlogischen syntaktischen Tautologien,
}{den Gleichheitsaxiomen,
}{der Existenzeinführung im Sukzedens,
}
durch sukzessive Anwendung der Ableitungsregeln
\definitionsverweis {Modus ponens}{}{}
und der \definitionsverweis {Existenzeinführung im Antezedens}{}{}
erhalten lässt.
}{Die Funktion $F$ heißt
repräsentierbar
in $\Gamma$, wenn es einen $L^{\rm Ar}$-Ausdruck $\psi$ in
\mathl{r+s}{}
\definitionsverweis {freien Variablen}{}{}
derart gibt, dass für alle
\mathl{(r+s)}{-}Tupel
\mathl{(n_1 , \ldots , n_{r+s}) \in \N^{r+s}}{} die folgenden Eigenschaften
\aufzaehlungdrei{Wenn
\mathl{F(n_1, \ldots , n_{r}) =(n_{r+1} , \ldots , n_{r+s})}{,} so ist
\mathl{\Gamma \vdash \psi (n_1 , \ldots , n_{r+s})}{,}
}{Wenn
\mathl{F(n_1, \ldots , n_{r}) \neq (n_{r+1} , \ldots , n_{r+s})}{,} so ist
\mathl{\Gamma \vdash \neg \psi (n_1 , \ldots , n_{r+s})}{,}
}{
\mathl{\Gamma \vdash \exists ! x_{r+1} \ldots \exists ! x_{r+s} \psi (n_1 , \ldots , n_{r}, x_{r+1} , \ldots , x_{r+s})}{,}
}
gelten.
}{Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Box \alpha \rightarrow \Diamond \alpha} { }
nennt man
Möglichkeitsaxiom.
}{Zu einer Teilmenge
\mathl{T \subseteq M}{} in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} nennt man
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Nachf} { \left( T \right) }
}
{ =} { { \left\{ z \in M \mid \text{ es gibt } y \in T \text{ mit } yRz \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
Nachfolgermenge
zu $T$.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die Vorgängereigenschaft in einem Peano-Halbring.}{Der \stichwort {Endlichkeitssatz} {} für die Prädikatenlogik.}{Die \stichwort {Unentscheidbarkeit der Arithmetik} {.}}
}
{
\aufzaehlungdrei{In einem
\definitionsverweis {Peano-Halbring}{}{}
$M$ gilt für jedes
\mathl{x \in M}{} die Eigenschaft: Entweder ist
\mathl{x=0}{} oder es gibt ein
\mathl{u \in M}{} mit
\mavergleichskette
{\vergleichskette
{x
}
{ = }{u+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}{Es sei $S$ ein Symbolalphabet, $\Gamma$ eine Menge an $S$-Ausdrücken und $\alpha$ ein weiterer $S$-Ausdruck. Dann gilt
\mathl{\Gamma \vDash \alpha}{} genau dann, wenn es eine endliche Teilmenge
\mathl{\Gamma_e \subseteq \Gamma}{} gibt mit
\mathl{\Gamma_e \vDash \alpha}{.}}{Die Menge der wahren arithmetischen Ausdrücke
\zusatzklammer {ohne freie Variablen} {} {}
ist nicht
$R$-\definitionsverweis {entscheidbar}{}{.}}
}
\inputaufgabeklausurloesung
{1}
{
In einer psychologischen Längsschnittstudie wird die Entwicklung von Einstellungen und Verhaltensweisen von Personen untersucht. Ein Fallbeispiel: Im Alter von $20$ Jahren geht Linda regelmäßig auf Demonstrationen, sie hilft im Eine-Welt-Laden mit, braut ökologisches Bier, kocht Bio-Gemüse und studiert manchmal Soziologie.
Welcher der folgenden Befunde ist nach 10 Jahren am unwahrscheinlichsten? \aufzaehlungdrei{Linda arbeitet für eine Versicherungsagentur. }{Linda engagiert sich bei Attac und arbeitet für eine Versicherungsagentur. }{Linda engagiert sich bei Attac. }
}
{
(2) ist am unwahrscheinlichsten. Dass zwei Ereignisse gleichzeitig eintreffen ist stets unwahrscheinlicher als die beiden einzelnen Ereignisse.
}
\inputaufgabeklausurloesung
{3}
{
Erläutere das Prinzip \stichwort {Beweis durch Widerspruch} {} für eine Aussage der Form \anfuehrung{Aus $A$ folgt $B$}{.}
}
{
Man möchte zeigen, dass aus einer Aussage $A$ eine weitere Aussage $B$ folgt. Beim Beweis durch Widerspruch nimmt man an, dass gleichzeitig $A$ und nicht $B$ gelten. Unter diesen Voraussetzungen zeigt man, dass sich ein Widerspruch ergibt. Dies bedeutet, dass $A$ und nicht $B$ nicht gleichzeitig gelten können, was eben die Implikation
\mathl{A \implies B}{} bedeutet.
}
\inputaufgabeklausurloesung
{3}
{
Es sei
\mathl{\Gamma \subseteq L^V}{} eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
über einer Aussagenvariablenmenge $V$ und es sei
\mathl{\alpha \in L^V}{.} Es gelte
\mathdisp {\Gamma \not \vdash \alpha} { . }
Zeige, dass dann
\mathdisp {\Gamma \cup \{ \neg \alpha \}} { }
\definitionsverweis {widerspruchsfrei}{}{}
ist.
}
{
Nehmen wir an, dass
\mathl{\Gamma \cup \{\neg \alpha \}}{} widersprüchlich ist. Dann ist
\mathl{\Gamma \cup \{\neg \alpha \} \vdash \alpha}{,} da aus einer widersprüchlichen Menge alles ableitbar ist. Nach
Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))
ist dann
\mathl{\Gamma \vdash \neg \alpha \rightarrow \alpha}{.} Wegen der Tautologie
\mathl{\vdash \alpha \rightarrow \alpha}{} folgt mit der Fallunterscheidungsregel
\mathl{\Gamma \vdash \alpha}{.}
}
\inputaufgabeklausurloesung
{2}
{
Es sei ein
\definitionsverweis {Symbolalphabet}{}{}
$S$ einer
\definitionsverweis {Sprache erster Stufe}{}{}
gegeben, $\alpha \in L^S$ und $I$ eine
\definitionsverweis {Interpretation}{}{}
mit
\mathl{I \vDash \alpha}{.} Zeige durch ein Beispiel, dass daraus nicht im Allgemeinen die Gültigkeit
\mathl{I \vDash \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} unter einer
\definitionsverweis {Substitution}{}{}
folgt.
}
{
Die Sprache enthalte Konstanten
\mavergleichskette
{\vergleichskette
{c
}
{ \neq }{d
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und es sei eine Interpretation mit
\mavergleichskette
{\vergleichskette
{I(c)
}
{ \neq }{I(d)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben. Die Variable $x$ sei bei der Interpretation durch $I(c)$ belegt. Dann gilt
\mathl{I \vDash x=c}{.} Die Substitution
\mathl{{ \frac{ d }{ x } }}{} führt den Ausdruck
\mathl{x=c}{} in
\mathl{d=c}{} über, und dieser gilt nicht unter der Interpretation.
}
\inputaufgabeklausurloesung
{4}
{
Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen
\mathdisp {x + 0 =x \text { für alle } x \in \N \text{ und } x + y' = (x + y )' \text { für alle } x,y \in \N} { }
eindeutig bestimmt ist.
}
{
Die Addition erfüllt nach Lemma 12.6 (Einführung in die mathematische Logik (Osnabrück 2021)) (1, 2) diese Eigenschaften.
Es seien zwei Verknüpfungen
\mathkor {} {+} {und} {*} {}
auf $\N$ gegeben, die beide diese charakteristischen Eigenschaften erfüllen. Es ist zu zeigen, dass dann diese beiden Verknüpfungen überhaupt übereinstimmen. Wir müssen also die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{x +y
}
{ =} {x *y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ x,y
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beweisen. Dies machen wir durch Induktion über $y$
\zusatzklammer {für beliebige $x$} {} {.}
Bei
\mavergleichskettedisp
{\vergleichskette
{y
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist wegen
\mavergleichskettedisp
{\vergleichskette
{ x+0
}
{ =} { x
}
{ =} { x*0
}
{ } {
}
{ } {
}
}
{}{}{}
die Aussage richtig. Es sei die Aussage nun für ein bestimmtes $y$ schon bewiesen. Dann ist mit der charakteristischen Eigenschaft und der Induktionsvoraussetzung
\mavergleichskettedisp
{\vergleichskette
{ x+y^\prime
}
{ =} { (x+y)^\prime
}
{ =} { (x*y)^\prime
}
{ =} { x * y^\prime
}
{ } {
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{4 (1+1+1+1)}
{
Es sei
\mathl{(M, \preccurlyeq)}{} eine nichtleere
\definitionsverweis {geordnete Menge}{}{.}
Wir betrachten die Relation $\prec$ auf $M$, die durch
\mavergleichskette
{\vergleichskette
{x
}
{ \prec }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
falls
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{x
}
{ \neq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, definiert ist.
\aufzaehlungvier{Ist $\prec$ transitiv?
}{Ist $\prec$ reflexiv?
}{Charakterisiere, wann $\prec$ symmetrisch ist.
}{Ist $\prec$ antisymmetrisch?
}
}
{
\aufzaehlungvier{Sei
\mavergleichskette
{\vergleichskette
{x
}
{ \prec }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{y
}
{ \prec }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Das bedeutet
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{y
}
{ \preccurlyeq }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ist wegen der Transitivität von $\preccurlyeq$ auch
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wäre
\mavergleichskette
{\vergleichskette
{x
}
{ = }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so wäre wegen der Antisymmetrie von $\preccurlyeq$ auch
\mavergleichskette
{\vergleichskette
{x
}
{ = }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
was den Voraussetzungen widerspricht.
}{Die Relation $\prec$ ist nicht reflexiv, da
\mavergleichskette
{\vergleichskette
{x
}
{ \prec }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Verschiedenheit von
\mathkor {} {x} {und} {y} {}
beinhaltet.
}{Die Relation $\prec$ ist nicht symmetrisch, außer wenn $\preccurlyeq$ die Identität ist. In diesem Fall ist nämlich $\prec$ die leere Relation, und diese ist symmetrisch. Wenn es hingegen ein Paar
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ \neq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt, so ist
\mavergleichskette
{\vergleichskette
{x
}
{ \prec }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
aber nicht umgekehrt.
}{Die Relation $\prec$ ist antisymmetrisch. Sei
\mavergleichskette
{\vergleichskette
{x
}
{ \prec }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{y
}
{ \prec }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist insbesondere
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{y
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Antisymmetrie der Ordnungsrelation impliziert
\mavergleichskette
{\vergleichskette
{x
}
{ = }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Doch dies ist ein Widerspruch zur Voraussetzung. D.h. die Voraussetzung in der Eigenschaft Antisymmetrie kann gar nicht erfüllt sein und daher ist die Antisymmetrie erfüllt.
}
}
\inputaufgabeklausurloesung
{8}
{
Beweise den Satz von Henkin.
}
{
Es sei $M$ das konstruierte Modell zu $\Gamma$ und $I$ die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz
\mathdisp {\alpha \in \Gamma \text{ genau dann, wenn } I \vDash \alpha} { }
für alle Ausdrücke $\alpha$, durch Induktion über den
\definitionsverweis {Rang}{}{}
der Ausdrücke. Zum Induktionsanfang sei der Rang von $\alpha$ gleich $0$, also $\alpha$
\definitionsverweis {atomar}{}{.}
D.h. $\alpha$ ist entweder von der Form
\mathkor {} {s=t} {oder} {Rt_1 \ldots t_n} {.}
Im ersten Fall ist
\mavergleichskette
{\vergleichskette
{s = t
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
äquivalent zu
\mavergleichskette
{\vergleichskette
{s
}
{ \sim }{t
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bzw.
\mavergleichskette
{\vergleichskette
{[s]
}
{ = }{[t]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in $M$. Dies ist nach
Lemma 14.9 (Einführung in die mathematische Logik (Osnabrück 2021))
äquivalent zu
\mavergleichskette
{\vergleichskette
{I(s)
}
{ = }{I(t)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und das bedeutet
\mathl{I \vDash s=t}{.}
Im zweiten Fall ist
\mavergleichskette
{\vergleichskette
{ Rt_1 \ldots t_n
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzgs {nach Konstruktion von $M$ und $R^M$} {}
äquivalent zu
\mathl{R^M([t_1] , \ldots , [t_n])}{,} und dies ist äquivalent zu
\mathl{I \vDash Rt_1 \ldots t_n}{.}
Es sei nun die Aussage für alle Ausdrücke vom Rang $\leq r$ bewiesen und sei $\alpha$ ein Ausdruck vom Rang
\mathl{r+1}{.} Wir betrachten die mögliche Struktur von $\alpha$ gemäß
Definition ..
Bei
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} {\neg \beta
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ergibt sich die Äquivalenz aus der Induktionsvoraussetzung
\zusatzklammer {$\beta$ hat kleineren Rang als $\alpha$} {} {}
und
Lemma 14.6 (Einführung in die mathematische Logik (Osnabrück 2021)) (1).
Bei
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { \beta_1 \wedge \beta_2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besitzen die beiden Bestandteile kleineren Rang als $\alpha$. Die Zugehörigkeit
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{\Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist nach
Lemma 14.6 (Einführung in die mathematische Logik (Osnabrück 2021)) (3)
äquivalent zur gemeinsamen Zugehörigkeit
\mavergleichskette
{\vergleichskette
{ \beta_1, \beta_2
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Nach Induktionsvoraussetzung bedeutet dies
\mathkor {} {I \vDash \beta_1} {und} {I \vDash \beta_2} {.}
Dies bedeutet wiederum
\mathl{I \vDash \beta_1 \wedge \beta_2}{} aufgrund der
\definitionsverweis {Modellbeziehung}{}{.}
Bei
\mavergleichskettedisp
{\vergleichskette
{\alpha
}
{ =} {\exists x \beta
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besitzt wieder $\beta$ einen kleineren Rang. Die Zugehörigkeit
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von
Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021))
äquivalent zur Existenz eines Terms $t$ und der Zugehörigkeit
\mavergleichskette
{\vergleichskette
{ \beta \frac{t}{x}
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Die Substitution von $\beta$ nach
\mathl{\beta \frac{t}{x}}{} verändert nach
Aufgabe 14.17 (Einführung in die mathematische Logik (Osnabrück 2021))
nicht den Rang. Wir können also auf
\mathl{\beta \frac{t}{x}}{} die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu
\mathl{I \vDash \beta \frac{t}{x}}{.} Nach
dem Substitutionslemma
ist dies äquivalent zu
\mathl{I \frac{I(t)}{x} \vDash \beta}{} bzw.
\mathl{I \frac{[t]}{x} \vDash \beta}{} wegen
Lemma 14.9 (Einführung in die mathematische Logik (Osnabrück 2021)).
Dies ist äquivalent zu
\mathl{I \vDash \exists x \beta}{} aufgrund der
\definitionsverweis {Modellbeziehung}{}{}
und der Surjektivität der Termabbildung.
}
\inputaufgabeklausurloesung
{2}
{
Zeige, dass mit
\mathdisp {\vdash \alpha \rightarrow \beta} { }
auch
\mathdisp {\vdash \forall x \alpha \rightarrow \forall x \beta} { }
gilt.
}
{
Aus der ableitbaren Implikation
\mathdisp {\vdash \alpha \rightarrow \beta} { }
ergibt sich mittels der Alleinführung im Antezedens
\mathdisp {\vdash \forall x \alpha \rightarrow \alpha} { }
und dem Kettenschluss
\mathdisp {\vdash \forall x \alpha \rightarrow \beta} { }
und daraus mit der Alleinführung im Sukzedens, die anwendbar ist, da $x$ vorne und in
\mathl{\forall x \beta}{} gebunden ist,
\mathdisp {\vdash \forall x \alpha \rightarrow \forall x \beta} { . }
}
\inputaufgabeklausurloesung
{2}
{
Zeige
\mathdisp {\vdash \forall x { \left( \alpha \wedge \beta \right) } \rightarrow \forall x \alpha \wedge \forall x \beta} { . }
}
{
Es ist
\mathdisp {\vdash \alpha \wedge \beta \rightarrow \alpha} { }
aufgrund einer aussagenlogischen Tautologie. Nach
Aufgabe 11.7 (Einführung in die mathematische Logik (Osnabrück 2021))
ergibt sich
\mathdisp {\vdash \forall x { \left( \alpha \wedge \beta \right) } \rightarrow \forall x \alpha} { }
und ebenso
\mathdisp {\vdash \forall x { \left( \alpha \wedge \beta \right) } \rightarrow \forall x \beta} { . }
Dies zusammengenommen ergibt
\mathdisp {\vdash \forall x { \left( \alpha \wedge \beta \right) } \rightarrow \forall x \alpha \wedge \forall x \beta} { . }
}
\inputaufgabeklausurloesung
{4}
{
Beweise den Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.
}
{
Aufgrund von
Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)),
angewendet auf $N_1$ und die Nachfolgerabbildung auf $N_2$,
gibt es genau eine Abbildung
\maabbdisp {\varphi} {N_1} {N_2
} {}
mit den angegebenen Eigenschaften. Wenn man die Rollen vertauscht, so erhält man eine eindeutige Abbildung
\maabbdisp {\psi} {N_2} {N_1
} {}
mit den gleichen Eigenschaften. Wir betrachten nun die Verknüpfung
\maabbdisp {\psi \circ \varphi} {N_1} {N_1
} {.}
Diese erfüllt ebenfalls diese Eigenschaften. Da aber die Identität auf $N_1$ auch diese Eigenschaften erfüllt, folgt aus der Eindeutigkeitsaussage aus
Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)),
dass
\mavergleichskette
{\vergleichskette
{ \psi \circ \varphi
}
{ = }{
\operatorname{Id}_{ N_1 }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Ebenso ist
\mavergleichskette
{\vergleichskette
{ \varphi \circ \psi
}
{ = }{
\operatorname{Id}_{ N_2 }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit sind
\mathkor {} {\varphi} {und} {\psi} {}
invers zueinander.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{6 (4+2)}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{ S
}
{ =} { \{0,1,+,\cdot, \geq \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
das
\definitionsverweis {Symbolalphabet}{}{}
für einen
\definitionsverweis {angeordneten Körper}{}{}
und es sei $\R$ die
$S$-\definitionsverweis {Struktur}{}{}
mit der Standardinterpretation.
\aufzaehlungzwei {Zeige, dass die Äquivalenzklassen zur
\definitionsverweis {elementaren Äquivalenz}{}{}
einelementig sind.
} {Zeige, dass es für die Elemente im Allgemeinen keinen charakterisierenden Ausdruck gibt.
}
}
{
\aufzaehlungzwei {Es seien
\mathl{r,s \in \R}{} verschiedene reelle Zahlen. Für müssen zeigen, dass es einen
\mathl{S}{-}Ausdruck in einer freien Variablen $x$ gibt, der gilt, wenn man $x$ durch $r$ interpretiert, aber nicht, wenn man ihn durch $s$ interpretiert. Ohne Einschränkung sei
\mavergleichskette
{\vergleichskette
{r
}
{ < }{s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wegen der Dichtheit der rationalen Zahlen $\Q$ in $\R$ gibt es eine rationale Zahl $q$ mit
\mavergleichskettedisp
{\vergleichskette
{r
}
{ \leq} {q
}
{ <} {s
}
{ } {
}
{ } {
}
}
{}{}{.}
Sei
\mavergleichskette
{\vergleichskette
{q
}
{ = }{ { \frac{ m }{ n } }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann bedeuten diese Ungleichungen
\mavergleichskette
{\vergleichskette
{ nr
}
{ \leq }{ m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ ns
}
{ > }{ m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Somit ist der Ausdruck
\mathl{nx \leq m}{,} der durch
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ \defeq} {x + \cdots + x \leq 1 + \cdots + 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit $n$ Summanden links und $m$ Summanden rechts realisiert wird, ein Ausdruck, der bei Interpretation von $x$ durch $r$ gilt, bei Interpretation durch $s$ aber nicht.
} {Da das Symbolalphabet abzählbar ist, gibt es überhaupt nur abzählbar viele Ausdrücke in der Sprache $L^S$. Da die reellen Zahlen überabzählbar sind, kann es also aus Anzahlgründen gar nicht für jede reelle Zahl einen charakterisierenden Ausdruck geben.
}
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{5}
{
Zeige, dass in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} das modallogische
\definitionsverweis {euklidische Axiom}{}{}
genau dann gilt, wenn $R$
\definitionsverweis {euklidisch}{}{}
ist.
}
{
Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ euklidisch und sei
\mathdisp {w \vDash \Diamond \alpha} { . }
Somit gibt es eine Welt $v$ mit
\mathl{wRv}{} und mit
\mathdisp {v \vDash \alpha} { . }
Es sei $z$ eine Welt mit
\mathl{wRz}{.} Nach der euklidischen Eigenschaft ist dann auch
\mathl{zRv}{,} daher ist
\mathdisp {z \vDash \Diamond \alpha} { . }
Somit ist
\mathdisp {w \vDash \Box \Diamond \alpha} { . }
Es sei nun $R$ nicht euklidisch und seien
\mavergleichskette
{\vergleichskette
{ w,v,z
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Punkte mit
\mathl{wRv}{,}
\mathl{wRz}{,} aber nicht
\mathl{vRz}{.} Es sei $p$ eine Aussagenvariable und sei $\mu$ die Belegung, bei der $\neg p$ in allen von $v$ aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist
\mathdisp {z \vDash p} { }
und somit
\mathdisp {w \vDash \Diamond p} { . }
In $v$ gilt hingegen $\Box \neg p$, also
\mathdisp {v \vDash \neg \Diamond p} { . }
Somit gilt
\mathdisp {w \vDash \neg \Box \Diamond p} { }
und damit
\mathdisp {w \not \vDash \Diamond p \rightarrow \Box \Diamond p} { . }
}