close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

B

EinbettenHerunterladen
65
Überblick über Relationalstrukturen
Äquivalenz- und Ordnungsrelationen
refl. sym. trans. antisym. asym. konnex semikon.
Äquivalenzrelation
(Halb-)Ordnung
Striktordnung
lineare Ordnung
lin. Striktord.
Quasiordnung
➔
➔
➔
➔
➔
➔
➔
➔
➔
➔
➔
➔
➔
➔
➔
➔
Bemerkung
In der Tabelle sind nur die definierenden Eigenschaften durch ein ”➔”
gekennzeichnet. Das schließt nicht aus, dass noch weitere Eigenschaften
vorliegen.
Eigenschaften von Relationen
66
Beispiel
▲
▲
▲
▲
Die Relation ”ist Schwester von” ist zwar in einer reinen Damengesellschaft symmetrisch, i.a. jedoch weder symmetrisch noch asymmetrisch
noch antisymmetrisch.
Die Relation ”ist Geschwister von” ist zwar symmetrisch, aber weder
reflexiv noch transitiv und somit keine Äquivalenzrelation.
❼R, ❅➁
ist irreflexiv, asymmetrisch, transitiv und semikonnex und somit
eine lineare Striktordnung.
❼R, ❇➁ und ❼P ❼M ➁, ❜➁ sind reflexiv, antisymmetrisch und transitiv und
somit Ordnungen.
▲
❼R, ❇➁
▲
❼P ❼M ➁, ❜➁
ist auch konnex und somit eine lineare Ordnung.
ist zwar im Fall ❨M ❨ ❇ 1 konnex, aber im Fall ❨M ❨ ❈ 2
weder semikonnex noch konnex.
❘
67
Darstellung von endlichen Relationen
Graphische Darstellung
A ➌a, b, c, d ➑
R ➌❼b, c ➁, ❼b, d ➁, ❼c, a➁, ❼c, d ➁, ❼d, d ➁➑
▲
▲
▲
a
b
c
d
Eine Relation R auf einer (endlichen) Menge A kann durch einen
gerichteten Graphen (kurz Digraphen) G ❼A, R ➁ mit Knotenmenge A
und Kantenmenge R veranschaulicht werden.
Hierzu stellen wir jedes Element x ❃ A als einen Knoten dar und
verbinden jedes Knotenpaar ❼x , y ➁ ❃ R durch eine gerichtete Kante
(Pfeil).
Zwei durch eine Kante verbundene Knoten heißen adjazent oder
benachbart.
68
Darstellung von endlichen Relationen
Definition
Sei R eine binäre Relation auf A.
▲
Die Menge der Nachfolger bzw. Vorgänger von x ist
R x ✆ ➌y ❃ A ❙ xRy ➑ bzw. R
✏
1
x ✆
➌y ❃ A ❙ yRx ➑.
▲
Der Ausgangsgrad eines Knotens x ist deg ❼x ➁ ❨R x ✆❨.
▲
Der Eingangsgrad von x ist deg ❼x ➁ ❨R
▲
Ist R symmetrisch, so können wir die Pfeilspitzen auch weglassen.
▲
✔
✏
✏
1
x ✆❨.
In diesem Fall heißt deg❼x ➁ deg ❼x ➁ deg ❼x ➁ der Grad von x und
R x ✆ R 1 x ✆ die Nachbarschaft von x in G.
✏
✔
✏
▲
▲
G ist schleifenfrei, falls R irreflexiv ist.
Ist R irreflexiv und symmetrisch, so nennen wir G ❼A, R ➁ einen
(ungerichteten) Graphen.
Darstellung von endlichen Relationen
69
Matrixdarstellung (Adjazenzmatrix)
Eine Relation R auf A ➌a1 , . . . , an ➑ lässt sich auch durch die boolesche
❼n ✕ n➁-Matrix MR ❼mij ➁ darstellen mit
mij ➐
1, ai Raj ,
0, sonst.
Beispiel
Die Relation R ➌❼b, c ➁, ❼b, d ➁, ❼c, a➁, ❼c, d ➁, ❼d, d ➁➑ auf A ➌a, b, c, d ➑
hat beispielsweise die Matrixdarstellung
MR ➆0
➊0
➊
➊1
➈0
0
0
0
0
0
1
0
0
0➇
1➋
➋.
1➋
1➉
❘
Darstellung von endlichen Relationen
70
Tabellendarstellung (Adjazenzliste)
R lässt sich auch durch eine Tabelle darzustellen, die jedem Element x ❃ A
seine Nachfolger in Form einer Liste zuordnet.
Beispiel
Die Relation R ➌❼b, c ➁, ❼b, d ➁, ❼c, a➁, ❼c, d ➁, ❼d, d ➁➑ auf A ➌a, b, c, d ➑
hat beispielsweise die Tabellendarstellung
x
R x ✆
a
b
c
d
c, d
a, d
d
❘
Berechnung des Relationenprodukts
71
Berechnung von R ❳ S
▲
Sind MR ❼rij ➁ und MS ❼sij ➁ boolesche n ✕ n-Matrizen für R und S,
so erhalten wir für T R ❳ S die Matrix MT ❼tij ➁ mit
tij ▲
✞
k 1,...,n
❼rik
✱
skj ➁.
Die Nachfolgermenge T x ✆ von x bzgl. der Relation T R ❳ S
berechnet sich zu
T x ✆ ✤
y ❃R x ✆
S y ✆ .
72
Das Relationenprodukt
Beispiel
Betrachte die Relationen R ➌❼a, a➁, ❼a, c ➁, ❼c, b ➁, ❼c, d ➁➑ und
S ➌❼a, b ➁, ❼d, a➁, ❼d, c ➁➑ auf der Menge A ➌a, b, c, d ➑.
Relation
R
R ❳S
S
S ❳R
a
b
a
b
a
b
a
b
c
d
c
d
c
d
c
d
Digraph
Adjazenzmatrix
Adjazenzliste
1010
0000
0101
0000
a ✂ a, c
b ✂c ✂ b, d
d ✂-
0100
0000
0000
1010
a✂b
b ✂c ✂d ✂ a, c
0100
0000
1010
0000
a✂b
b ✂c ✂ a, c
d ✂-
0000
0000
0000
1111
a✂b ✂c ✂d ✂ a, b, c, d
❘
73
Das Relationenprodukt
Beobachtung
Das Relationenprodukt ist nicht kommutativ, d.h. i.a. gilt nicht
R ❳ S S ❳ R.
Relationenalgebra
Als nächstes zeigen wir, dass die Menge ❘ P ❼A ✕ A➁ aller binären
Relationen auf A mit dem Relationenprodukt ❳ als binärer Operation ein
Monoid (also eine Halbgruppe mit neutralem Element) bildet.
Satz
Seien Q, R, S Relationen auf A. Dann gilt
1. ❼Q ❳ R ➁ ❳ S Q ❳ ❼R ❳ S ➁, d.h.
❳
ist assoziativ,
2. Id ❳ R R ❳ Id R, d.h. Id ist neutrales Element.
74
Relationenalgebra
Satz
Seien Q, R, S Relationen auf A. Dann gilt
1. ❼Q ❳ R ➁ ❳ S Q ❳ ❼R ❳ S ➁, d.h.
ist assoziativ,
❳
2. Id ❳ R R ❳ Id R, d.h. Id ist neutrales Element.
Beweis.
1.
✔ u x ❼Q R ➁ u u S y
✔ u ❼ v x Q v R u➁ u S y
✔ u, v x Q v R u S y
✔ v x Q v ❼ u v R u u S y➁
✔ v x Q v ❼R S ➁ y
✔ x Q ❼R S ➁ y
R y ✔ z x z
z R y ✔ x R y folgt Id R R.
x ❼Q ❳ R ➁ ❳ S y
➜
✂
➜
✂
❳
➜
➜
✱
✂
✱
✂
➜
✂
➜
✂
✱
➜
✂
✱
❳
❳
❳
2. Wegen x Id ❳
➜
✂
✱
Die Gleichheit R ❳ Id R folgt analog.
❳
❥
Hüllenoperatoren
75
Frage
Wieviele Paare muss man zu einer Relation R mindestens hinzufügen,
damit sie transitiv wird?
Antwort
▲
▲
Es ist leicht zu sehen, dass der Schnitt von transitiven Relationen
wieder transitiv ist.
Die transitive Hülle von R ist
R ✢➌S ❜ A ✕ A ❙ S ist transitiv und R ❜ S ➑.
✔
▲
▲
▲
✔
R ist also eine transitive Relation, die R enthält.
✔
Da R zudem in jeder Relation mit diesen Eigenschaften enthalten ist,
gibt es keine transitive Relation mit weniger Paaren, die R enthält.
Da auch die Reflexivität und die Symmetrie bei der Schnittbildung
erhalten bleiben, lassen sich nach demselben Muster weitere Hüllenoperatoren definieren.
Weitere Hüllenoperatoren
76
Definition
Sei R eine Relation auf A.
▲
Die reflexive Hülle von R ist
hrefl ❼R ➁ ✢➌S ❜ A ✕ A ❙ S ist reflexiv und R ❜ S ➑.
▲
Die symmetrische Hülle von R ist
hsym ❼R ➁ ✢➌S ❜ A ✕ A ❙ S ist symmetrisch und R ❜ S ➑.
▲
Die reflexiv-transitive Hülle von R ist
R ✢➌S ❜ A ✕ A ❙ S ist reflexiv, transitiv und R ❜ S ➑.
❻
▲
Die Äquivalenzhülle von R ist
häq ❼R ➁ ✢➌E ❜ A ✕ A ❙ E ist eine Äquivalenzrelation mit R ❜ E ➑.
77
Transitive und reflexive Hülle
Satz
hrefl ❼R ➁ R ✽ IdA , hsym ❼R ➁ R ✽ R T , R ✣n❈1 R n , R ✣n❈0 R n .
✔
❻
Beweis
❥
Siehe Übungen.
Bemerkung
▲
▲
Ein Paar ❼a, b ➁ ist also genau dann in der reflexiv-transitiven Hülle R
von R enthalten, wenn es ein n ❈ 0 gibt mit aR n b.
Dies bedeutet, dass es Elemente x0 , . . . , xn ❃ A gibt mit
x0 a, xn b und x0 Rx1 Rx2 . . . xn 1 Rxn .
✏
▲
x0 , . . . , xn heißt Weg der Länge n von a nach b.
❻
Ordnungsrelationen
78
Definition
❼A, R ➁
heißt Ordnung (auch Halbordnung oder partielle Ordnung), wenn R
eine reflexive, antisymmetrische und transitive Relation auf A ist.
Beispiel
▲
▲
▲
▲
❼P ❼M ➁, ❜➁, ❼Z, ❇➁, ❼R, ❇➁, ❼N, ❙➁,
sind Ordnungen. ❼Z, ❙➁ ist keine
Ordnung, aber eine Quasiordnung.
Ist R eine Relation auf A und B ❜ A, so ist RB R ✾ ❼B ✕ B ➁ die
Einschränkung von R auf B.
Einschränkungen von (linearen) Ordnungen sind ebenfalls (lineare)
Ordnungen.
Beispielsweise ist ❼Q, ❇➁ die Einschränkung von ❼R, ❇➁ auf Q und ❼N, ❙➁
die Einschränkung von ❼Z, ❙➁ auf N.
❘
Darstellung einer Ordnung durch ein Hasse-Diagramm
▲
Sei ❇ eine Ordnung auf A und sei ❅ die Relation ❇ ✓Id A , d.h.
x ❅y
▲
▲
▲
▲
79
✔ x ❇y
✱
x ①y
Ein Element x ❃ A heißt unterer Nachbar von y (kurz: x r y ), falls x ❅ y
gilt und kein z ❃ A existiert mit x ❅ z ❅ y .
r ist also die Relation ❅ ✓ ❅2 .
Um die Ordnung ❼A, ❇➁ in einem Hasse-Diagramm darzustellen, wird
nur der Digraph der Relation ❼A, r➁ gezeichnet.
Weiterhin wird im Fall x r y der Knoten y oberhalb vom Knoten x
gezeichnet, so dass auf die Pfeilspitzen verzichtet werden kann.
Das Hasse-Diagramm für
❼
P
❼
80
M ➁; ❜➁
Beispiel
Die Inklusion ❜ auf P ❼M ➁ mit M ➌a, b, c ➑ lässt sich durch folgendes
Hasse-Diagramm darstellen:
M
a, b ➑
➌
a➑
➌
a, c ➑
➌
b➑
b, c ➑
➌
c➑
➌
➌
❣
❘
Das Hasse-Diagramm der ”teilt”-Relation
81
Beispiel
Die Einschränkung der ”teilt”-Relation auf die Menge ➌1, 2, . . . , 10➑ ist
durch folgendes Hasse-Diagramm darstellbar:
8
4
6
9
10
2
3
5
7
1
❘
Maximale, minimale, größte und kleinste Elemente
82
Definition
Sei ❇ eine Ordnung auf A und sei b ein Element in einer Teilmenge B ❜ A.
▲
b heißt kleinstes Element oder Minimum von B, falls gilt:
b ❃B✂b❇b .
➛
▲
➐
➐
b heißt größtes Element oder Maximum von B, falls gilt:
b ❃ B ✂ b ❇ b.
➛
▲
➐
➐
b heißt minimal in B, falls es in B kein kleineres Element gibt:
b ❃B✂b ❇b
➛
▲
➐
➐
✟b
➐
b.
b heißt maximal in B, falls es in B kein größeres Element gibt:
b ❃B✂b❇b
➛
➐
➐
✟b b .
➐
Bemerkung
Wegen der Antisymmetrie kann es in B höchstens ein kleinstes und
höchstens ein größtes Element geben.
83
Maximale, minimale, größte und kleinste Elemente
Beispiel
Betrachte folgende Ordnung.
a
b
c
d
e
B
➌a, b ➑
➌c, d ➑
➌a, b, c ➑
➌a, b, c, e ➑
➌a, c, d, e ➑
minimal
in B
maximal
in B
Minimum
von B
Maximum
von B
a, b
c, d
c
e
e
a, b
c, d
a, b
a, b
a
c
e
e
a
Obere und untere Schranken
84
Definition
Sei ❇ eine Ordnung auf A und sei B ❜ A.
Ein Element u ❃ A mit u ❇ b für alle b ❃ B heißt untere Schranke von B.
Ein Element o ❃ A mit b ❇ o für alle b ❃ B heißt obere Schranke von B.
▲
▲
▲
B heißt nach oben beschränkt, wenn B eine obere Schranke hat.
▲
B heißt nach unten beschränkt, wenn B eine untere Schranke hat.
▲
B heißt beschränkt, wenn B nach oben und nach unten beschränkt ist.
85
Obere und untere Schranken
Beispiel (Fortsetzung)
a
b
c
d
e
B
➌a, b ➑
➌c, d ➑
➌a, b, c ➑
➌a, b, c, e ➑
➌a, c, d, e ➑
minimal maximal min max
a, b
c, d
c
e
e
a, b
c, d
a, b
a, b
a
c
e
e
a
untere obere
Schranken
c, d, e
e
c, e
e
e
a, b
a
Infima und Suprema
86
Definition
Sei ❇ eine Ordnung auf A und sei B ❜ A.
▲
Besitzt B eine größte untere Schranke i, d.h. besitzt die Menge U aller
unteren Schranken von B ein größtes Element i, so heißt i das Infimum
von B (i inf B):
❼➛ b
▲
❃ B ✂ b ❈ i ➁ ✱ ➛ u ❃ A ✂ ❼➛ b ❃ B ✂ b ❈ u ➁ ✟ u ❇ i ✆.
Besitzt B eine kleinste obere Schranke s, d.h. besitzt die Menge O aller
oberen Schranken von B ein kleinstes Element s, so heißt s das
Supremum von B (s sup B):
❼➛ b
❃ B ✂ b ❇ s ➁ ✱ ➛o ❃ A ✂ ❼➛b ❃ B ✂ b ❇ o ➁ ✟ s ❇ o ✆
Bemerkung
B kann nicht mehr als ein Supremum und ein Infimum haben.
87
Infima und Suprema
Beispiel (Schluss)
a
b
c
d
e
B
➌a, b ➑
➌c, d ➑
➌a, b, c ➑
➌a, b, c, e ➑
➌a, c, d, e ➑
minimal maximal min max
a, b
c, d
c
e
e
a, b
c, d
a, b
a, b
a
c
e
e
a
untere obere
inf sup
Schranken
c, d, e
e
c, e
e
e
a, b
a
e
c
e
e
a
❘
Existenz von Infima und Suprema in linearen Ordnungen 88
Bemerkung
▲
▲
Auch in linearen Ordnungen muss nicht jede beschränkte Teilmenge ein
Supremum oder Infimum besitzen.
So hat in der linear geordneten Menge ❼Q, ❇➁ die Teilmenge
B ➌x ❃ Q ❙ x 2 ❇ 2➑ ➌x ❃ Q ❙ x 2 ❅ 2➑
weder ein Supremum noch ein Infimum.
▲
Dagegen hat in ❼R, ❇➁ jede beschränkte Teilmenge B ein Supremum
und ein Infimum (aber möglicherweise kein Maximum oder Minimum).
Äquivalenzrelationen
89
Definition
❼A, R ➁
heißt Äquivalenzrelation, wenn R eine reflexive, symmetrische und
transitive Relation auf A ist.
Beispiel
▲
Auf der Menge aller Geraden im R2 die Parallelität.
▲
Auf der Menge aller Menschen ”im gleichen Jahr geboren wie”.
▲
Auf Z die Relation ”gleicher Rest bei Division durch m”.
❘
Äquivalenzrelationen
▲
Ist E eine Äquivalenzrelation, so nennt man die Nachbarschaft E x ✆ die
von x repräsentierte Äquivalenzklasse und bezeichnet sie auch mit x ✆E
(oder einfach mit x ✆, falls E aus dem Kontext ersichtlich ist):
x ✆E
▲
▲
90
x ✆ E x ✆ ➌y ❙ xEy ➑.
Wie wir sehen werden, bilden die Äquivalenzklassen eine Zerlegung
(Partition) von A, d.h. je zwei Äquivalenzklassen sind entweder disjunkt
oder gleich und ihre Vereinigung ergibt A.
Die Zerlegung von A in Äquivalenzklassen wird Quotienten- oder
Faktormenge von A bzgl. E genannt und mit A⑦E bezeichnet:
A⑦E ➌ x ✆E ❙ x ❃ A➑.
▲
▲
Die Anzahl ❨A⑦E ❨ der Äquivalenzklassen von E wird auch als der Index
von E bezeichnet.
Eine Menge S ❜ A heißt Repräsentantensystem, falls sie genau ein
Element aus jeder Äquivalenzklasse enthält.
Äquivalenzrelationen
91
Beispiel
Für die weiter oben betrachteten Äquivalenzrelationen erhalten wir
folgende Klasseneinteilungen:
▲
▲
▲
▲
Für die Parallelität auf der Menge aller Geraden im R2 :
alle Geraden mit derselben Richtung (oder Steigung) bilden jeweils eine
Äquivalenzklasse.
Ein Repräsentantensystem wird beispielsweise durch die Menge aller
Ursprungsgeraden gebildet.
Für die Relation ”im gleichen Jahr geboren wie” auf der Menge aller
Menschen: jeder Jahrgang bildet eine Äquivalenzklasse.
Für die Relation ”gleicher Rest bei Division durch m” auf Z:
jede der m Restklassen 0✆, 1✆, . . . , m ✏ 1✆ mit
r ✆
➌a ❃ Z ❙ a mod m r ➑
bildet eine Äquivalenzklasse.
▲
Repräsentantensystem: ➌0, 1, . . . , m ✏ 1➑.
❘
Verfeinerung und Vergröberung von Äquivalenzrelationen 92
Bemerkungen
▲
▲
▲
▲
Die kleinste Äquivalenzrelation auf A ist die Identität IdA , die größte ist
die Allrelation A ✕ A.
Die Äquivalenzklassen der Identität enthalten jeweils nur ein Element,
d.h. A⑦IdA ➌➌x ➑ ❙ x ❃ A➑.
Die Allrelation erzeugt nur eine Äquivalenzklasse, nämlich A, d.h.
A⑦❼A ✕ A➁ ➌A➑.
Für zwei Äquivalenzrelationen E ❜ E sind auch die Äquivalenzklassen
x ✆E von E in den Klassen x ✆E ➐ von E enthalten.
➐
➐
▲
▲
➐
Folglich ist jede Äquivalenzklasse von E die Vereinigung von (evtl.
mehreren) Äquivalenzklassen von E .
Im Fall E ❜ E sagt man auch, E bewirkt eine feinere Zerlegung von A
als E .
➐
➐
▲
Demnach ist die Identität die feinste und die Allrelation die gröbste
Äquivalenzrelation.
93
Das Hasse-Diagramm der Feiner-Relation
Beispiel
Die ”feiner als” Relation auf der Menge aller Partitionen von M ➌a, b, c ➑
ist durch folgendes Hasse-Diagramm darstellbar:
M➑
➌
a, b ➑, ➌c ➑➑
➌➌
a, c ➑, ➌b ➑➑
➌➌
a➑, ➌b ➑, ➌c ➑➑
➌➌
a➑, ➌b, c ➑➑
➌➌
❘
94
Partition einer Menge
Definition
Eine Familie ➌Bi ❙ i ❃ I ➑ von nichtleeren Teilmengen Bi ❜ A heißt Partition
der Menge A, falls gilt:
▲
▲
die Mengen Bi überdecken A, d.h. A ✣i ❃I Bi und
die Mengen Bi sind paarweise disjunkt, d.h. für je zwei verschiedene
Mengen Bi ⑦ Bj gilt Bi ✾ Bj ❣.
Satz
Sei E eine Relation auf A. Dann sind folgende Aussagen äquivalent:
1. E ist eine Äquivalenzrelation auf A,
2. Für alle x , y ❃ A gilt xEy
✔ E x ✆ E y ✆ ,
3. Es gibt eine Partition ➌Bi ❙ i ❃ I ➑ von A mit xEy
✔
➜
i ❃ I ✂ x , y ❃ Bi .
95
Äquivalenzrelationen und Partitionen
Satz
Sei E eine Relation auf A. Dann sind folgende Aussagen äquivalent:
1. E ist eine Äquivalenzrelation auf A,
2. Für alle x , y ❃ A gilt xEy
✔ E x ✆ E y ✆ ,
3. Es gibt eine Partition ➌Bi ❙ i ❃ I ➑ von A mit xEy
✔
➜
i ❃ I ✂ x , y ❃ Bi .
Beweis.
impliziert 2 : Sei E eine Äquivalenzrelation auf A.
Da E transitiv ist, impliziert xEy die Inklusion E y ✆ ❜ E x ✆:
1
z ❃ E y ✆
✟ yEz xEy
✟ xEz ✟ z ❃ E x ✆.
Da E symmetrisch ist, folgt aus xEy aber auch E x ✆ ❜ E y ✆.
Umgekehrt folgt aus E x ✆ E y ✆ wegen der Reflexivität von E , dass
y ❃ E y ✆ E x ✆ enthalten ist, und somit xEy .
96
Äquivalenzrelationen und Partitionen
Satz
Sei E eine Relation auf A. Dann sind folgende Aussagen äquivalent:
1. E ist eine Äquivalenzrelation auf A,
2. Für alle x , y ❃ A gilt xEy
✔ E x ✆ E y ✆ ,
3. Es gibt eine Partition ➌Bi ❙ i ❃ I ➑ von A mit xEy
✔
➜
i ❃ I ✂ x , y ❃ Bi .
Beweis.
impliziert 3 : Wir zeigen, dass ➌E x ✆ ❙ x ❃ A➑ eine Partition von A
bildet, falls E die Bedingung xEy
E x ✆ E y ✆ erfüllt.
2
✔
▲
Wegen E x ✆ E x ✆ folgt xEx und somit x ❃ E x ✆.
▲
Folglich überdecken die Mengen E x ✆ die Menge A.
▲
Ist E x ✆ ✾ E y ✆ ① ❣ und z ein Element in E x ✆ ✾ E y ✆, so gilt
xEz und yEz und daher folgt E x ✆ E z ✆ E y ✆.
97
Äquivalenzrelationen und Partitionen
Satz
Sei E eine Relation auf A. Dann sind folgende Aussagen äquivalent:
1. E ist eine Äquivalenzrelation auf A,
2. Für alle x , y ❃ A gilt xEy
✔ E x ✆ E y ✆ ,
3. Es gibt eine Partition ➌Bi ❙ i ❃ I ➑ von A mit xEy
✔
➜
i ❃ I ✂ x , y ❃ Bi .
Beweis.
impliziert 1 : Existiert schließlich eine Partition ➌Bi ❙ i ❃ I ➑ von A mit
xEy
➜i ❃ I ✂ x , y ❃ Bi , so ist E
3
✔
▲
reflexiv, da zu jedem x ❃ A eine Menge Bi mit x ❃ Bi existiert,
▲
symmetrisch, da aus x , y ❃ Bi auch y , x ❃ Bi folgt, und
▲
transitiv, da aus x , y ❃ Bi und y , z ❃ Bj wegen y ❃ Bi
Bi Bj und somit x , z ❃ Bi folgt.
✾
Bj die Gleichheit
❥
98
Abbildungen
Definition
Sei R eine binäre Relation auf einer Menge M.
▲
R heißt rechtseindeutig, falls für alle x , y , z ❃ M gilt:
xRy
▲
✱
xRz
R heißt linkseindeutig, falls für alle x , y , z ❃ M gilt:
xRz ✱ yRz
▲
✟ y z.
✟ x y.
Der Nachbereich N ❼R ➁ und der Vorbereich V ❼R ➁ von R sind
N ❼R ➁ ✤ R x ✆
x ❃M
und V ❼R ➁ ✤ R T x ✆.
x ❃M
99
Abbildungen
Abbildungen ordnen jedem Element ihres Definitionsbereichs genau ein
Element zu.
Definition
Eine rechtseindeutige Relation R mit V ❼R ➁ A und N ❼R ➁ ❜ B heißt
Abbildung oder Funktion von A nach B (kurz R ✂ A B).
Bemerkung
▲
Wie üblich werden wir Abbildungen meist mit kleinen Buchstaben
f , g, h, ... bezeichnen und für ❼x , y ➁ ❃ f nicht xfy sondern f ❼x ➁ y oder
f ✂ x y schreiben.
✭
▲
▲
Ist f ✂ A B eine Abbildung, so wird der Vorbereich V ❼f ➁ A der
Definitionsbereich und die Menge B der Wertebereich oder Wertevorrat
von f genannt.
Der Nachbereich N ❼f ➁ wird als Bild von f bezeichnet.
100
Abbildungen
Definition
Sei f ✂ A
B eine Abbildung.
▲
Im Fall N ❼f ➁ B heißt f surjektiv.
▲
Ist f linkseindeutig, so heißt f injektiv.
▲
In diesem Fall impliziert f ❼x ➁ f ❼y ➁ die Gleichheit x y .
▲
Eine injektive und surjektive Abbildung heißt bijektiv.
▲
Ist f injektiv, so ist auch f 1 ✂ N ❼f ➁ A eine Abbildung, die als die zu
f inverse Abbildung bezeichnet wird.
✏
Bemerkung
Man beachte, dass der Definitionsbereich V ❼f 1 ➁ N ❼f ➁ von f
gleich B ist, wenn f auch surjektiv, also eine Bijektion ist.
✏
✏
1
nur dann
101
Homomorphismen
Definition
Seien ❼A1 , R1 ➁ und ❼A2 , R2 ➁ Relationalstrukturen.
▲
Eine Abbildung h ✂ A1
a, b ❃ A1 gilt:
aR1 b
▲
▲
A2 heißt Homomorphismus, falls für alle
✟ h❼a➁R2h❼b➁.
Sind ❼A1 , R1 ➁ und ❼A2 , R2 ➁ Ordnungen, so spricht man auch von
Ordnungshomomorphismen oder einfach von monotonen Abbildungen.
Injektive Ordnungshomomorphismen werden auch streng monotone
Abbildungen genannt.
102
Homomorphismen
Beispiel
4
d
3
c
b
2
a
h
❼A, ❇➁
▲
▲
▲
Die Abbildung h ✂ A
1
❼B, ❩➁
B ist ein bijektiver Ordnungshomomorphismus.
Die Umkehrabbildung h
nicht monoton ist.
✏
1
ist jedoch kein Homomorphismus, da h
Es gilt nämlich 2 ❩ 3, aber h
✏
1
❼2 ➁
b ❇⑦ c h
✏
1
❼3 ➁.
✏
1
❘
103
Isomorphismen
Definition
▲
▲
Seien ❼A1 , R1 ➁ und ❼A2 , R2 ➁ Relationalstrukturen.
Ein bijektiver Homomorphismus h ✂ A1 A2 , bei dem auch h
Homomorphismus ist, d.h. es gilt für alle a, b ❃ A1 ,
aR1 b
✏
1
ein
✔ h❼a➁R2h❼b➁.
heißt Isomorphismus.
▲
In diesem Fall heißen die Strukturen ❼A1 , R1 ➁ und ❼A2 , R2 ➁ isomorph
(kurz: ❼A1 , R1 ➁ ☞ ❼A2 , R2 ➁).
Sind ❼A1 , R1 ➁ und ❼A2 , R2 ➁ isomorph, so bedeutet dies, dass sich die
beiden Strukturen nur in der Benennung ihrer Elemente unterscheiden.
104
Isomorphismen
Beispiel
▲
Die Bijektion h ✂ x
und ❼R , ❇➁.
✔
▲
✭ e x ist ein Ordnungsisomorphismus zwischen ❼R, ❇➁
Für n ❃ N sei
Tn ➌k ❃ N ❙ k teilt n➑
und
Pn ➌p ❃ Tn ❙ p ist prim➑.
Dann ist die Abbildung
h✂k
✭ Pk
ein Ordnungshomomorphismus von ❼Tn , ❙➁ auf ❼P ❼Pn ➁, ❜➁.
h ist sogar ein Isomorphismus, falls n quadratfrei ist (d.h. es gibt keine
Primzahl p, so dass p 2 die Zahl n teilt).
❘
105
Isomorphismen
Beispiel
1
1
5
2
4
5
3
G ❼V , E ➁
2
4
v 12345
h 1 ❼v ➁ 1 3 5 2 4
h 2 ❼v ➁ 1 4 2 5 3
3
G ❼V , E
➐
➐
➁
➐
▲
Die beiden Graphen G und G sind isomorph.
▲
Zwei Isomorphismen sind beispielsweise h1 und h2 .
❘
106
Isomorphismen
Beispiel
3
▲
Während auf der Knotenmenge V ➌1, 2, 3➑ insgesamt 2❽2➂ 23 8
verschiedene Graphen existieren, gibt es auf dieser Menge nur 4
verschiedene nichtisomorphe Graphen:
❘
Isomorphismen
107
Beispiel
▲
▲
Es existieren genau 5 nichtisomorphe Ordnungen mit 3 Elementen:
Anders ausgedrückt: Die Klasse aller dreielementigen Ordnungen
zerfällt unter der Isomorphierelation ☞ in fünf Äquivalenzklassen, die
durch obige fünf Hasse-Diagramme repräsentiert werden.
❘
Document
Kategorie
Gesundheitswesen
Seitenansichten
16
Dateigröße
333 KB
Tags
1/--Seiten
melden