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.
