Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge

Mathematik-Online-Kurs: Vorkurs Mathematik - Grundlagen - Mengen

Eigenschaften von Relationen


[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]

Eine Relation $ R\subseteq A^2$ in einer Menge $ A$ heißt

Ist eine Relation reflexiv, symmetrisch und transitiv, so wird sie Äquivalenzrelation genannt. Es wird dann meist $ a\sim b$ statt $ a \operatorname{R}b$ geschrieben. Eine Äquivalenzrelation unterteilt die Menge $ A$ in disjunkte Teilmengen (Äquivalenzklassen), wobei zwei Elemente einer Teilmenge zueinander in Relation stehen (äquivalent sind), während zwei Elemente aus unterschiedlichen Teilmengen dies nicht tun.

Ist eine Relation reflexiv, antisymmetrisch und transitiv, so ist sie eine Halbordnung und man schreibt meist $ a \leq b$ statt $ a \operatorname{R}b$. Ist eine Halbordnung zusätzlich total, heißt sie (totale) Ordnung und $ A$ heißt durch $ \leq$ geordnet.

(Autor: J. Hörner)

Die Mengeninklusion $ \subseteq$ ist eine Halbordnung in der Potenzmenge $ {\cal P}(M)$ einer Menge $ M$ denn es gilt: $ A\subseteq
A$ (reflexiv), $ A\subseteq B \land B \subseteq A \Rightarrow A=B$ (antisymmetrisch) und $ A\subseteq B \subseteq C \Rightarrow A
\subseteq C$ (transitiv). Hat $ M$ mehr als ein Element, so ist die Inklusion aber keine Ordnung, denn dann gilt für

$\displaystyle a,b \in M, a\neq b: \{a\} \not\subseteq \{b\} \land \{b\} \not\subseteq \{a\} \,,
$

das heißt sie ist nicht total.

Die Relation ,,hat gleich viele Elemente wie`` ist eine Äquivalenzrelation in der Potenzmenge $ {\cal P}(M)$ einer endlichen Menge $ M$ denn es gilt: $ \vert A\vert=\vert A\vert$(reflexiv), $ \vert A\vert=\vert B\vert \Rightarrow \vert B\vert=\vert A\vert$ (symmetrisch) und $ \vert A\vert=\vert B\vert=\vert C\vert \Rightarrow \vert A\vert =\vert C\vert$ (transitiv).

(Autor: J. Hörner)

Relationen bzw. Äquivalenz-Relationen auf Mengen werden oft durch Eigenschaften der Elemente definiert. Als Beispiel werden zwei Relationen auf

$\displaystyle M = \lbrace 1,2,\dots,12 \rbrace
$

betrachtet:

\includegraphics[width=0.45\moimagesize]{relationen1.eps}          \includegraphics[width=0.45\moimagesize]{relationen2.eps}

Die Abbildung zeigt den Graph der Relationen als Teilmenge von $ M \times M$. Die Relation $ R_1$ ist symmetrisch, aber weder reflexiv ( $ (1,1) \not\in R_1$) noch transitiv. Zum Beispiel haben $ x = 4$ und $ y = 6$ den gemeinsamen Teiler $ 2$ und $ y = 6$ und $ z = 9$ den gemeinsamen Teiler $ 3$, aber $ x = 4$ und $ z = 9$ haben keinen gemeinsamen Teiler. Also gilt

$\displaystyle (x R_1 y \land y R_1 z) \Rightarrow x R_1 z
$

nicht.

Die Relation $ R_2$ ist eine Äquivalenz-Relation. Reflexivität, Symmetrie und Transitivität sind offensichtlich erfüllt. Die Äquivalenzklassen sind

$\displaystyle \lbrace 1 \rbrace, \lbrace 2,3,5,7,11 \rbrace, \lbrace 4,9 \rbrace, \lbrace 6,8,10 \rbrace, \lbrace 12 \rbrace
$

mit einem, zwei, drei, vier und sechs Teilern.
(Autoren: Höllig/Kreitz)

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]

  automatisch erstellt am 23.10.2009