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