1 Mengenlehre

Hilbert:

Aus dem Paradies [die Mengenlehre], das Cantor uns geschaffen hat, soll uns niemand mehr vertreiben können.

Poincaré:

Spätere Generationen werden die Mengenlehre als Krankheit ansehen, die man überwunden hat.

In diesem ersten Abschnitt befassen wir uns mit der Sprache der Mathematik. Die natürlichen Sprachen wie deutsch, englisch, etc. mangelt es leider an der nötigen Präzision, insbesonders dann, wenn es darum geht unendliche Objekte und Prozesse zu beschreiben. Um die dadurch entstehenden Vieldeutigkeiten zu vermeiden wurde von Georg Cantor die Mengenlehre entwickelt.

1.1 Definition.
Unter einer Menge verstehen wir wie Cantor eine Zusammenfassung wohlunterschiedener Objekte unserer Anschauung oder unseres Denkens zu einem neuen Ganzen. Es muß dabei im Prinzip feststellbar sein, ob ein gegebenes Objekt zur Menge gehört oder nicht. Jene Objekte die zur Menge gehören heißen Elemente der Menge. Wenn $A$ eine Menge und $x$ ein Objekt ist, dann schreiben wir $x\in A$ falls $x$ ein Element der Menge $A$ ist und $x\notin A$ andernfalls. Dies folgt der allgemeinen Methode in der Mathematik die Negation einer Beziehung zweier Objekte durch Durchstreichen des Relationssymbols zu bezeichnen, also $x\notin A$ bedeutet es ist nicht $x\in A$, sowie $x\neq y$ bedeutet $x$ ist ungleich (nicht gleich) $y$ und $x\not<y$ bedeutet, daß $x$ nicht kleiner als $y$ ist.

Wir haben zwei Möglichkeiten Mengen $A$ zu beschreiben:

• Aufzählend: Durch Angabe einer Liste $x_1,x_2,\dots,x_n$ aller Elemente der Menge. Man schreibt dann $A:=\{x_1,x_2,\dots,x_n\}$. Das Symbol `$:=$' bedeutet `definitionsgemäß ist die linke Seite gleich der rechten' oder kurz `ist definitionsgemäß gleich'. Also $A$ ist definitionsgemäß gleich der Menge bestehend aus den Elementen $x_1$, $x_2$, ..., $x_n$. Man schreibt auch kürzer `` $x_1,\dots,x_n\in A$'' anstelle von ``$x_1\in A$, $x_2\in A$,..., $x_n\in A$''. Wir wollen dabei auch denn Fall zulassen, daß gewisse der $x$ gleich sind. Ist z.B. $x_1=x_2$ so ist $\{x_1,x_2,x_3,\dots,x_n\}=\{x_2,x_3,\dots,x_n\}$. Dies hat den Nachteil, daß wir nicht sofort erkennen, wieviel Elemente die Menge $\{x_1,x_2,\dots,x_n\}$ hat (höchstens jedenfalls $n$ viele), aber den ungemeinen Vorteil, daß wir die Menge hinschreiben können ohne die genauen Werte von $x_1$, $x_2$, ..., $x_n$ bestimmen zu müssen: Z.B.
  $$A:=\left\{\pi,2\int_{-1}^{1}\sqrt{1-x^2}\,dx,\int_{-1}^{1}\frac1{ 1-x^2}\,dx,\int_{-{\infty}}^{{\infty}}\frac1{1+x^2}\,dx\right\}.$$
  Dies wird bisweilen auch bei unendlichen Mengen verwendet. Z.B. $A:=\{1,2,3,\dots\}$. Hierbei gibt es aber natürlich viele völlig verschiedene Interpretationen wie die weiteren Elemente dieser Menge nun wirklich aussehen:
  • $A$ ist die Menge der positiven ganzen Zahlen.
  • $A$ ist die Menge der Primzahlen, d.h. nur jener ganzen Zahlen, die keine anderen Teiler als 1 und sich selbst besitzen. Ein etwas längerer Abschnitt wäre somit $A=\{1,2,3,5,7,11,13,17,19,\dots\}$.
  • $A$ besteht aus den Gliedern der Fibonacci-Folge, d.h. jedes Element ist die Summe seiner beiden unmittelbaren Vorgänger. Ein etwas längerer Abschnitt wäre somit $A=\{1,2,3,5,8,13,\dots\}$.
  • $\dots$
• Beschreibend: Durch Angabe einer Eigenschaft $\mathcal{A}$, welche die Elemente der Menge charakterisiert. Man schreibt dann
  $$A:=\{x:x$$ hat die Eigenschaft $$\mathcal{A}\}$$
  und liest dies als $A$ ist per Definition die Menge alle (Objekte) $x$ welche die Eigenschaft $\mathcal{A}$ besitzen. Also z.B. $A:=\{x:x$ ist positive ganze Zahl$\}$ oder $B:=\{x:x$ ist Primzahl$\}$. Natürlich darf man an Stelle von $x$ auch jeden anderen Buchstaben verwenden.

Insbesonders nennt man die Menge $\emptyset:=\{\}$ die kein einziges Element hat die leere Menge. Beschreibend kann man sie auch durch Angabe einer Eigenschaft die für kein $x$ erfüllt ist, wie z.B. $x\ne x$ angeben, d.h. $\emptyset=\{x:x\ne x\}$.

Ein analoger Ausdruck, nämlich $R:=\{x:x\notin x\}$ führt allerdings auf einen fatalen Widerspruch, denn die Untersuchung der Frage ``Ist $R$ ein Element von sich selbst oder nicht?'' kann nur eine der beiden Antworten: $R\in R$ oder $R\notin R$ haben. Im ersten Fall muß also $R$ die definierende Eigenschaft von $R$ besitzen, also $R\notin R$ erfüllen im Widerspruch zur Annahme. Im anderen Fall darf $R$ die definierende Eigenschaft von $R$ nicht besitzen, es darf also nicht $R\notin R$ gelten, und (wegen dem Satz vom ausgeschlossenen Dritten) muß $R\in R$ gelten, ebenfalls ein Widerspruch zur Annahme.

Auswege aus dem Widerspruch, den die Russel'sche Menge $R$ liefert, wurden viele ersonnen. Grundidee dabei ist nicht alle Konstruktionen von Mengen zuzulassen.

Die erste recht technische und heute überholte Methode wurde von Russel und Whitehead in der Principia Mathematica präsentiert und bestand darin Buchzuführen wie tief verschachtelt die Mengenklammern einer Menge sind und jeweils nur solche eine Elemente einer Menge von Tiefe $n$ zuzulassen, die selbst Tiefe $n-1$ haben. Dies ist aber sehr umständlich, und wollen wir ``Buchhaltern'' überlassen.

Zermelo, Fraenkel und Skolem sind ihrerseits so vorgegangen, daß nur mehr ganz bestimmte Konstruktionen, die wir in der Folge alle besprechen werden (wie z.B. Potenzmenge, Vereinigung, Durschnitt, etc.), verwendet werden dürfen um aus gegebenen Mengen neue zu definieren.

Eleganter ist der Zugang von Gödel, Bernays und Neumann, die in der Beschreibung $A:=\{x:x$ hat die Eigenschaft $\mathcal{A}\}$ wieder alle Eigenschaften $\mathcal{A}$ zulassen, aber die so erhaltenen Objekte $A$ nun Klassen oder Unmengen nennen, und nur deren Elemente als Mengen bezeichnen. Ein Menge in ihren Sinn ist also eine Klasse, die in mindestens einer Klasse als Element enthalten ist.

Morse, Kelley und Tarski haben dies noch insofern modifiziert, daß die Einschränkung, daß alle Variablen in den bei der Klassenbildung betrachteten Aussagen nur Mengen durchlaufen dürfen, fallengelassen wurde. Für genauere Details dazu sei auf eine Vorlesung über Mengenlehre oder entsprechende Bücher verwiesen.

Zwei Mengen $A$ und $B$ sind genau dann gleich, wenn sie genau die selben Elemente besitzen, d.h. jedes beliebige Objekt $x$ genau dann zu $A$ gehört, wenn es zu $B$ gehört. Um dies kürzer symbolisieren zu können schreiben wir ``$\forall$'' statt ``für alle''. Und wenn eine Aussage $\mathcal{A}$ genau dann wahr ist wenn es eine Aussage $\mathcal{B}$ ist, so schreiben wir $\mathcal{A}\Leftrightarrow \mathcal{B}$ und sagen dafür $\mathcal{A}$ ist äquivalent zu $\mathcal{B}$. Wir können aus den Wahrheitswerten TRUE und FALSE der beiden Teilaussagen $\mathcal{A}$ und $\mathcal{B}$ jene der (logischen) Äquivalenz $\mathcal{A}\Leftrightarrow \mathcal{B}$ bestimmen:

$\mathcal{A}$	$\mathcal{B}$	$\mathcal{A}\Leftrightarrow \mathcal{B}$
TRUE	TRUE	TRUE
FALSE	FALSE	TRUE
FALSE	TRUE	FALSE
TRUE	FALSE	FALSE

Wenn schlußendlich ``:'' als ``(für die) gilt'' gelesen wird, dann sind zwei Mengen $A$ und $B$ genau dann gleich (d.h. $A=B$) wenn $\forall x:(x\in A\Leftrightarrow x\in B)$, also

