TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 115

Aus VoWi
Zur Navigation springen Zur Suche springen
Nur teilweise gelöst: Gilt dies auch für die Vereinigung R_1 \cup R_2?

Seien R_1 und R_2 Äquivalenzrelationen auf der Menge M. Man beweise, dass dann auch ihr Durchschnitt R = R_1 \cap R_2 Äquivalenzrelation auf M ist.

Zu zeigen sind die drei Eigenschaften einer Äquivalenzrelation:

  • Reflexivität
  • Symmetrie
  • Transitivität

Hilfreiches[Bearbeiten]

Äquivalenzrelation[Bearbeiten]

Eine binäre Relation R auf einer Menge A heißt Äquivalenzrelation, wenn folgende drei Eigenschaften erfüllt sind:

Reflexivität: \forall a\, \in A: aRa,

Symmetrie: \forall a,b\, \in A: aRb \Rightarrow bRa,

Transitivität: \forall a,b,c\, \in A: (aRb \wedge bRc) \Rightarrow aRc.

Da ich mir nie sicher bin, wie man einen Sachverhalt mathematisch korrekt beschreibt, kann es durchaus sein dass der Lösungsvorschlag unten so nicht richtig ist. Ich hoffe die Idee dahinter ist ersichtlich, und wenn jemand die Lösung ausbessern oder bestätigen kann, bin ich für Feedback sehr dankbar. mfg, --W wallner

Reflexivität[Bearbeiten]

Da R_1 und R_2 beide Äquivalenzrelationen sind, stehen alle a \in M mit sich selbst in Relation, sowohl in Bezug auf R_1 als auch auf R_2.

\forall a \in M: (a,a) \in R_1
\forall a \in M: (a,a) \in R_2

\forall a \in M: (a,a) \in R_1 \wedge (a,a) \in R_2 \Rightarrow \forall a \in M: (a,a) \in (R_1 \cap R_2)

Symmetrie[Bearbeiten]

Ähnlich wie bei der Reflexivtät gilt hier

\forall (a,b) \in R_1: (b,a) \in R_1
\forall (a,b) \in R_2: (b,a) \in R_2

\forall (a,b) \in R_1 \wedge (a,b) \in R_2: (b,a) \in R_1 \wedge (b,a) \in R_2 \Rightarrow
\forall (a,b) \in (R_1 \cap R_2): (b,a) \in (R_1 \cap R_2)

Transitivität[Bearbeiten]

Da R_1 und R_2 beide transitiv sind, gilt ähnlich wie oben:

\forall (a,b), (b,c) \in R_1: (a,c) \in R_1
\forall (a,b), (b,c) \in R_2: (a,c) \in R_2

\forall (a,b), (b,c) \in R_1 \wedge (a,b), (b,c) \in R_2: (a,c) \in R_1 \wedge (a,c) \in R_2 \Rightarrow
\forall (a,b), (b,c) \in (R_1 \cap R_2): (a,c) \in (R_1 \cap R_2)

mfg, --W wallner

Alternative Lösung[Bearbeiten]

Sind R und S zwei Aquivalenzrelationen über A, dann ist auch R ∩ S eine Aquivalenzrelation über A.

Seien R und S zwei Aquivalenzrelationen, also reflexiv, symmetrisch und transitiv. Wir müssen nachweisen, dass dann auch R ∩ S diese drei Eigenschaft besitzt.

(1) Die Reflexivitat von R ∩ S folgt sofort aus der Reflexivität von R und S. Für alle x ∈ A gilt nämlich xRx und xSx und damit nach Definition von ∩auch x(R ∩ S)x.

(2) Zum Nachweis der Symmetrie von R ∩ S sei für zwei beliebige x, y ∈ A angenommen, dass x(R ∩ S)y, und damit sowohl xRy als auch xSy gilt. Da R und S als Aquivalenzrelationen symmetrisch sind, folgt daraus yRx und ySx, also y(R ∩ S)x. R ∩ S ist folglich symmetrisch.

(3) Zum Nachweis der Transitivität von R ∩ S betrachten wir drei Elemente x, y, z ∈ A mit x(R∩S)y und y(R∩S)z. In der formalen Sprache der mathematischen Logik formuliert, gilt also (xRy ∧ xSy) ∧ (yRz ∧ ySz). Da ∧ assoziativ und kommutativ ist, folgt (xRy ∧ yRz) ∧ (xSy ∧ ySz). Da R und S als Aquivalenzrelationen transitiv sind, folgt weiter xRz ∧ xSz, oder gleichbedeutend x(R ∩ S)z. R ∩ S ist also wie behauptet transitiv.

Quelle: Mathematische Grundlagen für Informatik (5. Auflage, ISBN 978-3-8348-8125-0), S. 80