Mengenlehre

Category: 

Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik, das sich mit der Untersuchung von Mengen, also von Zusammenfassungen von Objekten, beschäftigt. Sie ist für viele Bereiche in der Mathematik und Informatik von großer Bedeutung. Im Bereich der Informatik ist es z.B. für die Definition von kontextfreien Grammatiken wichtig.

Definition

"Unter einer Menge verstehen wir eine Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem Ganzen." - Georg Cantor (1845-1918), Begründer der Mengenlehre.

Eine Menge kann im Grunde eine beliebige Ansammlung an Objekten sein. Um diese Mengen darzustellen, gibt es zwei verschiedene Formen:
Explizit/Extensional: Aufzählung aller Elemente der Menge: {0, 1, 2, 3, 4, 5} oder auch {1, 2, Apfel, 3.141}
Implizit/Intensional: Definition anhand eines Ausdrucks: {x | f(x)}
Die intentionale Darstellung ist recht selbsterklärend, da man einfach jedes Element aufzählt. Die intensionale Darstellung ist etwas komplizierter, jedoch häufig weitaus praktischer. In dieser Darstellung werden die Elemente durch einen Ausdruck erzeugt.
{2,4,6,8} = { x | x ist eine gerade natürlich Zahl und x < 10}

Eine besondere Menge ist dabei die leere Menge. Wie der Name bereits sagt, enthält diese Menge keine Elemente. Dargestellt wird sie durch $\{ \}$ oder auch $\emptyset$.

Die Reihenfolge der Elemente einer Menge ist egal. Das heißt die beiden folgenden Mengen sind somit gleich:
$\{1, 2, 3\} = \{3, 2, 1\}$
Außerdem wird mehrfaches Auftreten des selben Elementes ignoriert:
$\{ 1, 2, 3\} = \{ 1, 1, 2, 1, 2, 3 \}$

Beziehungen von Mengen

Um Auszudrücken das ein bestimmtes Objekt in einer Menge liegt, nutzen wir den $\in$ Operator.
$x \in A$ sagt aus, dass x ein Element von A ist. Analog bedeutet $x \notin A$, dass x kein Element aus A ist.
Häufig ist es auch Interessant zu erfahren, wie viele Elemente eine Menge denn überhaupt besitzt. Die Anzahl der Elemente einer Menge M wird Mächtigkeit oder auch Kardinalität von M genannt, symbolisch ausgedrückt durch: $|M|$
$|\{ 2, 4, 6, 8\}| = 4$
$|\emptyset| = 0$

Wie bereits weiter oben erläutert, werden mehrfach auftretende Elemente nur einmal gezählt:
$|\{2,2,2\}| = 1$

Die Menge A heißt Teilmenge von B, wenn jedes Element von A auch in B vorkommt. $A \subseteq B$
$A \not\subseteq B$ bedeutet, dass A keine Teilmenge von B ist. D.h. A besitzt mindestens ein Element, welches eben nicht in B auftritt.

$A \subseteq B$ erlaubt auch, dass A und B ggf. gleich sind. Wenn man explizit ausdrücken möchte, dass A eine echte Teilmenge von B ist, also dass sie nicht gleich sein dürfen, dann nutzt man den $\subset$ Operator (manchmal auch durch $\subsetneq$ dargestellt).

Beispiele:
$1 \in \{1,2,3\}$
$1 \notin \{2, 4, 6\}$
$\{1,2,3\} \subset \{1,2,3,4\}$
$\{1,2,3\} \subseteq \{1,2,3,4\}$
$\{1,2,3\} \not\subset \{1,2,3\}$
$\{1,2,3\} \subseteq \{1,2,3\}$

Operationen auf Mengen

Die Mengenlehre kennt drei grundlegende Operationen, mit denen man zwei Mengen verknüpfen kann:

  • Vereinigung: $A \cup B := \{ x | x \in A$ oder $x \in B \}$
  • Durchschnitt: $A \cap B := \{ x | x \in A$ und $x \in B \}$
  • Differenz: $A \setminus B := \{ x | x \in A$ und $x \notin B \}$

Beispiele:
Sei $A := \{1,2,3\}$ und $B:=\{3,4,5\}$
$A \cup B = \{1,2,3,4,5\}$
$A \cap B = \{3\}$
$A \setminus B = \{1,2\}$
$B \setminus A = \{4,5\}$

