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

\setcounter{section}{5}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Zeige mit Hilfe des Auswahlaxioms, dass es zu jeder \definitionsverweis {Äquivalenzrelation}{}{} $\sim$ auf einer Menge $M$ ein \definitionsverweis {Repräsentantensystem}{}{} für die \definitionsverweis {Äquivalenzklassen}{}{} gibt.

}
{} {}

\inputaufgabe
{}
{

Skizziere ein Teilerdiagramm für die Menge $M$ der echten natürlichen \definitionsverweis {Teiler}{}{} von $100$ \zusatzklammer {dabei gelte $1$ als echter Teiler, $100$ nicht} {} {.} Was sind die \definitionsverweis {maximalen}{}{,} die \definitionsverweis {minimalen}{}{} Elemente, gibt es ein \definitionsverweis {größtes}{}{} und ein \definitionsverweis {kleinstes}{}{} Element, was sind die \definitionsverweis {total geordneten}{}{} Teilmengen?

}
{} {}

\inputaufgabe
{}
{

Besitzt die Menge $\N$ der \definitionsverweis {natürlichen Zahlen}{}{} in $\R$ eine \definitionsverweis {obere Schranke}{}{?} Wie sieht das in anderen \definitionsverweis {angeordneten Körpern}{}{} aus?

}
{} {}

\inputaufgabe
{}
{

Es sei $M$ eine Menge und $I$ die Menge der echten Teilmengen von $M$, also
\mathdisp {I = { \left\{ T \subseteq M \mid T \neq \emptyset \text{ und } T \neq M \right\} }} { . }
Diese Menge ist durch die \definitionsverweis {Inklusion}{}{} eine \definitionsverweis {geordnete Menge}{}{.} Bestimme die \definitionsverweis {minimalen}{}{} und die \definitionsverweis {maximalen Elemente}{}{} von $I$.

}
{} {}

\inputaufgabe
{}
{

Es sei $A$ eine endliche \definitionsverweis {total geordnete}{}{} Menge. Es sei $I=\{1,2 , \ldots , n\}$ eine endliche Indexmenge. Definiere auf der \definitionsverweis {Produktmenge}{}{}
\mavergleichskettedisp
{\vergleichskette
{ A^I }
{ =} { \underbrace{A \times \cdots \times A}_{n\text{-mal} } }
{ } { }
{ } { }
{ } { }
} {}{}{} die \anfuehrung{lexikographische Ordnung}{,} und zeige, dass es sich dabei ebenfalls um eine totale Ordnung handelt.

}
{} {}

Die nächste Aufgabe verwendet die folgende Definition.

