Äquivalenzklassen und Transitivität |
25.10.2011, 16:36 | math22 | Auf diesen Beitrag antworten » | ||||||||
Äquivalenzklassen und Transitivität Hallo zusammen, ich habe ein kleines Problem mit dem Thema Äquivalenzklassen. Und zwar möchte ich zeigen, dass die Relation R := eine Äquivalenzrelation ist. Außerdem will ich die Äquivalenzklassen angeben. Meine Ideen: Dazu muss ich ja beweisen, dass die Relation reflexiv, transitiv und symmetrisch ist. reflexiv: 1. Aus a=b folgt a=a. Somit ist für die Bedingung a=b die Relation transitiv. 2. Wenn a*b ungerade. Dann ist a*b = 2k - 1. Wie komme ich hier weiter? symmetrisch: 1. Aus a=b folgt b=a. Also symmetrisch 2. Wenn a*b ungerade: a*b = 2k-1 aRb: a*b = 2k -1 bRa: b*a = 2l -1 =>a*b = b*a transitiv: Hier fehlt mir der Ansatz.. Ich komme mit der Transitivität einfach nicht klar! Äquivalenzklassen: Hier bin ich auch recht ratlos. Ein Versuch von mir: [a] = {b | a=b} und [b] = {c | bc = 2k-1} Ich würde mich sehr über Tipps freuen! |
||||||||||
25.10.2011, 17:42 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Transitivität : Es seien also , zu zeigen ist Jetzt gibts die Fälle : a = b und b*c ungerade a*b ungerade und b = c a = b und b = c a*b ungerade und b*c ungerade Diese einfach durcharbeiten.
Nimm Dir einfach mal eine Zahl her, etwa die 3, was wäre dann alles Äquivalent zur 3 bezüglich R ? |
||||||||||
25.10.2011, 18:07 | math22 | Auf diesen Beitrag antworten » | ||||||||
Danke für die Hinweise. Also die ersten drei Fälle hab ich so bewiesen: 1. a=b und bc=2k-1 aRc: a=b => ac=2k-1 2. ab=2k-1 und b=c aRc: ac=2k-a 3. a=b und b=c aRc: a=c=b=a 4. ab=2k-1 und bc=2m-1 aRc: ??? Hier weiß ich nicht was machen. Zu den Äquivalenzklassen: Also zur wäre 1 oder 3 äquivalent (alle ungeraden und die selben Zahlen). Aber wie schreib ich sowas auf? |
||||||||||
25.10.2011, 18:19 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Naja, Du müsstest eine Zahl n finden , so dass ist. Benutze dafür dass Du weißt wie ab und bc aussehen .
Ich vermute mal Du hast es begriffen. Daher : Zur 3 sind alle ungeraden Zahlen äquivalent. Insbesondere heißt das, dass alle ungeraden Zahlen in einer (!) Äquivalenzklasse liegen. Was ist jetzt zum Beispiel mit der 2, welche Zahlen wären zur 2 äquivalent bezüglich R? |
||||||||||
25.10.2011, 18:26 | math22 | Auf diesen Beitrag antworten » | ||||||||
Kann ich das ganze so zeigen: ac = 2n-1 (2k-1)(2l-1) = 2n-1 ? --- Also zu 2 wäre ja nur die 2 äquivalent, da es kein m von N gibt, mit dem 2m = 2k + 1 erfüllt ist. Aber wie schreibe ich das nun formal richtig hin? |
||||||||||
25.10.2011, 18:35 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Wieso sollte das gelten ? Hinweis : wann ist das Produkt von zwei natürlichen Zahlen ungerade ?
Was bedeutet dass für die geraden Zahlen ? |
||||||||||
Anzeige | ||||||||||
|
||||||||||
25.10.2011, 19:20 | math22 | Auf diesen Beitrag antworten » | ||||||||
Das Produkt von zwei natürlichen Zahlen ist gerade, wenn beide Faktoren ungerade sind, oder? Was das für die geraden Zahlen bedeutet, weiß ich nicht. Irgendwie steh ich da auf dem Schlauch. Ich schlage mich mit dem Thema schon seit Tagen rum und checks irgendwie nicht. |
||||||||||
25.10.2011, 19:27 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Das wäre falsch.
Naja, die 2 ist nur zu sich selbst äuivalent. Was ist mit der 4, was mit der 6 ? |
||||||||||
25.10.2011, 19:41 | math22 | Auf diesen Beitrag antworten » | ||||||||
4 ist nur zu sich selbst äquivalent, genauso die 6. Da ja a=b oder a*b = 2k-1 sein muss. (Die Reflexivität hab ich auch noch nicht vollständig, denke ich). -- Ups sorry, da hab ich mich verschrieben, natürlich ist das Produkt zweier ungerader natürlicher Zahlen stets ungerade. |
||||||||||
25.10.2011, 20:16 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Das ist klar. Wir brauchen aber, dass wenn a*b ungerade ist, dass dann auch a und b ungerade sein müssen. Dann ist der Fall a*b, b*c ungerade nämlich trivial.
Was heißt das also für die Äquivalenzklassen bezüglich der geraden Zahlen? |
||||||||||
25.10.2011, 22:58 | math22 | Auf diesen Beitrag antworten » | ||||||||
irgendwie fehlt mir da der Ansatz... Wie gehe ich den Beweis an? -- Für die ÄK heißt das, dass alle geraden Zahlen eine ÄK sind oder? Also haben wir eine ÄK mit ungeraden und eine mit geraden Zahlen? PS: Ich finde es absolut großzügig, dass du Menschen hier so mit Nachdruck hilfst! |
||||||||||
25.10.2011, 23:01 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Alle Elemente einer Äquivalenzklasse sind äquivalent. Wenn Du jetzt sagst , dass die geraden Zahlen in einer ÄQ wären, dann wären zum Beispiel 2 und 4 äquivalent, wir haben aber doch gerade gesehen, dass 2 und 4 nicht äquivalent sind. Also ?
Das ist doch wirklich nicht mehr schwer. Wir wissen, dass a*b und b * c ungerade sind. Daher müssen a,b,c ungerade sein. Was gilt dann für a*c ? |
||||||||||
26.10.2011, 00:30 | math22 | Auf diesen Beitrag antworten » | ||||||||
Also haben wir n-ÄK. Für jedes Element von N für das gilt: n = 2k bildet eine ÄK mit einem Element, sich selbst. Und für jedes Element von N für das gilt: u = 2k +1 bildet eine ÄK mit allen Elementen für die auch gilt v = 2k +1. Stimmt das? Ich habe eben keine Ahnung wie man sowas formuliert und auch richtig hinschreibt. Leider finde ich keine Beispiele o.ä., diese ÄK treiben mich noch in den Wahnsinn.. -- Aus a*b = 2m-1 und b*c = 2k-1 folgt, a*c = 2l-1, da für a,b,c gilt: a,b,c = 2k-1. Wie formuliert man sowas richtig? Ich will es ja streng mathematisch schreiben können.. |
||||||||||
26.10.2011, 09:12 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Das wäre falsch, weil n ist eine Zahl. Wir haben aer unendlich viele Äquivalenzklassen, also mehr als n.
Ganz genau!
Merkwürdig formuliert, ich hätte gesagt, dass die ungeraden Zahlen in einer Äquivalenzklasse liegen. Aufgeschrieben : Das wäre das Ganze in Mengenschreibweise. Äquivalenzklassen werden aber in der Regel mit eckigen Klammern notiert, innerhalb der Klammern wird dann ein Repräsentant notiert. Etwa wäre die Äquivalenzklasse der ungeraden Zahlen dann einfach [1] oder [3] oder [5] Ganz egal, denn [1] = [3] = [5] , usw. , denn 1 , 3 , 5 ... sind alles Repräsentanten der selben Äquivalenzklasse. Dann haben wir
Es ist streng mathematisch wenn Du sagst, dass aus ab ungerade und bc ungerade folgt dass a,b,c jeweils ungerade sind. Dann muss aber auch ac ungerade sein. Damit ist R transitiv. Daran ist nichts auszusetzen. |
||||||||||
26.10.2011, 20:44 | math22 | Auf diesen Beitrag antworten » | ||||||||
Also transitiv habe ich bewiesen. Aber das mit den ÄK ist mir noch nicht ganz klar.. Für die ungeraden Zahlen kann ich also einfach, wenn die Angabe der ÄK bezüglich R gefordert sind [1] angeben? Reicht das schon aus? oder muss ich [1] = {n | n = 2k-1} schreiben? Genauso mit den ÄK von denen es unendlich viele gibt (das sind ja dann noch die ungeraden Zahlen die mit sich selbst in Relation stehen). Kann ich da [2i] i el. von N sagen? |
||||||||||
26.10.2011, 21:04 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Naja, sofern ihr diese Notation verwendet würde tatsächlich [1] reichen , für die Äquivalenzklasse der ungeraden Zahlen.
Ich habs ja auch so aufgeschrieben. Die Frage ist nur, ob Du die Quotientenmenge angeben willst, oder nur die ÄQ aufzählen . |
||||||||||
26.10.2011, 21:18 | math22 | Auf diesen Beitrag antworten » | ||||||||
Mal noch eine Verständnisfrage: Rein von den ÄK (z.B. [1]) kann ich ja nicht auf die Relation schließen bzw. ohne Kenntnis der Relation kann ich von der ÄK nicht auf die Elemente einer ÄK schließen, richtig? Bei den ungeraden reicht also [2i] i el. von N. wenn ich dazu noch schreiben wollte [2i] = {a el. N | a = 2i}, geht das so? Bzw. macht das Sinn? --- Andere Aufgabe, nur kurze Frage: R:= k el. Z : x + xy = 2k Also muss x + xy eine gerade Zahl sein. Hier muss doch eine Fallunterscheidung stattfinden, wann x + xy ungerade wird oder? (x und y ungerade, x und y gerade, x gerade und y ungerade). Wenn ich nun Symmetrie beweisen will, dann muss ich doch diese 3 Fälle durchrechnen und schauen ob xRy => yRx (zB. in dem ich x und y je nach Fall auf 2k - 1 oder 2k setze und durch Umformungen schaue ob ein gerades bzw. ungerades Ergebnis rauskommt?) |
||||||||||
26.10.2011, 21:27 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Das ist ziemlich überflüssig, denn für i aus N ist [2i] schon eindeutig.
Äquivalenzklassen sind auch nur Mengen! Wir notieren sie zwar mit [1], aber am Ende sind es auch nur Mengen. Wenn Du alle Äquivalenzklassen kennst, dann kennst Du die Relation.
Wenn x + xy ungerade wird, ist das für die Releation nicht relevant, da nur die geraden Varianten wichtig sind. Für die Symmetrie ist dann zu zeigen : x + xy gerade => y + xy gerade Mir fällt übrigens sofort ein Gegenbeispiel ein, denke mal sehr einfach |
||||||||||
26.10.2011, 21:49 | math22 | Auf diesen Beitrag antworten » | ||||||||
Jedoch kann ich ja von den ÄK [1] und [2i] i el. N nicht auf die Relation schließen. (Angenommen ich wäre ein Dritter, der nur diese zwei Begriffe an den Kopf geworfen bekommt, sonst nichts. Kann er nun die ÄR "rekonstruieren"?) Denn [1] könnte ja auch ein Repräsentant von R={(1,1), (2,1), (1,2)} sein oder nicht? Zu den ÄK allgemein: ein Repräsentant [x] von R kann jedes beliebige Element einer Relation sein oder muss es bei z.B. xRy das x oder das y sein? -- Ein Gegenbeispiel zu dieser Relation weiß ich auch, z.B. 2R1 aber nicht 1R2. Doch wie beweise ich das allgemein? Ein Gegenbeispiel reicht zwar, aber mich würde der allgemeine Weg trotzdem interessieren. |
||||||||||
26.10.2011, 23:11 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Wenn Du nur [1] schreibst kannst Du nichts von der Relation erkennen. Ich bin davon ausgegangen, dass Du die Menge [1] vollständig kennen würdest.
Was heißt hier allgemein. Eine Relation heißt symmetrisch, wenn für alle Paare (a,b) aus R auch (b,a) in R ist. Wenn Du also auch nur ein Paar findest, für das die Bedingung nicht gilt, bist Du fertig. Wenn Du Widerlegen wolltest, dass alle Vögel fliegen können, würdest Du doch auch nicht jeden Flugunfähigen Vogel aufzählen, sondern spontan "Pinguin" sagen, und wärst fertig. Um eine Aussage zu Widerlegenen reicht es grundsätzlich, wenn man ein Beispiel findet, welches die Voraussetzungen erfüllt aber die Schlussfolgerung verletzt. |
||||||||||
26.10.2011, 23:27 | math22 | Auf diesen Beitrag antworten » | ||||||||
Ok, somit muss die Menge von [x] bekannt oder benannt sein. Zum Beweis: Mir ist bewusst, dass ein Gegenbeispiel reicht. Jedoch funktioniert dies ja nicht immer, oft sucht man sich ja dumm und dämlich bis man eines findet. Also würde ich das ganze gerne (zu Übungszwecken für mich) mit dem direkten Beweis oder dem Beweis durch Widerspruch probieren. -- Zu den ÄK allgemein: ein Repräsentant [x] von R kann jedes beliebige Element einer Relation sein oder muss es bei z.B. xRy das x oder das y sein? Das ist mir noch nicht ganz klar. |
||||||||||
27.10.2011, 09:36 | Mazze | Auf diesen Beitrag antworten » | ||||||||
Jedes Element der Äquivalenzklasse [x] kann ein Repräsentant sein. Für unser Beispiel wäre zum Beispiel jede bel. ungerade Zahl ein Repräsentant für die ÄQ der ungeraden Zahlen, also wie ich oben schrieb: [1] = [3] = [5] ...
Also gerade später findet sich sehr viel leichter ein Gegenbeispiel als eine expliziter Beweis. So oder so, man muss verstehen warum etwas nicht funktioniert, damit man entweder den Beweis führen kann oder das Beispiel findet. Ansonsten formuliere mal ordentlich was Du Widerlegen willst. |
||||||||||
27.10.2011, 18:47 | math22 | Auf diesen Beitrag antworten » | ||||||||
Danke, ich habs soweit glaube ich verstanden! Besten Dank für deine Ausdauer |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|