Beweis Äquivalenzrelation

Cherrylein · 7. August 2009 um 11:50

Hi, ich hoffe ihr könnt mir helfen. Ich steh bei diesen abstrakten Beweisen total aufm Schhlauch.

Also,

Sei M = P ({1,2,3,4}). Gegeben ist die folgende Relation : R = {(A,B) € M x M | |A|=|B|}

Zeigen Sie: R ist eine Äquivalenzrelation.

So,dass ich jetzt Reflexivität, Symmetrie und Transitivität beweisen muss, weiss ich.

Nur ich komm mit den Defintionen überhaupt nicht klar, bzw.weiss nicht wie ich die anwenden soll.

Für reflexiv, für alle a € A gilt (a,a) € R.

Muss ich jetzt doch irgendwie zeigen das a ein Element des
Kreuzprodukts ist und A den gleichen Betrag wie A hat, oder?!

aRa da A € M x M |A|=|A| ?!

Und was soll diese (a,a) € R überhauot bedeuten?

Ich hab zwei gleiche Elementen aus A und díe sollen in der Realtion enthalten sein?!

Symmetrie, (a,b) € R und (b,a) € R

(A,B) € M x M und |A|=|B|

(B,A) € M x M und |B|=|A|

Für mich klingt das alles unlogisch, woher weiss ich denn , dass (a,b) sowie (b,a) in der Relation vorhanden ist. Mir ist das alles zu abstrakt.

Und beim Kreuzprodukt ist doch die Reihenfolge wichtig, oder nicht? Wieso kann ich dann a und b einfach vertauschen, und sagen beides ist Element der Relation.

Ich glaub ich hab das ganze Prinzip einfach noch nicht verstanden, vielleicht könnt Ihr mir ja weiterhelfen.

Ganz lieben Dank schonmal…

Anonym_e52f27a38f6b · 7. August 2009 um 13:27

Hallo!

Mir scheint, Du hast wirklich das ganze Prinzip noch nicht durchschaut. Nehmen wir mal einfach den Begriff „Äquivalenzrelation“ auseinander.

Was ist eine Relation? Mathematisch gesehen ist eine Relation auf M eine Teilmenge von MxM, also der Paare aus M. Vom Begriff her bedeutet „Relation“ jedoch nichts Anderes als „Verhältnis“. Wie passt das zusammen?

Nehmen wir uns mal ein Beispiel, eine bestimmte Relation. Ich schlage vor: M sind natürliche Zahlen, und x steht in Beziehung zu y, wenn x ein Teiler von y ist.
Den sprachlichen Aspekt befriedigt dies vollkommen: Sicherlich beschreibt „x ist ein Teiler von y“ eine Beziehung zwischen x und y. Und wie sieht’s mathematisch aus?
Da sehe ich mir also Paare von natürlichen Zahlen an und wähle jetzt bestimmte aus, und zwar genau die, wo x ein Teiler von y ist. (1,2) packe ich also in die Menge rein, (2,10) ebenfalls, aber (10,2) und (2,3) nicht. Schon habe ich eine wunderbare Menge von Zahlenpaaren, die mir eine Beziehung - also Relation - beschreibt.
R={(x,y) in NxN mit x|y}.

Was bedeutet nun „äquivalent“? Nichts weiter als „gleichwertig“. Eine Relation ist also genau dann eine Äquivalenzrelation, wenn beide Zahlen in ihrer Beziehung als gleichwertig angesehen können.
Dazu gehört z.B., dass jede von ihnen mal „oben liegen“ darf , also wenn (1,2) in Beziehung stehen, dann sollte auch (2,1) drin sein. Bei der Teiler-Relation ist das nicht so, also ist’s wohl keine Äquivalenzrelation.

Gehen wir jetzt erst einmal die drei Eigenschaften von Äquivalenzrelationen durch und schauen mal, was die Partner in dieser Beziehung so „gleichwertig“ macht:

Reflexivität: Was kann man sich Gleichwertigeres vorstellen als zwei vollkommen gleiche Objekte?! Offenbar sind im Paar (1,1) beide Partner gleichwertig, also sollte dieses Paar auch in jeder Äquivalenzrelation drin sein (vorausgesetzt, M enthält ein Element namens „1“).

Symmetrie: Das hatten wir gerade: Jeder darf mal oben liegen. Also: Wenn (1,-1) in der Relation ist, muss auch (-1,1) da drin sein, sonst ist die arme -1 benachteiligt, weil sie immer hinten stehen muss.

