Zum Hauptinhalt springen

Eine weitere wichtige Art der Relationen sind die Äquivalenzrelationen. Die Äquivalenzrelationen und die mit diesen eng zusammenhängenden Äquivalenzklassen sind für viele weiterführende Begriffe der Mathematik essentiell.

Äquivalenzrelationen

Bevor wir die Äquivalenzrelationen formal einführen, widmen wir uns erst nochmal ein paar wichtige Einordnungen Relationen betreffend.

Reflexivität / Symmetrie / Transitivität

Sei MM eine Menge und ϱ⊆M×M\varrho \subseteq M \times M eine Relation.

  • ϱ\varrho heißt reflexiv :⇔∀x∈M ⁣:(x,x)∈ϱ:\Leftrightarrow \forall x \in M \colon (x,x) \in \varrho
  • ϱ\varrho heißt symmetrisch :⇔∀x,y∈M ⁣:(x,y)∈ϱ→(y,x)∈ϱ:\Leftrightarrow \forall x,y \in M \colon (x,y) \in \varrho \rightarrow (y,x) \in \varrho
  • ϱ\varrho heißt transitiv :⇔∀x,y,z∈M ⁣:(x,y)∈ϱ∧(y,z)∈ϱ→(x,z)∈ϱ:\Leftrightarrow \forall x,y,z \in M \colon (x,y) \in \varrho \wedge (y,z) \in \varrho \rightarrow (x,z) \in \varrho

Beispiele​

Gegeben sei die Menge M={a,b,c}M = \{a,b,c\}.

  • ϱ={(a,a),(b,b),(c,c),(a,b),(a,c)}\varrho = \{(a,a), (b,b), (c,c), (a,b), (a,c)\} ist reflexiv, da die Paare (a,a)(a,a), (b,b)(b,b) und (c,c)(c,c) in ϱ\varrho sind.
    ϱ={(a,a),(c,c),(a,b)}\varrho = \{(a,a), (c,c), (a,b)\} dagegen ist nicht reflexiv, da (b,b)(b,b) fehlt.

  • ϱ={(a,a),(a,b),(b,a),(b,c),(c,b)}\varrho = \{(a,a), (a,b), (b,a), (b,c), (c,b)\} ist symmetrisch, da zu jedem Paar (x,y)(x,y) auch das Inverse Paar (y,x)(y,x) vorkommt.
    ϱ={(a,a),(a,c),(b,a)}\varrho = \{(a,a), (a,c), (b,a)\} dagegen ist nicht symmetrisch, da sowohl (c,a)(c,a) und (a,b)(a,b) fehlt.

  • ϱ={(a,b),(b,c),(a,c)}\varrho = \{(a,b), (b,c), (a,c)\} ist transitiv, da (a,c)(a,c) vorhanden ist, nachdem schon (a,b)(a,b) und (b,c)(b,c) in ϱ\varrho sind.
    ϱ={(a,b),(b,a),(b,c)}\varrho = \{(a,b), (b,a), (b,c)\} dagegen ist nicht transitiv, da sowohl (a,a)(a,a) fehlt.

Eine Relation, die nun all diese drei Eigenschaften zugleich erfüllt nennt sich Äquivalenzrelation.

Äquivalenzrelation

Sei MM eine Menge und ϱ⊆M×M\varrho \subseteq M \times M eine Relation. ϱ\varrho heißt Äquivalenzrelation, falls ϱ\varrho reflexiv, symmetrisch und transitiv ist.

Beispiele​

Die wohl bekannteste Äquivalenzrelation auf jeder Menge MM ist die Gleichheit == mit ihren üblichen Eigenschaften. Äquivalenz in der Logik ist ebenfalls eine Äquivalenzrelation.