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

\setcounter{section}{14}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Es seien $S \subseteq S'$ \definitionsverweis {Symbolalphabete}{}{} und seien $L^S \subseteq L^{ S^\prime}$ die zugehörigen Sprachen Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge. \aufzaehlungzwei { $\Gamma$ sei widerspruchsfrei. Ist dann auch $\Gamma$, aufgefasst in
\mathl{L^{ S^\prime}}{,} widerspruchsfrei? } { $\Gamma$ sei \definitionsverweis {maximal widerspruchsfrei}{}{.} Ist dann auch $\Gamma$, aufgefasst in
\mathl{L^{ S^\prime}}{,} maximal widerspruchsfrei? }

}
{} {}

\inputaufgabe
{}
{

Zeige durch ein Beispiel, dass Lemma 14.5 ohne die Voraussetzung, dass eine surjektive Terminterpretation vorliegt, nicht gelten muss.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $I$ eine $S$-\definitionsverweis {Interpretation}{}{} auf einer Menge $M$ mit der zugehörigen \definitionsverweis {Terminterpretation}{}{.} Zeige, dass man diese Terminterpretationsabbildung durch die Hinzunahme von Variablen \zusatzklammer {oder durch die Hinzunahme von Konstanten} {} {} \definitionsverweis {surjektiv}{}{} machen kann.

}
{} {}

\inputaufgabe
{}
{

Das Symbolalphabet $S$ bestehe aus einer einzigen Variablen $x$ und einem einzigen einstelligen Relationssymbol $P$. Zeige, dass zu einer \definitionsverweis {Interpretation}{}{} $I$ die Gültigkeitsmenge
\mathl{I^\vDash \subseteq L^S}{} keine \definitionsverweis {Beispiele enthalten}{}{} muss.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache und $T$ die zugehörige Termmenge. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge. \aufzaehlungzwei {Zeige, dass durch
\mathdisp {s \cong_\Gamma t \text{ genau dann, wenn } I(s)=I(t) \text{ für jede Interpretation } I \text{ mit } I \vDash \Gamma} { }
eine \definitionsverweis {Äquivalenzrelation}{}{} auf $T$ definiert wird. } {Wenn man $\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner? }

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{,} $T$ die zugehörige \definitionsverweis {Termmenge}{}{} und $L^S$ die zugehörige Sprache. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge. Zeige, dass die Äquivalenzrelation $\sim_\Gamma$ aus Konstruktion 14.7 die semantische Äquivalenz $\cong_\Gamma$ aus Aufgabe 14.5 impliziert.

}
{} {}

\inputaufgabe
{}
{

Das Symbolalphabet $S$ bestehe neben Variablen
\mathl{x,y,z, \ldots}{} aus einer Konstanten $0$ und einem einstelligen Funktionssymbol $f$. Wir betrachten die Teilmengen
\mavergleichskettedisp
{\vergleichskette
{\Gamma_i }
{ \subseteq} { L^S }
{ } { }
{ } { }
{ } { }
} {}{}{} mit
\mavergleichskettedisp
{\vergleichskette
{\Gamma_1 }
{ =} { \{ fff0= 0 \}^\vdash }
{ } { }
{ } { }
{ } { }
} {}{}{,}
\mavergleichskettedisp
{\vergleichskette
{\Gamma_2 }
{ =} { \{ fff x= x \}^\vdash }
{ } { }
{ } { }
{ } { }
} {}{}{,}
\mavergleichskettedisp
{\vergleichskette
{\Gamma_3 }
{ =} { \{ \forall x { \left( fffx = x \right) } \}^\vdash }
{ } { }
{ } { }
{ } { }
} {}{}{.} Es seien
\mathl{\sim_i}{} die zugehörigen Äquivalenzrelationen gemäß Konstruktion 14.7 auf der Termmenge. \aufzaehlungvier{Gelten die Äquivalenzen
\mathdisp {ffff0 \sim_1 f0,\, ffffff0 \sim_1 fff0,\, fffffffff0 \sim_1 fffffff0,\, ffffx \sim_1 fx} { ? }
}{Gelten die Äquivalenzen
\mathdisp {ffffx \sim_2 fx,\, ffffy \sim_2 fy,\, fffx \sim_2 y,\, ffffy \sim_3 fy} { ? }
}{Welche Inklusionsbeziehungen bestehen zwischen $\Gamma_1,\Gamma_2,\Gamma_3$? }{Wie viele Termklassen gibt es zu
\mathl{\sim_1,\sim_2,\sim_3}{,} wenn die Variablenmenge nur aus $x$ besteht? }

}
{} {}

