Kongruenz und Äquivalenzklassen |
| 16.02.2013, 15:19 | Nspace | Auf diesen Beitrag antworten » | ||||
| Kongruenz und Äquivalenzklassen Da wir in Kürze eine Klausur schreiben, haben wir Vorbereitungsmaterialien bekommen, allerdings ohne Lösung. Zwei der Aufgaben sind mir allerdings nicht völlig klar. I: Ist die aussage 3^66 kongruent zu 6^33 (mod 12) wahr oder falsch? II: Es sei |A| = 7. Wieviele verschiedene Äquivalenzrelationen R gibt es auf A, für die gilt: R besitzt genau 6 Äquivalenzklassen. Danke im voraus. Meine Ideen: I: Ich sage einfach 66 ist kongruent zu 6 (mod 12) und 33 ist kongruent zu 9 (mod 12). Da verschiedene Reste -> verschiedene Restklassen und damit ist die Aussage falsch. II: 2^(7 über 6) = 128 |
||||||
| 17.02.2013, 16:54 | weisbrot | Auf diesen Beitrag antworten » | ||||
| RE: Kongruenz und Äquivalenzklassen I: es geht nicht um die kongr. von 33 und 66! II: wie war hier dein gedankengang? ich habe eine andere lsg. lg |
||||||
| 18.02.2013, 20:01 | Nspace | Auf diesen Beitrag antworten » | ||||
Bei I: Gut aber dann habe ich leider keine Idee... Muss ich etwa für beide den Satz von Fermat zeigen um zu zeigen, dass sie einen anderen Rest haben? Ich denke das sollte einfacher gehen. Zu II: Nunja wir suchen Äquivalenzrelationen auf A mit |A| = 7. Also dachte ich mir, das wären 7 über 6. Und da es nun auf A ist wären es demnach wohl 2^(7 über 6) Äquivalenzrelationen. Wenn ich zeigen soll, wie viele binäre Relationen über einer Menge A mit |A| = 7 sind sage ich ja auch: 2^(7 x 7) Mag etwas dümmlich erscheinen aber ich habe bei den Aufgaben wirklich absolut keine Idee und das waren meine Gedankengänge, so dämlich sie vllt. auch rüberkommen mögen. |
||||||
| 18.02.2013, 20:36 | weisbrot | Auf diesen Beitrag antworten » | ||||
I: ne, fermat (bzw. euler) bringt nichts, 3 ist doch nicht teilerfremd zu 12. ich hätt einfach gesagt: 3^66 ist ungerade, 6^33 gerade - das ändert sich auch mod 12 nicht - also sind die nicht kongruent. im zweifelsfall kann man sowas auch immer noch ausrechnen: 3^66 = 27^22 = 5^22 = ... mod 12 usw. II: ja, verstehe dein gedankengang jetzt. bei deinem beispiel für allg. bin. rel. würde man mit 7*7 die anzahl der überhaupt möglichen in rel. stehenden paare zählen, und hätte dann 2^(7*7) möglichkeiten, weil die paare entweder in rel. stehen können oder nicht. aber das scheint sich für mich nicht so offensichtlich auf äquivalenzrel. zu übertragen, denn sobald man einige paare als in relation stehend festlegt bekommt man automatisch (wegen der äquivalenzeig.) weitere dazu. stattdessen würde ich da so rangehen: eine aq.rel. auf einer menge A bedeutet immer genau eine disjunkte einteilung (partition) von A in (äquivalenz-) klassen - also man kann anstatt der äq.rel. die menge der äq.klassen untersuchen (d.h. hier: #(äquivalenzrelationen) = #(einteilungen von A in äquivalenzklassen)): die soll 6 äq.klassen beinhalten - das bedeutet widerum, dass 5 der äq.klassen von genau einem element von A vertreten werden, und eine von genau 2. die möglichkeiten hierfür kannst du sicher selbst bestimmen. lg |
||||||
| 18.02.2013, 20:46 | Nspace | Auf diesen Beitrag antworten » | ||||
Diese Erkenntnis kam auch gerade durch herumprobieren: ungerade Basis -> ungerade Zahl während gerade Basis -> gerade Zahl. Danke!
Das versteh' ich leider nicht völlig. Also 5 der Äq. Klassen werden von genau einem Element von A vertreten. Das ergibt jetzt entweder 5 Möglichkeiten wenn alle Elemente verschieden sein sollen oder aber 7 * 5 wenn jedes Element für eine Klassen stehen kann. {a, b, c, d, e, f, g} = 7 Elemente Dann steht jetzt für die erste Äquivalenzklasse entweder nur bspw. a oder aber jeweils eines von a - g. Also für jede Klasse dann 7 Möglichkeiten und das für 5 Klassen. Bin da leider etwas verwirrt. Magst du das nochmal für mich etwas genauer erklären? |
||||||
| 18.02.2013, 21:06 | weisbrot | Auf diesen Beitrag antworten » | ||||
mh, ich hätte nicht "vertreten" sagen sollen. also wenn ein element a aus A nur mit sich selbst in relation steht, so ist die entspr. äq.kl. {a}, wenn es nur mit einem anderen element b in rel. steht, so sieht sie so aus: {a, b}, usw. und es ist klar, dass eine wie hier geforderte äquivalenzrelation A in eine menge von äq.klassen einteilen muss, die die folgende form hat: {{a},{b},{c},{d},{e},{f,g}} - a bis g paarw. verschieden aus A. und jenachdem welche elemente a bis g genau sind, werden dadurch (möglicherweise) verschiedene äq.relationen charakterisiert. und dann soll man merken, dass es nur darauf ankommt, welche elemente die 2-elementige klasse bilden (also welches sind die zwei verschiedenen elemente, die in relation stehen) - damit ist die ganze äq.rel. eind. bestimmt, und für verschiedene paare (bis auf reihenfolge) bekommt man verschiedene äq.relationen. das bedeutet also dass es genausoviele äquivalenzrelationen gibt wie 2-elementige teilmengen von A. lg |
||||||
| Anzeige | ||||||
|
|
||||||
| 18.02.2013, 21:15 | Nspace | Auf diesen Beitrag antworten » | ||||
{a},{b},{c},{d},{e},{f,g}} Also {a} bis {e} kann man jeweils einzeln als Klasse auffassen und {f, g} muss man in eine zusammen packen weil man nur noch eine Äq. Klasse über hat (weil's ja nur 6 sein dürfen). Und da für die letzte eben noch zwei Elemente über sind packt man sie zusammen. Kann man das laienhaft so ausdrücken? Demnach gibt es (7 über 2) Wege 2 dieser Elemente in eine Klasse zu packen und ebenso gilt natürlich (7 über 2) = die Anzahl zwei Elementiger Teilmengen = 21. Ist das so korrekt? |
||||||
| 18.02.2013, 21:33 | weisbrot | Auf diesen Beitrag antworten » | ||||
genau, so kann man sich das vorstellen.
lg |
||||||
| 18.02.2013, 21:39 | Nspace | Auf diesen Beitrag antworten » | ||||
Nun ich hab mich von der 5 anderweitig ablenken lassen und es in die selbe Kategorie wie "Relationen auf A" gesteckt. Es macht auf jedenfall Sinn und ich danke dir mir das eingeprägt zu haben. 
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
