Mengenlehre Flashcards
Einführung in die Mengenlehre.
Welche vier Postulate sind die zentralen Annahmen der naiven Mengenlehre?
(1) Eine Menge besteht aus beliebigen unterscheidbaren Elementen.
(2) Eine Menge ist unverwechselbar durch ihre Elemente bestimmt.
(3) Eine Menge ist nicht Element ihrer selbst.
(4) Jede Aussage A über Elemente einer Menge X definiert die Menge der Elemente in X , für die die Aussage A wahr ist: {x ∈ X | A gilt für x}.
Wie definiert sich die symmetrische Differenz zweier Mengen P Δ Q? Was wäre das Pendant in der Aussagenlogik?
P Δ Q = (P ∪ Q) \ (P ∩ Q)
= {x | x∈ P XOR x ∈ Q} (exklusives Oder)
Sei A eine Familie von Mengen. Wie sind Vereinigung und Durchschnitt der Mengen X in A definiert?
∪(X ∈ A) X = {x | ∃X ∈ A: x ∈ X}
∩(X ∈ A) X = {x | ∀X ∈ A: x ∈ X}
Wann sind zwei Mengen X₁ und X₂ in einer Kollektion A paarweise disjunkt?
Für alle X₁, X₂ ∈ A mit X₁ ≠ X₂: X₁ ∩ X₂ = ∅.
Was ist eine Potenzmenge 𝒫(X) und was ist 𝒫(∅)?
𝒫(X) ist die Menge aller Teilmengen von X. Also für X = {0, 1} wäre 𝒫(X) = {{0, 1}, {1, 1}, {1, 0}, {0, 0}}.
𝒫(∅) ist wiederum ∅.
Was ist eine Indexmenge? Gib ein Beispiel.
Die Menge, deren Elemente zur Nummerierung der eigentlichen Elemente dient.
Als Beispiel die Menge aller xₙ für n ∈ ℕ, also x₁, x₂, …, xₙ, so ist ℕ die Indexmenge.
Was ist das kartesische Produkt zweier Mengen X × Y?
Die Menge aller geordneten Paare (x, y), wobei x ∈ X und y ∈ Y, also:
X × Y = {(x, y) | x ∈ X und y ∈ Y}
Wie lautet das Regularitätsaxiom (auch: Fundierungsaxiom) und wie kann man daraus folgern, dass eine Menge X nicht Element von X, also sich selbst, ist?
X ≠ ∅ ⇒ (∃y ∈ X: (y ∩ X = ∅)).
Es besagt, dass es ein ∈-minimales Element y gibt, so dass wenn y selbst als Menge betrachtet wird, X und y disjunkte Mengen sind. Sei nun X = {y}, so wäre y ∩ X = X ∩ X = ∅. Deshalb kann X nicht Teil von sich selbst sein.
Was ist eine Funktion von X nach Y?
(Auf welche zwei Arten kann man Funktionen behandeln?)
Wie bezeichnet man X und Y?
Eine Funktion f: X → Y ist eine Teilmenge F des kartesischen Produkts X × Y mit der Eigenschaft, dass es für jedes x ∈ X genau ein y ∈ Y mit (x, y) ∈ F gibt:
∀x ∈ X ∃!y ∈ Y : (x, y) ∈ F.
Alternativ: Eine Funktion ist eine Zuordnung y = f(x) und somit: F = {(x, f(x)) | x ∈ X}.
Die Menge X ist der Definitionsbereich und Y der Wertebereich einer Funktion.
Was sind Graph, Argument und Wert einer Funktion?
Graph ist die Menge F = {(x, f(x)) | x ∈ X}.
Ein Element x des Definitionsbereichs X ist das Argument und ein Element y des Wertebereichs Y wird als Wert bezeichnet.
Was ist eine Inklusionsabbildung? Wann wird die Inklusionsabbildung zur Identität?
Eine Inklusionsabbildung ist die Einbettung einer Teilmenge in die höhere Menge. i: A → X, i(a) = a.
Falls die Inklusionsabbildung i: X → X vorliegt, heisst sie Identität (von X).
Was ist eine Einschränkung von einer Funktion f: X → Y auf eine Menge A und was gilt für die Elemente a von A?
Die Verknüpfung der Funktion f mit der Inklusion i: A → X heisst Einschränkung f | A. Da die Funktion f “gleich bleibt” und durch die Inklusion nur der Definitionsbereich auf A eingeschränkt ist (solange gilt: A ≠ X), gilt für die Elemente a auch f | A (a) = f (a) für alle a ∈ A.
Was ist eine injektive Funktion?
Eine Injektion liegt vor, wenn f(x₁) = f(x₂) ⇒ x₁ = x₂ für alle x₁, x₂ ∈ X gilt.
(Für zwei gleiche y-Werte müssen die x-Werte ebenfalls gleich sein, f(x) = x^2 ist zum Beispiel nicht injektiv.)
Was ist eine surjektive Funktion?
Eine Surjektion liegt vor, wenn für jedes y ∈ Y ein x ∈ X mit f(x) = y existiert.
(Die Funktion f(x) = x^2 ist nicht surjektiv, da (sofern f nicht nur auf ℕ und nicht auf ℂ definiert ist) für f(x) = -1 kein x vorliegt).
Was ist eine bijektive Funktion?
Eine Bijektion liegt vor, wenn eine Funktion sowohl injektiv als auch bijektiv ist, d.h. wenn es für jedes x genau ein eindeutiges y gibt und jedes y genau einem x zugewiesen werden kann.
Wie steht eine Bijektion im Zusammenhang mit der Umkehrfunktion?
Eine Funktion f: X → Y ist nur bijektiv, wenn eine Umkehrfunktion g: Y → X existiert, so dass f ∘ g = id(x) und g ∘ f = id(y).
Anmerkung: f ∘ g ist id(x), da die Elemente von X zuerst auf gewisse Elemente von Y abgebildet werden und dann wieder zurück nach X (es kann also auch mehr Elemente in Y als in X haben, die Elemente x₁, x₂, usw. landen aber auf jeden Fall wieder bei x₁, x₂, usw. . Genau gleich verhält es sich mit g ∘ f = id(y).
Welche fünf Aussagen kann man für die Komposition zweier Funktionen f: X → Y und g: Y → X machen?
(1) Falls f und g injektiv sind, so ist auch g ∘ f injektiv.
(2) Falls g ∘ f injektiv ist, dann ist auch f injektiv.
(3) Falls f und g surjektiv sind, dann ist auch g ∘ f surjektiv.
(4) Falls g ∘ f surjektiv ist, dann ist auch g surjektiv.
(5) Falls f und g bijektiv sind, dann ist auch g ∘ f bijektiv.
(Für Beweise, s. Skript S. 24)
Was sind Bild und Urbild unter bezüglich einer Funktion?
Für eine Funktion f: X → Y und Teilmengen A ⊂ X und B ⊂ Y nennen wir:
f(A) = {y ∈ Y | ∃x ∈ A: f(x) = y} das Bild von A unter bezüglich der Funktion f, und
f^-1(B) = {x ∈ X | ∃y ∈ B: f(x) = y} das Urbild von B unter bezüglich der Funktion f.
Was ist eine Relation?
Welche vier Eigenschaften kann eine Relation annehmen?
Wann ist die Relation eine Äquivalenz-, wann eine Ordnungsrelation?
Eine Relation auf X ist eine Teilmenge ℛ ⊂ X × X. Falls (x, y) ∈ ℛ, kann man auch xℛy schreiben.
Eine Relation ∼ heisst:
(1) Reflexiv, falls ∀x ∈ X : x ∼ x.
(2) Transitiv, falls ∀x, y, z ∈ X : ((x ∼ y) ⋀ (y ∼ z)) ⇒ x ∼ z.
(3) Symmetrisch, falls ∀x, y ∈ X: x ∼ y ⇒ y ∼ x.
(4) Antisymm., falls ∀x, y ∈ X: ((x ∼ y) ⋀ (y ∼ x)) ⇒ x = y.
Äquivalenzrelation, falls reflexiv, transitiv und symmetrisch.
Ordnungsrelation, falls reflexiv, transitiv und antisymmetrisch.
Was sind Äquivalenzklassen und Quotientenmengen und wie stehen sie im Verhältnis zueinander?
Sei ∼ eine Äquivalenzrelation auf einer Menge X, dann wird für x ∈ X die Menge [x]~ = {y ∈ X | y ∼ x} als Äquivalenzklasse von x genannt. Die Menge aller Äquivalenzklassen X/∼ = {[x]~ | x ∈ X} nennt man Quotientenmenge von X modulo ∼.
Was ist eine Partition von einer Menge X?
Eine Partition von X ist eine Familie 𝒫 von nicht leeren, paarweise disjunkten Teilmengen von X, so dass gilt:
X = Vereinigung aller P ∈ 𝒫. Die Mengen P sind also nicht leer, und jedes Element von X ist Element von genau einem P ∈ 𝒫.
Wie stehen Äquivalenzrelationen auf X und Partitionen von X zueinander im Verhältnis?
Für eine gegebene ÄR ∼ auf X ist die Menge 𝒫 = {[x]~ | x ∈ X} eine Partition von X. Umgekehrt:
x ∼ y ⇔ ∃P ∈ 𝒫: x ∈ P ⋀ y ∈ P.
Folglich sind Konstruktion einer ÄR aus einer Partition und die Konstruktion einer Partition aus einer ÄR zu einander invers.
Wann ist eine Funktion f: X → Y wohldefiniert?
Was ist ein Beispiel für eine nicht wohldefinierte Funktion?
Wenn die Funktion f jedem Element x des Definitionsbereichs X das eindeutig bestimmte Element y des Wertebereichs Y zuordnen kann, das “Aufgehen” der Funktion also nicht von den Repräsentanten abhängig ist.
Als Bsp. ist f(x) = √x für Definitions- und Wertebereich ℝ
nicht wohldefiniert, da für alle x ∈ ℝ < 0 keine Wurzeln definiert sind, also hängt die Gültigkeit der Funktion von den Repräsentanten ab.
Wann sind zwei Mengen X und Y gleichmächtig?
Falls es eine Bijektion von X nach Y gibt, bzw. beide Mengen die selbe Anzahl an Elementen haben.
Was besagt Cantors Erstes Diagonalargument? Wie lässt sich das veranschaulichen?
Tipp: Warum sind ℕ und ℚ gleichmächtig.
Zwei unendlich abzählbare Mengen sind gleichmächtig.
Man kann z.B. die Menge ℚ als Tabelle schreiben, in der links oben 1/1 steht und auf der Waagerechten dann immer der Nenner um 1 erhöht wird, also 1/2, 1/3, 1/n, und auf der Vertikalen der Zähler um eins erhöht wird, also 2/1, 3/1, 4/1. Man kürzt nun die Diagonalen mit kürzbaren Brüchen weg und lässt nur eine “Version” stehen (1/1, 2/2, 3/3, n/n sind alle gleich). Somit erhält man eine abzählbare Menge an Brüchen, zu denen je ein Element aus ℕ zugewiesen werden kann. Diese Funktion f: ℚ → ℕ ist bijektiv. Somit sind die Mengen gleichmächtig.
Was sind die zwei wichtigsten Punkte in Cantors Zweitem Diagonalargument?
- Die Menge der reellen Zahlen ist überabzählbar (man kann für einen Intervall zwischen zwei reellen Zahlen stets einen Intervall finden, der kleiner ist).
- Die Potenzmenge 𝒫(X) ist mächtiger als die Menge X und nicht gleichmächtig zu X (Bew. s. Skript S. 33).
Was ist die Hauptaussage des Satzes von Cantor-Schröder-Bernstein?
Seien X und Y Mengen, so dass X ≲ Y und Y ≲ X. Dann gilt X ∼ Y, oder in Worten: Ist eine erste Menge X gleichmächtig zu einer Teilmenge der zweiten Menge Y und ist diese Menge Y gleichmächtig zu einer Teilmenge der ersten Menge X, so sind beide Mengen gleichmächtig.
(Bew. s. Skript S. 34)
Auswahlaxiom (Variante 1): Was ist ein Schnitt einer Funktion f und wie steht es im Zusammenhang zum Auswahlaxiom?
Für eine surjektive Funktion f: X → Y existiert eine Funktion g: Y → X, genannt “Schnitt von f”, sodass f ∘ g = id(y).
Die Aussage, dass so eine Funktion existiert, ist äquivalent zur Aussage, dass eine Auswahlfunktion existiert (wie in Var. 2 des Axioms behauptet). Die Verknüpfung dieser beiden Funktionen wählt Elemente von X aus und bildet sie wieder nach X ab.
Auswahlaxiom (Variante 2): Was ist eine Auswahlfunktion?
Eine Auswahlfunktion α: 𝒳 → Y bildet Elemente von einer Familie 𝒳 nicht leerer Teilmengen X von einer Menge Y wieder auf diese Menge Y ab, sodass α(X) ∈ X für alle X ∈ 𝒳.
Es gibt also Teilmengen X in der Menge Y, die zu einer Familie 𝒳 gehören. Die Auswahlfunktion α wählt nun aus jeder Teilmenge X ein Element aus und schickt dieses nach Y, d.h. die Funktion macht nichts anderes als aus jeder Teilmenge ein Element auswählen.
So kann z.B. für Y = {X₁, X₂, X₃, Y₁, Y₂} die Funktion aus den Teilmengen X₁, X₂, X₃ ein Element auswählen. Für X₁ = {0, 1, 2, 3, 4} kann z.B. α(X₁) = {3} sein.
Was ist eine geordnete Menge?
Ist ≤ eine Ordnungsrelation auf einer Menge X, so ist die Menge (X, ≤) eine geordnete Menge.
Was ist ein maximales Element x in einer geordneten Menge (X, ≤)?
Ein Element x heisst maximal, falls für alle y ∈ X gilt: x ≤ y ⇒ x = y (d.h. es gibt kein Element y, das kleiner als x ist). Ein Element m ∈ X heisst Maximum von X, falls für alle x ∈ X gilt: x ≤ m.
Was sind untere und obere Schranke einer Teilmenge A ⊆ X, wenn X eine geordnete Menge (X, ≤) ist?
Ein Element x ∈ X heisst obere Schranke, falls a ≤ x und untere Schranke, falls x ≤ a für alle a ∈ A gilt.
Was ist eine Kette und was ist eine induktive Ordnung einer geordneten Menge (X, ≤)?
Warum ist die leere Menge ebenfalls eine Kette?
Eine Teilmenge K ⊆ X heisst Kette, wenn für alle x, y ∈ K gilt: x ≤ y oder y ≤ x.
Hat jede Kette in X eine obere Schranke, so heisst X eine induktiv geornete Menge.
Die leere Menge ist ebenfalls eine Kette, da sie Teilmenge von X ist und eine obere Schranke hat (so ist also insbesondere X nicht leer).
Was ist die zentrale Aussage vom Zorn’schen Lemma?
Es sei M eine nicht leere halbgeordnete Menge, in der jede total geordnete Teilmenge A ⊆ M eine obere Schranke hat. Danngibt es in M (wenigstens) ein maximales Element.
(Für Beweis s. Skript!)