$$A=B\;:\Leftrightarrow\;\forall x:(x\in A\Leftrightarrow x\in B).$$

Eine schwächere Möglichkeit Mengen miteinander zu vergleichen ist folgende: Eine Menge $A$ heißt Teilmenge einer Menge $B$ (und wir schreiben dann $A\subseteq B$, oder sagen auch $B$ ist Obermenge von $A$), genau dann, wenn jedes Element von $A$ auch Element von $B$ ist. Wenn eine Aussage $\mathcal{A}$ eine Aussage $\mathcal{B}$ zur Folge hat, so schreibt man für diesen Sachverhalt $\mathcal{A}\Rightarrow \mathcal{B}$ und sagt auch $\mathcal{A}$ impliziert $\mathcal{B}$. Es ist also $\mathcal{A}\Rightarrow \mathcal{B}$ selbst eine Aussage, die nur dann falsch sein kann, wenn zwar $\mathcal{A}$ erfüllt ist, nicht aber $\mathcal{B}$. Die Wahrheitstafel für `` $\Rightarrow$'' ist somit die folgende:

$\mathcal{A}$	$\mathcal{B}$	$\mathcal{A}\Rightarrow \mathcal{B}$
TRUE	TRUE	TRUE
FALSE	FALSE	TRUE
FALSE	TRUE	TRUE
TRUE	FALSE	FALSE

Beachte, daß $\mathcal{A}\Leftrightarrow \mathcal{B}$ genau dann gilt, wenn sowohl $\mathcal{A}\Rightarrow \mathcal{B}$ als auch $\mathcal{B}\Rightarrow \mathcal{A}$ (auch als $\mathcal{B}\Leftarrow \mathcal{A}$ geschrieben) gilt, d.h. die beiden Aussagen $\mathcal{A}$ und $\mathcal{B}$ sich gegenseitig implizieren.

Wir können obige Definition nun kurz wie folgt schreiben:

$$A\subseteq B\;:\Leftrightarrow\;\forall x:(x\in A\Rightarrow x\in B).$$

Graphisch können wir das durch folgendes sogenanntes Venn-Diagramm veranschaulichen:

Beachte, daß analog zu $\leq$ bei Zahlen für alle Mengen $A$ die Aussage $A\subseteq A$ gilt. Will man nur echte Teilmengen $A\subseteq B$ betrachten, d.h. welche $A\ne B$ erfüllen, so schreiben wir dafür $A\subset B$ (und sagt $A$ ist eine echte Teilmenge von $B$), d.h.

$A\subset B$ $:\Leftrightarrow$ $A\subseteq B$ und $A\ne B$.

Für das Teilmengesein wird oft auch das Symbol $A\subset B$ anstelle von $A\subseteq B$ verwendet, da diese Situation in der Mathematik viel öfter auftaucht als jene der echten Teilmenge (für die man dann allerdings soetwas schreckliches wie $A\varsubsetneq$B oder $A\subsetneqq B$ schreiben muß). Da man bei Zahlen in der entsprechenden Situation aber auch $a\leq b$ und nicht $a<b$ schreibt, will ich nicht so schreibfaul sein.

Offensichtlich ist $A=B$ $\Leftrightarrow$ $A\subseteq B$ und $B\subseteq A$. Diese Eigenschaft von $\subseteq$ heißt Antisymmetrie.

Weiters folgt aus $A\subseteq B$ und $B\subseteq C$ die Aussage $A\subseteq C$. Mann nennt diese Eigenschaft die Transitivität von $\subseteq$.

Natürlich können Mengen selbst wieder Elemente einer Menge sein. Z.B. können wir die Menge $\mathcal{P}(A)$ aller Teilmengen einer Menge betrachten, also

$$\mathcal{P}(A) :=\{B:B\subseteq A\},$$

$$B\in\mathcal{P}(A) \Leftrightarrow B\subseteq A.$$

Diese Menge $\mathcal{P}(A)$ heißt Potenzmenge von $A$. Z.B. ist

$$\mathcal{P}(\emptyset) =\{\emptyset\},$$

$$\mathcal{P}(\{a\}) =\{\emptyset,\{a\}\},$$

$$\mathcal{P}(\{a,b\}) =\{\emptyset,\{a\},\{b\},\{a,b\}\}$$

$$\mathcal{P}(\{a,b,c\}) =\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{c,a\},\{a,b,c\}\}.$$

Wir werden später in (3.23) zeigen, daß die Anzahl der Elemente von $\mathcal{P}(A)$ also der Teilmengen von $A$ gerade $2^{\vert A\vert}$ ist, wobei $\vert A\vert$ die Anzahl der Element von $A$ bezeichnet. Dies ist der Grund für die Namensgebung ``Potenzmenge''.

Beachte, daß sehr deutlich zu unterscheiden ist zwischen $A\subseteq B$, $A\subset B$ und $A\in B$. Wenn $0:=\emptyset$, $1:=\{0\}$, $2:=\{0,1\}$ bezeichnet (Wer meint schon zu wissen, was die Zahlen $0,1,2,\dots$ sind, der möge andere Symbole für die 3 eben definierten Mengen verwenden), so ist

• $0\subseteq 0$ (Die leere Menge ist Teilmenge jeder Menge), aber nicht $0\subset 0$ (denn $0=0$) und auch nicht $0\in 0$ (denn die leere Menge hat kein einziges Elemente).
• $1\in \{1\}$, aber nicht $1\subseteq \{1\}$ (da $0\in 1$ aber nicht $0\in\{1\}$), und somit auch nicht $1\subset \{1\}$.
• $1\subset 2$ (denn das einzige Element 0 von $1$ ist auch Element der Menge $2$) und somit $1\subseteq 2$ aber auch $1\in 2$.

Es ist also gefährlich Formulierungen wie ``$x$ liegt in $A$'' zu verwenden, denn dabei ist es nicht klar, ob dies $x$ liegt in $A$ als Element ($x\in A$) oder $x$ liegt in $A$ als Teilmenge ( $x\subseteq A$) bedeutet.

1.2 Definition. Mengenoperationen.
Aus je zwei Mengen $A$ und $B$ können wir neue Mengen bilden:
Der Durchschnitt $A\cap B$ von $A$ und $B$ ist die Menge aller Objekte die sowohl Elemente von $A$ als auch von $B$ sind. Salopp könnte man auch sagen: Der Durchschnitt besteht aus den Elementen die in beiden Mengen liegen. Dies könnte allerdings zu Verwechslung mit der weiter unten definierten Vereinigungsmenge führen, z.B. wenn wir die Menge aller Studentinnen, die in beide parallel-Klassen gehen, betrachten.

Wenn $\mathcal{A}$ und $\mathcal{B}$ zwei Aussagen sind, dann bezeichnet man mit `` $\mathcal{A},\mathcal{B}$'' oder $\mathcal{A}\wedge\mathcal{B}$ die Aussage, daß beide Aussagen zutreffen. In vielen Computersprachen wird `&&' anstelle des auf der Tastatur nicht vorhandenen $\wedge$ verwendet. Man ließt dies als `` $\mathcal{A}$ und $\mathcal{B}$''. Die Wahrheitstafel des (logischen) Unds $\wedge$ ist also folgende:

$\mathcal{A}$	$\mathcal{B}$	$\mathcal{A}\wedge\mathcal{B}$
TRUE	TRUE	TRUE
FALSE	FALSE	FALSE
FALSE	TRUE	FALSE
TRUE	FALSE	FALSE

Es ist also

$$A\cap B := \{x: x\in A\wedge x\in B \}.$$

Dies kan man durch ein Venn-Diagramm veranschaulichen:

Man sagt zwei Mengen $A$ und $B$ seien Element-fremd oder auch disjunkt, wenn $A\cap B=\emptyset$, d.h. sie kein einziges gemeinsames Element besitzen.

Beachte, daß $A\cap B$ die größte gemeinsame Teilmenge von $A$ und $B$ ist, siehe auch (1.5).

Beweis. Offensichtlich ist $A\cap B\subseteq A$ und $A\cap B\subseteq B$, denn aus $\mathcal{A}\wedge\mathcal{B}$ folgt $A$ und es folgt $B$.

Sei nun $M$ eine weitere gemeinsame Teilmenge von $A$ und $B$. Dann ist $M\subseteq A\cap B$ (also $A\cap B$ die größte gemeinsame Teilmenge), denn aus $x\in M$ folgt $x\in A$ und $x\in B$ also $(x\in A)\wedge(x\in B)$ und somit $x\in A\cap B$.     []

Es ist $A\subseteq B$ $\Leftrightarrow$ $A\cap B=A$.

Beweis. Aus $A\subseteq B$ folgt, daß $A\subseteq A\cap B$. Und wegen $A\cap B\subseteq A$ gilt Gleichheit.
Umgekehrt folgt aus $A\cap B=A$, daß $A=A\cap B\subseteq B$.     []

Die Vereinigung $A\cup B$ von $A$ und $B$ ist die Menge aller Objekte die Element mindestens einer der beiden Mengen $A$ bzw. $B$ sind. Wenn $\mathcal{A}$ und $\mathcal{B}$ zwei Aussagen sind, dann bezeichnet man mit $\mathcal{A}\vee\mathcal{B}$ die Aussage, daß zumindestens eine der beiden Aussagen zutrifft. In vielen Computersprachen wird $\vert\vert$ anstelle von $\vee$. Man liest dies als `` $\mathcal{A}$ oder $\mathcal{B}$'', muß dabei aber beachten, daß dies ein nicht ausschließendes oder ist, also auch den Fall, daß $\mathcal{A}$ und $\mathcal{B}$ gelten, inkludiert. Interpretiere z.B. den Satz `Jack liebt Jill oder (Jack liebt) Jane''. D.h. die Wahrheitstafel des (logischen) Oders $\vee$ ist folgende:

