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

\setcounter{section}{8}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Zeige, dass die folgenden \definitionsverweis {prädikatenlogischen Ausdrücke}{}{} \definitionsverweis {allgemeingültig}{}{} sind. \aufzaehlungdrei{
\mathdisp {\forall x \forall y \forall z ((x=y \wedge y=z) \rightarrow x=z)} { . }
}{
\mathdisp {(\forall x \alpha) \rightarrow \alpha} { }
(wobei $\alpha$ ein Ausdruck ist). }{
\mathdisp {\alpha_1 \wedge \alpha_2 \wedge \alpha_3 \rightarrow \beta} { , }
wobei
\mathl{\alpha_1,\alpha_2,\alpha_3}{} die Gruppenaxiome sind und
\mathdisp {\beta \defeq \forall z ( \forall x ( zx=x \wedge xz =x) \rightarrow z =e )} { }
ist. }

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {erststufiges Symbolalphabet}{}{} und
\mathl{f \in S}{} ein $n$-stelliges Funktionssymbol. Zeige, dass der Ausdruck
\mathdisp {\exists y { \left( { \left( fx_1 { \ldots } x_n = y \right) } \wedge \forall z { \left( { \left( fx_1 { \ldots } x_n = z \right) } \rightarrow y = z \right) } \right) }} { }
\definitionsverweis {allgemeingültig}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {erststufiges Symbolalphabet}{}{} und
\mathl{f \in S}{} ein $2$-stelliges Funktionssymbol. Zeige, dass der Ausdruck
\mathdisp {(\forall x \forall y \forall z (ffxyz=fxfyz )) \rightarrow (\forall x \forall y \forall z \forall w (fffxyzw=fxfyfzw ))} { }
\definitionsverweis {allgemeingültig}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es seien
\mathl{p_1 , \ldots , p_n}{} \definitionsverweis {Aussagenvariablen}{}{} und
\mathl{\beta_1 , \ldots , \beta_n}{} \definitionsverweis {prädikatenlogische Ausdrücke}{}{.} Zeige, dass man, wenn man in einer \definitionsverweis {allgemeingültigen}{}{} \definitionsverweis {aussagenlogischen Aussage}{}{} $\alpha$, in dem keine weiteren Aussagenvariablen vorkommen, jedes Vorkommen von $p_i$ durch $\beta_i$ ersetzt, einen \definitionsverweis {allgemeingültigen}{}{} prädikatenlogischen Ausdruck erhält.

}
{} {}

\inputaufgabe
{}
{

Formuliere ein Axiomensystem für das Konzept \definitionsverweis {Äquivalenzrelation}{}{} in einer \definitionsverweis {prädikatenlogischen Sprache erster Stufe}{}{.}

}
{} {}

\inputaufgabe
{}
{

Axiomatisiere den Körperbegriff in einer geeigneten Sprache erster Stufe.

Eine Menge $K$ heißt ein \definitionswort {Körper}{,} wenn es zwei \definitionsverweis {Verknüpfungen}{}{} \zusatzklammer {genannt Addition und Multiplikation} {} {}
\mathdisp {+: K \times K \longrightarrow K \text{ und } \cdot: K \times K \longrightarrow K} { }
und zwei verschiedene Elemente
\mavergleichskette
{\vergleichskette
{0,1 }
{ \in }{K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt, die die folgenden Eigenschaften erfüllen. \aufzaehlungdrei{Axiome der Addition \aufzaehlungvier{Assoziativgesetz: Für alle
\mavergleichskette
{\vergleichskette
{ a,b,c }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt:
\mavergleichskette
{\vergleichskette
{ (a + b) + c }
{ = }{ a + (b + c) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{Kommutativgesetz: Für alle
\mavergleichskette
{\vergleichskette
{a,b }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt
\mavergleichskette
{\vergleichskette
{a+b }
{ = }{b+a }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{$0$ ist das neutrale Element der Addition, d.h. für alle
\mavergleichskette
{\vergleichskette
{a }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist
\mavergleichskette
{\vergleichskette
{a+0 }
{ = }{a }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{Existenz des Negativen: Zu jedem
\mavergleichskette
{\vergleichskette
{a }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt es ein Element
\mavergleichskette
{\vergleichskette
{b }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit
\mavergleichskette
{\vergleichskette
{a+b }
{ = }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} } }{Axiome der Multiplikation \aufzaehlungvier{Assoziativgesetz: Für alle
\mavergleichskette
{\vergleichskette
{ a,b,c }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt:
\mavergleichskette
{\vergleichskette
{ (a \cdot b) \cdot c }
{ = }{ a \cdot (b \cdot c) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{Kommutativgesetz: Für alle
\mavergleichskette
{\vergleichskette
{ a,b }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt
\mavergleichskette
{\vergleichskette
{ a \cdot b }
{ = }{b \cdot a }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{$1$ ist das neutrale Element der Multiplikation, d.h. für alle
\mavergleichskette
{\vergleichskette
{ a }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist
\mavergleichskette
{\vergleichskette
{ a \cdot 1 }
{ = }{ a }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{Existenz des Inversen: Zu jedem
\mavergleichskette
{\vergleichskette
{ a }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit
\mavergleichskette
{\vergleichskette
{a }
{ \neq }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt es ein Element
\mavergleichskette
{\vergleichskette
{ c }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit
\mavergleichskette
{\vergleichskette
{a \cdot c }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} } }{Distributivgesetz: Für alle
\mavergleichskette
{\vergleichskette
{ a,b,c }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt
\mavergleichskette
{\vergleichskette
{a \cdot (b+c) }
{ = }{ (a \cdot b) + (a \cdot c) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }

}
{} {}

\inputaufgabe
{}
{

Axiomatisiere den Begriff eines angeordneten Körpers in einer geeigneten Sprache erster Stufe.

Ein \definitionsverweis {Körper}{}{} $K$ heißt \definitionswort {angeordnet}{,} wenn es eine \definitionsverweis {totale Ordnung}{}{} $\geq$ auf $K$ gibt, die die beiden Eigenschaften \aufzaehlungzwei {Aus
\mavergleichskette
{\vergleichskette
{ a }
{ \geq }{ b }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} folgt
\mavergleichskette
{\vergleichskette
{ a + c }
{ \geq }{ b + c }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \zusatzklammer {für beliebige
\mavergleichskettek
{\vergleichskettek
{ a , b , c }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}} {} {,} } {Aus
\mavergleichskette
{\vergleichskette
{ a }
{ \geq }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{ b }
{ \geq }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} folgt
\mavergleichskette
{\vergleichskette
{ a b }
{ \geq }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \zusatzklammer {für beliebige
\mavergleichskettek
{\vergleichskettek
{ a, b }
{ \in }{ K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}} {} {,} } erfüllt.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{S=\{ 0,1,+,\cdot,\geq\}}{} die Symbolmenge für einen \definitionsverweis {angeordneten Körper}{}{.} Zeige
\mathdisp {\R \vDash \forall x \forall y { \left( x \geq y \leftrightarrow \exists z { \left( x-y = z^2 \right) } \right) }} { }
und
\mathdisp {\Q \vDash \neg { \left( \forall x \forall y { \left( x \geq y \leftrightarrow \exists z \zusatzklammer {x-y = z^2} {} {} \right) } \right) }} { . }

}
{} {} Über den reellen Zahlen kann man also das Symbol
\mathl{\geq}{} mit anderen Symbolen ausdrücken.

\inputaufgabegibtloesung
{}
{

In einem \definitionsverweis {angeordneten Körper}{}{} ist durch
\mavergleichskettedisp
{\vergleichskette
{ \betrag { x } }
{ \geq} { \betrag { y } }
{ } { }
{ } { }
{ } { }
} {}{}{} eine zweistellige \definitionsverweis {Relation}{}{} gegeben. Drücke diese Relation mit den üblichen Symbolen
\mathl{0, -,\geq}{,} Variablen und aussagenlogischen Junktoren aus.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{S }
{ = }{ \{ 0,1,+,\cdot,\geq\} \cup V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die \definitionsverweis {Symbolmenge}{}{} für einen \definitionsverweis {angeordneten Körper}{}{} und $f$ ein einstelliges Funktionssymbol. Formuliere über
\mavergleichskette
{\vergleichskette
{S' }
{ = }{S \cup \{f\} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} folgende Eigenschaften. \aufzaehlungdrei{Die \definitionsverweis {Stetigkeit}{}{} von $f$. }{Die \definitionsverweis {gleichmäßige Stetigkeit}{}{} von $f$. }{Die \definitionsverweis {Differenzierbarkeit}{}{} von $f$. }

}
{Gesucht ist also ein Ausdruck $\alpha$ aus
\mathl{L^{S'}}{} mit der Eigenschaft, dass $\alpha$ in einer Interpretation von $S'$ \zusatzklammer {gegeben durch einen angeordneten Körper $K$ und eine Funktion \maabb {f} {K} {K } {}} {} {} genau dann gilt, wenn $f$ stetig ist.} {}

\inputaufgabe
{}
{

Zeige, dass die \definitionsverweis {Polynomfunktionen in einer Variablen}{}{} über einem \definitionsverweis {angeordneten Körper}{}{} \definitionsverweis {stetig}{}{} sind. Formuliere diese Aussage über dem \definitionsverweis {Symbolalphabet}{}{}
\mathl{S=\{0,1,+,\cdot, \geq\}}{} für Polynome eines festes Grades.

}
{} {}

\inputaufgabe
{}
{

Sei
\mavergleichskette
{\vergleichskette
{S }
{ = }{ \{ 0,1,+,\cdot,\geq\} \cup V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die \definitionsverweis {Symbolmenge}{}{} für einen \definitionsverweis {angeordneten Körper}{}{} und $f$ ein einstelliges Funktionssymbol. Formuliere über
\mathl{S'=S \cup \{f\}}{} die Aussage des Zwischenwertsatzes.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{S }
{ = }{ \{ 0,1,+,\cdot,\geq\} \cup V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die \definitionsverweis {Symbolmenge}{}{} für einen \definitionsverweis {angeordneten Körper}{}{.} Formuliere über $S$ die Aussage des Zwischenwertsatzes für Polynome vom Grad $d$.

}
{} {}

In welchem Zusammenhang stehen die beiden vorstehenden Formulierungen?

\inputaufgabe
{}
{

Es seien
\mathl{\alpha_1, \alpha_2,\alpha_3}{} die \definitionsverweis {Gruppenaxiome}{}{} und
\mavergleichskettedisp
{\vergleichskette
{ \alpha }
{ \defeq} {\forall x ( \forall y ( \forall z ( \mu yx = e \wedge \mu x y = e \wedge \mu zx = e \wedge \mu x z = e \rightarrow y = z ))) }
{ } { }
{ } { }
{ } { }
} {}{}{,} also die Aussage, dass das inverse Element eindeutig bestimmt ist. Zeige, dass $\alpha$ aus keiner echten Teilmenge
\mathl{\Gamma \subset \{ \alpha_1, \alpha_2,\alpha_3 \}}{} folgt.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass der \definitionsverweis {prädikatenlogische Ausdruck}{}{}
\mathdisp {\exists x(\forall y(x=y) )} { }
\definitionsverweis {erfüllbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $\Gamma$ eine Ausdrucksmenge und $\alpha$ ein Ausdruck in einer Sprache erster Stufe. Zeige, dass
\mathl{\Gamma \vDash \alpha}{} genau dann gilt, wenn
\mathl{\Gamma \cup \{ \neg \alpha\}}{} nicht \definitionsverweis {erfüllbar}{}{} ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Formuliere die \definitionsverweis {Injektivität}{}{} für eine Abbildung \maabbdisp {f} {D} {Z } {} prädikatenlogisch mit Hilfe der Verwendung von Sorten.

}
{} {}

\inputaufgabe
{}
{

Formalisiere mit dem Symbolalphabet
\mathl{S=\{f,g\} \cup V}{,} wobei
\mathl{f,g}{} einstellige Funktionssymbole sind, die Aussage, dass die \definitionsverweis {Hintereinanderschaltung}{}{} von \definitionsverweis {injektiven Abbildungen}{}{} zwischen Mengen wieder injektiv ist.

}
{} {}

Häufig sind in mathematische Strukturen gewisse Teilmengen wichtig, die Bezug auf die umgebende Struktur nehmen. Eine solche Teilmenge wird prädikatenlogisch durch eine einstellige Relation mit zusätzlichen Eigenschaften wiedergegeben.


\inputaufgabegibtloesung
{}
{

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet $S$, dass ein \definitionsverweis {Untervektorraum}{}{} in einem \definitionsverweis {Vektorraum}{}{} über einem \definitionsverweis {Körper}{}{} vorliegt.

}
{} {}

\inputaufgabe
{}
{

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet $S$ den Sachverhalt, dass der Durchschnitt von zwei \definitionsverweis {Untervektorräumen}{}{} in einem \definitionsverweis {Vektorraum}{}{} über einem \definitionsverweis {Körper}{}{} wieder ein Untervektorraum ist.

}
{} {}

\inputaufgabe
{}
{

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet $S$, dass ein \definitionsverweis {Ideal}{}{} in einem \definitionsverweis {kommutativen Ring}{}{} vorliegt.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{2}
{

Formalisiere in der \definitionsverweis {prädikatenlogischen Sprache}{}{,} dass die \definitionsverweis {Hintereinanderschaltung}{}{} von \definitionsverweis {surjektiven Abbildungen}{}{} zwischen Mengen wieder surjektiv ist.

}
{} {}

\inputaufgabe
{2}
{

Welche der folgenden \definitionsverweis {prädikatenlogischen Ausdrücke}{}{} sind \definitionsverweis {allgemeingültig}{}{} \zusatzklammer {$x,y$ seien Variablen} {} {?} \aufzaehlungvier{
\mathl{\forall x (\exists y (x=y))}{,} }{
\mathl{\forall x (\forall y (x=y) )}{,} }{
\mathl{\exists x (\forall y (x=y))}{,} }{
\mathl{\exists x (\exists y (x=y))}{.} }

}
{} {}

\inputaufgabe
{5 (2+2+1)}
{

Es seien
\mavergleichskette
{\vergleichskette
{ \alpha, \beta }
{ \in }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

a) Zeige, dass
\mathdisp {{ \left( \exists x { \left( \alpha \rightarrow \beta \right) } \right) } \rightarrow { \left( \exists x \alpha \rightarrow \exists x \beta \right) }} { }
nicht \definitionsverweis {allgemeingültig}{}{} ist.

b) Zeige, dass
\mathdisp {{ \left( \exists x \alpha \rightarrow \exists x \beta \right) } \rightarrow { \left( \exists x { \left( \alpha \rightarrow \beta \right) } \right) }} { }
allgemeingültig ist.

c) Zeige, dass
\mathdisp {{ \left( \exists x \alpha \rightarrow \exists x \beta \right) } \rightarrow { \left( \exists x { \left( \alpha \rightarrow \beta \right) } \right) }} { }
nicht allgemeingültig wäre, wenn man auch leere Grundmengen zulassen würde.

}
{} {}

\inputaufgabe
{3}
{

Es sei $f$ ein einstelliges Funktionssymbol. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent\zusatzfussnote {Zwei Ausdrücke \mathkor {} {\alpha} {und} {\beta} {} heißen äquivalent, wenn
\mathl{\alpha \leftrightarrow \beta}{} \definitionsverweis {allgemeingültig}{}{} ist} {.} {} sind. \aufzaehlungdrei{ $\forall x \exists y (fx=y)$, }{ $\forall x \exists x (fx=x)$, }{ $\exists x (fx=x)$. }

}
{} {}

\inputaufgabe
{5}
{

Es seien $u, x,y,z$ Variablen und
\mathl{f,g}{} einstellige Funktionssymbole. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent sind.

a) \aufzaehlungdrei{ $\forall x \forall y ( ( fx =fy \rightarrow x=y ) \wedge (gx =gy \rightarrow x=y))$, }{ $\forall x \forall y ( fx =fy \rightarrow x=y ) \wedge \forall x \forall y ( gx =gy \rightarrow x=y )$, }{ $\forall x \forall y \forall u \forall z ( ( fx =fy \rightarrow x=y ) \wedge (gu =gz \rightarrow u=z ))$. }

b) \aufzaehlungvier{ $\forall x \exists y (fy=x) \wedge\forall x \exists y (gy=x)$, }{ $\forall x \exists y { \left( fy = x \wedge gy = x \right) }$, }{ $\forall x \exists y \forall u \exists z ( fy =x \wedge gz = u )$, }{ $\forall x \forall u \exists y \exists z ( fy =x \wedge gz =u )$. }

}
{} {}

\inputaufgabe
{2}
{

Zeige, dass die Kommutativität der Addition aus den übrigen \definitionsverweis {Körperaxiomen}{}{} folgt.

}
{} {Tipp: Zeige zuerst, dass
\mathl{0x=0}{} ist.}

\inputaufgabe
{2}
{

Sei
\mavergleichskette
{\vergleichskette
{S }
{ = }{ \{ 0,1,+,\cdot,\geq\} \cup V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Symbolmenge für einen \definitionsverweis {angeordneten Körper}{}{} und $f,g$ zwei einstellige Funktionssymbole. Formuliere über
\mathl{S'=S \cup \{f,g\}}{} die Aussage, dass die Hintereinanderschaltung von zwei stetigen Funktionen wieder stetig ist.

}
{} {}

\inputaufgabe
{3}
{

Formuliere ein prädikatenlogisches Axiomensystem für einen \definitionsverweis {metrischen Raum}{}{} über einem \definitionsverweis {angeordneten Körper}{}{} mit Hilfe von Sortenprädikaten.

}
{} {}

\inputaufgabe
{3}
{

Es sei
\mathl{k \in \N}{} fixiert. Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet $S$ den Sachverhalt, dass $k$ Elemente eines \definitionsverweis {kommutativen Ringes}{}{} ein gegebenes \definitionsverweis {Ideal}{}{} erzeugen.

}
{} {}