A ×A
auf einer Menge A
werden manchmal auch homogene
(binäre) Relationen genannt. Die (Nicht-) Gültigkeit einiger
Eigenschaften entscheidet, ob die Relation
Ordnungsrelation,
Äquivalenzrelation, oder ein
(ungerichteter) Graph ist.
Wir werden zwei Möglichkeiten solche Relationen darzustellen
kennenlernen---einerseits durch quadratische 0-1 Matrizen, andererseits
als gerichtete Graphen.
Definition:
Eine binäre Relation R A ×A
auf A heißt
|
Die natürlichste binäre Relation auf einer Menge A
ist die Identität
(oder Gleichheitsrelation, Diagonale)
idA = {(a,a) | a 
A}.
Darstellung binärer Relationen
Binäre Relationen auf endlichen Mengen M
können auf zwei Arten visualiert werden.
Erstens durch quadratische |M| × |M| 0-1 Matrizen.
Zuerst muß man die Elemente von M als
x1,x2,...,x|M|
durchnummerieren. Für i,j {1,2,..|M|}
definiert man ai,j = 1
falls (xi,xj) R,
und andernfalls ai,j = 0.
Die zweite
Visualisierungsmöglichkeit benutzt sogenannte
gerichtete Graphen oder (Digraphen).
Die Elemente von M werden aufs Blatt
gezeichnet und Ecken genannt.
Nun zieht man einen Pfeil (gerichtete Kante)
von x nach y wenn
(x,y) R ist. Eventuelle
gerichtete Kanten von x nach x werden wegen ihrer Bumerangnatur
Schlingen genannt.
Natürlich kann dieselbe Relation, d.h. derselbe Digraph
sehr verschieden gezeichnet werden.
| Beispiel: Sei M = {a,b,c,d,e} und R={(a,b),(a,e),(b,a),(b,d),(c,d),(e,e)}. Hier ist die Matrix (für Reihenfolge a,b,c,d,e) und der gerichtete Graph. |
 |
 |
A ×A
auf eine Relation
R' A' ×A'
ist eine Abbildung f: A 
A'
mit der Eigenschaft daß aus
(x,y) R
stets (f(x),f(y)) R' folgt.
Zwei Relationen R A ×A
und R' A' ×A' sind
isomorph
wenn es eine bijektive Abbildung f: A A'
gibt, so daß sowohl f als auch f-1
Homomorphismen sind.
Isomorphe binäre Relationen sind bis auf
Benennung der Elemente dieselben Strukturen.
Die Transposition oder inverse Relation RT
zu einer Relation R auf A ist definiert als
RT = {(b,a) | (a,b) R}.
Ist R eine Abbildung, so ist RT = R-1.
Die Bezeichnung rührt daher, daß die Matrix von RT
gleich der transponierten Matrix von R ist. Den gerichteten Graphen
von RT erhält man durch Umdrehen aller Richtungen.
Sind R und S Relationen auf einer Menge A,
so ist die Komposition (das Relationenprodukt)
R ° S = {(a,c) | 
b A:
(a,b) R 
(b,c) S}. Dummerweise ist die Konvention genau
umgekehrt wie bei Abbildungen: Sind f und g Abbildungen, so ist
f ° g (als Relationenprodukt) = g ° f (als Komposition von Abbildungen),
also aufpassen!
Die Matrix von R ° S ist das Matrizenprodukt der Matrizen von R und S,
wenn man beim Addieren "1 + 1 = 1" beachtet
(man möchte ja wieder eine 0-1 Matrix erhalten---andernfalls
würde man die Zahl der b A
mit (a,b) R und (b,c) R
zählen).
Man kann R ° S auch aus der Digraphendarstellung ablesen:
Färbt man alle gerichtete Kanten von R rot
und alle gerichtete Kanten von S schwarz,
dann ist ganu dann (x,y) R ° S falls man durch
einen "Doppelzug", erst entlang einer roten Kante,
danach entlang einer schwarzen Kante,
von x nach y kommen kann.
R ist genau dann
R,
R =
,
RT
idA,
R.
, idA, sowie
1A := A ×A erhalten wir:
R)T = (RT),
T = ,
1AT = 1A,
("Tarski-Regel"),
S genau dann wenn
QT ° S
R genau dann wenn
S ° RT
Q ("Schröder-Umformung")
Beweis,
Beispiel
S
(Q (S ° RT)) °
(R (QT ° S)) ("Dedekind-Formel"),
Beweis
= ° R = ,
Q und R S,
dann P ° R Q ° S,
S) =
(Q ° R) (Q ° S) und
Q ° (R 
S) = (Q ° R) (Q ° S)
(Distributivgesetze mit °).
A ×A
ist R idA reflexiv und
R RT symmetrisch. Die
Relationen sind die kleinsten reflexiven bzw. symmetrischen Relationen auf A,
die R enthalten. Ähnliches ist auch für "transitiv" möglich:
|
Die transitive Hülle R*
einer binären Relation R auf einer Menge M
wird definiert durch:
(x,y) R*
Û k
N0:
z1, z2, ... , zk
M: (x,z1),
(z1,z2),
... , (zk-
1,zk),
(zk,y) R.
|
n 
0 Rn.
Der Name ist gerechtfertigt, denn sind (x,y), (y,w)
R*, d.h.
gibt es natürliche Zahlen k, t 0
und
z1, z2, ... , zk,
u1, u2, ... , ut
M: mit (x,z1),
(z1,z2),
... , (zk-
1,zk),
(zk,y) R,
und (y,u1),
(u1,u2),
... , (ut-
1,ut) R,
(ut,w), so ist ja offenbar damit auch
(x,w) R*
Die transitive Hülle jeder binären Relation auf einer Menge
ist transitiv.
D2:
D3:
D5:
D6:
|
|