1.3 Korrespondenzen, Relationen, Abbildungen

Unser nächstes Ziel besteht darin, den Begriff der Zuordnung mathematisch, d.h. mengentheoretisch, zu präzisieren. Wenn wir davon gesprochen haben, daß eine zweistellige Operation $\Box$ je zwei Elementen a, b einer Menge G ein Element $a \Box b$ aus G eindeutig zuordnet, so haben wir dabei an die Anschauung appelliert, aber nicht gesagt, was Zuordnen eigentlich ist.

1.3.1 Geordnetes Paar und Cartesisches Produkt

Der einfachste Fall einer Zuordnung liegt vor, wenn einem einzigen Element a ein Element b zugeordnet ist, was man z.B. durch $\left[a, b\right]$notieren kann. Die erste Komponente dieses sogenannten geordneten Paares, das Element a, wird in einen Zusammenhang gesetzt mit der zweiten Komponente, dem Element b; dem a wird das b zugeordnet und nicht umgekehrt -- es kommt also auf die Reihenfolge der Komponenten (Elemente) an. Für geordnete Paare $\left[a, b\right]$, $\left[c, d\right]$muß also gelten

$$\left[a, b\right] = \left[c, d\right] \;\mbox{gdw.} \; a = c \;\mbox{und} \; b = d$$

Diese Eigenschaft ist die grundlegende Eigenschaft geordneter Paare, sie kann zur axiomatischen Charakterisierung dieses Begriffs verwendet werden. Wir können aber diesen Begriff mengentheoretisch wie folgt definieren:

Definition 1.3.1 (Geordnetes Paar)
 Es seien a, b beliebige Elemente. Dann ist das geordnete Paar $\left[a, b\right]$ das Mengensystem

$$\left[a, b\right] \defg \left\{ \left\{a\right\}, \left\{a, b\right\} \right\}\mbox{.}$$

Man kann nun beweisen

Satz 1.3.2
Für beliebige Elemente a, b, c, d gilt

$$\left[a, b\right] = \left[c, d\right] \;\mbox{gdw.} \; a = c \;\mbox{und} \; b = d \mbox{.}$$

Durch wiederholte Paarbildung kann man nun den Begriff des geordneten Tripels, Quadrupels, ...(allgemein:) den des n-Tupels einführen. Dazu überträgt man die Definition von Elementen a, b auf beliebige Mengen a, b gleicher Stufe und definiert dann:

Definition 1.3.3
Es seien $a, b, c, d, a_1, a_2, \cdots$ beliebige Elemente.

• $\left[a, b, c\right] \defg \left[\left[a, b\right], \left\{\left\{c\right\}\right\}\right]$ (Tripel)
• $\left[a, b, c, d\right] \defg \left[\left[a, b, c\right], \left\{\left\{\left\{\left\{d\right\}\right\}\right\}\right\}\right]$ (Quadrupel)
  $\vdots$ $\vdots$
• $\left[a_1,\ldots , a_n\right] \defg [\left[a_1, \ldots , a_{n-1}\right], \und... ...{\{\cdots\{}_{2\left(n-2\right)}a_n\underbrace{\}\cdots\}}_{2\left(n-2\right)}]$ (n-Tupel)

Man zeigt durch Induktion über $n \geq 2$:

Satz 1.3.4
$\left[a_1, \ldots ,a_n\right] = \left[b_1, \ldots , b_n\right]$ gdw. a₁ = b₁ und ...und a_n = b_n.

Einfachste Zuordnungen der Form ,,a geht über in b`` können wir also durch das geordnete Paar $\left[a, b\right]$ beschreiben, kompliziertere Zuordnungen werden wir durch Mengen geordneter Paare beschreiben.

Definition 1.3.5 (Cartesisches Produkt)
Es seien $M_1, M_2, \ldots ,M_n$ Mengen (gleicher Stufe). Das CARTESISCHE Produkt (direktes Produkt, Kreuzprodukt) von $M_1, \ldots , M_n$ in dieser Reihenfolgen) ist die Menge

$$M_1 \times M_2 \defg\left\{\left[a, b\right]\vert\, a \in M_1 \;\mbox{und}\; b \in M_2 \right\} \mbox{.}$$

bzw.

