Mathematische Grundlagen

Relation

 aufwärts

Eine Relation ist nichts anderes als eine Teilmenge eines kartesischen Produkts.

Definition

Definition:  Seien A und B Mengen. Eine Teilmenge R enthalten in A × B heißt (zweistellige) Relation zwischen A und B. Gilt A = B, so heißt R Relation auf A.

Schreibweise:  Statt (a, bElement R schreibt man im allgemeinen a R b; statt des Buchstabens R verwendet man bei Relationen meist spezielle Symbole: = , kleiner gleich, < ,  enthalten in , ~ , ...

Beispiel:  Die folgende Mengen stellen die Kleiner- bzw. die Gleichheits­relation auf der Menge natürliche Zahlen dar:

<   =  { (1,2), (1,3), (2,3), (1,4) ... }  enthalten in  natürliche Zahlen × natürliche Zahlen

=   =  { (1,1), (2,2), (3,3), (4,4) ... }  enthalten in  natürliche Zahlen × natürliche Zahlen

Eigenschaften von Relationen

Definition:  Sei R eine Relation auf einer Menge AR heißt

reflexiv  genau dann wenn    für alle a Element A  : (a, aElement R
anti­symmetrisch  genau dann wenn    für alle a, b Element A  : (a,bElement R  und  (b, aElement R  folgt  a = b
transitiv  genau dann wenn    für alle a, b, c Element A  : (a, bElement R und (b, cElement R  folgt  (a, cElement R
symmetrisch  genau dann wenn    für alle a, b Element A  : (a, bElement R genau dann wenn (b, aElement R
irreflexiv  genau dann wenn    für alle a Element A  : (a, anicht Element R
total  genau dann wenn    für alle a, b Element A  : a ≠ b  folgt  (a, bElement R  oder  (b, aElement R

Beispiel:  Sei M die Menge aller Menschen. Die Relation verheiratet ("ist verheiratet mit") auf M ist symmetrisch (wenn a mit b verheiratet ist, dann ist auch b mit a verheiratet), irreflexiv (niemand ist mit sich selbst verheiratet), aber nicht total (es gibt unverheiratete Menschen).

Die Relation ~ ("hat dieselben Eltern wie") auf M ist reflexiv (jeder hat dieselben Eltern wie er selbst), symmetrisch (wenn a dieselben Eltern hat wie b, dann hat auch b dieselben Eltern wie a) und transitiv (wenn a dieselben Eltern hat wie b und b dieselben Eltern hat wie c, dann hat auch a dieselben Eltern wie c).

Die Relation eckig enthalten ("ist Vorfahre von") auf M ist anti­symmetrisch (wenn a Vorfahre von b ist und b Vorfahre von a ist, dann sind a und b gleich – die Aussage ist wahr, da die ersten beiden Bedingungen nie gleichzeitig eintreten können), transitiv (wenn a Vorfahre von b ist und b Vorfahre von c ist, dann ist a Vorfahre von c) und irreflexiv (niemand ist Vorfahre von sich selbst).

Eine (nichtleere) Relation kann nicht gleichzeitig reflexiv und irreflexiv sein. Aber es gibt Relationen, die weder reflexiv noch irreflexiv sind. Ebenso gibt es Relationen, die weder symmetrisch noch anti­symmetrisch sind, und Relationen, die gleichzeitig symmetrisch und anti­symmetrisch sind (siehe Beispiele unten). Insofern verhalten sich die Begriffe nicht komplementär zueinander. Wir können nicht folgern: Die Relation ist nicht symmetrisch, also ist sie anti­symmetrisch.

Beispiel:  Sei A = {1, 2, 3}. Die folgenden Mengen R1, R2 und R3 sind Relationen auf A, und es gilt

R1  =  { (1, 1), (1, 2) }   ist nicht reflexiv und nicht irreflexiv,

R2  =  { (1, 2), (2, 1), (1, 3) }   ist nicht symmetrisch und nicht anti­symmetrisch,

R3  =  { (2, 2), (3, 3) }   ist symmetrisch und anti­symmetrisch.

Ordnungs- und Äquivalenzrelation

Definition:  Eine Relation heißt Halbordnung, wenn sie reflexiv, anti­symmetrisch und transitiv ist.

Eine Relation heißt strenge Halbordnung, wenn sie irreflexiv und transitiv ist.1)

Eine Relation heißt lineare Ordnung oder totale Ordnung oder Ordnung, wenn sie Halbordnung ist und zusätzlich noch total ist.

Eine Relation heißt Äquivalenz­relation, wenn sie reflexiv, symmetrisch und transitiv ist.

Beispiel:  Die Relationen  kleiner gleich  und  |  ("teilt") auf natürliche Zahlen sind Halb­ordnungen,  kleiner gleich  ist sogar totale Ordnung.

Die Relation   kongruent n ("ist kongruent modulo n", d.h. liefert bei ganzzahliger Division durch n denselben Rest) ist eine Äquivalenz­relation auf ganze Zahlen.

Die Relation eckig enthalten auf der Menge der Menschen M ist eine strenge Halbordnung. Die Relation ~ auf M ist eine Äquivalenz­relation.

Äquivalenz­relationen auf einer Menge A bewirken eine Klassen­einteilung von A, d.h. eine Zerlegung von A in paarweise disjunkte Mengen (Äquivalenz­klassen).

Die Äquivalenz­relation  kongruent 2 bewirkt eine Klassen­einteilung von ganze Zahlen in die geraden und die ungeraden Zahlen. Die Äquivalenz­klassen der Relation ~ auf der Menge der Menschen sind die Geschwister.

Operationen auf Relationen

Definition:  Das Produkt zweier Relationen R, T enthalten in A × A ist die Relation

RT  =  { (a, c)  |   es existiert b Element A :  (a, bElement R  und  (b, cElement T }.

Potenzen einer Relation R enthalten in A × A sind wie folgt definiert:

R0  =  { (a, a) | a Element A },

Ri  =  Ri-1 R   für alle i Element natürliche Zahlen.

Definition:  Die transitive Hülle einer Relation R ist die Relation

R+  =  Vereinigung i Element IN  Ri   =   R  vereinigt  R2  vereinigt  R3  vereinigt  . . .

Die reflexive Hülle einer Relation R ist die Relation

R?  =  R0  vereinigt  R.

Die reflexive und transitive Hülle einer Relation R ist die Relation

R*  =  Vereinigung i Element IN0  Ri   =   R0  vereinigt  R+ .

Die Hülle einer Relation R bezüglich einer Eigenschaft ergibt sich, indem die fehlenden Elemente hinzu­genommen werden. D.h. die Hülle ist die kleinste Relation, die R umfasst und die betreffende Eigenschaft hat.

Aus einer strengen Halbordnung R lässt sich eine Halbordnung H machen, indem die reflexive Hülle H = R0 vereinigt R gebildet wird. Umgekehrt ergibt sich die zu einer Halbordnung H gehörige strenge Halbordnung R, indem R = H \ H0 gebildet wird.

 

Definition:  Die inverse Relation von R enthalten in A × A ist die Relation

R -1  =  { (b, a)  |  (a, bElement R }.

Beispiel:  Sei M die Menge der Menschen und ist Elternteil von die Relation "ist Elternteil von" auf M. Die Relation ist Elternteil von-1 bedeutet dann "ist Kind von", die Relation ist Elternteil von2 bedeutet "ist Groß­eltern­teil von" und die Relation ist Elternteil von+ ist identisch mit der Relation eckig enthalten ("ist Elternteil oder Groß­eltern­teil oder Urgroß­eltern­teil oder ..., d.h. ist Vorfahre von").

Das Produkt der Relationen ist Elternteil von ("ist Elternteil von") und verheiratet ("ist verheiratet mit") ist die Relation ist Elternteil vonverheiratet. Zwei Menschen a und c stehen in der Relation ist Elternteil vonverheiratet, wenn es einen Menschen b gibt, so dass a Elternteil von b ist und b mit c verheiratet ist. Damit ist a Schwieger­mutter oder Schwieger­vater von c.

Aufgaben

Aufgabe 1:  Eine strenge Halbordnung ist irreflexiv und transitiv. Zeigen Sie, indem Sie die Definitionen dieser Eigen­schaften heranziehen, dass jede strenge Halbordnung anti­symmetrisch ist.

Aufgabe 2:  Offenbar gilt für eine Relation R auf einer Menge A

R ist reflexiv  genau dann wenn  R0 enthalten in R.

Charakterisieren Sie auf ähnliche Weise mithilfe von Ri:

Literatur

Bücher


1)  Der Begriff "strenge Halbordnung" ist etwas unglücklich, da er wie "Halbordnung, und zusätzlich noch streng" klingt. Tatsächlich ist aber eine strenge Halbordnung nicht reflexiv und daher keine Halbordnung im Sinne der obigen Definition, sondern eine "andere Art von Halbordnung".

 

Weiter mit:   [Abbildung]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 15.09.1997   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik