Äquivalenzrelation beweisen bzw. widerlegen: Bsp. M=ℤ, R={(a,b)∈ℤxℤ |a-b|≤3

Question

bitte um Hilfe:

Aufgabe ist, die folgenden Relationen zu untersuchen, ob es sich um Äquivalenzrelationen handelt:

i) M=ℤ, R={(a,b)∈ℤxℤ |a-b|≤3

ii) M=ℤ, R={(a,b)∈ℤxℤ | es gibt k ∈ ℤ mit a=b+k*3}

iii) M=ℤ², R={((a₁,b₁),(a₂,b₂))∈MxM | a₁*b₂=a₂*b₁}

iv) M=ℝxℝ, R={((x₁,y₁),(x₂,y₂))∈MxM | x₁²+y₁²=x₂²+y₂²}

Bisher habe ich, dass:

i) keine Äquivalenzrelation ist, da nicht transitiv, denn:

z.B. erfüllen (1,3) und (3,5) die Relation, aber (1,5) nicht.

ii) ist ebenfalls keine Äquivalenzrelation, da nicht symmetrisch, denn:

z.B. für k=1 und (6,3) aber nicht für (3,6)

Korrekt soweit?

Bei iii) und iv) hänge ich, daher bitte um Hilfe :)

Edit: Reflexiv sind beide wohl, oder?

Answer 1

(iii) und (iv) sind es.

Comments

Du meinst es sind Äquivalenzrelationen?

---

Genau..............................

---

Cool, danke. Kann ich dich detailliert zu iv) befragen? :)

Reflexiv ist ja recht klar, wenn (x1,y1)=(x2,y2) ist x₁²+y₁²=x₂²+y₂² reflexiv.

Wie prüfe ich die Symmetrie?

---

Reflexiv heißt, ein Element steht in Relation zu sich selbst, also

\( (x,y) \sim (x,y) \)

Symmetrie:

\( (x1,y1) \sim (x2,y2) \iff (x2,y2) \sim (x1,y1) \)

---

Dann schreibe ich die Reflexivität so:

x1²+y1²=x1²+y1² ?

Symmetrie also so:

x₁²+y₁²=x₂²+y₂² ⇔ x₂²+y₂²=x₁²+y₁

---

Deine Schlussfolgerung fehlt noch.

Und transitiv auch.

---

Wie schlussfolgere ich denn weiter?

Transitiv wäre dann:

Aus x₁²+y₁²=x₂²+y₂² und x₂²+y₂²=x₃²+y₃² folgt x₁²+y₁²=x3²+y3²

---

Du hast drei Formeln hingeschrieben, und die sind formal richtig.

Hast Du jetzt eine Äquivalenzrelation oder nicht? Und warum?

---

Ah, ok :)

Ja, ich habe eine Äquivalenzrelation, da die gegebene Relation sowohl reflexiv, als auch symmetrisch als auch transitiv ist.

---

Nein, Du hast erst einmal drei Behauptungen aufgestellt. Sind die richtig oder falsch?

---

Ich stehe grad auf dem Schlauch. Ich muss das noch beweisen, klar. Aber wie?

---

Du hast bei reflexiv \( x1^2+y1^2 = x1^2+y1^2 \). Das ist ein reiner Formalismus und eine Behauptung. Stimmt diese Behauptung, oder nicht?

---

Klar stimmt das, da ja die Summe von zwei Quadratzahlen das gleiche ist wie die Summe derselben Zahlen. Aber ist das nicht offensichtlich?

---

Nein, das ist nicht immer so offensichtlich, wie Du denkst, und Du musst das überprüfen.

Primitives Beispiel:

x steht in Relation zu y, wenn x Sohn von y ist.

Reflexiv ist dann rein formal: "A ist Sohn von A".

Du musst immer überprüfen, ob die Behauptung richtig ist, und hier ist sie es sicher nicht.

---

Dein Beispiel ist klar. Meinst du x₁²+y₁²=x₁²+y₁²  ist nicht richtig? Hier haben wir doch aber gleichheit mit den gleichen Zahlen?

---

Ich meine nicht, dass das nicht richtig ist. Natürlich ist das richtig. Aber Du musst das trotzdem bei allen 3 Behauptungen dazuschreiben.

---

Also:

Die Relation ist reflexiv, da für alle x,y ∈ ℝ gilt: x1²+y1²=x1²+y1²

