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

Skizziere ein Inklusionsdiagramm für sämtliche Teilmengen einer dreielementigen Menge.

}
{} {}

\inputaufgabe
{}
{

Es sei $(I, \preccurlyeq)$ eine \definitionsverweis {total geordnete}{}{} Menge. Zeige durch Induktion, dass jede nichtleere endliche Teilmenge $T \subseteq I$ ein eindeutiges \definitionsverweis {Maximum}{}{} besitzt.

}
{} {}

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

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $M$ eine endliche Menge. Betrachte die \definitionsverweis {Relation}{}{} auf der \definitionsverweis {Potenzmenge}{}{}
\mathl{\mathfrak {P} \, (M )}{,} die durch
\mathdisp {S \preccurlyeq T, \text{ falls } { \# \left( S \right) } \leq { \# \left( T \right) }} { , }
gegeben ist. Handelt es sich dabei um eine \definitionsverweis {Ordnungsrelation}{}{?}

}
{} {}

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

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{(I, \preccurlyeq)}{} eine nichtleere \definitionsverweis {geordnete Menge}{}{} mit der Eigenschaften, dass alle \definitionsverweis {Ketten}{}{} in $I$ endlich seien. Beweise in dieser Situation direkt, dass es in $I$ \definitionsverweis {maximale Elemente}{}{} gibt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{G}{} eine unendliche Menge und
\mavergleichskette
{\vergleichskette
{M }
{ \subset }{ \mathfrak {P} \, (G ) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Menge, die aus sämtlichen endlichen Teilmengen von $G$ besteht. \aufzaehlungzwei {Ist $(M, \subseteq)$ \definitionsverweis {induktiv geordnet}{}{?} } {Besitzt $M$ \definitionsverweis {maximale Elemente}{}{?} }

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{G}{} eine Menge und
\mavergleichskette
{\vergleichskette
{M }
{ \subseteq }{ \mathfrak {P} \, (G ) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Teilmenge der Potenzmenge, die unter beliebigen Vereinigungen abgeschlossen ist. \aufzaehlungzwei {Zeige, dass $(M, \subseteq)$ \definitionsverweis {induktiv geordnet}{}{} ist. } {Zeige, dass $M$ ein \definitionsverweis {größtes Element}{}{} besitzt. }

}
{} {}

\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 der folgenden 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
{}
{

Zeige, dass es keine Abbildung \maabbdisp {\varphi} {\N} {\N } {} gibt, die die folgende Eigenschaft erfüllt: Es ist
\mavergleichskette
{\vergleichskette
{k }
{ \geq }{n }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} genau dann, wenn
\mavergleichskette
{\vergleichskette
{\varphi(k) }
{ \leq }{ \varphi(n) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

}
{} {}

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

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine \definitionsverweis {widerspruchsfreie}{}{} \definitionsverweis {aussagenlogische}{}{} Ausdrucksmenge, die unter Ableitungen abgeschlossen sei. Zeige, dass $\Gamma$ der Durchschnitt von \definitionsverweis {maximal widerspruchsfreien}{}{} Ausdrucksmengen ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $V$ eine beliebige \definitionsverweis {Aussagenvariablenmenge}{}{} und sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine \definitionsverweis {abzählbare}{}{} Ausdrucksmenge. Zeige, dass man in diesem Fall den Vollständigkeitssatz der Aussagenlogik ohne das Lemma von Zorn beweisen kann.

}
{} {}

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 konstruktiv eine Ableitung angeben. Dieses Verfahren zur Erzeugung eines Beweises für eine Tautologie wurde von Nick Gärtner implementiert, siehe http://formalproofmachine.appspot.com/.


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

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine endliche Menge an Aussagen. Skizziere ein Entscheidungsverfahren, mit dem man feststellen kann, ob $\Gamma$ \definitionsverweis {widersprüchlich}{}{} ist oder nicht.

}
{} {}

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

}
{} {}