Transitivität: Nehmen wir an, wir finden (1,2) und (2,3) in unserer Äquivalenzrelation. 1 und 2 gehen also eine Beziehung ein, 2 und 3 gehen ebenfalls eine Beziehung ein. Eine Klassische Ménage à trois - das kann nur funktionieren, wenn sich auch 1 und 3 mögen (sonst fühlen sich 1 und 3 nur ausgenutzt), also muss (1,3) auch noch in die Relation rein.

Mehr ist da nicht dran.

Wenn Du das verstanden hast, kannst Du vielleicht schon den „abstrakten Beweis“ führen. (Ich hab das hier in Gänsefüßchen gesetzt, weil’s eigentlich gar kein abstrakter Beweis ist - Du hast ja eine ganz konkrete Beziehung gegeben und sollst nur für diese die Eigenschaften überprüfen: Weniger abstrakt geht’s ja kaum!)

Für den Fall, dass Dir der Beweis immer noch nicht gelingt, werde ich (wenn jetzt nicht jemand schneller war) noch ein paar Hinweise zum Beweisen im Allgemeinen und im Besonderen geben, dann versuchst Du’s einfach damit noch mal, und wenn’s dann immer noch nicht klappt, kannst Du Deine konkreten Probleme hier klar darlegen, und damit werden sie sich flugs aus der Welt schaffen lassen.

Liebe Grüße
Immo

Anonym_e52f27a38f6b · 7. August 2009 um 13:52

Hallo noch mal!

Falls Du neu hier im Forum bist, möchte ich Dich darauf hinweisen, dass die älteren Antworten auf Deine Frage weiter unten stehen. Lies also bitte zuerst meinen anderen Beitrag, bevor Du (evtl.) hier weiterliest.

Wenn Du einen Beweis führen möchtest, musst Du genau zwischen Voraussetzungen und Behauptungen unterscheiden. Das fällt vielen Beweisanfängern schwer, deshalb hier einige Hinweise:

Schreibe zu beweisende Behauptungen immer ganz auf, also nicht:

Zu zeigen: a²+b²=c²; sondern:
Zu zeigen: In einem rechtwinkligen Dreieck mit Hypotenuse der Länge c und Katheten der Längen a bzw. b gilt: a²+b²=c².

Daraus kannst Du sofort entnehmen, welche Voraussetzungen in Deinen Beweis einfließen (es wird halt nicht ohne rechten Winkel gehen, und wenn ich die Seiten falsch benenne, geht’s auch schief).

ist eigentlich nur ein Unterpunkt zu 1.: Wenn Der Satz Quantoren („für alle“ / „es gibt ein“ / „es gibt genau ein“) beinhaltet, lasse diese _ nie - unter keinen Umständen! - _ weg. Sonst erschwert das das Verständnis der Aussage, und zwar nicht nur für Dich, sondern für alle, die Dir helfen wollen.

Diese beiden Punkte wendest Du jetzt auf die Eigenschaften der Äquivalenzrelation an:

Reflexivität: Nicht: (a,a) in R; sondern: Für alle a in M gilt: (a,a) in R.

Symmetrie: Nicht: (a,b) und (b,a) in R; sondern?
Na, wie hatten wir’s denn vorhin formuliert? Wenn (1,-1) in Beziehung stehen, dann sollen bitteschön auch (-1,1) in Beziehung stehen.
Also: Wenn (a,b) in R ist, dann ist auch (b,a) in R.

Transitivität: Ich wette, das schaffst Du allein. Ist ja fast so ähnlich wie Symmetrie.

ist der Wichtigste Punkt für Beweisanfänger: Schreibe Dir Voraussetzungen und Behauptungen getrennt auf, also links Voraussetzungen, rechts Behauptungen, von mir aus auch umgekehrt, aber so, dass Du selbst nicht durcheinander kommst. Reserviere zumindest auf Deinem Schmierblatt (ich hoffe mal, dass Du den Beweis nicht sofort ins Reine schreiben willst!) einen bestimmten Bereich immer für die Voraussetzungen, einen anderen immer für die Behauptungen.
Dann siehst du nämlich erstens, was Du alles verwenden kannst, und zweitens, was Du herausbekommen willst.
Du kannst Dir dann beide Seiten so lange äquivalent umformen, wie’s halt geht, und dann solltest Du sehen, wie der Beweis funktioniert (zumindest in der Linearen Algebra sind 95% der Beweise derart, dass man dann sieht, wie sie gehen).

