Äquivalenzrelation über der Menge der 3-Kombinationen von M prüfen. Verstehe die Begründung der Antwort nicht...

Question

Aufgabe:

Kombinationen und Äquivalenzrelationen

Sei \( M=\{1,2, \ldots, 101\} \) und \( A=\left(\begin{array}{c}{M} \\ {3}\end{array}\right) \) die Menge aller 3 -Kombinationen von \( M \) Für jede 3 -Kombination \( K=\left\{n_{1}, n_{2}, n_{3}\right\} \in A \) mit \( n_{1}<n_{2}<n_{3} \) bezeichnen wir \( n_{1} \) als \( \min (K), n_{2} \) als \( \operatorname{med}(K) \) und \( n_{3} \) als \( \max (K) \)
Nun betrachten wir die folgenden drei Relationen \( \sim, \approx, \simeq \) über \( A \):

\( K_{1} \sim K_{2} \stackrel{\text { def }}{\Longleftrightarrow} \operatorname{med}\left(K_{1}\right)=\min \left(K_{2}\right) \)

\( K_{1} \approx K_{2} \stackrel{\text { def }}{\Longleftrightarrow} \min \left(K_{1}\right)=\min \left(K_{2}\right) \vee \operatorname{med}\left(K_{1}\right)=\operatorname{med}\left(K_{2}\right) \)
\( K_{1} \simeq K_{2} \stackrel{\text { def }}{\Longleftrightarrow} \min \left(K_{1}\right)=\min \left(K_{2}\right) \wedge \max \left(K_{1}\right)=\max \left(K_{2}\right) \)

a) Welche dieser drei Relationen ist eine Ä quivalenzrelation und welche nicht? Positive Antworten müssen nicht begründet werden. Bei negativen Antworten sollte durch ein Beispiel gezeigt werden, welche Eigenschaft verletzt ist.

Antworten:

\( ~ \) und \( \simeq \) sind Äquivalenzrelation

\( \approx \) ist keine Äquivalenzrelation, denn \( \approx \) ist nicht transitiv: \(  \)

\( \{1,2,3\} \approx\{1,5,7\} \land \{1,5,7\} \approx\{4,5,6\}, \), aber \( \{1,2,3\} \neq\{4,5,6\} \)

Verstehe die Begründung der Antworten nicht.

Answer 1

Bei Äquivalenzrelationen müssen ja Äquivalenzklassen entstehen. Um Elemente von diesen Klassen sind dann untereinander äquivalent. Man kann auch denken 'gleich' für einen bestimmten Zweck' Im Folgenden schreibe ich in Grün gleich. Anstelle von äquivalent. (Nur z Erklärungszwecken) Besser als 'äquivalent' abschreiben.

Gemäss Definition muss Symmetrie, Transitivität und Reflexivität gelten.

1. Refl: Jedes Element einer Klasse ist 'gleich'  sich selbst.

2. Symm: Wenn ein Element 'gleich' ist wie ein anderes, ist auch das andere 'gleich' wie das erste.

3. Trans: Wenn ein Element 'gleich' ist wie das Zweite und das Zweite gleich wie ein Drittes, ist auch das Erste 'gleich' wie das Dritte.

In der Aufgabe geht es nun um geordnete Mengen von 3 verschiedenen Zahlen.

Bei der ersten Relation gilt: 'gleich' wenn das mittlere Element gleich ist. Da entstehen automatisch 98 Äquivalenzklassen, mit den Zahlen 2,3,4,5,6,....,99 in der Mitte.

Bei der dritten Relation ist 'gleich': Das erste und das letzte Element sind gleich. Eine Äquivalenzklasse ist z.B.
(7,8,20);(7,9,20);(7,10,20);…(7,19,20) 

Die Transitivitäsbedingung ist wegen dem 'oder' in der Definition der 2. Relation der Aufgabenstellung nicht erfüllt.
D.h. es genügt nicht zu verlangen, dass das kleinste oder das mittlere Element gleich sind, wenn da eine Klasse entstehen soll. (1,2,3)   und    ( 1,5,7) wären gleich, weil ihr kleinstes Element gleich ist. (1,5,7)  und    (4,5,6) wären gleich, weil ihr mittleres Element gleich ist. Aber bei (1,2,3) und (4.5.6) sind weder das kleinste noch das mittlere Element gleich. Deshalb gemäss der Definition 'ungleich'. Also ist Transitivität verletzt.

 

 

Comments

Hi Lu,

für die 3. Relation ≅  wären (1,2,3) und (4.5.6) auch nicht transitiv, weil das maximum auch nicht gleich ist. kannst du mir das erklären bitte.

Danke

---

für die dritte Relation ist nur äquivalent, was die gleiche kleinste und die gleiche grösste zahl hat.

Du findest da keine Möglichkeit, um in 2 Schritten von 123 auf 456 zu kommen.

123 ist nur äquivalent mit sich selbst.

456 ebenfalls.

---

Achso,ok

Das gegenbeispiel ist nicht dafür geeignet. ok....danke

Answer 2

Du musst hier zwischen Beweis und Gegenbeispiel unterscheiden: willst du die Richtigkeit einer Aussage zeigen, dann musst du eigentlich alle Bedingungen prüfen. Willst du dagegen zeigen, dass sie falsch ist, dann reicht ein einziges Gegenbeispiel aus.