$\mathcal{A}$	$\mathcal{B}$	$\mathcal{A}\vee\mathcal{B}$
TRUE	TRUE	TRUE
FALSE	FALSE	FALSE
FALSE	TRUE	TRUE
TRUE	FALSE	TRUE

Es ist also

$$A\cup B := \{x: x\in A\vee x\in B \}.$$

Auch dies kan man durch ein Venn-Diagramm veranschaulichen:

Wir wollen nun die wichtigsten Rechenregeln für Durchschnitt und Vereinigung aufstellen:

1.3 Lemma.
Es seien $A$, $B$ und $C$ Mengen. Dann gilt:

1. Kommutativität: $A\cap B=B\cap A$, $A\cup B=B\cup A$.
2. Assoziativität: $(A\cap B)\cap C=A\cap (B\cap C)$, $(A\cup B)\cup C=A\cup (B\cup C)$.
3. Distributivität:

   $$(A\cup B)\cap C =(A\cap C)\cup (B\cap C), (A\cap B)\cup C =(A\cup C)\cap (B\cup C).$$

   
   

Kommutativität besagt also, daß wir bei der Durchschnitts- und Vereinigungsbildung die beiden Mengen miteinander vertauschen dürfen.

Assoziativität besagt also, daß es ist egal ist, wie wir bei mehrfachen Vereinigungen oder mehrfachen Durchschnitten Klammern setzen (in welcher Reihenfolge wir sie also ausrechnen), und wir können sie auch ganz weglassen, also $A\cap B\cap C$ oder $A\cup B\cup C$ schreiben, ohne irgendwelche Mißverständnisse zu provozieren.

Distributivität zeigt, daß wenn sich Durchschnitts- und Vereinigungsbildung abwechseln, so darf man nicht mehr Klammern vertauschen, aber kann $C$ ``hineinmultiplizieren''. Vergleiche dies mit dem Distributivgesetz für das Rechnen mit Zahlen: $(a+b)\cdot c=(a\cdot c) + (b\cdot c)$ aber nicht $(a\cdot b)+c=(a+c)\cdot (b+c)$.

Beweis. Wir geben verschiedene Beweise für das Distributivitätsgesetz $A\cap(B\cup C)=(A\cap B)\cup (A\cap C)$, die anderen Gesetze lassen sich ähnlich aber einfacher beweisen:

1. Durch Zeichnung (Venn-Diagramme). Wichtig dabei ist, daß die drei Mengen $A$, $B$ und $C$ in allgemeiner Lage gezeichnet werden, d.h. alle möglichen Fälle für Punkte zu den einzelnen Mengen zu gehören oder nicht wirklich vorkommen. Für vier Mengen wäre das schon nicht mehr ganz einfach erreichbar.
   