$$M_1 \times \cdots \times M_n \defg\left\{\left[a_1, \ldots , ... ...in M_1 \;\mbox{und \ldots und}\; a_n \in M_n \right\} \mbox{.}$$

Nach dieser Definition kann das CARTESISCHE Produkt nur zwischen Mengen gleicher Stufe gebildet werden. Man braucht aber auch Produkte zwischen Mengen verschiedener Stufen, z.B. wenn man eine Zuordnung beschreiben will, die jedem Element eine gewisse Menge zuordnet. Eine Definition läßt sich ebenfalls angeben, wir verzichten hier darauf und gehen im folgenden davon aus, daß für beliebige Mengen N, K das Kreuzprodukt definiert ist. Wichtige Eigenschaften des Produkts formulieren wir als

Satz 1.3.6

1.

$M \times N = \emptyset$ gdw. $M = \emptyset$ oder $N = \emptyset$

2.

Wenn $M\subseteq N$, so $M \times K \subseteq N \times K$ und $K \times M \subseteq K \times N$.

3.

$M \times \left(N \cup K \right) = \left( M \times N\right) \cup \left( M \times K\right)$

4.

$M \times \left(N \cap K \right) = \left( M \times N\right) \cap \left( M \times K\right)$

1.3.2 Korrespondenzen

Wir sind nun in der Lage, den Begriff der Zuordnung, wir sagen ,,Korrespondenz`` mengentheoretisch zu definieren:

Definition 1.3.7 (Korrespondenz)
Es seien M, N Mengen. Dann wird K eine Korrespondenz aus M in N(bzw. zwischen M und N) genannt, wenn $K \subseteq M \times N$ ist.

Beispiele

• Es sei $M = N = \mbox{\N }$ (die Menge der natürlichen Zahlen) und
  
  $$\begin{eqnarray*}\leq & = & \left\{ \left[a, b\right] \vert a, b \in \mbox{\N\ u... ...er gleich $b$ }\right\} \subseteq \mbox{\N } \times \mbox{\N } \end{eqnarray*}$$
  
  
• Es sei $M = \mbox{\N }$, $N = \left\{\mbox{wahr}, \mbox{falsch}\right\}$ (die Menge der Wahrheitswerte) und
  
  $$P_2 = \parbox[t]{10cm}{$\{ \left[a, \alpha\right] \vert a \in... ...der [$a$\space ist Primzahl und $\alpha =$\space wahr]}\} $ }$$
  
  

• Es sei $M = \left\{1, \ldots ,99\right\}$, N die Menge aller Straßennamen in Berlin und
  
  $$\begin{eqnarray*}F & = & \parbox[t]{10cm}{$\{\left[a, x\right] \vert a \in M \;\... ...ie Nr.$a$\space f\uml {u}hrt durch die Stra\ss{}e $x\} $\space } \end{eqnarray*}$$
  
  
• Es sei A eine Menge, dann bezeichnet I_A die Identität über A mit
  
  $$\begin{eqnarray*}I_A & \defg & \left\{[a,a] \mid a\in A \right\} \end{eqnarray*}$$
  
  

Ist K eine Korrespondenz, so schreiben wir für $\left[a, b\right] \in K$auch aKb und sagen dafür ,,a steht zu b in Korrespondenz K`` oder ,,b ist ein K-Bild von a`` oder ,,a ist ein K-Urbild von b``. Unser erstes Beispiel zeigt, daß ein Element im allgemeinen mehrere Bilder oder Urbilder haben kann; das dritte Beispiel zeigt, daß ein Element kein Bild bzw. Urbild haben muß.

Definition 1.3.8 (Benennungen von Korrespondenzen)
Es sei $K \subseteq M \times N$ eine Korrespondenz zwischen M und N.

1.

Der Definitionsbereich (Argumentenbereich, Vorbereich) von K ist die Menge D_K der Elemente von M, die K-Urbilder eines Elementes von N sind, d.h.

$$D_K \defg\left\{ a \vert \;\mbox{Es gibt ein $b$\space mit $\left[a, b\right] \in K$ }\right\}$$

2.

Der Bildbereich (Wertebereich, Nachbereich) von K ist die Menge B_K der Elemente von N, die K-Bild eines Elementes von M sind, d.h.

$$B_K \defg\left\{ b \vert \;\mbox{Es gibt ein $a$\space mit $\left[a, b\right] \in K$ }\right\}$$