Da hier nach den Beweise nicht gefragt ist, erscheint die Aufgabe vielleicht etwas undurchsichtig, deswegen führe ich sie einfach.

 

Du musst also zeigen, dass die drei Bedingungen für eine Relation o erfüllt sind:

i) Reflexivität: a o a
ii) Symmetrie: a o b ⇔ b o a
iii) Transitivität: a o b und b o c ⇒ a o c

Dann heißt die Relation o Äquivalenzrelation.

 

Zu ~: i) Sei a = (n₁, n₂, n₃) dann gilt: med(a) = n₂ und wegen med(a)=med(a) ⇒ a ~ a

ii) Sei a = (n₁, n₂, n₃), b = (m₁, m₂, m₃) und es gelte a ~ b, das heißt: med(a) = med(b) bzw. n₂ = m₂. Dann gilt auch m₂ = n₂ bzw. med(b) = med(a) ⇒ b ~ a.
Die Rückrichtung wird analog gezeigt.

iii) Sei a = (n₁, n₂, n₃), b = (m₁, m₂, m₃), c =(k₁, k₂, k₃), und es gelte a ~ b (also n₂ = m₂) sowie b ~ c (also m₂ = k₂).
Setzt man nun die beiden Gleichungen gleich ergibt sich n₂ = k₂ also: a ~ c.

Damit ist ~ eine Äquivalenzrelation.

 

Zu ≈: Wie bereits da steht verstößt ≈ gegen die dritte Bedingung der Transitivität. Dadurch dass die beiden Bedingungen der Relation mit einem "Oder" verbunden sind, muss nur eine erfüllt sein. Dadurch ist es bei drei Elementen möglich, dass zwischen a und b nur die erste Bedingung erfüllt ist und zwischen b und c nur die zweite. Dann gilt zwar a ~ b und b ~ c aber nicht zwangsläufig a ~ c. Ein Gegenbeispiel ist ja genannt.

 

Zu ≅:i) Sei a = (n₁, n₂, n₃), dann gilt: max(a) = n₃, min(a)=n₁ und wegen min(a)=min(a) sowie max(a)=max(a) folgt a ≅ a.

ii) Sei a = (n₁, n₂, n₃), b = (m₁, m₂, m₃) und es gelte a ≅ b, das heißt n₁ = m₁ und n₃ = m₃. Dann gilt auch m₁ = n₁ und m₃ = n₃ also: b ≅a.

iii) Sei a = (n₁, n₂, n₃), b = (m₁, m₂, m₃), c =(k₁, k₂, k₃), und es gelte a ≅ b (also n₁ = m₁ und n₃=m₃) sowie b ≅ c (also m₁ = k₁ und m₃ = k₃). Setzt man die jeweils zusammenpassenden Gleichungen gleich, erhält man n₁=k₁ und n₃=k₃ also gilt auch a ≅ c.

Also ist ≅eine Äquivalenzrelation.

Comments

Deine Begründüng zu  ≈ habe ich nicht verstanden mit der Transitivität:

Könntest du es vielleicht nochmal erklären.Bitte

 

also wenn ich eine 3. Menge einführe in die relation  ≈  verstehe ich deine Meinung mit dem Oder nicht,

da beim Oder auch eine wahre aussage ergibt wenn beide richtig sind....oder bin ich neben der spur

---

Nein, das ist schon richtig, aber schau doch mal:

Nimm zum Beispiel an, für dich wären alle grünen Autos gleichwertig. Gleichzeitig sind für dich aber alle Autos von VW gleichwertig.

Mit dieser Unterscheidung erschaffst du keine Äquivalenzrelation, denn es gibt zwar grüne VWs aber nicht jedes grüne Auto ist gleichwertig mit jedem VW.

Das liegt an der Verletzung der Transitivität:

Ein grüner Mercedes ist gleichwertig mit einem grünen VW.

Und ein grüner VW ist gleichwertig mit einem blauen VW, das sind gerade die "Definitionen", die ich oben getroffen habe.

Das bedeutet aber nicht, dass ein grüner Mercedes gleichwertig mit einem blauen VW ist, die beiden lassen sich in unserer Kategorisierung ja überhaupt nicht vergleichen.

---

Eine letzte Frage.

Für den Lösungsansatz im Bild sind K₁  und K₂  gewählt.

Das sind 2 verschiedene Mengen aber trotzdem wurden {1,5,7} und {1,5,7} gewählt und mit einer UND verknüfung gebunden

das verstehe ich nicht

---

Das UND im Lösungsansatz ist das UND in der Definition für Transitivität. Links und Rechts von diesem und im Bild stehen Relationen zwischen 2 Elementen, in denen das ODER ausgenützt wird, indem nur eine der beiden Bedingungen (kleinstes oder mittleres Element gleich) erfüllt ist.

---

Achso, beispielsweise min(K₂) bedeutet schon eine Relation zwischen 2 Mengen, oder?

Wenn ja, dann hab ich es schon verstanden.

 

---

ok. tönt vernünftig. min(K₂) = min(K₁)  genügt wegen ODER für Relation.