Wenn man etwas neu definiert, dann verwendet man $:=$. Wenn man z.B. sagen möchte, dass $A$ von nun an der Menge $\{1,2,3\}$ entspricht, so schreibt man $A := \{1,2,3\}$. Wenn man aber nur zeigen möchte, dass die Mengen $A$ und $B$ gleich sind, so verwendet man das $=$ Zeichen. Also z.B. $\{1,2,3\} = \{3,2,1\}$.

Exkurs zu Tupeln

Tupel sind ebenfalls eine wichtige Art und Weise um Objekte zusammenzufassen. Ein Tupel besteht aus einer Liste endlich vieler Objekte (Mengen können auch unendlich sein). Zudem spielt bei einem die Tupel die Reihenfolge eine Rolle und Objekte können auch mehrfach auftreten! Tupel werden durch runde Klammern dargestellt, zwischen denen beliebig viele Objekte durch Kommata getrennt geschrieben werden.
$(1,2,3) \neq (3,2,1)$
$(1,2,3) \neq (1,1,2,3)$
Sowohl Mengen, als auch Tupel können beliebige Objekte aufnehmen, d.h. aber auch insbesondere, dass sie beliebig kombiniert werden können!
$\{(1,2,3), (1,3), \{1,(2,3)\}\}$

Weitere Mengenoperationen

Symmetrische Differenz
Diese Operation wird eher selten benötigt, soll hier aber keineswegs fehlen:
$A \triangle B := \{x | (x \in A $ und $x \notin B) $ oder $ (x \in B $ und $x \notin A) \}$
Anders ausgedrückt, enthält $A \triangle B$ alle Elemente, die in nur einer der beiden Mengen auftreten.
$\{1,2,3,4\} \triangle \{2,4,6,8\} = \{ 1,3,6,8 \}$

Kartesisches Produkt
Die Produktmenge oder auch das kartesische Produkt definieren wir erst einmal für zwei Mengen. Die Produktmenge von $A$ und $B$ ist die Menge aller geordneten Paare, deren erstes Element aus $A$ und deren zweites Element aus $B$ ist.
$A \times B := \{(a,b) | a \in A $ und $ b \in B \}$
$\{1,2,3\} \times \{a,b,c\} = \{ (1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c) \}$

Das kartesische Produkt wird auch für mehr als zwei Mengen definiert:
$A_1 \times A_2 \times ... \times A_n := \{ (a_1, a_2, ... , a_n) | a_1 \in A_1 $ und $a_2 \in A_2 $ und $...$ und $a_n \in A_n \} = \{ (a_1, ... , a_n) | a_i \in A_i \}$

Für den Sonderfall, dass man das kartesische Produkt über die selbe Menge berechnen will, gibt es die folgende Kurznotation:
$A \times A \times ... \times A := A^{n}$
Also z.B. $A \times A = A^2$.

$A \times A^2 \neq A^3$, denn $A^2$ ist bereits eine Menge aus Tupeln und somit ist $A \times A^2$ eine Menge aus Tupeln, deren erstes Element aus A ist und deren zweites Element wieder ein Tupel ist!
Sei zur Verdeutlichung $A=\{1,2\}$, dann gilt:
$A \times A^2 = A \times \{ (1,1), (1,2), (2,1), (2,2) \} \\
= \{ (1, (1,1)), (1, (1,2)), (1, (2,1)), (1, (2,2)), .... \}$

$|A \times B| = |A| \times |B|$

Potenzmenge
Die Potenzmenge $\mathcal{P}(A)$ von $A$ ist die Menge aller Teilmengen von $A$. Da die leere Menge Teilmenge von jeder Menge ist, ist die leere Menge Element der Potenzmenge.
Die Potenzmenge einer Menge A, enthält also jede Teilmenge von A und somit auch A selbst.
Formal ist sie wie folgt definiert: $\mathcal{P}(A) := \{ U | U \subseteq A \}$
$\mathcal{P}(\{1,2,3\}) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \}$
$\mathcal{P}(\emptyset) = \{ \emptyset \}$

$\{ \emptyset \} \neq \emptyset$

$|\mathcal{P}(A)| = 2^{|A|}$
Dies kann auch hilfreich sein, um zu überprüfen ob man beim Erzeugen der Potenzmenge einen Fehler gemacht hat.

Auf den nachfolgenden Seiten findet ihr ein paar Beispielaufgaben, zusammen mit den entsprechenden Lösungen.