Ich mach das mal am Beispiel für die Symmetrie Deiner Äquivalenzrelation, und den Rest kriegst Du dann sicher alleine hin:

<u>Voraussetzung:</u><u>Behauptung (zu zeigen):</u>

(a,b) in R (b,a) in R
 (a,b) in {(X,Y) in MxM mit |X|=|Y|} (b,a) in {(X,Y) in MxM mit |X|=|Y|}
 a in M; b in M; und |a|=|b| b in M; a in M; und |b|=|a|

<u>Also (Beweis):</u>

b in M und a in M gelten nach Voraussetzung.
Da "=" symmetrisch ist, ist die Voraussetzung |a|=|b| äquivalent zu |b|=|a|, was zu zeigen war.

Noch Fragen? Nur zu, bis alles klar ist.

Liebe Grüße
Immo

michael_f7f5bc · 7. August 2009 um 13:59

hi,

Sei M = P ({1,2,3,4}). Gegeben ist die folgende Relation : R =
{(A,B) € M x M | |A|=|B|}
Zeigen Sie: R ist eine Äquivalenzrelation.

übersetzt in die sprache deutsch: du sollst für alle teilmengen der menge {1,2,3,4} zeigen: die mächtigkeit der mengen ist eine äquivalenzrelation.

das schwierige an der sache ist vermutlich, zwischen „mengen“ und „elementen“ zu unterscheiden. in der potenzmenge von {1,2,3,4} sind die elemente mengen (nämlich die teilmengen von {1,2,3,4}; jede teilmenge von {1,2,3,4} ist ein element von M).

was ich nicht genau weiß: wie ihr |A| (die mächtigkeit einer menge A = die anzahl ihrer elemente, wenn die menge endlich ist) definiert habt. ist hier aber fast egal.

So,dass ich jetzt Reflexivität, Symmetrie und Transitivität
beweisen muss, weiss ich.

ja.
also zur reflexivität:

es sei also A € M (d.h. A teilmenge von {1,2,3,4}).
dann ist - weil |A| = |A| für jedes A (das gilt allgemein, egal für jedes A - (A,A) aus R. also ist R reflexiv.

zur symmetrie:
sei also A € M und B € M
wenn (A,B) € R ==> |A| = |B| ==> |B| = |A| ==> (B,A) € R
(es gilt allgemein: x=y ==> y=x)
also ist R symmetrisch.

zur transitivität:
seien also A, B, C € M
seien (A,B) € R und (B,C) € R.

dann ist |A| = |B| und |B| = |C| … nach def. von R
also ist |A| = |C|
also ist (A,C) € R

also ist R transitiv.

Nur ich komm mit den Defintionen überhaupt nicht klar,
bzw.weiss nicht wie ich die anwenden soll.

Für reflexiv, für alle a € A gilt (a,a) € R.

Muss ich jetzt doch irgendwie zeigen das a ein Element des

Kreuzprodukts ist und A den gleichen Betrag wie A hat,
oder?!

dass
da gehts jetzt mit den As durcheinander. die As sind einerseits elemente von P({1,2,3,4}), also teilmengen von {1,2,3,4]. andrerseits sind sie für dich hier mengen, auf denen die relation definiert ist. die relation ist aber auf der menge der teilmengen definiert.
deine klein-a a sind also eigentlich die mengen A in der relation R auf der potenzmenge P({1,2,3,4})

aRa da A € M x M |A|=|A| ?!

Und was soll diese (a,a) € R überhauot bedeuten?

Ich hab zwei gleiche Elementen aus A und díe sollen in der
Realtion enthalten sein?!

nö, nicht wirklich. du hast ein element A von M = eine teilmenge von {1,2,3,4} und betrachtest |A| = die anzahl der elemente von A

jetzt gilt immer: |A| = |A|
usw.

Symmetrie, (a,b) € R und (b,a) € R

(A,B) € M x M und |A|=|B|

(B,A) € M x M und |B|=|A|

Für mich klingt das alles unlogisch, woher weiss ich denn ,
dass (a,b) sowie (b,a) in der Relation vorhanden ist. Mir ist
das alles zu abstrakt.

s.o.
mathematik ist in gewissem sinn die förderung von bzw. die forderung nach abstraktion.

Und beim Kreuzprodukt ist doch die Reihenfolge wichtig, oder
nicht? Wieso kann ich dann a und b einfach vertauschen, und
sagen beides ist Element der Relation.

äquivalenzrelationen sind i.w. verallgemeinerte (abstrahierte) gleichheiten. wenn 2 dinge in bezug auf einen aspekt (hier: die mächtigkeit) gleich sind, kann man das als äquivalenz schreiben.

hth
m.

Blahahaking · 7. August 2009 um 14:42

Hmm, vlt solltest du dir auch erstmal klarmachen was das überhaupt für eine Menge ist , bzw was mit dem Kreuzprodukt genau gemeint ist,evt. wir Dir dann klarer was genau zu beweisen ist:

M:=P(…) Ich nehme mal an P bedeutet Potenzmenge.
dann sind dann alle möglichen Teil mengen von {1,2,3,4}
also z.B : {1},{2}…{1,2}…{2,3,4}…usw.

Mit den betragststichen ist wahrsch. die kardinalität dieser menge gemeint, also (hier bei endlichen mengen) die anzahl an elementen in einer menge.

nun ist a€{MxM} ,platt ausgedrückt,einfach ein beliebiges Paar
aus zwei elementen von M , also z.B. ({1},{2,3,4}) oder sowas.Ist hier eher obligat und dient zus ordnung.

naja, nochmal der Kern ist , mach dir immer klar was das für mengen sind, z.B. anfangen auszuschreiben wenns nicht anders geht .

dann ist die aufgabe recht simpel, denn es geht einfach nur um die anzahl der elemente.

also
1.hat A soviele Elemente wie A?
2.wenn A soviele Elemente hat wie B ,hat dann B soviele Elemente wie A?
3.Wenn A soviele Elemente hat wie B , und B soviele wie C , hat dann C soviele wie A?

und gilt das alles immer.

naja , der trick ist jetzt noch das so auszuschreiben das es nach mathematik aussieht…

Cherrylein · 7. August 2009 um 15:04

noch ein paar Verständnisfragen^^
Wow, vielen Dank, so ausführliche Erklärungen habe ich nicht erwartet. Ich verzweifel gerade an mir selbst, da ich dafür einfach kein Verständnis aufbringen kann, aber ich versuche zu kämpfen und der Sache näher zu kommen^^

Also, noch mal eine kleine Verständnisfrage,
gibt es überhaupt Relationen die nich reflexiv sind? Weil ich betrachte ja dabei ja zwei gleichwertige Objekte, und wie können die nicht gleich sein?
Oder kommt sowas dann vor, wenn ich zwei utnerschiedliche Mengen betracht, und das Objekt nur in einer Menge vorhanden ist. Also wenn ich nicht MxM betrachte, wo a in M enthalten ist, sondern bspw. MxB, wo a dann nur in M enthalten ist und nicht in B.

So, und dann nocheinmal zum sicher gehen, ich betrachte also bei meiner Aufgabenstelle, die Relation von |A|=|B| ?!
Und in Bezug zur symmetrie, kann man es dann auf einfachster „mathematischer“ Ebene sagen,dass man |A| =|B| vertauschen darf, wegen dem Gleichheitszeichen.

Und die Transitivität mal rein sprachlich ausgedrückt, bedeutet in dem Fall so viel, wie A hat so viele Elemente wie B. B hat so viele Elemente wie C, daher hat A auch so viele Elemente wie C. ?!

Ganz liebe Grüße =)

Blahahaking · 7. August 2009 um 15:14

gibt es überhaupt Relationen die nich reflexiv sind? Weil ich
betrachte ja dabei ja zwei gleichwertige Objekte, und wie
können die nicht gleich sein?

ja, z.B: Paul ist der Bruder von Sophie ,(wäre eine relation)
aber Paul ist nicht der Bruder von Paul (also nicht reflexiv)

So, und dann nocheinmal zum sicher gehen, ich betrachte also
bei meiner Aufgabenstelle, die Relation von |A|=|B| ?!
Und in Bezug zur symmetrie, kann man es dann auf einfachster
„mathematischer“ Ebene sagen,dass man = vertauschen
darf, wegen dem Gleichheitszeichen.

genau, noch einfacher |A| und |B| sind natürliche zahlen,da beisst die maus kein faden ab.

Und die Transitivität mal rein sprachlich ausgedrückt,
bedeutet in dem Fall so viel, wie A hat so viele Elemente wie
B. B hat so viele Elemente wie C, daher hat A auch so viele
Elemente wie C. ?!

genau.

Ganz liebe Grüße =)

Gruß zurück

michael_f7f5bc · 7. August 2009 um 17:04

hi,

Also, noch mal eine kleine Verständnisfrage,
gibt es überhaupt Relationen die nich reflexiv sind? Weil ich
betrachte ja dabei ja zwei gleichwertige Objekte, und wie
können die nicht gleich sein?

in der menge M = {1,2,3,4} ist
R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
eine relation, denn R ist eine teilmenge von M x M (mehr ist ja für eine relation zunächst nicht verlangt)

diese relation könnte man z.b. auch durch das zeichen

Anonym_e52f27a38f6b · 7. August 2009 um 22:32

Wow, vielen Dank, so ausführliche Erklärungen habe ich nicht
erwartet.

Tja, wie schon Westernhagen sang: „Frauen gegenüber bin ich willenlos.“

Also, noch mal eine kleine Verständnisfrage,
gibt es überhaupt Relationen die nich reflexiv sind? Weil ich
betrachte ja dabei ja zwei gleichwertige Objekte, und wie
können die nicht gleich sein?

Mooooment – gleichwertige Objekte betrachtest Du doch nur in _Äquivalenz_relationen. Zwischen den Elementen einer Menge kann ich mir aber auch zahlreiche Beziehungen (Relationen) ausdenken, in denen die Partner nicht gleichwertig sind. Die prominentesten Beispiele hast Du ja schon bekommen: „a teilt b“ und "a Äquivalenzrelation, wenn Du also wirklich gleichwertige Objekte betrachtest, gilt natürlich die Reflexivität. Vom mathematischen Standpunkt aus betrachtet ohnehin, denn diese ist ja gerade eine definierende Eigenschaft für Äquivalenzrelationen. Und vom sprachlichen Standpunkt hast Du es ja offenbar selbst verinnerlicht, wenn Du sagst: „Wie können zwei gleichwertige Objekte nicht gleich sein?“
(Wobei das ja ginge. Wenn ich sage, alle Mengen mit genau zwei Elementen sind gleichwertig, dann sind sie ja noch lange nicht gleich. Aber ich bin mir sicher, dass dieses Problem nur auf sprachlicher Ebene bestand.)

Liebe Grüße
Immo

Martin · 7. August 2009 um 22:50

Hallo,

Sei M = P ({1,2,3,4}). Gegeben ist die folgende Relation:
R = {(A,B) € M x M | |A|=|B|}
Zeigen Sie: R ist eine Äquivalenzrelation.

diese Aufgabe ist ein didaktischer Lapsus. Kein Wunder, dass Du davon verwirrt bist.

Erklärung: Das Wesentliche daran ist die Gleichung |A| = |B|, die die Relation R spezifiziert. Nun steht auf den beiden Seiten dieser Gleichung aber dieselbe Funktion, hier |…|. Außerdem ist „=“ eine Äquivalenzrelation (nämlich die einfachste, die es gibt). Aus beidem zusammen folgt evidenterweise sofort, dass auch R eine Äquivalenzrelation ist. Allgemeiner ist {(A, B) ∈ M × M | f(A) = f(B)} eine Äquivalenzrelation für jede beliebige Funktion f. Das ist unmittelbar klar.

Bei dieser Aufgabe gibt es also nichts zu rechnen. Sollte das ihrem Erfinder nicht bewusst gewesen sein, ist er ein Opfer unfreiwilliger Komik geworden.

Ein Beispiel für eine Aufgabe, bei der die Sache anders liegt, wäre etwa:

R = {(A, B) ∈ M × M | |A| + |B| = eine gerade Zahl}

Auch dieses R ist eine Äquivalenzrelation, aber das ist nicht ganz so offensichtlich.

Muss ich jetzt doch irgendwie zeigen das a ein Element des
Kreuzprodukts ist und A den gleichen Betrag wie A hat, oder?!

Nix Kreuzprodukt, nix Betrag. Mit dem × ist hier das kartesische Produkt von Mengen gemeint und |…| bezeichnet die Mächtigkeit (= Elementanzahl) einer Menge.

Gruß
Martin