Äquivalenzrelation - Theoretische Informatik?
Hallo Leute,
ich habe eine Frage zur Äquivalenzrelation. An sich habe ich die Relationen untereinander zu verstanden (reflexiv, symmetrisch und transitiv). Hier ist mal ein Beispiel. Die Äquivalenzrelation gilt für dieses Beispiel laut dem Prof.
Gegeben ist die Menge M = {1, 2, 3, 9, 10, 12, 18, 21, 30, 45}. Jetzt soll man nachweise das die Relation R = {(x, y) ∈ M × M | x hat die gleiche Quersumme wie y} eine Äquivalenzrelation darstellt.
Das ganze wurde in einer Tabelle dargestellt (Tabelle im Anhang). Die Reflexivität und die Symmetrie zu beweisen ist kein Problem, aber wie stellt man hier die Transitivität da? Man hat ja nur x und y. Um die Transitivität darzustellen braucht man ja eigentlich auch jetzt z. Die Transitivität wird ja erfüllt wenn: Für x,y,z sind Elemente aus M. Wenn x R y und y R z dann folgt daraus das x R z ist. Aber woher bekomme ich das z jetzt?
Der Prof schreibt z.B. folgendes: Transitiv: Ja, denn wenn x1 und y sowie x2 und y die gleiche Quersumme haben, dann hat auch x1 und x2 die gleiche Quersumme. --> Wie ist das jetzt zu erklären?
6 Antworten
Ich hatte max Zeichen; dies der Schluss meiner Anekdote von Teil 1
Absätze mach ich jetzt nicht mehr rein, weil er mir ständig den gesamten Textpuffer auf Blank setzt. Und meine ( aus Word importierte ) Savedatei kann er nicht richtig formatieren.
Überhaupt erkennst du den guten Hochschullehrer daran, dass er Pausen los seine Hörer motiviert. Und gerade hier passiert Kerner ein Lapsus. Matematik ist kaserniertes Denken; wie beim Kommiss wird alles bewiesen, weil man es beweisen KANN - nicht weil jemand den Beweis braucht. Kommilitone " Dagobert " steckt denn auch voll in der Sinnkrise; noch Fragen? " 0 a = 0 - können Sie mir mal ein Beispiel sagen, wo das NICHT gilt? " Kerner reagiert denn auch wie Herr Hauptmann beim Truppendienstunterricht " ich habe eben erklärt, dass es immer gilt. Der ganze Saal hat meine Erklärung verstanden so wie den Beweis nach vollzogen. Wie KÖNNEN Sie da kommen und ein Gegenbeispiel von mir verlangen !? " Und Viele kicherten über den " Depp der Kompanie " . . . Nur weg getreten hat er nicht gebrüllt .
Bei dieser Relation ist die Transitivität trivial, denn die Relation ist über eine Zahl definiert, nämlich die Quersumme, also über die Gleichheit einer Zahl. Und die Gleichheit ist natürlich transitiv. Seien a und b und c drei Quersummen, dann ist es logisch, dass aus a = b und b = c auch a = c folgt.
Ich will kurz auf deinen Satz zu sprechen kommen: "Und die Gleichheit ist natürlich transitiv." Könntest du das etwas genauer definieren?
Und "Seien a und b und c drei Quersummen,...". Woher hast du jetzt das c? Ich habe ja nur die Elemente a und b.
bei Transitivität geht es um jedes mögliche Quersumme a,b,c aus der gegebenen Menge. wenn es halt nur zwei zahlen gibt die diegleiche Quersumme haben, dann ist die Transitivität ja automatisch erfüllt.
die Gleichheit ist doch eine Äquivalenzrelation. a=a gilt immer , aus a=b folgt b=a egal was a und b sind und aus a=b und b=c folgt auch a=c. Relationen , die über gleichheiten definiert sind , sind automatisch Äquivalenzrelationen
Erst soll ich mich einloggen; dann ist meine gesamte Antwort weg:
Zunächst mal. Auch ich kann Deutsch, nicht nur ihr mit eurem ewigen " Hochpunkt " statt Maximum
( Beachte das schöne " deutsche " Wort " Punkt " ; es gibt einen Komponisten Johann Wenzislaus Stich; der italienisierte sich zu " Giovanni Punto " )
Statt Äquivalenzrelation schlage ich vor Gleichheitsbeziehung ( GB )
Sämtliche Antworten sind ungenügend; also eine TABELLE sämtlicher Zahlen zu erstellen - ich muss schon sagen . . .
Die beiden größten Fehler, die du in der Matematik begehen kannst: Du denkst entweder zu konkret oder zu abstrakt. Und du denkst eindeuitig zu konkret; wir stehen quasi unter Erfolgszwang. Wir kommen auf keinen grünen Zweig, wenn wir nicht mehr beweisen, als ursprünglich gefordert war. Jetzt löse dich mal völlig von den natürlichen Zahlen; statt dessen gehen wir aus von der BELIEBIGEN Menge M . Das ist die Abstraktion, die ich meine. Und jetzt führe ich eine Abbildung ein
f : M ===> |R ( 1 )
f möge heißen Kennzahl-Abbildung; vermöge f wird jedem Element von M eine Kennzahl zugeordnet. Bitte mach dir klar, dass die Quersumme nichts weiter ist als der Sonderfall einer Kennzahl.
Und jetzt führe ich eine GB ein, und zwar die Relation R
R : M X M ( 2a )
a R b <===> f ( a ) = f ( b ) ( 2b )
Und jetzt überlege dir zwei Dinge:
1) R ist tatsächlich eine GB
2) R verallgemeinert deine Quersumme.
Aus gegebenem Anlass weise ich auch dich wieder darauf hin. die natürlichen Zahlen kannst du nur deshalb tabellieren, weil sie ===> abzählbar sind. Darf ich die beiden ===> Cantorschen Diagonalbeweise voraus setzen?
Aus einer ( unendlichen ) Menge M kannst du dir immer die ===> Potenzmenge 2 ^ M schnitzen; und stets gilt
card ( 2 ^ M ) > card ( M ) ( 3 )
Du willst also beweisen, dass R in ( 2b ) eine GB ist - und dies im Allgemeinen auf einer über-über-überabzählbaren Menge - mit Tabellen wärst du da grundsätzlich schlecht beraten.
Ich hatte ja unverschämtes Glück mit meinem AGULA Prof Kerner. Allein was ich da gesehen hab, wie andere Profs rum geschlampt haben. Wir Physiker waren ja schon verständige " alte Herren " im 3. Semester. Aber gerade die Mattetiker, die sonst immer so verächtlich auf uns herab sahen, erwiesen sich als die absoluten Kindsköpfe im ersten Semester.
Satz für Satz spricht Kerner immer leiser, bis endlich jemand brüllt
" Herr Professor; bitte etwas lauter. Wir verstehen Sie nicht. "
" Sie sollen sich ja auch nicht unterhalten und stören, sondern mir lauschen. Wenn Sie nicht aufhören zu schwätzen, werde ich immer leiser und noch leiser . . . "
Dann - unvermeidlich - der erste Papierflieger. Tosende Heiterkeit, weil das ( Gefährt? Geflügt? Geflügel? ) direkt vor Kerners Schuhspitze gelandet ist. Kerner
" Aaah bitt scheen; weerfens noo aan rüber; Sie wüüßn doo; ii hab zwoo Kinder . . . "
Die folgende Hausaufgabe von Kerner wird mir ewig unvergesslich bleiben - keiner in unserer Übungsgruppe hatte sie richtig.
" Satz 47 11 ( Lemma von Katzenbach )
Jede Relation, die symmetrisch und transitiv ist, ist auch reflexiv. "
Jetzt erwartest du, dass du das beweisen sollst - weit gefehlt. Der fertige Beweis steht schon auf dem Aufgabenzettel gedruckt:
Symmetrie: a R b ===> b R a ( 4a )
Transitivität allgemein: a R b ^ b R c ===> a R c ( 4b )
Regel ( 4b ) angewandt auf ( 4a )
a R b ^ b R a ===> a R a ===> reflexiv ( 4c ) wzbw
Jetzt stand aber da
" Man zeige
1) Dieser Satz ist falsch.
2) Sein Beweis ist fehlerhaft. "
Naa? Lass mal was von dir hören . . .
Nochne kleine Anekdote von Kerner gefällig? bei dem Konkurrenzportal ===> Lycos fragen Schüler als, warum bloß gibt " Minus Mal Minus = Plus " ? Eine unmittelbare Folge des Distributivgesetzes ( DG ) das freilich axiomatisch voraus gesetzt werden muss. Dies ist allerdings plausibel; denn was eigentlich dahinter steckt: Jedem Element a deines ==> Ringes ( R ; + * ) wird ein " Operator der Multiplikation " zugeordnet, bei dem es sich in Wirklichkeit um einen ===> Endomorphismus der Gruppe ( R ; + ) handelt.
Aber vorher beweist Kerner noch etwas anderes: 0 a = 0 für alle a . Er selbst geht wieder über das DG ; aber gerade hier bewährt sich der abstrakte Standpunkt. Wenn ß ein Endo ist und e das neutrale Element, dann ß ( e ) = e
Sorry, aber man braucht hier überhaupt keine tabellarisch Darstellung. Dieses Ergebnis führt auf ein sehr einfaches Lemma zurück.
Definition 0. Seien (X,E), (Y,F) Relationen Dann heißt eine Abbildung ƒ : X—>Y eine Reduktion, genau dann wenn folgende Bedigung gilt:
∀x,x´∈X: x E x´ <==> ƒ(x) F ƒ(x´). ⊣
Es reicht aus, folgendes Lemma zur Kenntnis zu nehmen:
Lemma 1. Seien (X, E) und (Y,F) Relationen mit einer Reduktion ƒ : X —> Y. Dann gilt (Y,F) Äquivalenzrelation ==> (X,E) Äquivalenzrelation. ⊣
Folgerung 2. (M, R) |—> ({0; 1; …; 9},=) gegeben durch x |—> Quersumme(x) bildet eine Reduktion per Definition der Relation R. Da = per Definition eine Äquivalenzrelation ist, folgt aus Lemma 1, dass R eine Äquivalenzrelation ist. ⊣
BEWEIS (Lemma 1). Angenommen, (Y,F) sei eine Äquivalenzrelation. Seien x,x´,x´´ ∈ X. Man betrachte zunächst ƒ(x),ƒ(x´),ƒ(x´´) ∈ Y. Da (Y,F) eine Äquivalenzrelation ist, gilt
* ƒ(x) F ƒ(x)
* ƒ(x) F ƒ(x´) ==> ƒ(x´) F ƒ(x)
* ƒ(x) F ƒ(x´) F ƒ(x´´) ==> ƒ(x) F ƒ(x´´)
Vermittels der Reduktion erhält man:
* x E x
* x E x´ ==> x´ E x
* x E x´ E x´´ ==> x E x´´
Da dies für alle x,x´,x´´ ∈ X gilt, ist (X,E) eine Äquivalenzrelation. ⊣
q(x)=Quersumme von x
Seien x,y,z∈M und es gelte xRy und yRz, also q(x)=q(y) und q(y)=q(z), also q(x)=q(z), also yRz.
Ist das so irgendwie klarer?
Leider nicht.. Die Formel verstehe ich ja aber du hast in deinem Beispiel: x, y, z sind Elemente aus M. Sobald die einzelnen Elemente(x,y,z) bekannt sind, ist das auch kein Problem. In meinem Fall ist aber nur gegeben R = {(x, y) ∈ M × M | x hat die gleiche Quersumme wie y}. Wo ist jetzt z ist meine Frage. Könnte z aus der Quersumme entstehen?