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