Die Relation ist symmetrisch, da für alle x,y ∈ ℝ gilt: x₁²+y₁²=x₂²+y₂² ⇔ x₂²+y₂²=x₁²+y₁
Die Relation ist transitiv, da für alle x,y ∈ ℝ gilt: x₁²+y₁²=x₂²+y₂² und x₂²+y₂²=x₃²+y₃² folgt x₁²+y₁²=x₃²+y₃²

Ist das so formal korrekt?

---

Ich würde das anders machen:

(1) reflexiv:

\( x1^2+y1^2 = x1^2+y1^2 \)

Diese Behauptung ist richtig.

(2) symmetrisch:

..........

Weil reflexiv richtig, und symmetrisch ..... ist das eine Äquivalenzrelation.

---

ok, dann mal Probe an iii) :)

a1*b2=a2*b1 ⇔ a1/b1=a2/b2

(1) reflexiv:

a1/b1=a1/b1

Diese Behauptung ist richtig.

(2) symmetrisch:

a1/b1=a2/b2 ⇒ a2/b2=a1/b1

Diese Behauptung ist richtig.

(3)

a1/b1=a2/b2 ∧ a2/b2=a3/b3 ⇒ a1/b1=a3/b3

Da die Relation reflexiv, symmetrisch und transitiv ist, handelt es sich um eine Äquivalenzrelation.

Ja?

---

Vom Prinzip würde ich das so lassen.

Du hast bei (3) das "transitiv" vergessen und auch "richtig" oder "falsch".

Außerdem gefällt mir an der ganzen Vorgehensweise nicht, dass Du Brüche verwendest. Halte Dich an die Definition der gegebenen Relation. Die heißt hier \( a1*b2 = a2*b1 \) und nicht \( a1/b1 = a2/b2 \). Du kannst Dir durch solche Umformungen viel Ärger machen. Hier ist es nur die Division durch 0, die das Original überhaupt nicht hat. Manchmal ist der Ärger durch Umformungen wesentlich größer.

---

Würde es denn auch mit a1* b2 = a2* b1 funktionieren? Ich dachte durch die Umformung sind die Tupel "sauber getrennt". (a1,b1) ist dann quasi das x mit x ~ x.

---

Mit dem Original funktioniert das natürlich. Setze in den Formalismus ein. Prüfe, ob richtig oder falsch, genau wie bei (iv) auch. (Das mit dem "sauber trennen" würde ich wirklich lassen. Wenn Du z.B. Relation über komplexe Zahlen hast, kannst Du das meist auch gar nicht.)

Reflexiv:

\( (a,b) \sim (a,b) \)

\( a*b = a*b \)

Richtig.

Symmetrisch:

Usw.

---

ok, cool.

Vielen Dank. Es hilft echt, wenn jemand mit Ahnung viel hilft :)

Falls ich dir nicht zuviel Zeit stehle, darf ich noch zur ii) fragen? Da oben geht es wohl nicht weiter.

Reflexiv:

a=b+k*3 ist für k=0 immer reflexiv, da a=a+0*3

Diese Behauptung ist richtig.

Symmetrisch:

a=b+k*3 ist symmetrisch, da b=a+(-k)*3

Diese Behauptung ist richtig.

Transitiv:

a=b+3k und b=c+3k folgt a=c+3k mit verschiedenen k

Diese Behauptung ist richtig.

Da die Relation reflexiv, symmetrisch und transitiv ist, handelt es sich um eine Äquivalenzrelation.

Ja?

---

Dein Ansatz ist falsch. Reflexiv heißt, ein Element steht in Relation zu sich selbst (s.o.)

Reflexiv:

\( \exists ~ k \in Z: a = a+k*3 \)

Richtig, da ein k existiert, nämlich k = 0.

Usw.

---

Symmetrisch:

∃ k∈Z: a=b+k*3 ⇒ b=a+k*3

Diese Behauptung ist für ein k und (-1)*k richtig.

Transitiv:

∃ k∈Z: a=b+3k ∧ b=c+3k ⇒ a=c+3k

Diese Behauptung ist richtig.

---

Dein Ansatz für symmetrisch ist falsch (halte Dich exakt an die Vorgabe):

\( \exists ~ k1 \in Z: a = b+k1*3 \iff \exists ~ k2 \in Z: b = a+k2*3 \)