3.

K heißt Korrespondenz von M in N, wenn D_K = M ist

4.

K heißt Korrespondenz aus M auf N, wenn B_K = N ist

5.

K heißt Korrespondenz von M auf N, wenn D_K = M ist und B_K = N ist.

6.

Die Korrespondenz K wird eindeutig genannt, wenn zu jedem $a \in M$ höchstens ein $b \in N$ (eventuell keines) mit $\left[a, b\right] \in K$ existiert.

7.

Die Korrespondenz K wird eindeutig umkehrbar genannt, wenn es zu jedem $b \in N$ höchstens ein $a \in M$ mit $\left[a, b\right] \in K$ gibt

Beispiele
Die Korrespondenzen $\leq$, P₂ und I_A sind Korrespondenzen von-auf, bei F ist das nicht der Fall; ferner ist P₂ eindeutig, aber nicht eindeutig umkehrbar; I_A ist dagegen eindeutig umkehrbar.

Definition 1.3.9 (Verkettung und Inversion)
Es seien K und L Korrespondenzen, $K \subseteq A \times B$, $L \subseteq C \times D$.

1.

Die Verkettung $K \circ L$ von K mit L ist die Menge

$$K \circ L \defg\left\{ \left[a, d\right] \vert \mbox{ Es gibt... ...b\right] \in K$\space und $\left[b, d\right] \in L$ }\right\}$$

2.

Die Inversion K^-1 von K ist die Menge

$$K^{-1} \defg\left\{\left[b, a\right] \vert \left[a, b\right] \in K\right\}$$

Man zeigt nun:

Satz 1.3.10
Es seien $K \subseteq A \times B$, $L \subseteq C \times D$ Korrespondenzen.

1.

$K \circ L$ ist eine Korrespondenz zwischen A und D

2.

Die Verkettung ist eine assoziative Operation

3.

Die Identität I_E über dem Objektbereich E ist neutrales Element, d.h.
$K \circ I_E = I_E \circ K = K$

4.

$K \circ L = \emptyset$ genau dann, wenn $B_K \cap D_L = \emptyset$.

5.

K^-1 ist eine Korrespondenz zwischen B und A

6.

$\left(K^{-1}\right)^{-1} = K$

7.

$\left(K \circ L\right)^{-1} = L^{-1} \circ K^{-1}$.

Übung 11
Man beweise die Aussagen des vorstehenden Satzes.

1.3.3 Relationen

Korrespondenzen aus einer Menge A in diese Menge selbst, werden als Relationen bezeichnet:

Definition 1.3.11 (Relation)
R wird binäre (zweistellige) Relation in A genannt, wenn $R \subseteq A \times A$ ist. Ist dabei $D_R \cup B_R = A$, so heißt R Relation über A.

Beispiele

• $\leq$ ist eine Relation über
• I_E ist eine Relation über E
• die leere Menge $\nset{\emptyset}{3}$ dritter Stufe ist eine Relation in jeder Menge erster Stufe
• $A \times A$ ist eine Relation über A (die Allrelation über A).

Bemerkung
Ist R eine binäre Relation, d.h. $R \subseteq A \times A$, so schreiben wir statt $[a,b]\in R$ häufig aRb.

Für Relationen werden wir einige Begriffe, die wir weiter oben schon benutzt haben, allgemein zusammenfassen mit folgender

Definition 1.3.12
Sei R eine Relation in der Menge A. R heißt

1.

reflexiv wenn für alle $a\in A$ gilt: aRa

2.

irreflexiv wenn für kein $a\in A$ gilt: aRa

3.

transitiv wenn für alle $a,b,c\in A$ gilt: wenn aRb und bRc, so aRc

4.

antisymmetrisch wenn für alle $a,b\in A$ gilt: wenn aRb und bRa, so a=b

5.

asymmetrisch wenn für alle $a,b\in A$ gilt: wenn aRb, so nicht bRa

6.

symmetrisch wenn für alle $a,b\in A$ gilt: wenn aRb, so bRa

Eine Relation R heißt

1.

reflexive Halbordnung
wenn R reflexiv, transitiv und antisymmetrisch ist

2.

irreflexive Halbordnung
wenn R irreflexiv, transitiv und asymmetrisch ist

3.