Es seien \mathkor {} {(M_1, \leq_1)} {und} {(M_2, \leq_2)} {} zwei Mengen, auf denen jeweils eine \definitionsverweis {Ordnung}{}{} definiert ist. Eine \definitionsverweis {Abbildung}{}{} \maabbeledisp {F} {M_1} {M_2 } {x} {F(x) } {,} heißt \definitionswort {ordnungstreu}{} \zusatzklammer {oder \definitionswort {monoton}{}} {} {,} wenn für alle
\mavergleichskette
{\vergleichskette
{x,x' }
{ \in }{M_1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit
\mavergleichskette
{\vergleichskette
{x }
{ \leq_1 }{x' }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} stets auch
\mavergleichskette
{\vergleichskette
{F(x) }
{ \leq_2 }{F(x') }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt.

\inputaufgabe
{}
{

Es sei $(M, \leq)$ eine \definitionsverweis {geordnete Menge}{}{} und $\mathfrak {P} \, (M )$ die \definitionsverweis {Potenzmenge}{}{} von $M$. Zeige, dass die Abbildung \maabbeledisp {} {M} {\mathfrak {P} \, (M ) } {x} {{ \left\{ y \in M \mid y \leq x \right\} } } {,} \definitionsverweis {ordnungstreu}{}{} und \definitionsverweis {injektiv}{}{} ist, wobei die Potenzmenge mit der \definitionsverweis {Inklusion}{}{} versehen ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in $\Z$ die \definitionsverweis {maximalen Ideale}{}{} genau die von \definitionsverweis {Primzahlen}{}{} $p$ \definitionsverweis {erzeugten}{}{} \definitionsverweis {Ideale}{}{}
\mathl{\Z p = { \left\{ kp \mid k \in \Z \right\} }}{} sind.

}
{} {}

\inputaufgabe
{}
{

Es sei $R$ ein \definitionsverweis {kommutativer Ring}{}{} und
\mavergleichskette
{\vergleichskette
{ I }
{ \subseteq }{ R }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ein \definitionsverweis {Ideal}{}{} in $R$. Zeige, dass $I$ genau dann ein \definitionsverweis {maximales Ideal}{}{} ist, wenn der \definitionsverweis {Restklassenring}{}{} $R/I$ ein \definitionsverweis {Körper}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $X$ ein \definitionsverweis {topologischer Raum}{}{} und $F$ ein \definitionsverweis {topologischer Filter}{}{} auf $X$ mit
\mathl{\emptyset \not\in F}{.} Zeige, dass es einen \definitionsverweis {Ultrafilter}{}{} $G \supseteq F$ gibt.

}
{} {}

Wenn man die natürlichen Zahlen $\N$ mit der \definitionsverweis {diskreten Topologie}{}{} versieht, so dass also jede Teilmenge offen ist, so ist ein topologischer Filter auf $\N$ einfach eine Teilmenge
\mathl{F \subseteq \mathfrak {P} \, (\N )}{} mit \aufzaehlungdrei{
\mathl{\N \in F}{.} }{Mit
\mathl{U \in F}{} und
\mathl{U \subseteq V}{} ist auch
\mathl{V \in F}{.} }{Mit
\mathl{U \in F}{} und
\mathl{V \in F}{} ist auch
\mathl{U \cap V \in F}{.} }

\inputaufgabe
{}
{

Ein \definitionsverweis {Filter}{}{}
\mathl{F \subseteq \mathfrak {P} \, (\N )}{} ist genau dann ein \definitionsverweis {Ultrafilter}{}{,} wenn für jede Teilmenge
\mathl{T \subseteq \N}{} entweder
\mathl{T \in F}{} oder
\mathl{\N \setminus T \in F}{} gilt

}
{} {}

Die einfachen Ultrafilter in $\N$ werden in folgender Aufgabe beschrieben.


\inputaufgabe
{}
{

Es sei
\mathl{n \in \N}{} eine fixierte Zahl. Dann ist
\mavergleichskettedisp
{\vergleichskette
{F }
{ =} { { \left\{ T \subseteq \N \mid n \in T \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{} ein \definitionsverweis {Ultrafilter}{}{.}

}
{} {}

\inputaufgabe
{}
{

Zeige, dass es in $\N$ \definitionsverweis {Ultrafilter}{}{} gibt, die keine endlichen Teilmengen enthalten.

}
{} {}

\inputaufgabe
{}
{

Wir betrachten den Folgenring
\mathl{R=\R^\N}{.} Zu einer Folge
\mathl{x= { \left( x_n \right) }_{n \in \N } \in R}{} sei
\mavergleichskettedisp
{\vergleichskette
{Z(x) }
{ =} { { \left\{ n \in \N \mid x_n = 0 \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Zeige, dass über die Zuordnungen
\mathdisp {I \longmapsto { \left\{ T \subseteq \N \mid T = Z(x) \text{ für ein } x \in I \right\} }} { }
und
\mathdisp {F \longmapsto { \left\{ x \in R \mid Z(x) \in F \right\} }} { }
sich die Ideale aus $R$ und die Filter aus $\N$ entsprechen.

}
{} {}

\inputaufgabe
{}
{

Wir betrachten die Menge
\mathdisp {{\mathcal G} = { \left\{ T \subseteq \N_+ \mid \sum_{n \in T} { \frac{ 1 }{ n } } \text{ ist eine divergente Reihe} \right\} }} { . }
Ist ${\mathcal G}$ ein \definitionsverweis {Filter}{}{?}

}
{} {}

\inputaufgabe
{}
{

Man mache sich an den folgenden Beispielen klar, dass der Satz von Hamel keineswegs selbstverständlich ist. \aufzaehlungdrei{Die reellen Zahlen $\R$ als $\Q$-Vektorraum betrachtet. }{Die Menge der reellen Folgen
\mavergleichskettedisp
{\vergleichskette
{\R^\N }
{ =} { { \left\{ { \left( x_n \right) }_{n \in \N } \mid x_n \in \R \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} }{Die Menge aller stetigen Funktionen von $\R$ nach $\R$. }

}
{} {}

\inputaufgabegibtloesung
{}
{

Betrachte die reellen Zahlen $\R$ als $\Q$-\definitionsverweis {Vektorraum}{}{.} Zeige, dass die Menge der reellen Zahlen $\ln p$, wobei $p$ durch die Menge der \definitionsverweis {Primzahlen}{}{} läuft, \definitionsverweis {linear unabhängig}{}{} ist. Tipp: Verwende, dass jede positive natürliche Zahl eine eindeutige Darstellung als Produkt von Primzahlen besitzt.

}
{} {}

\inputaufgabe
{}
{

Beweise durch Induktion, dass die natürliche Ordnung auf den natürlichen Zahlen $\N$ eine \definitionsverweis {Wohlordnung}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die natürliche Ordnung auf den ganzen Zahlen keine \definitionsverweis {Wohlordnung}{}{} ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige, dass die natürliche Ordnung auf den reellen Zahlen keine \definitionsverweis {Wohlordnung}{}{} ist.

}
{} {}

Die folgenden beiden Aussagen ergeben zusammen einen konstruktiven Beweis für den Vollständigkeitssatz der Aussagenlogik in der Version von Korollar 5.20, d.h. für eine semantische Tautologie $\alpha$ weiß man nicht nur die Existenz einer Ableitung
\mathl{\vdash \alpha}{,} sondern man kann prinzipiell eine Ableitung angeben.


\inputaufgabegibtloesung
{}
{

Es sei $\alpha$ eine aussagenlogische Aussage und es seien
\mathl{p_1 , \ldots , p_n}{} die darin vorkommenden Aussagenvariablen. Es sei
\mavergleichskettedisp
{\vergleichskette
{ \gamma }
{ =} { \pm p_1 \wedge \ldots \wedge \pm p_n }
{ } { }
{ } { }
{ } { }
} {}{}{} eine fixierte Konjunktion dieser \zusatzklammer {negierten} {} {} Aussagenvariablen. Zeige, dass dann
\mathdisp {\vdash \gamma \rightarrow \alpha \text{ oder } \vdash \gamma \rightarrow \neg \alpha} { }
gilt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Skizziere einen konstruktiven Beweis für die Tautologieversion der Vollständigkeit der Aussagenlogik.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{2}
{

Beweise das Lemma von Zorn für eine \definitionsverweis {total geordnete}{}{} Menge.

}
{} {}

\inputaufgabe
{3}
{

Wir betrachten die Menge
\mavergleichskettedisp
{\vergleichskette
{ {\mathcal F} }
{ =} {{ \left\{ T \subseteq \N_+ \mid \sum_{n \not\in T} { \frac{ 1 }{ n } } \text{ ist eine konvergente Reihe} \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Zeige, dass ${\mathcal F}$ ein \definitionsverweis {Filter}{}{} auf $\N_+$ ist.

}
{} {}

\inputaufgabe
{3}
{

Zeige, dass sich bei der in Aufgabe 5.13 beschriebenen Korrespondenz maximale Ideale und Ultrafilter entsprechen.

}
{} {}

\inputaufgabe
{3}
{

Definiere eine \definitionsverweis {Wohlordnung}{}{} auf der Menge der ganzen Zahlen $\Z$.

}
{} {}

\inputaufgabe
{5}
{

Es sei
\mathl{(M,\preccurlyeq)}{} eine \definitionsverweis {total geordnete Menge}{}{,} die sowohl nach unten als auch nach oben \definitionsverweis {wohlgeordnet}{}{} ist. Zeige, dass $M$ endlich ist.

}
{} {}

\inputaufgabe
{2}
{

Beweise den \stichwort {Endlichkeitssatz für die Aussagenlogik} {:} Wenn die Aussage $\alpha$ aus der Aussagenmenge
\mathl{\Gamma \subseteq L^V}{} \definitionsverweis {folgt}{}{,} dann gibt es eine endliche Teilmenge
\mathl{\Gamma_0 \subseteq \Gamma}{,} aus der diese Aussage folgt.

}
{} {}