2. Durch Wahrheitstafel. D.h. man betrachtet alle Fälle dafür, daß $x\in A$ oder nicht, $x\in B$ oder nicht und $x\in C$ oder nicht, und überprüft ob in allen Fällen $x$ genau dann ein Element der linken Seite ist, wenn es auch eines der rechten Seite ist.
   $$\begin{array}{\vert c\vert c\vert c\vert\vert c\vert c\vert c\ver... ...\notin &\in \\ \in &\in &\in &\in &\in &\in &\in &\in \\ \hline \end{array}$$

3. Durch Umwandeln mittels der Definitionen in Aussagenlogik:

   $$A\cap (B\cup C) = \{x:x\in A x\in B\cup C\}$$

   $$= \{x:x\in A (x\in B x\in C)\}$$

   $$= \{x:(x\in A x\in B) (x\in A x\in C)\}$$

   $$= \{x: x\in A\cap B x\in A\cap C\}$$

   $$= (A\cap B)\cup (A\cap C)$$

   
   
   Wir haben das distributiv-Gesetz für Durchschnitt und Vereinigung von Mengen also auf das distributiv-Gesetz für `und' und `oder' von Aussagen zurückgeführt. Die Gültigkeit des letzteren sagt uns der gesunde Hausverstand oder wir (als Logiker) beweisen es mittels Wahrheitstafel so wie zuvor.

    []

1.4 Definition.
Wenn man anstelle zweier Mengen $A$ und $B$ endlich viele Mengen $A_1$, $A_2$, ..., $A_n$ gegeben hat, so kann man rekursiv (siehe (3.4)) Durchschnitt und Vereinigung als

$$A_1\cap\dots\cap A_n := (A_1\cap\dots\cap A_{n-1})\cap A_n$$

$$A_1\cup\dots\cup A_n := (A_1\cup\dots\cup A_{n-1})\cup A_n$$

definieren. Motiviert wird diese Definition durch das Assoziativgesetz (1.3.2). Direkter können wir diesen Durchschnitt und Vereinigung durch

$$A_1\cap\dots\cap A_n = \{x:x\in A_1\wedge\dots\wedge x\in A_n\}$$

$$A_1\cup\dots\cup A_n = \{x:x\in A_1\vee\dots\vee x\in A_n\}$$

beschreiben, also als die Menge jener Objekte, die in allen $A$'s enthalten sind, bzw. in mindestens einem der $A$'s enthalten sind.

Man schreibt kürzer und eindeutiger unter Vermeidung von `` $\dots$'' auch $\bigcap_{i=1}^n A_i$ bzw. $\bigcup_{i=1}^n A_i$ für diese Mengen und liest dies als ``Durchschnitt/Vereinigung für $i$ gleich 1 bis $n$ der $A$ unten $i$''.

Will man das nun auf unendlich viele Mengen übertragen, also den Durchschnitt $\bigcap \mathcal{A}$ oder die Vereinigung $\bigcup\mathcal{A}$ einer beliebigen Menge $\mathcal{A}$ von Mengen $A$ definieren, dann sollte wohl der Durchschnitt $\bigcap \mathcal{A}$ die Menge all jener Objekte sein, die gleichzeitig in jeder der Mengen $A\in\mathcal{A}$ als Element enthalten sind, d.h.

$$\bigcap \mathcal{A}:=\{x:\forall A\in\mathcal{A}:x\in A\},$$

und die Vereinigung $\bigcup\mathcal{A}$ sollte die Menge all jener Objekte sein, die zumindest in einer der Mengen $A\in\mathcal{A}$ als Element enthalten sind, d.h.

$$\bigcup \mathcal{A}:=\{x:\exists A\in\mathcal{A}:x\in A\},$$

wobei `` $\exists$'' für ``es gibt (mindestens) ein'' steht. Besteht $\mathcal{A}$ nur aus endlich vielen Mengen $A_1,A_2,\dots,A_n$, d.h. $\mathcal{A}=\{A_1,\dots,A_n\}$, dann ist

$$\bigcap \mathcal{A} =\bigcap \{A_1,\dots,A_n\}=A_1\cap\dots\cap A_n$$

$$\quad \bigcup \mathcal{A} =\bigcup \{A_1,\dots,A_n\}=A_1\cup\dots\cup A_n$$

Wenn $\mathcal{A}$ eine Eigenschaft für Mengen ist, so benutzt man auch die Schreibweise

$$\bigcap_{A\text{ hat }\mathcal{A}}A := \bigcap\;\Bigl\{A:A \mathcal{A}\Bigr\}$$

$$\bigcup_{A\text{ hat }\mathcal{A}}A := \bigcup\;\Bigl\{A:A \mathcal{A}\Bigr\}$$

Also wenn z.B. $M$ eine fixe Menge ist und $\mathcal{A}$ die Eigenschaft ``Teilmenge von $M$ zu sein'' ist, dann ist

$$\bigcup_{A\subseteq M} A = \bigcup\;\Bigl\{A:A\subseteq M\Bigr\}=\bigcup\mathcal{P}(M) = M.$$

Ist für jedes Element $i\in I$ einer (Index-)Menge $I$ eine Menge $A_i$ gegeben, so setzt man

$$\Bigl\{A_i:i\in\mathcal{I}\Bigr\} :=\Bigl\{A:\exists i:i\in\mathcal{I}$$ und $$A=A_i\Bigr\},$$

und nennt dies eine durch $i\in I$ indizierte Menge (oder auch Familie) von Mengen. Allgemeiner, wenn $\mathcal{I}$ eine Eigenschaft für Mengen und $A_i$ ein Ausdruck (Term) für eine Menge mit der Variablen $i$ ist, so setzt man

$$\Bigl\{A_i:i$$ hat Eigenschaft $$\mathcal{I}\Bigr\} :=\Bigl\{A:\exists i:i$$ hat Eigenschaft $$\mathcal{I}$$ und $$A=A_i\Bigr\}.$$

Damit kann man nun die Schreibweisen

$$\bigcap_{i\in I}A_i := \bigcap\;\{A_i:i\in I\} = \bigl\{x:\forall i\in I:x\in A_i\bigr\}$$

$$\bigcup_{i\in I}A_i := \bigcup\;\{A_i:i\in I\} = \bigl\{x:\exists i\in I:x\in A_i\bigr\}$$

einführen.

Wie für zweifache Vereinigung und Durchschnitt erhalten wir auch in dieser allgemeinen Situation:

1.5 Lemma.
Es sei $\mathcal{A}$ eine nicht-leere Menge von Mengen. Dann ist $\bigcup\mathcal{A}$ die kleinste (im Sinne von ``Teilmenge sein'') Menge, die alle $A\in\mathcal{A}$ als Teilmengen enthält.
Ebenso ist $\bigcap \mathcal{A}$ die größte (im Sinne von ``Teilmenge sein'') Menge, die in allen $A\in\mathcal{A}$ enthalten ist.

Beweis. Für jedes $A\in\mathcal{A}$ gilt $\bigcap\mathcal{A}\subseteq A\subseteq \bigcup\mathcal{A}$, denn aus $x\in\bigcap\mathcal{A}$ folgt nach Definition $\forall A\in\mathcal{A}$: $x\in A$. Und aus $x\in A\in\mathcal{A}$ folgt ebenso nach Definition $x\in\bigcup\mathcal{A}$.

Sei nun $M$ eine Menge mit $A\subseteq M$ für alle $A\in\mathcal{A}$. Dann ist $\bigcup \mathcal{A}\subseteq M$, denn aus $x\in\bigcup\mathcal{A}$ folgt $\exists A\in\mathcal{A}$ mit $x\in A$ und wegen $A\subseteq M$ ist somit $x\in M$.

Sei andererseits $M$ eine Menge mit $M\subseteq A$ für alle $A\in\mathcal{A}$. Dann ist $M\subseteq \bigcap\mathcal{A}$, denn aus $x\in M$ folgt $x\in A$ für alle $A\in\mathcal{A}$, also $x\in\bigcap\mathcal{A}$.

    []

1.6 Definition.
Unter der Differenzmenge $A\setminus B$ zweier Mengen $A$ und $B$ (man sagt dafür auch: $A$ vermindert um $B$) versteht man die Menge aller Objekte $x$ die zwar Elemente von $A$ nicht aber von $B$ sind, d.h.

$$A\setminus B := \{x:x\in A\wedge x\notin B\}$$

Das entsprechenden Venn-Diagramm ist:

Wenn die Menge $A$ klar ist, d.h. sich alles in einer fixen Grundmenge $A$ abspielt, dann schreibt man auch kürzer $B^c$ für $A\setminus B$ und nennt dies das Komplement von $B$ (in $A$).

1.7 Proposition.
Sei $\mathcal{A}\ne\emptyset$ eine Menge von Mengen $A$ und $B$ eine weitere Menge. Dann gelten:

$$B\cap \bigcup\mathcal{A} = \bigcup_{A\in\mathcal{A}} B\cap A, B\cup \bigcap\mathcal{A} = \bigcap_{A\in\mathcal{A}} B\cup A,$$

$$B\cap \bigcup_{i\in I} A_i = \bigcup_{i\in I} B\cap A_i, B\cup \bigcap_{i\in I} A_i = \bigcap_{i\in I} B\cup A_i.$$
De Morgan'schen Gesetze:

$$B\setminus \bigcup\mathcal{A} = \bigcap_{A\in\mathcal{A}} B\setminus A, B\setminus \bigcap\mathcal{A} = \bigcup_{A\in\mathcal{A}} B\setminus A$$

$$\left(\bigcup\mathcal{A}\right)^c =\bigcap_{A\in\mathcal{A}} A^c, \left(\bigcap\mathcal{A}\right)^c =\bigcup_{A\in\mathcal{A}} A^c,$$

$$\Bigl(\bigcup_i A_i\Bigr)^c =\bigcap_i (A_i)^c, \Bigl(\bigcap_i A_i\Bigr)^c =\bigcup_i (A_i)^c.$$

Eine verbale Formulierung des links stehenden distributiv-Gesetzes ist: Ein Objekt liegt genau dann in $B$ und in mindestens einem $A\in\mathcal{A}$, wenn es sowohl in $B$ als auch in $A$ für mindestens ein $A\in\mathcal{A}$ liegt. Für das rechts stehende ist eine solche: Ein Objekt liegt genau dann in allen $A\in\mathcal{A}$ oder in $B$, wenn es für jedes $A\in\mathcal{A}$ in $A$ oder in $B$ liegt.

Eine graphische Darstellung der De Morgan'schen Gesetze ist:

Eine verbale Formulierung ist: Ein Objekt ist genau dann kein Element der Vereinigung, wenn es in keinen der $A\in\mathcal{A}$ liegt. Und ein Objekt ist genau dann kein Element des Durchschnitts, wenn es in einen der $A\in\mathcal{A}$ nicht enthalten ist.

Beweis. Es gilt:

$$x\in B\cap\bigcup\mathcal{A} \Leftrightarrow x\in B x\in\bigcup\mathcal{A}$$

$$\Leftrightarrow x\in B \exists A\in\mathcal{A}:x\in A$$

$$\Leftrightarrow \exists A\in\mathcal{A}: x\in B x\in A$$

$$\Leftrightarrow \exists A\in\mathcal{A}: x\in B\cap A$$

$$\Leftrightarrow x\in\bigcup_{A\in \mathcal{A}} B\cap A$$

Dabei haben wir wieder das Gesetz für Mengen auf ein entsprechendes distributiv-Gesetz für Aussagen zurückgeführt. Und entsprechend zeigt man auch die übrigen Identitäten, wobei man verwendet daß eine Aussage über $A$ genau dann nicht für alle $A$ gilt, wenn ein $A$ existiert, für welche sie nicht gilt.     []

Um Beziehungen zwischen Objekten behandeln zu können, benötigen wir eine Möglichkeit diese paarweise zusammenzufassen. Natürlich könnten wir zu $a$ und $b$ die Menge $\{a,b\}$ betrachten. Wegen $\{a,b\}=\{b,a\}$ ist das aber für Vergleiche nicht geeignet, und wir brauchen den Begriff des geordneten Paares $(a,b)$, der gewährleistet, daß

$$(a,b)=(c,d)\Leftrightarrow a=b\wedge c=d$$

gilt. Mengentheoretisch kann dies, wie man leicht zeigt, durch die Definition $(a,b):=\{\{a\},\{a,b\}\}$ erreicht werden, denn grob gesagt erkennt man welches das Erste der beiden sein soll daran, daß es das Element $a$ des 1-elementigen Elements $\{a\}$ von $\{\{a\},\{a,b\}\}$ ist. Die Menge aller geordneten Paare wird als kartesischen Produkt

$$A\times B:=\{(a,b):a\in A,b\in B\}:=\{x:\exists a\in A\exists b\in B:x=(a,b)\}$$

von $A$ und $B$ bezeichnet. Man kann sich $A\times B$ als Menge der Gitterpunkte eines rechteckigen Gitters mit Seiten $A$ und $B$ vorstellen.

Um also z.B. die Beziehung des Elternseins zu beschreiben müßte man eine Tabelle, wo für jeden Menschen seine Eltern angeführt sind, aufstellen, oder eine solche, wo für jeden Menschen alle seine Kinder angeführt sind, oder für je zwei Menschen $a$ und $b$ angeben, ob $a$ ein Kind von $b$ (bzw. $b$ ein Elternteil von $a$) ist. D.h. in $A\times B$ sind alle Punkte $(a,b)$ entsprechend mit den Werten TRUE oder FALSE zu belegen. Es genügt natürlich dabei alle mit den Wert TRUE anzugeben, also eine Teilmenge von $A\times B$ auszuzeichnen. Dies führt zu folgender

1.8 Definition.
Eine Relation $R$ auf $A\times B$ ist eine Teilmenge von $A\times B$. Man schreibt kürzer $a\,R\, b$ anstelle von $(a,b)\in R$, und sagt dafür $a$ steht in Relation $R$ zu $b$. Ist $A=B$ so spricht man kürzer (aber nicht ganz sauber) von einer Relation auf $A$.

Z.B. haben wir die Relationen $\in$, $\notin$, $=$, $\subseteq$, $\subset$, $\dots$ für Mengen, also auch auf der Potenzmenge $\mathcal{P}(M)$ jeder fix vorgegebenen Menge $M$.

Wir können eine Relation auch mittels gerichteten Graph veranschaulichen, z.B. für die Teilmengenrelation auf $\mathcal{P}(\{0,1\})$ wobei wir Pfeile die sich aus der Reflexivität ergeben nicht eingezeichnet sind:

$$\xymatrix{ \emptyset \ar@{->}[2,0] \ar@{->}[0,... ...{ 0\} \ar@{->}[2, 0] \\ & & \\ \{ 1\} \ar@{->}[0,2] & &\{ 0,1\} \\ }$$

Auf folgende wichtige Eigenschaften können wir Relationen $R$ auf $A$ untersuchen

• Reflexivität: $\forall x\in A$: $xRx$.
• Symmetrie: $\forall x,y\in A$: $xRy$ $\Rightarrow$ $yRx$.
• Transitivität: $\forall x,y,z\in A$: $xRy$, $yRz$ $\Rightarrow$ $xRz$.

Eine Relation heißt Äquivalenzrelation, wenn sie alle diese 3 Eigenschaften besitzt. Man schreibt dann oft $\sim$ anstelle von $R$, beziehungsweise versieht $\sim$ noch mit einen Index, wenn man mehrere Relationen gleichzeitig betrachtet. Es ist z.B. die Gleichheit `=' von Mengen eine Äquivalenzrelation. Beachte jedoch das in vielen Computersprachen Befehle wie $x=x+1$ verwendet werden. Dort wird das Symbol `=' nicht für die logische Gleichheit der linken mit der rechten Seite verwendet, sondern so aufgefaßt, daß der linken Seite (wo nur eine Variable stehen darf) der Wert der rechten Seite zugeordnet wird. Es ist also in der Informatik ein wesentlicher Unterschied zwischen $a=b$ und $b=a$. Als Symbol für Gleichheit wird in diesen Sprachen zumeist `==' verwendet.

Äquivalenzrelationen sind zumeist dadurch gegeben, daß man Objekte äquivalent nennt, wenn sie eine gewisse Eigenschaft gemein haben. Z.B. ist für $m\in\mathbb{N}$ die Relation ``gleicher Rest bei Division durch $m$'' also $x\sim_m y$ $:\Leftrightarrow$ $m$ teilt $x-y$, d.h. $\exists k\in\mathbb{Z}$: $x-y=k\,m$, eine Äquivalenzrelation auf $\mathbb{N}$. Ebenso sind ``gleicher Geburtstag'', ``gleiches Sternzeichen'', ``gleich viele Kinder'', ``gleiches Gewicht'', ``gleicher Vornamen'', ``in die gleiche Klasse gehen'' u.s.w. Äquivalenzrelationen auf der Menge aller Menschen.

Beim letzten Beispiel, der in gleiche Klassen gehenden Schüler einer Schule, steckt offensichtlich dahinter, daß die Schule (oder auch deren Schüler) in Klassen eingeteilt sind. Wir wollen eine analoge Beschreibung nun für jede Äquivalenzrelation $\sim$ auf Mengen $X$ erhalten. Dazu bezeichnen wir Mengen $A$, die bezüglich `` $\subseteq$'' so groß wie möglich (man sagt maximal) unter allen Teilmengen $A\subseteq X$ sind welche nur paarweise äquivalente Elemente enthalten, als Äquivalenzklassen der Äquivalenzrelation $\sim$. Wir verwenden dabei die Sprechweise ``paarweise äquivalenter'' anstelle ``äquivalenter'' Elemente, denn wir können ja jeweils nur 2 Elemente miteinander vergleichen um ihre Äquivalenz zu überprüfen und nicht alle Elemente der Menge $A$ auf einmal. Wir können auch nicht von der größten Teilmenge mit obiger Eigenschaft sprechen, denn man denke nur an die Klassen einer Schule, welche mehrere maximale Mengen mit obiger Eigenschaft sind.

Wie kann man nun Äquivalenzklassen finden? Man beginnt mit einen Element $a\in X$ und betrachtet die Menge

$$[a]_{\sim} :=\{x\in X:x\sim a\}.$$

Falls klar ist, von welcher Äquivalenzrelation $\sim$ wir sprechen, so lassen wir auch den Index $\sim$ weg.

Diese Menge besteht offensichtlich aus paarweise äquivalenten Elementen, denn wegen der Transitivität und Symmetrie sind je zwei Elemente $x,x'\in[a]_{\sim}$ zueinander äquivalent. Es kann auch keine echte Obermenge $A\supset [a]_{\sim}$ mit dieser Eigenschaft geben, denn deren Elemente müßten dann zu $a\in [a]_{\sim}$ äquivalent sein. Also ist $[a]_{\sim}$ eine Äquivalenzklasse von $\sim$, die einzige Klasse in der $a$ als Element liegt, die sogenannte von $a$ erzeugte Äquivalenzklasse.

Umgekehrt ist jede Äquivalenzklasse $A$ von dieser Form, denn kann $A$ nicht leer sein, andernfalls wählen wir irgend ein $a\in X$ und erhalten eine größere Menge $[a]_{\sim}\supset A=\emptyset$, einen Widerspruch zur Maximalität. Somit existiert ein $a\in A$ und wir wählen ein solches. Dann ist $A\subseteq [a]_{\sim}$, da jedes $x\in A$ zu $a\in A$ äquivalent ist und wegen der Maximalität von $A$ ist $A=[a]_{\sim}$.

Es ist also $\{[a]_{\sim}:a\in A\}$ gerade die Menge aller Äquivalenzklassen von $X$.

Die Äquivalenzklassen zur Teilbarkeit durch $m$ heißen Restklassen modulo $m$, und man schreibt $\mathbb{Z}_m$ für die Menge $\{[k]_{\sim_m}:k\in\mathbb{Z}\}$ der Restklassen ganzer Zahlen modulo $m$.

Beachte, daß sich hier unsere Vereinbarung, daß in der aufzählenden Beschreibung einer Menge gleiche Elemente mehrfach auftreten dürfen bezahlt macht, denn z.B. ist $\{[k]_{\sim_2}:k\in\mathbb{Z}\} =\{\dots,[-2]_{\sim_2},[-1]... ...sim_2}, [1]_{\sim_2},[2]_{\sim_2},\dots\} =\{[0]_{\sim_2},[1]_{\sim_2}\}$, denn als Reste bei Division durch 2 kann ja nur 0 und $1$ auftreten.

1.9 Definition.
Eine Klasseneinteilung $\mathcal{A}$ einer Menge $X$ ist eine Menge $\mathcal{A}$ von nicht-leeren Teilmengen $A\subseteq X$ die paarweise disjunkt sind (d.h. $A,A'\in\mathcal{A}$ mit $A\cap A'\ne\emptyset$ $\Rightarrow$ $A=A'$) und deren Vereinigung $X$ ist, d.h. $X=\bigcup\mathcal{A}$.

1.10 Proposition.
Es sei $X$ eine nicht-leere Menge. Dann entsprechen den Äquivalenzrelation $\sim$ auf $X$ genau den Klasseneinteilungen $\mathcal{A}$ von $X$.

Beweis. ( $\mapsto$) Sei $\sim$ eine Äquivalenzrelation auf $X$. Die Menge $\mathcal{A}=\{[a]_{\sim}:a\in A\}$ aller Äquivalenzklassen von $X$ ist dann eine Klasseneinteilung von $X$: Offensichtlich ist $X\supseteq \bigcup\mathcal{A} =\bigcup_{a\in X}[a]_{\sim}\supseteq \bigcup_{a\in X}\{a\}=X$, also $X=\bigcup\mathcal{A}$.

Sei weiters $A,A'\in\mathcal{A}$ und $a\in A\cap A'\ne\emptyset$. Dann ist $A=[a]_{\sim}=A'$ nach obigen.

( $\DOTSB\kern.2em\setbox0=\hbox{$\leftarrow$\kern-.15em\raise0.1ex\hbox{$\vert$}}\box0 \kern.3em$) Umgekehrt sei $\mathcal{A}$ eine Klasseneinteilung von $X$. Wir definieren $x\sim x'$ $:\Leftrightarrow$ $\exists A\in\mathcal{A}$: $x,x'\in A$. Dies beschreibt eine Äquivalenzrelation $\sim$ auf $X$:
Die Relation ist reflexiv, denn für $x\in X=\bigcup\mathcal{A}$ existiert eine $A\in\mathcal{A}$ mit $x\in A$, also $x\sim x$. Sie ist offensichtlich symmetrisch. Nun zur Transitivität. Sei $x\sim y\sim z$, d.h. $\exists A,B\in\mathcal{A}$ mit $x,y\in A$, $y,z\in B$. Also ist $y\in A\cap B\ne\emptyset$ und somit $A=B$, d.h. $x\in A=B\ni z$, also $x\sim z$.

Bleibt zu zeigen, daß das hin und her zwischen Äquivalenzrelationen $\sim$ und Klasseneinteilungen $\mathcal{A}$ zusammenpaßt.

Sei also $\mathcal{A}$ die Menge der Äquivalenzklassen einer Äquivalenzrelation $\sim$ und $\sim_{\mathcal{A}}$ die aus $\mathcal{A}$ gewonnene Äquivalenzrelation. Wir behaupten, daß diese mit der ursprünglichen übereinstimmt. Wir müssen also $\forall x,y\in X:x\sim y\Leftrightarrow x\sim_{\mathcal{A}} y$ zeigen.
Sei zuerst $x\sim y$, dann liegt $x,y\in [y]_{\sim}\in\mathcal{A}$, also ist auch $x\sim_{\mathcal{A}} y$ nach Definition. Umgekehrt sei $x\sim_{\mathcal{A}} y$, d.h. es existiert ein $A\in\mathcal{A}$ mit $x,y\in A$. Da $A$ aber aus bezüglich $\sim$ paarweise äquivalenten Elementen bestehen muß, ist $x\sim y$.

Sei nun andererseits $\mathcal{A}$ irgend eine Klasseneinteilung von $X$ und $\sim$ die zugehörige Äquivalenzrelation, d.h. $x\sim y:\Leftrightarrow\exists A\in\mathcal{A}:x,y\in A$. Wir müssen zeigen, daß $\mathcal{A}$ gerade aus den Äquivalenzklassen $[x]_{\sim}$ von $\sim$ besteht.
Es ist $[x]_{\sim}\in\mathcal{A}$, denn für $y\in [x]_{\sim}$ ist $y\sim x$, also existiert ein $A\in\mathcal{A}$ mit $x,y\in A$. Verschiedene $y$ liefern das gleiche $A$, denn die $A\in\mathcal{A}$ sind nach Voraussetzung paarweise disjunkt. Also ist $[x]_\sim\subseteq A$. Sei umgekehrt $a\in A$. Dann ist $a,x\in A$, also $a\sim x$ und damit $a\in [x]_{\sim}$.
Sei nun $A\in\mathcal{A}$. Nach Voraussetzung ist $A\ne\emptyset$, also können wir ein $a\in A$ wählen. Dann ist aber wie zuvor $[a]_{\sim}=A$, denn $x\in[a]_{\sim}$ impliziert $x\sim a$ und somit $\exists A'\in\mathcal{A}:x,a\in A'$. Wegen der paarweisen Disjunktheit ist somit $x\in A'=A$.     []

1.11 Definition. Ordnungsrelationen.
Eine weitere wichtige Eigenschaft, auf die wir Relationen $\leq$ auf einer Menge $X$ untersuchen können, ist die Antisymmetrie, d.h. $\forall x,y\in X$: $x\leq y$ $\wedge$ $y\leq x$ $\Rightarrow$ $x=y$.

Eine Relation die reflexiv, antisymmetrisch und transitiv ist heißt Ordnungsrelation (oder auch partielle Ordnung).

Ein Beispiel dafür ist die Relation $\subseteq$ für Mengen.

Gilt zusätzlich die Dichothomie $x\leq y$ $\vee$ $y\leq x$, d.h. je zwei Elemente sind miteinander vergleichbar, so heißt die Ordnung linear oder auch totale Ordnung.

Ein Beispiel dafür ist die Relation $\leq$ für Zahlen.

Mittels solcher Relationen, können wir die Elemente einer Menge in eine Reihenfolge bringen.

Ordnungsrelationen auf einer endlichen Menge können wir mittels sogenannten Hasse-Diagramm veranschaulichen, wobei größere Elemente weiter oben stehen und Verbindungen die sich aus Reflexivität oder Transitivität ergeben nicht eingezeichnet werden. Z.B. für die Teilmengenrelation auf $\mathcal{P}(\{0,1,2\})$:

$$\xymatrix{ & &\{0,1,2\} & \\ \{0,1\}\ar@{-{}}... ...\ &\emptyset\ar@{-{}}[-2,0] \ar@{-{}}[-1,2] \ar@{-{}}[-1,-1] & & \\ }$$

1.12 Definition. Funktionen.
Unter einer Abbildung (oder Funktion) $f$ von $X$ nach $Y$ (man schreibt $f:X\to Y$ und nennt $X$ den Definitionsbereich und $Y$ den Wertebereich von $f$) versteht man eine Relation $f\subseteq A\times B$ mit der Eigenschaft, daß für jedes $x\in X$ genau ein $y\in Y$ existiert mit $(x,y)\in f$ (und man schreibt dann $f(x)$ für dieses $y$ oder auch $x\mapsto y$ und nennt es den Funktionswert von $x$ bezüglich der Funktion $f$). Wir können uns eine Abbildung $f:X\to Y$ als Programm (oder besser als eine blackbox) vorstellen, welches für jeden Input $x\in X$ einen wohldefinierten Output $y\in Y$ liefert.

Wir schreiben $Y^X$ für die Menge aller Abbildungen $f:X\to Y$. Die Motivation für diese Bezeichnungsweise ist, daß $\vert Y^X\vert=\vert Y\vert^{\vert X\vert}$ für endliches $X$ und $Y$ gilt, siehe (3.23).

Für Abbildungen $f:X\to Y$ und $A\subseteq X$ und $B\subseteq Y$ ist das Bild von $A$ unter $f$ definiert durch $f(A):=\{f(x):x\in A\}$

und das Urbild von $B$ unter $f$ definiert durch $f^{-1}(B):=\{x:f(x)\in B\}$.

Man kann Abbildungen $f:X\to Y$ und $g:Y\to Z$ zusammensetzen zu einer Abbildung $g\o f:X\to Z$, die definiert ist durch $(g\o f)(x):=g(f(x))$. Lies dies als ``g ring f'' oder ``g zusammengesetzt mit f''. Als Teilmenge $g\o f\subseteq X\times Z$ bedeutet dies

$$g\o f :=\{(x,z)\in X\times Z:\exists y\in Y:(x,y)\in f$$ und $$(y,z)\in g\}.$$

Wichtige Eigenschaften, auf die hin man Abbildungen $f:X\to Y$ untersuchen kann, sind:

• $f$ heißt injektiv, wenn aus $x\ne x'\Rightarrow f(x)\ne f(x')$, oder äquivalent wenn $f(x)=f(x')\Rightarrow x=x'$, d.h. jedes $y\in Y$ tritt höchstens für ein $x$ als Output unter $f$ auf. Nicht Injektivität läßt sich graphisch wie folgt darstellen:

  

• $f$ heißt surjektiv, wenn $f(X)=Y$ ist, also für jedes $y\in Y$ ein $x\in X$ mit $f(x)=y$ existiert, d.h. jedes $y\in Y$ tritt mindestens für ein $x$ als Output unter $f$ auf. Nicht Surjektivität läßt sich graphisch wie folgt darstellen:

  

• $f$ heißt bijektiv, wenn $f$ sowohl injektiv als auch surjektiv ist, d.h. zu jedem $y\in Y$ genau ein $x\in X$ existiert mit $f(x)=y$.

Beispiel.
Wir betrachten die Funktion $f(x):=x^2$ als Funktion zwischen folgenden Mengen wobei $\mathbb{R}^+:=\{x\in\mathbb{R}:x\geq 0\}$ bezeichnet:

• $f:\mathbb{R}\to\mathbb{R}$ ist weder injektiv noch surjektiv.
• $f:\mathbb{R}^+\to\mathbb{R}$ ist injektiv aber nicht surjektiv.
• $f:\mathbb{R}\to\mathbb{R}^+$ ist nicht injektiv aber surjektiv.
• $f:\mathbb{R}^+\to\mathbb{R}^+$ ist bijektiv.

1.13 Bemerkung.
Die Notation $g\o f$ für die Zusammensetzung von $f:X\to Y$ mit $g:Y\to Z$ ist keineswegs glücklich gewählt, denn dabei wirkt ja zuerst $f$ und dann $g$ auf einen Input $x\in X$. Würde man hier allerdings die Reihenfolge umdrehen, so wäre es wegen der definierenden Formel $(g\o f)(x):=g(f(x))$ zweckmäßig auch die rechte Seite besser als $((x)f)g$ zu schreiben, d.h. den Wert von $x$ bzgl. der Abbildung $f$ als $(x)f$ und nicht $f(x)$. Dies würde auch durchwegs der Idee entsprechen, daß ja $x$ genommen wird und darauf dann die Vorschrift $f$ angewandt wird, was auch der Schreibweise $x\overset{f}{\longmapsto} y$ entspricht. Die Definition der Zusammensetzung wäre dann $(x)(f\o g):=((x)f)g$. Allerdings ist dies fast allen MathematikerInnen doch eine zu radikale Veränderung alteingessener Bezeichnungsweisen und es würde zweifellos zu einem heillosen Durcheinander kommen, würden diese Bezeichnungsweise gleichzeitig verwendet werden. Im Sinne der kulturellen Vielfalt können wir wohl durchaus damit leben, daß Teile unserer Notation halt nicht europäisch von links nach rechts laufend geschrieben werden. Anhand vieler Beweise werden wir sowieso zum Schluß kommen, daß Mathematik nicht linear von sich geht. In diesem Sinn werden wir viele Relationssymbole in allen möglichen Orientierungen schreiben, wie z.B.

$$\begin{array}{ccccc} & & 1 & & \\ & & \wedge\... ...cup\hspace{-.70em}\shortmid\hspace{.25em} & & \\ & & 1 & & \end{array}$$

Mit Buchstaben sollten wir das natürlich besser nicht machen ;-),
z.B. $b\leq q$ im Gegensatz zu $p\geq d$.

Auch die Bezeichnung $f(A)$ für die Bildmenge und $f^{-1}(A)$ für Urbildmenge ist mit Vorsicht zu geniesen, denn wenn $f:X\to Y$ eine Abbildung ist dann kann für eine Teilmenge $A\subseteq X$ gleichzeitig auch $A\in X$ gelten und somit kann die Bildmenge $f(A)$ und der Funktionswert $f(A)$ etwas ganz verschiedenes sein. Wenn man dazuschreibt, ob man $A\in X$ oder $A\subseteq X$ betrachtet, so ist allerdings eine Mißverständnis ausgeschlossen.

Die grundlegenden Eigenschaften von Bild und Urbild faßt folgende Proposition zusammen:

1.14 Proposition.
Es sei $f:X\to Y$ eine Abbildung, $A,A'\subseteq X$, $B,B'\subseteq Y$, $\mathcal{A}\subseteq \mathcal{P}(X)$ und $\mathcal{B}\subseteq \mathcal{P}(Y)$. Dann gilt:

$$(0)\quad A\subseteq f^{-1}(B)\;\Leftrightarrow\;f(A)\subseteq B;$$

$$(1)\quad A\subseteq f^{-1}(f(A)); (1')\quad B\supseteq f(f^{-1}(B));$$

$$(2)\quad A\subseteq A'\;\Rightarrow\;f(A)\subseteq f(A'); (2')\quad B\subseteq B'\;\Rightarrow\;f^{-1}(B)\subseteq f^{-1}(B');$$

$$(3)\quad f\Bigl(\bigcap\mathcal{A}\Bigr)\subseteq \bigcap_{A\in\mathcal{A}}f(A); (3')\quad f^{-1}\Bigl(\bigcap\mathcal{B}\Bigr)= \bigcap_{B\in\mathcal{B}}f^{-1}(B);$$

$$(4)\quad f\Bigl(\bigcup\mathcal{A}\Bigr)=\bigcup_{A\in\mathcal{A}}f(A); (4')\quad f^{-1}\Bigl(\bigcup\mathcal{B}\Bigr)= \bigcup_{B\in\mathcal{B}}f^{-1}(B);$$

$$(5')\quad f^{-1}(B^c)=f^{-1}(B)^c.$$

Visualisieren kann man diese Aussagen folgendermaßen:

Verbale Formulierungen sind z.B.:

(0)

$A$ liegt genau dann im Urbild von $B$, wenn das Bild von $A$ in $B$ liegt.

(1)

Jede Menge liegt im Urbild ihres Bildes.

(1')

Jede Menge enthält das Bild ihres Urbilds.

(2)

Sind zwei Mengen ineinander enthalten, so auch ihre Bilder.

(2')

Sind zwei Mengen ineinander enthalten, so auch ihre Urbilder.

(3)

Das Bild eines Durchschnitts ist im Durchschnitt der Bilder enthalten, d.h. Elemente, die Bilder eines Elements sind, welches in allen $A\in\mathcal{A}$ liegt, liegt in den Bildern $f(A)$ aller $A\in\mathcal{A}$.

(3')

Das Urbild eines Durchschnitts ist der Durchschnitt der Urbilder, d.h. ein Element hat genau dann Bild in allen $B\in\mathcal{B}$, wenn für alle $B\in\mathcal{B}$ sein Bild in $B$ liegt.

(4)

Die Bilder jener Elemente die in mindestens einen $A\in\mathcal{A}$ liegen sind genau jene Objekte die in mindestens einen Bild $f(A)$ mit $A\in\mathcal{A}$ liegen.

(4')

Das Urbild einer Vereinigung ist die Vereinigung der Urbilder, d.h. das Bild eines Element liegt genau dann in mindestens einen $B\in\mathcal{B}$, wenn für mindestens ein $B\in\mathcal{B}$ sein Bild in $B$ liegt.

(5')

Das Urbild des Komplements ist das Komplement des Urbilds, d.h. das Bild eines Elements liegt genau dann nicht in $B$, wenn nicht stimmt, daß das Bild des Elements in $B$ liegt.

Beweis. (0)

$$A\subseteq f^{-1}(B) \Leftrightarrow \forall x\in A:x\in f^{-1}(B)$$

$$\Leftrightarrow \forall x\in A:y:=f(x)\in B$$

$$\Leftrightarrow \forall y\in f(A):y\in B$$

$$\Leftrightarrow f(A)\subseteq B$$

(1) $A\subseteq f^{-1}(f(A))$ nach (0), da $f(A)\subseteq f(A)$.

(2) Sei $A\subseteq A'$, $y\in f(A)$, d.h. $\exists a\in A:y=f(a)$. Somit ist $a\in A\subseteq A'$ und damit $y=f(a)\in f(A')$.

(3)

$$y\in f(\bigcap\mathcal{A}) \Leftrightarrow \exists a\in\bigcap\mathcal{A}:y=f(a)$$

$$\Leftrightarrow \exists a\forall A\in\mathcal{A}:a\in A y=f(a)$$

$$\Rightarrow \forall A\in\mathcal{A}\exists a\in A:y=f(a)$$

$$\Leftrightarrow \forall A\in\mathcal{A}:y\in f(A)$$

$$\Leftrightarrow :y\in \bigcap_{A\in\mathcal{A}}f(A)$$

(4)

$$y\in f(\bigcup\mathcal{A}) \Leftrightarrow \exists a\in\bigcup\mathcal{A}:y=f(a)$$

$$\Leftrightarrow \exists a\exists A\in\mathcal{A}:a\in A y=f(a)$$

$$\Leftrightarrow \exists A\in\mathcal{A}\exists a\in A y=f(a)$$

$$\Leftrightarrow \exists A\in\mathcal{A}:y\in f(A)$$

$$\Leftrightarrow y\in \bigcup_{A\in\mathcal{A}}f(A)$$

(5')

$$x\in f^{-1}(B^c) \Leftrightarrow f(x)\in B^c$$

$$\Leftrightarrow f(x)\notin B$$

$$\Leftrightarrow f(x)\in B$$

$$\Leftrightarrow x\in f^{-1}(B)$$

$$\Leftrightarrow x\notin f^{-1}(B)$$

$$\Leftrightarrow x\in f^{-1}(B)^c$$

    []

Beachte, daß in (3) nicht Gleichheit gilt: Es sei $f:\mathbb{R}\to\mathbb{R}$ die Funktion $f(x):=x^2$, $A:=\{x:x\geq 0\}$ und $A':=\{x:x\leq 0\}$. Dann ist $f(A)=f(A')=\{x:x\geq 0\}=f(A)\cap f(A')$, aber $A\cap A'=\{0\}$ und somit auch $f(A\cap A')=\{0\}\ne f(A)\cap f(A')$.

Der Grund warum der Beweis für Gleichheit nicht funktioniert ist, daß zwar ``es gibt ein $a$, sodaß für alle $A$ eine Aussage gilt'' zur Folge hat, daß ``für jedes $A$ ein $a$ existiert, sodaß dieselbe Aussage gilt'' jedoch nicht umgekehrt. Man vergleiche z.B. ``Jeder Mensch besitzt eine Mutter'' mit ``Es gibt eine Frau die Mutter von jedem Menschen ist''. Oder auch ``jeder wird von jemanden geliebt'' im Gegensatz zu ``Es gibt jemanden der jeden liebt''.

1.16 Proposition.
Es sei $f:X\to Y$ eine Abbildung und $X\ne\emptyset$. Dann gilt:

• $f$ ist injektiv $\Leftrightarrow$ $\exists g:Y\to X$: $g\o f=\operatorname{id}_X$.
• $f$ ist surjektiv $\Leftrightarrow$ $\exists g:Y\to X$: $f\o g=\operatorname{id}_Y$.
• $f$ ist bijektiv $\Leftrightarrow$ $\exists g:Y\to X$ mit $f\o g=\operatorname{id}_Y$ und $g\o f=\operatorname{id}_X$.

Beweis. (1) ( $\Rightarrow$) Es sei $f$ injektiv und $X\ne 0$. Dann wählen wir ein $x_0\in X$ und definieren

$$g:y\mapsto \begin{cases}x &\text{falls }f(x)=y \\ x_0 &\text{falls }y\notin f(X) \end{cases}.$$

Wegen der Injektivität ist $g$ wohldefiniert und offensichtlich gilt $g\o f=\operatorname{id}_X$.

( $\Leftarrow$) Umgekehrt sei $g\o f=\operatorname{id}_X$ und $f(x_1)=f(x_2)$. Dann ist $x_1=g(f(x_1))=g(f(x_2))=x_2$, also $f$ injektiv.

(2) ( $\Rightarrow$) Sei nun $f$ surjektiv. Für jedes $y\in Y$ wählen wir ein zugehöriges $x\in f^{-1}(y)\subseteq X$ (Das dies wirklich möglich ist, ist das Auswahlaxiom der Mengenlehre) und setzen $g(y):=x$. Dann ist $g:Y\to X$ eine wohldefinierte Funktion mit $f\o g=\operatorname{id}_Y$.

( $\Leftarrow$) Umgekehrt sei $f\o g=\operatorname{id}_Y$ und $y\in Y$. Es ist $x:=g(y)\in X$ und $f(x)=y$, d.h. $f$ ist surjektiv.

(3) ( $\Rightarrow$) Entweder man definiert $f^{-1}:=\{(y,x)\in Y\times X:x,y\in f\}$ und rechnet leicht nach, daß diese Relation eine Abbildung ist, welche invers zu $f$ ist, oder man verwendet (1) und (2) und erhält ein linksinverses $g$ und ein rechtsinverses $h$. Dann ist

$$g=g\o\operatorname{id}_Y=g\o (f\o h)=(g\o f)\o h=\operatorname{id}_X\o h=h.$$

( $\Leftarrow$) Dies folgt sofort aus (1) und (2).     []

1.15 Bemerkung.
Die eindeutige Abbildung $g:Y\to X$ mit $f\o g=\operatorname{id}_Y$ und $g\o f=\operatorname{id}_X$, die für bijektive $f:X\to Y$ existiert, heißt Umkehrfunktion von $f$ oder auch inverse Funktion zu $f$ und wird auch als $f^{-1}$ bezeichnet.

Falls $f$ bijektiv ist, so ist das Urbild $f^{-1}(B)$ von $B$ bzgl. der Funktion $f$ gerade das Bild von $B$ bzgl. der Umkehrfunktion $f^{-1}$ von $f$. Beachte jedoch, daß $f^{-1}(B)$ auch dann definiert ist, wenn $f^{-1}$ als Abbildung nicht existiert.

1.17 Definition.
Es sei $f:V\to W$ eine Abbildung und $U\subseteq V$ eine Teilmenge. Unter der Einschränkung $f\vert _U$ verstehen wir die Abbildung $f\vert _U:U\to W$, die auf $x\in U$ mit $f$ übereinstimmt, also durch $f\vert _U(x):=f(x)$ gegeben ist. Als Teilmenge von $U\times W$ ist also $f\vert _U:=\{(v,w)\in U\times W:(v,w)\in f\}=f\cap (U\times W)$.

1.18 Um Mengen der Größe nach miteinander vergleichen zu können, können wir für endliche Mengen natürlich die Anzahlen der Elemente bestimmen und diese dann vergleichen. Ohne wirklich zählen zu können gibt es aber auch eine andere Möglichkeit: Um z.B. festzustellen, ob gleichviele HöhrerInnen wie Sitzplätze vorhanden sind, bittet man darum, daß sich alle setzten und falls weder leere Sitze überbleiben noch Personen stehenbleiben, dann sind es gleich viele. Mathematisch kann man das so beschreiben, daß versucht wird jeder Person $x$ einen Platz $y$ so zuzuordnen, daß keine zwei Personen den gleichen Platz angewiesen bekommen und auch kein Platz übrigbleibt, d.h. diese Zuordnung $f$ von der Menge aller Personen in die Menge aller Plätze bijektiv ist. Dieses Verfahren können wir auch bei unendlichen Mengen durchführen und geben dazu folgende

Definition.
Wir schreiben $X\cong Y$ (oder auch $X\sim Y$), falls $X$ und $Y$ gleichmächtig sind, d.h. eine bijektive Abbildung $f:X\to Y$ existiert. Eine Menge $X$ heißt abzählbar (unendlich) falls sich gleichmächtig mit der Menge $\mathbb{N}:=\{0,1,2,\dots\}$ der natürlichen Zahlen ist.

Eine Menge heißt endlich, falls sie nur endlich viele Elemente besitzt, also gleichmächtig zu einer natürlichen Zahl $n:=\{0,1,\dots,n-1\}\in\mathbb{N}$ ist.

1.19 Bemerkung.
Im Unterschied zu endlichen Mengen, kann eine unendliche Menge durchaus gleichmächtig mit einer echten Teilmenge sein. Z.B. definiert $x\mapsto x+1$ eine bijektive Abbildung $f:\mathbb{N}\to \mathbb{N}\setminus\{0\}\subset\mathbb{N}$.

Veranschaulichen kann man sich dies wie folgt: Man betrachtet Hilbert's Hotel, ein Hotel mit abzählbar unendlich vielen Zimmern, die mit den natürlichen Zahlen 0,1,2,...durchnumeriert sind. Diese Hotel sei voll belegt und es kommt ein neuer Gast, welcher dadurch untergebracht werden kann, daß man die bereits einquartierten Gäste bittet jeweils in das Zimmer mit der nächst höheren Nummer zu wechseln und somit Zimmer 0 freibekommt.

Man kann sogar eine unendliche Teilmenge entfernen ohne die Gleichmächtigkeit zu stören: Betrachte die Menge $\Bbb G:=\{2k:k\in\mathbb{N}\}$ der gerade Zahlen. Dann definiert $n\mapsto 2n$ eine bijektive Abbildung $\mathbb{N}\to \Bbb G$. Und für die Menge $\mathbb{N}\setminus \Bbb G$ der ungeraden Zahlen gilt ebenfalls $\mathbb{N}\cong\mathbb{N}\setminus\Bbb G$ vermöge $n\mapsto 2n+1$. Es ist also $\mathbb{N}$ die disjunkte Vereinigung $\Bbb G\cup (\mathbb{N}\setminus\Bbb G)$ und beide Teilmengen sind gleichmächtig mit $\mathbb{N}$.

Ebenso ist $\mathbb{Z}\cong\mathbb{N}$, denn $\mathbb{Z}=\{n:n\geq 0\}\cup \{-n:n>0\}$ und $\{n:n\geq 0\}=\mathbb{N}\cong \Bbb G$ sowie $\{-n:n> 0\}\cong \{n:n>0\}\cong\mathbb{N}\cong \mathbb{N}\setminus\Bbb G$, also $\mathbb{Z}=\{n:n>0\}\cup \{-n:n>0\}\cong \Bbb G\cup (\mathbb{N}\setminus\Bbb G)=\mathbb{N}$ nach Übungsaufgabe (43).

Veranschaulichen kann man sich das wieder durch Hilbert's Hotel. Diesmal kommt ein Reisebus mit abzählbar unendlich vielen Passagieren die alle untergebracht werden sollen. Diesmal werden die bereits einquartierten Gäste gebeten jeweils in das Zimmer mit der doppelt so großen Nummer zu wechseln. Dann werden alle Zimmer mit ungerader Nummer frei und wir können die Passagiere des Reisebusses in diesen abzählbar unendlich vielen Zimmern unterbringen.

Aber auch $\mathbb{N}^2:=\mathbb{N}\times \mathbb{N}$ ist abzählbar. Dazu numeriere man die Punkte in $\mathbb{N}^2$ wie folgt:

$$\begin{array}{rrrrrrrr} 0 & 1 & 3 & 6 & 10& 15... ... & & & & \\ 20& \cdot& & & & & & \\ \cdot& & & & & & & \\ \end{array}$$

Eine andere Bijektion $f:\mathbb{N}\times \mathbb{N}\to\mathbb{N}$ ist durch $f(n,m):=(2m+1)2^n-1$ gegeben. Dabei stehen in der $n$-ten Zeile gerade jene Zahlen, die um 1 vermehrt in der Dualzahlentwicklung von rechts gelesen genau $n$ 0'er stehen haben.

Das bedeutet also, daß selbst wenn auf abzählbar unendlich vielen Welten jeweils ein voll belegtes Hotel von Hilbert steht und aus Einsparungsgründen alle bis auf ein Hotel aufgelöst werden sollen, dann kann man den Gästen, die durch Hotelnummer und Zimmernummer beschrieben werden können (also durch Punkte in $\mathbb{N}\times \mathbb{N}$), auf eindeutige Weise neue Zimmernummern in $\mathbb{N}$ des verbleibenden Hotels zuweisen.

In Übungsaufgabe (44) werden wird zeigen, daß die Menge aller endlichen Folgen natürlicher Zahlen ebenfalls abzählbar ist, und somit auch die Menge der Polynome mit rationalen Koeffizienten und ebenso die Menge der algebraischen Zahlen, d.h. Nullstellen solcher Polynome. Aus dem gleichen Argument ist auch die Menge aller möglichen (endlich langen) Worte (die mittels Buchstaben aus einen abzählbaren Alphabet gebildet werden können) abzählbar und ebenfalls die Menge aller mögliche (endlichen) Sätze und genauso aller (endlichen) Bücher.

Daß es aber auch echt mächtigere unendliche Mengen (sogenannte überabzählbare Mengen) gibt, war eine von Cantor's wesentlichen Erkenntnissen:

1.20 Proposition.
Es sei $X$ eine Menge. Dann ist die Potenzmenge $\mathcal{P}(X)$ nicht gleichmächtig mit $X$.

Offensichtlich definiert $x\mapsto \{x\}$ eine injektive Abbildung $X\to\mathcal{P}(X)$, und somit ist $\mathcal{P}(X)$ entscheidend größer als $X$.

Beweis. Angenommen es gäbe eine surjektive Abbildung $f:X\to \mathcal{P}(X)$. Dann betrachten wir die Menge $A:=\{x\in X:x\notin f(x)\}\subseteq X$. Nach Voraussetzung existiert ein $a\in X$ mit $f(a)=A$. Falls $a\in A=\{x\in X:x\notin f(x)\}$ liegt, so folgt $a\notin f(a)=A$, ein Widerspruch. Also kann nur $a\notin A=\{x\in X:x\notin f(x)\}$ gelten und damit nicht $a\notin f(a)=A$ also $a\in A$, ebenfalls ein Widerspruch. Folglich muß die Annahme, daß $f$ surjektiv ist, falsch sein.     []

Bemerkung.
Ähnlich zeigt man, daß die Menge der reellen Zahlen nicht abzählbar ist.

1.21 Definition.
Es sei $\mathcal{A}$ eine Menge von Mengen. Unter dem Produkt $\prod\mathcal{A}$ versteht man die Menge

$$\prod\mathcal{A}:=\Bigl\{f:\mathcal{A}\to\bigcup\mathcal{A}:\forall A\in\mathcal{A}:f(A)\in A\Bigr\}.$$

Im Falle $\mathcal{A}=\{A_i:i\in I\}$ schreibt man

$$\prod_{i\in I}A_i := \prod\mathcal{A}.$$

Im Fall $\mathcal{A}=\{A,B\}$ ist $\prod \{A,B\}\ne A\times B$ im Unterschied zu Vereinigung und Durchschnitt, jedoch gilt $\prod\{A,B\}\cong A\times B$ vermöge $\prod\{A,B\}\ni f\mapsto (f(A),f(B))\in A\times B$, siehe Aufgabe (37). Beachte auch, daß nach Aufgabe (38) zwar $A\times B\ne B\times A$ aber zumindest $A\times B\cong B\times A$ gilt. Und nach Aufgabe (40) ist das Produkt $\prod$ assoziativ.