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

\setcounter{section}{14}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

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

}
{} {}

\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? }

}
{} {}

\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.3 impliziert.

}
{} {}

\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 $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.

}
{} {}

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

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.

}
{} {}

\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
{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) }$. }

}
{} {}