TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 120

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. & Gilt dies auch für die Vereinigung $R_{1}\cup R_{2}$?

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Zu zeigen sind die drei Eigenschaften einer Äquivalenzrelation:

• Reflexivität
• Symmetrie
• Transitivität

Hilfreiches

Äquivalenzrelation

Äquivalenzrelation

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

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

Ä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

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

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

Lösungsvorschlag für R1 ∪ R2 von Marco Z.

Nein, R1 und R2 sind keine Äquivalenzrelationen. Begründung folgt zugleich:

Reflexivität

folgt aus der Reflexivität von R1 ∩ R2 und der Definition von Vereinigungsmengen. Ist erfüllt.

Symmetrie

x,y ∈ R1 ∩ R2 mit x(R1 ∪ R2)y damit sowohl xR1y, als auch xR2y gilt, weil R1 und R2 auch symmetrisch => yR1x und yR2x, also y(R1 ∪ R2)x, R1 ∪ R2 ist symmetrisch. Ist erfüllt.

Transitivität

Das ist am leichtesten mit einem Gegenbeispiel widerlegt:

R1= {(x,x), (x,y), (y,x), (z,z)}

R2= {(x,x), (y,z), (z,y), (z,z)}

R1 ∩ R2 ist folgerlich: {(x,x), (x,y), (y,x), (z,z), (x,x), (y,z), (z,y), (z,z)}

Wenn wir nun versuchen die Transitivität herzustellen sehen wir das zwar (x,y) und (y,z) Elemente der Menge sind, (x,z) aber nicht. Folglich ist die Transitivität verletzt. Es ist keine Äquivalenzrelation.

Anhang: Für das Komplement R1 \ R2 gilt folgendes

Betrachten wir die Menge M = {1,2} mit den Relationen:

R1 = {(1,1), (1,2), (2,1), (2,2)}

R2 = {(1,1), (2,2)}

(jeweils Reflexiv, symmetrisch und transitiv - stellen also ÄR auf M dar)

R1\R2 = {(1,2),(2,1)} ist jedoch wegen (1,1) ∉ R1 \ R2 die Reflexivität verletzt, folglich ist auch das Komplement keine Äquivalenzrelation (in diesem Fall auf die Menge M)

Quelle