\inputaufgabe
{}
{

Das Symbolalphabet $S$ bestehe neben Variablen
\mathl{x,y,z, \ldots}{} aus einer Konstanten $0$ und einem zweistelligen Funktionssymbol $+$. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Menge aller Ableitungen aus dem Axiomensystem
\mathdisp {\forall x (x+0 = x ) ,\, \forall x (0+x = x ) ,\, \forall x \forall y \forall z ( (x+y)+z) = x+ (y+z) ) , \, \forall x (x+x = 0 )} { . }
Es sei $\sim$ die zugehörige Äquivalenzrelation gemäß Konstruktion 14.7. Zeige
\mavergleichskette
{\vergleichskette
{x+y }
{ \sim }{y+x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} für jedes Variablenpaar
\mathl{x,y}{.}

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache. Zeige, dass zu
\mavergleichskettedisp
{\vergleichskette
{\Gamma }
{ =} { \emptyset }
{ } { }
{ } { }
{ } { }
} {}{}{} die in Konstruktion 14.7 eingeführte Äquivalenzrelation die Identität ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine widersprüchliche, unter Ableitungen abgeschlossene Teilmenge. Zeige, dass es nur eine Termklasse im Sinne von Konstruktion 14.7 gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine unter Ableitungen abgeschlossene Teilmenge, die zu je zwei Termen
\mathl{s,t}{} die Gleichheit
\mavergleichskette
{\vergleichskette
{s }
{ = }{t }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} enthalte. Wie viele Termklassen im Sinne von Konstruktion 14.7 gibt es? Ist $\Gamma$ widersprüchlich?

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache. Die Ausdrucksmenge $\Gamma$ bestehe aus
\mathl{x=y}{,} wobei $x,y$ verschiedene Variablen seien. Zeige, dass zwei Terme
\mathl{s,t}{} genau dann äquivalent im Sinne von Konstruktion 14.7 sind, wenn es eine Kette von Termen
\mathdisp {t_0=s,t_1, t_2 , \ldots , t_{k-1}, t_k=t} { }
derart gibt, dass beim Übergang von
\mathl{t_i}{} nach
\mathl{t_{i+1}}{} genau ein Vorkommen von $x$ \zusatzklammer {bzw. $y$} {} {} in $t_i$ durch $y$ \zusatzklammer {bzw. $x$} {} {} ersetzt wird.

}
{} {}

\inputaufgabe
{}
{

Es sei $V$ eine Variablenmenge und $\simeq$ eine \definitionsverweis {Äquivalenzrelation}{}{} auf $V$ mit der Quotientenmenge
\mavergleichskette
{\vergleichskette
{W }
{ = }{V/\simeq }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Es sei $S$ ein erststufiges Symbolalphabet mit $V$ als Variablenmenge und
\mavergleichskettedisp
{\vergleichskette
{\Gamma }
{ \defeq} { { \left\{ x= y \mid x \simeq y \right\} }^\vdash }
{ } { }
{ } { }
{ } { }
} {}{}{.} Es sei
\mathl{\sim}{} die zugehörige Äquivalenzrelation auf der Termmenge gemäß Konstruktion 14.7. Zeige, dass die Termklassenmenge zu $\Gamma$ in kanonischer Weise mit der Termmenge zum Symbolalphabet $S'$ in Bijektion steht, wobei $S'$ aus $S$ entsteht, indem man die Variablenmenge $V$ durch $W$ ersetzt.

}
{} {}

In der folgenden Aufgabe sollen die Variablen
\mathl{x_1 , \ldots , x_n}{} verschieden sein. Dennoch gibt es zwei Interpretationen für Teil (2), die aber inhaltlich äquivalent sind.


\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge. Zu fixiertem
\mathl{n \in \N_+}{} sei
\mathl{F_n}{} die Menge der $n$-stelligen Funktionssymbole. Zeige die folgenden Aussagen. \aufzaehlungvier{Durch
\mathdisp {f \cong g\, , \text{ falls } I(f) = I(g) \text{ für alle Interpretationen } I \text{ mit } I \vDash \Gamma} { }
wird eine \definitionsverweis {Äquivalenzrelation}{}{} auf $F_n$ definiert. }{Durch
\mathdisp {f \sim g\, , \text{ falls } \Gamma \vdash \forall x_1 \forall x_2 \ldots \forall x_n fx_1 \ldots x_n = g x_1 \ldots x_n} { }
wird eine \definitionsverweis {Äquivalenzrelation}{}{} auf $F_n$ definiert. }{Die Äquivalenzrelation $\sim$ impliziert die Äquivalenzrelation $\cong$. }{Es sei $\sim$ die zu $\Gamma$ gehörende formale Äquivalenzrelation auf der Termmenge im Sinne von Konstruktion 14.7. Dann gilt für Terme
\mathl{s_1 \sim t_1 , \ldots , s_n \sim t_n}{} und Funktionssymbole
\mathl{f,g \in F_n}{} mit
\mathl{f \sim g}{} die Beziehung
\mavergleichskettedisp
{\vergleichskette
{fs_1 \ldots s_n }
{ \sim} { gt_1 \ldots t_n }
{ } { }
{ } { }
{ } { }
} {}{}{.} }

}
{} {}