Äquivalenzrelation
wenn R reflexiv, transitiv und symmetrisch ist

Der Vollständigkeit halber haben wir hier schon den Begriff der Äquivalenzrelation genannt, der weiter unten ausführlicher behandelt wird.

Wie wir später sehen werden, spielen reflexive und transitive Relationen in der Mathematik eine große Rolle -- Äquivalenzrelationen und reflexive Ordnungsrelationen haben diese Eigenschaften. Deshalb interessiert eine Operation, die (ausgehend von einer Relation ohne diese Eigenschaften) die bezüglich $\subseteq$ kleinste reflexive und transitive Relation R' mit $R \subseteq R'$ als Resultat liefert.

Definition 1.3.13 (reflexiv-transitive Hülle)
Es sei R eine Relation über A. Wir setzen

• R⁰ = I_A
• $R^{i+1} = R^i \circ R$
• $\left\langle R\right\rangle \defg\bigcup \left\{ R^0, R^1, \ldots\right\} = \bigcup_{i \in \mbox{\N }} R^i$

Die Menge $\left\langle R\right\rangle$ wird als reflexiv-transitive Hülle von R bezeichnet.

Man überlegt sich sofort

Satz 1.3.14
 Es sei R Relation über A

1.

$\left\langle R\right\rangle$ ist eine Relation über A

2.

$\left\langle R\right\rangle$ ist reflexiv über A, d.h. für alle $a\in A$ gilt: $a\left\langle R\right\rangle a$

3.

$\left\langle R\right\rangle$ ist transitiv über A, d.h. für alle $a,b,c\in A$ gilt:
wenn $a\left\langle R\right\rangle b$, $b\left\langle R\right\rangle c$, so $a \left\langle R\right\rangle c$

Beweis
der einzelnen Aussagen:

1.

es ist zu zeigen: $\left\langle R \right\rangle \subseteq A \times A$ und $D_{\left\langle R\right\rangle} = A$, woraus $D_{\left\langle R\right\rangle} \cup B_{\left\langle R\right\rangle} = A$ folgt.

2.

gilt offensichtlich, weil $I_A \subseteq \left\langle R\right\rangle$ ist.

3.

Wegen $a\left\langle R\right\rangle b$, $b\left\langle R\right\rangle c$ gibt es Zahlen $i, j \geq 0$ mit aRⁱb, bR^jc. Bei i=0 folgt a=b, also aR^jc, d.h. $a \left\langle R\right\rangle c$. Analog schließt man bei j=0.

Sei i>0. Man überlegt sich (durch Induktion über i) daß in diesem Fall Elemente $a_1, \ldots ,a_{i+1} \in A$ existieren mit a₁ = a, a_i+1 = b und a_lRa_l+1 für $l = 1, \ldots ,i$.

Analog existieren Elemente $b_1, \ldots ,b_{j+1}$ mit b₁ = b, b_j+1 = c und b_kRb_k+1 für $k = 1, \ldots , j$.

Daraus folgt $\left[a, c\right] \in R^{i+j} \subseteq \left\langle R\right\rangle$, d.h. $a \left\langle R\right\rangle c$.

Der Gebrauch der Bezeichnung ,,Hülle`` ist in der Mathematik für solche Operationen reserviert, die die sogenannten Hülleneigenschaften haben:

Definition Hüllenoperation

Eine Operation $Op:\goth{P} (A)\rightarrow \goth{P} (A)$ heißt Hüllenoperation, wenn folgende Eigenschaften gelten:

1.

$M\subseteq Op(M)$(Satz der Einbettung)

2.

Wenn $M\subseteq N$, so $Op(M)\subseteq Op(N)$ (Satz der Monotonie)

3.

Op(Op(M))=Op(M)(Satz der Abgeschlossenheit)

Op erfüllt den Endlichkeitssatz, wenn für alle $a\in A,M\subseteq A$ gilt:
Wenn $a\in Op(M)$, so existiert eine endliche Teilmenge $M^\ast \subseteq M$ mit $a\in Op(M^\ast)$.

Satz 1.3.15
Die Operation $\kleene{\ }$ hat die Hülleneigenschaften, d.h. es gilt

1.

$R \subseteq \left\langle R\right\rangle$

2.

Wenn $R_1 \subseteq R_2$, so $\left\langle R_1\right\rangle \subseteq \left\langle R_2\right\rangle$