Usw.

(Transitiv später, erst einmal dieses.)

---

Muss ich dann zur Symmetrie noch erwähnen, dass k2=(-1)*k1 ist?

---

Würde ich machen, ja. Beide Bedingungen in der Äquivalenz hängen ja zusammen.

---

Also:

Symmetrie:

∃ k1∈Z:a=b+k1∗3⟺∃ k2∈Z:b=a+k2∗3

Diese Behauptung ist für k2=(-1)*k1 richtig.

---

Und jetzt noch transitiv. Formalismus beachten, der oben ist falsch. Außerdem hast Du nicht begründet, warum richtig.

---

∃ k1∈Z: a=b+3k ∧ ∃ k2∈Z: b=c+3k ⇒ ∃ k3∈Z: a=c+3k

Die Behauptung ist richtig für... hm. Man könnte a,b,c als rekursive Folge definieren, also x_n+1 = x_n   +3, x₁ = 1, a=x_n+2 ,b=x_n+1 ,c=x_n  und k=n

Oder?

---

Auf gar keinen Fall. Das ist eine Implikation. "Wenn k1 und k2, dann k3". Du setzt voraus, dass es ein k1 und ein k2 gibt, und willst dann ein k3 haben. Kriegst Du es? Wie sieht es aus?

(Du hast Deine k123 in den Formeln nicht richtig eingetragen.)

Answer 2

z.B. für k=1 und (6,3) aber nicht für (3,6)

Korrekt soweit?

Nein, nicht korrekt. Wenn es für (6,3) den Wert k=1 gibt, dann gibt es auch für (3,6) einen solchen k-Wert (in dem Fall k=-1).

a₁*b₂=a₂*b₁ kannst du übrigens umschreiben in a₁/b₁=a₂/ b₂ (sofern die Nenner nicht gerade 0 sind).

Die Paare sind also zueinander äquivalent, wenn sie die gleichen Brüche darstellen.

Damit ist auch die Transitivität klar (aus Bruch1=Bruch2 und Bruch2=Bruch3 folgt Bruch1=Bruch3).

Comments

danke! ist das k bei ii) nicht fest? Ich meine, ich wähle ein k und prüfe dann ein beliebiges Tupel auf Symmetrie?

---

danke! ist das k bei ii) nicht fest?

Nein.  1 steht in Relation zu 4 steht in Relation zu 7 steht in Relation zu 10...

jeweils mit verschiedenem k.

Die Äquivalenzklassen sind hier die Restklassen mod 3.

---

Sorry, da komme ich nicht mit. Kannst du das genauer erklären?

Mein Gedanke zwischendurch:

ist ii) also symmetrisch weil es immer ein k gibt, das a=b+3k erfüllt, da b=a-3k?

---

Sorry, da komme ich nicht mit. Kannst du das genauer erklären?

1 steht in Relation zu 4, denn es gibt eine ganze Zahl k mit  1+3k=4 (und zwar k=1).

1 steht in Relation zu 7, denn es gibt eine ganze Zahl k mit  1+3k=7 (und zwar k=2).

1 steht in Relation zu 10, denn es gibt eine ganze Zahl k mit  1+3k=10 (und zwar k=3).

Es gilt auch

4 steht in Relation zu 4, denn es gibt eine ganze Zahl k mit  4+3k=4 (und zwar k=0).
4 steht in Relation zu 7, denn es gibt eine ganze Zahl k mit  4+3k=7 (und zwar k=1).
4 steht in Relation zu 10, denn es gibt eine ganze Zahl k mit  4+3k=10 (und zwar k=2).

Es gilt auch

4 steht in Relation zu 1, denn es gibt eine ganze Zahl k mit  4+3k=1 (und zwar k=-1).
7 steht in Relation zu 1, denn es gibt eine ganze Zahl k mit  7+3k=1 (und zwar k=-2).
10 steht in Relation zu 1, denn es gibt eine ganze Zahl k mit  10+3k=1 (und zwar k=-3).

---

Ok, stimmt dann die Begründung:

ist ii) also symmetrisch weil es immer ein k gibt, das a=b+3k erfüllt, da b=a-3k?

Transitiv geht dann also auch, da es auch immer k gibt für

aus a=b+3k und c=d+3k folgt a=d+3k?