\inputaufgabe
{}
{

Es sei $\alpha \in L^S$ ein \definitionsverweis {atomarer Ausdruck}{}{,} der zugleich eine Tautologie ist, also
\mathl{\vdash \alpha}{.} Zeige, dass $\alpha$ gleich
\mathl{s=s}{} mit einem $S$-\definitionsverweis {Term}{}{} $s$ ist.

}
{} {}

\inputaufgabe
{}
{

Bestimme den \definitionsverweis {Rang}{}{} der folgenden Ausdrücke. \aufzaehlungvier{ $a = fx$, }{ $\exists x a = fx$, }{${ \left( \neg Rxy \wedge ffx = c \right) } \rightarrow { \left( \exists x a = fx \right) }$, }{ ${ \left( \forall y Rxy \right) } \rightarrow { \left( \exists x a = fx \right) }$. }

}
{} {}

\inputaufgabe
{}
{

Zeige durch Induktion über den Aufbau der Ausdrücke, dass sich bei einer \definitionsverweis {Termsubstitution}{}{} der \definitionsverweis {Rang}{}{} eines Ausdrucks nicht ändert.

}
{} {}

\inputaufgabe
{}
{

Warum führt man im Beweis zum Satz von Henkin nicht Induktion über den Aufbau der Ausdrücke?

}
{} {}

\inputaufgabe
{}
{

Es sei $M$ ein \definitionsverweis {kommutativer Halbring}{}{.} Zeige, dass es eine eindeutig bestimmte \zusatzklammer {kanonische} {} {} Abbildung \maabbdisp {\varphi} {\N} {M } {} gibt, die sowohl die Addition als auch die Multiplikation respektiert.

}
{} {}

