Mengen - Relationen (Forts.)
kartesischer Begriff der Mengen
(n Mal kartes. Prod.)
A = {0,1},
= {(0,0,0), ... , (1,1,1)}
(Würfel)
Definition: Unter einer zweistelligen (=binären) Relation zwischen den Mengen A und B versteht man eine Teilmenge des kartesischen Produktes von A und B, d.h.
. Insbesondere wenn A = B, dann heißt R eine binäre Relation auf A,
. Statt
schreibt man meist a R b.
Beispiel: Endliche Mengen
A={1,2}, B={3,4,5}
Weiters Bsp.: A = B =
(natürliche Ordnung auf
R = {(0,0), (0,1), (0,2), (1,1), (1,2), ....)}
Definition: Unter einer n-stelligen Relation zwischen den Mengen
versteht man eine Teilmenge von
, d.h.
Falls
, dann heisst
eine n-stellige Relation auf A.
Beispiel: Relationale Datenbanken
Spezielle Relationen
Sei R eine binäre Relation auf A.
Betrachte
zugehöriger Graph der Relation R:
- Knoten: Elemente von A
- gerichtete Kanten: eine gerichtete Kante verläuft von a nch b. g.d.w. a R b.
![{\displaystyle \forall (a,b)\in R}](/index.php?title=Spezial:MathShowImage&hash=7993f897a7331fa26875cd016eb3324a&mode=mathml)
A = {a,b,c,d}
R = {(a,a), (b,b), (a,b), (b,a), (a,c), (d,c)}
Definition: Sei R eine binäre Relation auf A. Dann heißt die Relation R
- (R) reflexiv, falls a R a,
![{\displaystyle \forall a\in A}](/index.php?title=Spezial:MathShowImage&hash=2b4bc191b3cfd58072aebb928d39281b&mode=mathml)
- (S) symmetrisch, falls: a R b
b R a, ![{\displaystyle \forall a,b\in A}](/index.php?title=Spezial:MathShowImage&hash=24c3ae19416ce519afeee31176ded25b&mode=mathml)
- (A) antisymmetisch, falls: a R b
b R a
a = b, ![{\displaystyle \forall a,b\in A}](/index.php?title=Spezial:MathShowImage&hash=24c3ae19416ce519afeee31176ded25b&mode=mathml)
- (T) transitiv, falls a R b
![{\displaystyle \vee bRc\Rightarrow aRc,\forall a,b,c\in A}](/index.php?title=Spezial:MathShowImage&hash=37e54f8140475b0737217299b1a27a26&mode=mathml)
Falls für eine Relation R die Eigenschaften (R),(S) und (T) gelten, dann heisst R eine Äquivalenzrelation auf A.
Falls für eine Relation R die Eigenschaften (R), (A) und (T) gelten, dann heisst R eine Halbordnungsrelation auf A.
Betrachte
Ist (R), (S), nicht antisymmetisch, (T)
Äquivalenzrelation auf
A = P(M) .... Potenzmenge einer Menge M
Ist: (R), nicht symmetrisch, (A) da
, (T)
A =
natürliche Ordnung auf
Ist (R), (A), (T)
Halbordungsrelation
Es gilt weiters: für
gilt:
. Je zwei Elemente sind vergleichbar
Vollordnung (Kette)
- Allrelation:
(Graph) (R) (S) (T)
- Identische Relation:
![{\displaystyle \epsilon =R=:\{(a,b),a\in A\}}](/index.php?title=Spezial:MathShowImage&hash=2fbdd60b4e7b892e91188cb832b1b060&mode=mathml)