Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei $A$ eine Menge mit ihrer \definitionsverweis {Potenzmenge}{}{} $\mathfrak {P} \, (A )$. Entwerfe ein Symbolalphabet mithilfe von Sortenprädikaten, mit dem man bei adäquater Interpretation folgendes erreichen kann. \aufzaehlungsechs{Man kann zwischen Elementen und Teilmengen von $A$ unterscheiden. }{Man kann die Zugehörigkeit eines Elementes zu einer Teilmenge ausdrücken. }{Man kann die leere Teilmenge benennen. }{Man kann die Disjunktheit von zwei Teilmengen ausdrücken. }{Man kann die Teilmengenbeziehung zwischen zwei Teilmengen ausdrücken. }{Man kann die Vereinigung und den Durchschnitt von zwei Teilmengen ausdrücken. } Entwerfe ferner ein Axiomensystem für das entwickelte Symbolalphabet, mit dem man \aufzaehlungsechs{die charakteristische Eigenschaft der leeren Teilmenge, }{die charakteristische Eigenschaft der Disjunktheit, }{die charakteristische Eigenschaft der Teilmengenbeziehung, }{das Extensionalitätsprinzip für Teilmengen, }{die charakteristische Eigenschaft des Durchschnitts, }{die charakteristische Eigenschaft der Vereinigung, } formulieren kann.
}
{} {}
\zwischenueberschrift{Aufgaben zum Abgeben}
\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
{2}
{
Formalisiere in der \definitionsverweis {prädikatenlogischen Sprache}{}{,} dass die \definitionsverweis {Hintereinanderschaltung}{}{} von \definitionsverweis {surjektiven Abbildungen}{}{} zwischen Mengen wieder surjektiv 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.
}
{} {}