\inputaufgabe
{}
{

Es sei $M$ ein \definitionsverweis {Peano-Halbring}{}{} und \maabbdisp {\varphi} {\N} {M } {} die kanonische Abbildung. Zeige, dass $\varphi$ \definitionsverweis {injektiv}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{n\in \N_+}{} und betrachte
\mavergleichskette
{\vergleichskette
{M }
{ = }{ \Z/(n) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit den natürlichen Operationen. Welche der Peano-Axiome gelten, welche nicht?

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $M$ ein \definitionsverweis {kommutativer Halbring}{}{} und
\mathl{x,y \in M}{.} Es sei
\mavergleichskettedisp
{\vergleichskette
{I }
{ \defeq} { { \left\{ u \in M \mid \exists a \exists b \exists c \exists d \text{ mit } u+ ax+by= cx+dy \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} \aufzaehlungzwei {Zeige, dass $I$ die folgenden drei Eigenschaften erfüllt. \aufzaehlungdrei{
\mathl{0 \in I}{.} }{Wenn
\mathl{u,v \in I}{} sind, so ist auch
\mathl{u+v \in I}{.} }{Wenn
\mathl{u \in I}{} und
\mathl{r \in M}{} ist, so ist auch
\mathl{ru \in I}{.} } } {$M$ erfülle nun die Abziehregel. Zeige, dass aus
\mathl{u,v \in I}{} mit
\mavergleichskette
{\vergleichskette
{u }
{ = }{v+z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} auch
\mathl{z \in I}{} folgt. }

}
{} {}

Die folgende Aufgabe gibt eine Version des Lemmas von Bezout für Peano-Halbringe.


\inputaufgabe
{}
{

Es sei $M$ ein \definitionsverweis {Peano-Halbring}{}{} und
\mathl{x,y \in M}{.} Es sei
\mavergleichskettedisp
{\vergleichskette
{I }
{ \defeq} { { \left\{ u \in M \mid \exists a \exists b \exists c \exists d \text{ mit } u+ ax+by= cx+dy \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Zeige, dass es ein eindeutig bestimmtes $v \in M$ derart gibt, dass $I$ aus sämtlichen Vielfachen von $v$ besteht. Zeige, dass $v$ der größte gemeinsame Teiler von \mathkor {} {x} {und} {y} {} ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in einem \definitionsverweis {Peano-Halbring}{}{} $M$ die Begriffe \definitionsverweis {irreduzibel}{}{} und \definitionsverweis {prim}{}{} zusammenfallen.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in
\mavergleichskette
{\vergleichskette
{M }
{ \subseteq }{\Z[V] }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} aus Beispiel 13.9 durch
\mavergleichskette
{\vergleichskette
{x }
{ \geq }{y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} falls es ein
\mathl{z \in M}{} mit
\mavergleichskette
{\vergleichskette
{x }
{ = }{y+z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt, eine \definitionsverweis {totale Ordnung}{}{} gegeben ist.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{3}
{

Es sei $\Gamma$ eine Menge an $S$-\definitionsverweis {Ausdrücken}{}{} \zusatzklammer {über einem \definitionsverweis {Symbolalphabet}{}{} $S$} {} {,} die folgende Eigenschaften erfüllt. \aufzaehlungdrei{Für jeden Ausdruck $\alpha$ ist
\mathl{\alpha \in \Gamma}{} oder
\mathl{\neg \alpha \in \Gamma}{.} }{Aus
\mathl{\Gamma \vdash \alpha}{} folgt
\mathl{\alpha \in \Gamma}{,} d.h. $\Gamma$ ist abgeschlossen unter Ableitungen. }{$\Gamma$ ist widerspruchsfrei. } Zeige, dass $\Gamma$ maximal widerspruchsfrei ist.

}
{} {}

\inputaufgabe
{4}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache. Es seien
\mathl{s,t}{} verschiedene Terme. Zeige, dass es eine $S$-\definitionsverweis {Interpretation}{}{} $I$ mit
\mavergleichskettedisp
{\vergleichskette
{I(s) }
{ \neq} {I(t) }
{ } { }
{ } { }
{ } { }
} {}{}{} gibt.

}
{} {}

\inputaufgabe
{5}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^{\rm Ar} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Peano-Arithmetik, also die Menge aller aus den erststufigen Peano-Axiomen ableitbaren Ausdrücke. Zeige, dass jeder variablenfreie Term im Sinne von Konstruktion 14.7 äquivalent zu einem Term ist, bei dem das Multiplikationszeichen nicht mehr vorkommt.

}
{} {}

\inputaufgabe
{8 (1+3+1+3)}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge. Zu fixiertem
\mathl{n \in \N_+}{} sei
\mathl{R_n}{} die Menge der $n$-stelligen Relationssymbole in $S$. Zeige die folgenden Aussagen. \aufzaehlungvier{Durch
\mathdisp {P \cong Q \, , \text{ falls } I(P) = I(Q) \text{ für alle Interpretationen } I \text{ mit } I \vDash \Gamma} { }
wird eine \definitionsverweis {Äquivalenzrelation}{}{} auf $R_n$ definiert. }{Durch
\mathdisp {P \simeq Q \, , \text{ falls } \Gamma \vdash \forall x_1 \forall x_2 \ldots \forall x_n { \left( P x_1 \ldots x_n \leftrightarrow Q x_1 \ldots x_n \right) }} { }
wird eine Äquivalenzrelation auf $R_n$ definiert. }{Die Äquivalenzrelation $\simeq$ impliziert die Äquivalenzrelation $\cong$. }{Es sei $\sim$ die zu $\Gamma$ gehörende Äquivalenzrelation auf der Termmenge im Sinne von Konstruktion 14.7. Dann gilt für Terme mit
\mathl{s_1 \sim t_1 , \ldots , s_n \sim t_n}{} und Relationsssymbole
\mathl{P,Q \in R_n}{} mit
\mathl{P \simeq Q}{} die Beziehung
\mathdisp {\Gamma \vdash Ps_1 \ldots s_n \leftrightarrow Qt_1 \ldots t_n} { . }
}

}
{} {}

\inputaufgabe
{2}
{

Bestimme den \definitionsverweis {Rang}{}{} der folgenden Ausdrücke. \aufzaehlungvier{ $gxy = c$, }{ $\forall x gcx = gxx$, }{${ \left( \neg Pz \vee ggxyy = gcc \right) } \rightarrow { \left( \exists x Px \right) }$, }{ ${ \left( \forall y Py \right) } \rightarrow { \left( \neg \exists x gcx = gcgcx \wedge c = c \right) }$. }

}
{} {}