3.

$\left\langle\left\langle R\right\rangle\right\rangle = \left\langle R\right\rangle$

Überdies erfüllt die Operation $\kleene{\ }$ den Endlichkeitssatz:

$$[a,b]\in\kleene{R}\mbox{, so existiert eine endliche Teilmenge }R'\subseteq R\mbox{ mit }[a,b]\in\kleene{R'}$$

Übung 12
Man beweise den vorstehenden Satz.

Ferner gilt der bereits oben erwähnte

Satz 1.3.16
Es sei R eine Relation über A. Dann ist $\left\langle R\right\rangle$ die bezüglich $\subseteq$kleinste reflexive und transitive Relation R' mit $R \subseteq R'$, d.h. für alle Relationen R' über A gilt: Wenn $R \subseteq R'$ und R' ist reflexiv und transitiv, so ist $\left\langle R\right\rangle \subseteq R'$.

Beweis
Daß $\left\langle R\right\rangle$ reflexiv und transitiv ist, sagt Satz . Aus dem Satz der Einbettung haben wir $R \subseteq \left\langle R\right\rangle$. Ist $R \subseteq R'$, so ist $\left\langle R\right\rangle \subseteq \left\langle R'\right\rangle$wegen der Monotonie. Für reflexive und transitive Relationen R' gilt aber $R' = \left\langle R'\right\rangle$, denn aus der Reflexivität von R' über Afolgt $R^0 = I_A \subseteq R'$ und aus der Transitivität von R'folgt $R' \circ R' = R'$, d.h. $\left(R'\right)^i \subseteq R'$. Also ist $\left\langle R\right\rangle \subseteq \left\langle R' \right\rangle = R'$.

In analoger Weise wie zweistellige Korrespondenzen definiert man n-stellige Korrespondenzen zwischen Mengen $M_1, \ldots , M_n$und n-stellige Relationen R in A als

$$R \subseteq A \times \cdots \times A = \timesu{n} A \mbox{.}$$

1.3.4 Abbildungen

Wir wenden uns nun dem Begriff der Abbildung zu.

Definition 1.3.17 (Abbildung und deren Benennung)
Es seien A, B Mengen

1.

f heißt Abbildung von A in B, wenn

(a)

f eine Korrespondenz von A in B und

(b)

f eindeutig ist.

2.

Eine Abbildung f wird surjektiv genannt (oder Abbildung auf B), wenn B_f = B ist.

3.

Eine Abbildung f heißt injektiv (oder umkehrbar eindeutig), wenn f eindeutig umkehrbar ist.

4.

Eine Abbildung f heißt bijektiv, wenn f surjektiv und injektiv ist.

Beispiel
Die oben angegebene Korrespondenz P₂ ist eine surjektive Abbildung von auf $\left\{\mbox{wahr, falsch}\right\}$.

Bemerkung
Die Aussage ,,f ist eine Abbildung von A in B`` notieren wir künftig durch
,, $f: A \rightarrow B$`` und statt ,, $\left[a, b\right] \in f$`` schreiben wir ,, $b = f\left(a\right)$``.

Zum Abschluß dieses Abschnittes machen wir eine Bemerkung über die Beschreibung von Korrespondenzen durch Abbildungen. Dabei verwenden wir, daß das Kreuzprodukt auch zwischen Mengen unterschiedlicher Stufen definiert ist.

Es sei $K \subseteq A \times B$ eine Korrespondenz zwischen A und B. Die zu K gehörige Abbildung f_K ist definiert durch

$$f_K : A \rightarrow \potset{B}$$

mit

$$f_K\left(a\right) \defg\left\{b \vert \left[a, b\right] \in K\right\}$$

für alle $a\in A$.

Offenbar kann K aus einer Kenntnis von f_K gewonnen werden (ist durch f_K eindeutig bestimmt), denn es gilt:

$$K = \bigcup_{a \in A} \left\{a\right\} \times f_K\left(a\righ... ...left\{a\right\} \times f_K\left(a\right) \vert a \in A\right\}$$

Da die Beziehung zwischen K undf_K also eineindeutig ist, kann man wirklich von einer Beschreibung sprechen; Beschreibung (f_K) und Beschriebenes (K) entsprechen einander eineindeutig.