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

Übungsaufgaben

Aufgabe

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

Aufgabe

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

Aufgabe

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

Aufgabe

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

Aufgabe

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

Aufgabe *

Es sei ${}M$ eine endliche Menge. Betrachte die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$, die durch

$S\preccurlyeq T,{\text{ falls }}{\#\left(S\right)}\leq {\#\left(T\right)},$

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?

Aufgabe

Es sei ${}M$ eine Menge und ${}I$ die Menge der echten Teilmengen von ${}M$, also

$I={\left\{T\subseteq M\mid T\neq \emptyset {\text{ und }}T\neq M\right\}}.$

Diese Menge ist durch die Inklusion eine geordnete Menge. Bestimme die minimalen und die maximalen Elemente von ${}I$.

Aufgabe

Es sei ${}A$ eine endliche total geordnete Menge. Es sei ${}I=\{1,2,\ldots ,n\}$ eine endliche Indexmenge. Definiere auf der Produktmenge

${}A^{I}=\underbrace {A\times \cdots \times A} _{n{\text{-mal}}}\,$

die „lexikographische Ordnung“, und zeige, dass es sich dabei ebenfalls um eine totale Ordnung handelt.

Aufgabe

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

Aufgabe *

Es sei ${}G$ eine unendliche Menge und ${}M\subset {\mathfrak {P}}\,(G)$ die Menge, die aus sämtlichen endlichen Teilmengen von ${}G$ besteht.

1. Ist ${}(M,\subseteq )$ induktiv geordnet?
2. Besitzt ${}M$ maximale Elemente?

Aufgabe *

Es sei ${}G$ eine Menge und ${}M\subseteq {\mathfrak {P}}\,(G)$ eine Teilmenge der Potenzmenge, die unter beliebigen Vereinigungen abgeschlossen ist.

1. Zeige, dass ${}(M,\subseteq )$ induktiv geordnet ist.
2. Zeige, dass ${}M$ ein größtes Element besitzt.

Aufgabe

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

Aufgabe

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

Aufgabe

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

Wenn man die natürlichen Zahlen ${}\mathbb {N}$ mit der diskreten Topologie versieht, so dass also jede Teilmenge offen ist, so ist ein topologischer Filter auf ${}\mathbb {N}$ einfach eine Teilmenge ${}F\subseteq {\mathfrak {P}}\,(\mathbb {N} )$ mit

1. ${}\mathbb {N} \in F$.
2. Mit ${}U\in F$ und ${}U\subseteq V$ ist auch ${}V\in F$.
3. Mit ${}U\in F$ und ${}V\in F$ ist auch ${}U\cap V\in F$.

Aufgabe

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

Die einfachen Ultrafilter in ${}\mathbb {N}$ werden in der folgenden Aufgabe beschrieben.

Aufgabe

Es sei ${}n\in \mathbb {N}$ eine fixierte Zahl. Dann ist

${}F={\left\{T\subseteq \mathbb {N} \mid n\in T\right\}}\,$

ein Ultrafilter.

Aufgabe

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

Aufgabe

Wir betrachten den Folgenring ${}R=\mathbb {R} ^{\mathbb {N} }$. Zu einer Folge ${}x={\left(x_{n}\right)}_{n\in \mathbb {N} }\in R$ sei

${}Z(x)={\left\{n\in \mathbb {N} \mid x_{n}=0\right\}}\,.$

Zeige, dass über die Zuordnungen

$I\longmapsto {\left\{T\subseteq \mathbb {N} \mid T=Z(x){\text{ für ein }}x\in I\right\}}$

und

$F\longmapsto {\left\{x\in R\mid Z(x)\in F\right\}}$

sich die Ideale aus ${}R$ und die Filter aus ${}\mathbb {N}$ entsprechen.

Aufgabe

Wir betrachten die Menge

${\mathcal {G}}={\left\{T\subseteq \mathbb {N} _{+}\mid \sum _{n\in T}{\frac {1}{n}}{\text{ ist eine divergente Reihe}}\right\}}.$

Ist ${}{\mathcal {G}}$ ein Filter?

Aufgabe

Man mache sich an den folgenden Beispielen klar, dass der Satz von Hamel keineswegs selbstverständlich ist.

1. Die reellen Zahlen ${}\mathbb {R}$ als ${}\mathbb {Q}$-Vektorraum betrachtet.
2. Die Menge der reellen Folgen

   ${}\mathbb {R} ^{\mathbb {N} }={\left\{{\left(x_{n}\right)}_{n\in \mathbb {N} }\mid x_{n}\in \mathbb {R} \right\}}\,.$

3. Die Menge aller stetigen Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$.

Aufgabe *

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

Aufgabe

Zeige, dass es keine Abbildung

$\varphi \colon \mathbb {N} \longrightarrow \mathbb {N}$

gibt, die die folgende Eigenschaft erfüllt: Es ist ${}k\geq n$ genau dann, wenn ${}\varphi (k)\leq \varphi (n)$.

Aufgabe

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

Aufgabe

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

Aufgabe *

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

Aufgabe

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

Aufgabe

Es sei ${}V$ eine beliebige Aussagenvariablenmenge und sei ${}\Gamma \subseteq L^{V}$ eine 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 ${}\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/.

Aufgabe *

Es sei ${}\alpha$ eine aussagenlogische Aussage und es seien ${}p_{1},\ldots ,p_{n}$ die darin vorkommenden Aussagenvariablen. Es sei

${}\gamma =\pm p_{1}\wedge \ldots \wedge \pm p_{n}\,$

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Zeige, dass dann

$\vdash \gamma \rightarrow \alpha \,\,{\text{ oder }}\,\,\vdash \gamma \rightarrow \neg \alpha$

gilt.

Aufgabe *

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

Aufgabe *

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

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Beweise das Lemma von Zorn für eine total geordnete Menge.

Aufgabe (3 Punkte)

Wir betrachten die Menge

${}{\mathcal {F}}={\left\{T\subseteq \mathbb {N} _{+}\mid \sum _{n\not \in T}{\frac {1}{n}}{\text{ ist eine konvergente Reihe}}\right\}}\,.$

Zeige, dass ${}{\mathcal {F}}$ ein Filter auf ${}\mathbb {N} _{+}$ ist.

Aufgabe (3 Punkte)

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

Aufgabe (3 Punkte)

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

Aufgabe (5 Punkte)

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

Aufgabe (2 Punkte)

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