Anzahl der Äquivalenzklassen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | [Dateianhang nicht öffentlich] |
Wir haben in der Übung dazu ein Beispiel gerechnet mit A= (a,b). Somit hatte das kartesische Produkt 4 Elemente und es gab 16 Relationen. Dann haben wir nur die reflexiven Rel. betrachtet und von denen die Äklassen bestimmt. Da die Relationen jeweils nur wenige Elemente hatten konnte man sich schnell Pfeildiagramme zeichnen und so die ÄK mehr oder weniger ablesen.
Jetzt ist bei dieser Aufgabe das kartesische Produkt 16 Elemente (4*4):
aa ab ac ad
ba bb bc bd
ca cb cc cd
da db dc dd
Insgesamt gibt es [mm] 2^9=512 [/mm] Relationen. Das sind mir zu viele um alle hinzuschreiben und einzeln zu untersuchen. Wie gehe ich denn nun vor um die Relationen zu finden die die gewünschte Anzahl an ÄK haben?
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:38 Do 30.04.2009 | | Autor: | felixf |
Hallo!
> [Dateianhang nicht öffentlich]
> Wir haben in der Übung dazu ein Beispiel gerechnet mit A=
> (a,b). Somit hatte das kartesische Produkt 4 Elemente und
> es gab 16 Relationen. Dann haben wir nur die reflexiven
> Rel. betrachtet und von denen die Äklassen bestimmt. Da die
> Relationen jeweils nur wenige Elemente hatten konnte man
> sich schnell Pfeildiagramme zeichnen und so die ÄK mehr
> oder weniger ablesen.
>
> Jetzt ist bei dieser Aufgabe das kartesische Produkt 16
> Elemente (4*4):
> aa ab ac ad
> ba bb bc bd
> ca cb cc cd
> da db dc dd
>
> Insgesamt gibt es [mm]2^9=512[/mm] Relationen. Das sind mir zu viele
> um alle hinzuschreiben und einzeln zu untersuchen. Wie gehe
> ich denn nun vor um die Relationen zu finden die die
> gewünschte Anzahl an ÄK haben?
Es gibt zwei Arten eine Aequivalenzrelation anzugeben:
a) als Teilmenge von $M [mm] \times [/mm] M$ (das hast du oben beschrieben);
b) indem du die einzelnden Aequivalenzklassen hinschreibst.
Bei zweiterem entspricht einer Aequivalenzrelation genau einer Partition der Menge $M$ (wobei alle Teile der Partition nicht-leer sind, und die Anzahl der Teile gleich der Anzahl der Aequivalenzklassen ist).
Und Partitionen einer vierelementigen Menge zaehlen mit genau drei Teilen geht gleich viel schneller :)
LG Felix
|
|
|
| |
|
Ich hoffe ich habe das mit den Partitionen richtig verstanden. Dann sind das alle ÄRelationen mit 3 Äklassen folgende:
(a,b,c) (d), (a,b,d) (c), (a,c,d) (b), (b,c,d) (a)
Stimmt das?
|
|
|
| |
|
> Ich hoffe ich habe das mit den Partitionen richtig
> verstanden. Dann sind das alle ÄRelationen mit [mm] \red{3} [/mm] Äklassen
> folgende:
> (a,b,c) (d), (a,b,d) (c), (a,c,d) (b), (b,c,d) (a)
>
> Stimmt das?
Hallo,
ich sehe hier eher die möglichen Äquivalenzklassen aufgelistet für Äquivalenzrelationen mit [mm] \red{2} [/mm] Äquivalenzklassen.
Deine 4 Partitionen bestehen ja aus 2 Teilmengen.
Gruß v. Angela
|
|
|
| |
|
Klar, stimmt. Weiß auch nicht, wie ich da drauf komme.
Also die mit 3 ÄK:
(a,b) (c) (d), (a,c) (b) (d), (a,d) (b) (c)
(b,c) (a) (d), (b,d) (a) (c)
(c,d) (a) (b)
Bei denen mit 2 habe ich noch welche gefunden:
(a,b) (c,d), (a,c) (b,d), (a,d) (b,c) + (a,b,c) (d), (a,b,d) (c), (a,c,d) (b), (b,c,d) (a)
|
|
|
| |
|
> Klar, stimmt. Weiß auch nicht, wie ich da drauf komme.
>
> Also die mit 3 ÄK:
> (a,b) (c) (d), (a,c) (b) (d), (a,d) (b) (c)
> (b,c) (a) (d), (b,d) (a) (c)
> (c,d) (a) (b)
>
> Bei denen mit 2 habe ich noch welche gefunden:
> (a,b) (c,d), (a,c) (b,d), (a,d) (b,c) + (a,b,c) (d),
> (a,b,d) (c), (a,c,d) (b), (b,c,d) (a)
Hallo,
ja, nun müßte es wirklich vollständig sein.
Gruß v. Angela
|
|
|
| |
|
Super, vielen Dank für die Hilfe. Das mit den Partitionen (das wurde in der Vorlesung nicht behandelt) müsste doch auch der Lösungsweg sein, der verlangt ist, oder? Ich kann ja nicht die 512 Relationen alle hinschreiben und dann unterteilen...
|
|
|
| |
|
> Super, vielen Dank für die Hilfe. Das mit den Partitionen
> (das wurde in der Vorlesung nicht behandelt) müsste doch
> auch der Lösungsweg sein, der verlangt ist, oder? Ich kann
> ja nicht die 512 Relationen alle hinschreiben und dann
> unterteilen...
Hallo
nee, daß Du die alle aufschreibst, kann wirklich nicht gemeint sein!
Vielleicht habt Ihr die Partition "verdeckt" durchgenommen
Äquivalenzklassen habt Ihr ja besprochen.
Da kam doch bestimmt auch vor, daß zwei Äquivalenzklassen entweder elementfremd sind oder gleich.
Dann ist es noch wichtig, daß wirklich jedes Element in einer Äquivalenzklasse liegt, jedes Element also zu einem Element äquivalent ist. (Das wird einem durch die Reflexivität garantiert.)
Diese Überlegungen sind's dann ja schon.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:13 Do 30.04.2009 | | Autor: | Lockenheld |
Mm, das könnte sein. Ich stöber mal nochmal die Mitschrift durch, um mein Lösungsweg zu begründen. Ich hatte mir auf jeden Fall mal eine Notiz mit den disjunkten Teilmengen gemacht. Da schau ich noch nach. Nochmals vielen vielen Danl für die Antworten.
|
|
|
|
