Äquivalenzrelationen



Definition:
Eine Äquivalenzrelation ist eine zweistellige Relation (Bezeichnung: $\sim$), für die folgende Regeln gelten:

  1. $x \sim x$ (reflexiv)
    (D.h. jedes Element steht zu sich selbst in Relation.)
  2. $x \sim y \Rightarrow y \sim x$ (symetrisch)
    (D.h. wenn ein Element in Relation zu einem anderen steht,
    so steht das andere Element auch in Relation zu dem Ersten.)
  3. $x \sim y$ und $y \sim z \Rightarrow x \sim z$ (transitiv)
    (D.h. wenn ein Element in Relation zu einem anderen steht
    und das andere Element in Relation zu einem weiteren Element steht,
    so steht das erste Element auch in Relation zu dem Weiteren (Letzten).)


Beispiele:

Beispiele für Äquivalenzrelationen:

  1. Sei M die Menge der Menschen, A, B zwei (beliebige) Menschen aus M und ``A ist gleich groß wie B'' sei die Relation.
    Um zu zeigen, dass diese Relation eine Äquivalenzrelation ist, müssen wir überprüfen, ob die drei Regeln aus der Definition erfüllt werden:
    Wir zeigen 1)
    Sei A ein Mensch aus M ($A \in M$).``A ist gleich groß wie A'', d.h. ein Mensch ist so groß wie er selber. Ich denke, da kann man mit gutem Gewissen zustimmen.
    Wir zeigen 2)
    Seien $A, B \in M$.``Wenn A so groß ist wie B, so ist B so groß wie A.'' Wenn also ein Mensch so groß ist wie ein anderer, so ist der Andere so groß wie der Erste. Ist auch richtig.
    Wir zeigen 3)
    Seien $A, B, C \in M$. ``Wenn A so groß ist wie B und B so groß ist wie C, so ist A so groß wie C.'' Wenn also eine beliebige 1. Person so groß wie eine 2. Person UND diese 2. Person so groß wie eine Dritte ist, so ist die erste Person so groß wie die dritte Person. Ja, ist einleuchtend, stimmt.
    Damit erfüllt also unsere Relation ``ist gleich groß wie'' die drei Regeln, und ist somit eine Äquivalenzrelation auf der Menge der Menschen.

    Fertig.

  2. Seien $x, y \in \mathbb{N}, f: \mathbb{N} \rightarrow \mathbb{N}$ eine Funktion auf den natürlichen Zahlen.
    Dann definieren wir eine Relation wie folgt:

    \begin{displaymath}x \sim y \Leftrightarrow f(x)=f(y)\end{displaymath}

    (D.h. zwei Elemente stehen in Relation zueinander, wenn sie denselben Funktionswert haben.)
    Wir überprüfen wieder die drei Regeln:
    1)
    Sei $x \in \mathbb{N}$.
    Es gilt natürlich f(x) = f(x).
    Das heisst also $x \sim x$ (nach der Definition von $\sim$).
    Also ist die Relation reflexiv.
    2)
    Seien $x,y \in \mathbb{N}$ (das x hier ist eine ``neue'' Variable und hat nichts mit dem x in 1) zu tun).
    Wenn $x \sim y$, d.h. also f(x)=f(y), dann ist auch f(y)=f(x) und somit (nach Definition von $\sim$) auch $y \sim x$.
    Also ist die Relation symmetrisch.
    3)
    Seien $x,y, z \in \mathbb{N}$ (x und y sind wieder ``neue'' Variablen und haben nichts mit 1) oder 2) zu tun).
    Sei $x \sim y$ und $y \sim z$.
    Dass heisst f(x)=f(y) und f(y)=f(z) (nach der Def. von $\sim$).
    Damit ist auch f(x)=f(z).
    Dass heißt aber wiederum $x \sim z$ (nach Def. von $\sim$).
    Also ist die Relation transitiv.
    Da die Relation wie gezeigt die drei Regeln erfüllt, ist sie eine Äquivalenzrelation.$\Box$


    Beispiele für Relationen, die keine Äquivalenzrelationen sind:

  3. Seien $x, y \in \mathbb{N}, f: \mathbb{N} \rightarrow \mathbb{N}$ eine Funktion auf den natürlichen Zahlen.
    Wir definieren folgende Relation: $ x \sim y \Leftrightarrow f(x) \le f(y)$
    Wir überprüfen wieder die drei Regeln:
    1)
    Sei $x \in \mathbb{N}$.
    Da gilt f(x) = f(x), gilt insbesondere auch $f(x) \le f(x)$.
    Damit gilt dann $x \sim x$ (wieder weil $\sim$ so definiert ist).
    Also ist die Relation reflexiv.
    2)
    Seien $x,y \in \mathbb{N}$
    Wenn $x \sim y$, d.h. also (nach Def.)$f(x) \le f(y)$,
    dann gilt nicht unbedingt $f(y) \le f(x)$.
    (z.B. fuer f(x)=3, f(y)=4)
    Also ist die Relation nicht symmetrisch.
    Damit erfüllt die Relation nicht alle drei geforderten Regeln, und ist somit auch keine Äquivalenzrelation. Damit sind wir fertig. $\Box$
    Interessehalber können wir jetzt noch die dritte Regel überprüfen. Dies ist aber nicht nötig, da wir ja jetzt schon wissen, das es sich hier nicht um eine Äquivalenzrelation handelt.
    3)
    Seien $x,y, z \in \mathbb{N}$
    Sei $x \sim y \; und \; y \sim z$.
    Dass heisst $f(x) \le f(y) \; und \; f(y) \le f(z)$.
    Damit ist auch $f(x) \le f(z)$.
    Dass heißt aber wiederum $x \sim z$.
    Also ist die Relation transitiv.
    Wir haben es also mit einer reflexiven, transitiven und nicht symmetrischen Relation zu tun.

  4. Sei M die Menge der Menschen, A, B zwei (beliebige) Menschen aus M und die Relation sei wie folgt definiert:

    $A \sim B \Leftrightarrow$``A versteht sich mit B''

    Wir überprüfen wieder die Regeln:

    1)
    $A \sim A$ heisst: ``A versteht sich mit A''.
    Da wir mal davon ausgehen, dass jeder Mensch sich mit sich selbst versteht (ja, ich weiss, darüber könnte man jetzt eigentlich hochphilosophische Diskussionen führen), ist dies also erfüllt.
    Also ist die Relation reflexiv.
    2)
    Sei $A \sim B$ d.h. ``A versteht sich mit B''.
    Daraus folgt natürlich auch, dass ``B versteht sich mit A'' ebenso gilt.
    Also $B \sim A$, d.h. die Relation ist symmetrisch.
    3)
    Sei $A \sim B$ und $B \sim C$. D.h. ``A versteht sich mit B'' und ``B versteht sich mit C''
    Daraus folgt aber nicht unbedingt, dass A und C sich verstehen.
    Es ist durchaus möglich, dass eine Person sich mit zwei anderen versteht, diese beiden anderen müssen sich aber nicht gegenseitig verstehen.
    Also ist die Relation nicht transitiv, und damit keine Äquivalenzrelation.
  5. Seien $a, b \in \mathbb{Z}$ und die Relation wie folgt definiert: $a \sim b \Leftrightarrow a \cdot b \ge 0$
    Wir überprüfen wieder die Regeln:
    1)
    $a \sim a \Leftrightarrow a \cdot a \ge 0$ Dies ist erfüllt, weil eine Zahl zum Quadrat immer $\ge 0$ ist. Damit haben wir die Reflexivität.
    2)
    Sei $a \sim b$.
    $\Leftrightarrow a \cdot b \ge 0$ (wegen der Definition von $\sim$ (in diesem Bsp.))
    $\Leftrightarrow b \cdot a \ge 0$ (wegen der Kommutativität der ganzen Zahlen (ab=ba))
    $\Leftrightarrow b \sim a$ (Definition von $\sim$)
    Die Relation ist somit symmetrisch.
    3)
    Gegenbeispiel:
    $-1 \sim 0 \; und \; 0 \sim 1$, denn
    $-1 \cdot 0 = 0 \ge 0 \; und \; 0 \cdot 1 = 0 \ge 0$
    ABER: $-1 \cdot 1 = -1 < 0 \Leftrightarrow -1 \not\sim 1$
    D.h. die Relation ist nicht transitiv, also keine Äquivalenzrelation.




mathe
home