Anzahl Äquivalenzrelationen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:56 Do 16.12.2010 | | Autor: | ella87 |
| Aufgabe | | Bestimmen Sie die Anzahl der Äquivalenzrelationen auf der Menge [mm]\{ 1,2,3,4,5 \}[/mm]. |
Ich weiß nichts über "Anzahlen"....
Ich weiß nur, dass eine Äquivalenzrelation reflexiv, symmetrisch und transitiv ist.
Ich kann mit der Aufgabe leider garnichts anfangen.
Hab das mit der Anzahl auch mal gegoogelt, aber nichts neues herausgefunden.
Kann mir wer helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:37 Do 16.12.2010 | | Autor: | Sax |
Hi,
> Ich weiß nur, dass eine Äquivalenzrelation reflexiv, symmetrisch und transitiv ist.
Du musst auch wissen, dass jede Äquivalenzrelation auf M = {1 ; 2 ; 3 ; 4 ; 5} eine Klasseneinteilung der Menge M induziert und umgekehrt.
Die Klasseneinteilung M = {1 ; 3} [mm] \cup [/mm] {2 ; 4 ; 5} ist z.B. diejenige Äquivalenzrelation, in der 1 und 3 zueinander in Relation stehen und außerdem je zwei der Elemente 2, 4 und 5, sowie natürlich jede Zahl zu sich selbst.
Die Anzahl der Klasseneinteilungen ist viel einfacher abzuzählen.
Wenn du nämlich oben die Mengenklammern {} durch runde Klammern () ersetzt, erhälst du (1 3)(2 4 5), das ist eine P... von M und die Anzahl der P... sollte dir bekannt sein.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:45 Do 16.12.2010 | | Autor: | ella87 |
dann meinst du bestimmt die Potenzmenge, oder? Das hätte ich mir ja schon fast gedacht.
Aber ich habe dann Probleme mit den Mengen { }, sowie den einelementigen Mengen.
Kann denn so eine Menge z.B. Transitiv sein? Man hat ja nur ein Element oder sogar keins.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:46 Do 16.12.2010 | | Autor: | Marcel |
Hallo,
> dann meinst du bestimmt die Potenzmenge, oder? Das hätte
> ich mir ja schon fast gedacht.
leider nein!
> Aber ich habe dann Probleme mit den Mengen { }, sowie den
> einelementigen Mengen.
> Kann denn so eine Menge z.B. Transitiv sein? Man hat ja
> nur ein Element oder sogar keins.
Klar. Schau' mal nach, was in der Definition einer Äquivalenzrelation steht:
Reflexiv: Für alle Elemente der Menge soll gelten...
Wenn da keine Elemente sind, dann ist da nix zu prüfen.
Und bei einelementigen Mengen ist auch klar, dass man alles prüfen kann. Die einzigen "Prüf-Elemente" $a,b,c$ sind dann halt identisch. Beachte aber, dass eine einelementige Menge [mm] $M\,$ [/mm] noch nicht mal reflexiv sein muss. Man muss natürlich die Relation [mm] $R\,$, [/mm] wobei eigentlich $R [mm] \subseteq [/mm] M [mm] \times [/mm] M$ gilt, gegeben haben. (Schlag' auch nochmal bei Wiki den Begriff Äquivalenzrelation nach!)
P.S.:
Man kann sich leicht überlegen, dass man - wenn man eine fest vorgegebene Äquivalenzrelation bzgl. einer Menge hat - mithilfe der Äquivalenzklassen diese Menge partitioniert - d.h. die Vereinigung der (disjunkten) Äquivalenzklassen ist gerade wieder die Ausgangsmenge. Umgekehrt korreliert eine solche Partitionierung in eindeutiger Weise mit einer Äquivalenzrelation, und die "Partitionsmengen" sind dabei gerade die entsprechenden Äquivalenzklassen.
Nun zu Deiner Aufgabe:
Wegen dem obigen P.S. ist zu überlegen, auf wieviele Arten man eine Menge partitionieren kann.
Dazu:
Versuche mal, herauszufinden, wie man die Anzahl aller möglichen Partitionierungen einer Menge mithilfe einer Rekursionsformel beschreiben kann. (Tip: ![[]](/images/popup.gif) Bellsche Zahl. Wichtig: Mache Dir klar, wie sich dieses Schema hier überträgt, unter Beachtung: ${n [mm] \choose [/mm] k}$ gibt die Anzahl der Auswahlmöglichkeiten aller [mm] $k\,$-elementiger [/mm] Mengen von einer n-elementigen Mengen (z.B. [mm] $\{1,\ldots,n\}$) [/mm] an!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:48 Fr 17.12.2010 | | Autor: | ella87 |
Ich habe nochmal ein bisschen nachgelesen, aber ich bin irgendwie nicht wirklich schlauer geworden. Das ist mir irgendwie zu abstrakt. Aber ich habe da eine Widerspruch gefunden (allerdigs bei Wikipedia)
>
> > Aber ich habe dann Probleme mit den Mengen { }, sowie den
> > einelementigen Mengen.
> > Kann denn so eine Menge z.B. Transitiv sein? Man hat ja
> > nur ein Element oder sogar keins.
>
> Klar. Schau' mal nach, was in der Definition einer
> Äquivalenzrelation steht:
> Reflexiv: Für alle Elemente der Menge soll gelten...
>
da steht aber:
"Die Äquivalenzrelation ist in der Logik und Mathematik von großer Bedeutung:
* Sie teilt eine Menge restlos in nichtleere und disjunkte (elementfremde) Untermengen, Äquivalenzklassen genannt..."
hier steht nicht leere Mengen .
Soll ich bei der Aufgabe jetzt also die Anzahl der disjunkten Mengen aufschreiben?
also:
1. Ä-Klasse: {1,2,3,4},{5}
2. Ä-Klasse: {1,2,3,5},{4} ....
Es tut mir leid. Ich begreif das nicht.
zur Bellschen Zahl. n über k gibt es bei uns in der Vorlesung noch nicht. Das kann ich also nicht verwenden.
|
|
|
| |
|
> Ich habe nochmal ein bisschen nachgelesen, aber ich bin
> irgendwie nicht wirklich schlauer geworden. Das ist mir
> irgendwie zu abstrakt. Aber ich habe da eine Widerspruch
> gefunden (allerdigs bei Wikipedia)
> >
> > > Aber ich habe dann Probleme mit den Mengen { }, sowie den
> > > einelementigen Mengen.
> > > Kann denn so eine Menge z.B. Transitiv sein? Man hat
> ja
> > > nur ein Element oder sogar keins.
> >
> > Klar. Schau' mal nach, was in der Definition einer
> > Äquivalenzrelation steht:
> > Reflexiv: Für alle Elemente der Menge soll gelten...
> >
>
> da steht aber:
> "Die Äquivalenzrelation ist in der Logik und Mathematik
> von großer Bedeutung:
>
> * Sie teilt eine Menge restlos in nichtleere und disjunkte
> (elementfremde) Untermengen, Äquivalenzklassen
> genannt..."
>
> hier steht nicht leere Mengen .
Hallo,
betrachte einfach Äquivalenzrelationen auf nichtleeren Mengen, dann bist Du Deinen Widerspruch los.
Du sollst ja über eine Menge nachdenken, die sogar 5 Elemente hat.
Festgestellt wurde bereits, daß Du zur Beantwortung der gestellten Frage die Anzahl der möglichen Partitionen zählen kannst.
> Soll ich bei der Aufgabe jetzt also die Anzahl der
> disjunkten Mengen aufschreiben?
So könntest Du es machen.
> also:
> 1. Ä-Klasse: {1,2,3,4},{5}
> 2. Ä-Klasse: {1,2,3,5},{4} ....
Wenn Du dies durchziehst, dann hast Du die Partitionen, bei denen eine Menge 4-elementig, die andere einelementig ist.
Alle anderen mußt Du nun auch noch sammeln.
>
> Es tut mir leid. Ich begreif das nicht.
Du hast doch gar nicht so übel begonnen.
Was genau begreifst Du nicht?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:22 So 19.12.2010 | | Autor: | ella87 |
Also: ich hab mir nochmal alles genaustens angeguckt, was wir zu Äquivalenzrelationen gemacht haben und fass das mal inklusive meiner Fragen und Widersprüche zusammen.
(bezieht sich also erstmal nicht direkt auf die Aufgabe)
1. Eine Äquivalenzrelation auf M wir definiert als reflexiv, symmetrisch und transitiv .
das ist soweit klar
2. [mm]\Phi[/mm] ist eine Partition von M, wenn es eine disjunkte Zerlegung von M ist
auch soweit klar
3. Für eine Menge M mit einer Äquivalenzrelation R gilt:
[mm][a]_R := \{ x \in M | x R a \}[/mm] ist Äquivalenzklasse von [mm]a \in M [/mm]. [mm]a^ [/mm] ist der Repräsentant der Äquivalenzklasse.
Dann ist: [mm] M/R := \{ [a]_R | a \in M \} [/mm]
das würde ich gerne mal sinnvoll in Worte fassen:
"Die Menge M mit der zugehörigen Äquivalenzrelation R ist die Menge aller Äquivalenzklassen von Elementen aus M"
das kann ich nicht so ganz greifen. Verstehe ich das richtig, dass ich für meine Menge [mm] \{1,2,3,4,5\}[/mm] die Äquivalenzkassen [mm] [1]_R , [2]_R , [3]_R , [4]_R , [5]_R [/mm] habe?
Das ist mir allerdings nicht ganz klar. Kann ich noch weitere Aussagen zu diesen Klassen treffen, also z.B.[mm] [1]_R = \{1,2,3,4,5\} [/mm], weit die Relation R für alle Elemente aus M in Kombination mit 1 gilt oder geht das nicht, weil man R nicht näher bestimmt ist?
Eigentlich müsste das doch gelten (Def. Äquivalenzrelation). Und dann sind die Äquivalenzklassen auch alle gleich.
genau das sagt glaub ich 4.aus:
4. R Relation auf M
[mm]a R b [/mm] [mm] \gdw [/mm] [mm] [a]_R = [b]_R [/mm]
5. R eine Äquivalenzrelation auf M.
Dann ist [mm]M/R[/mm] eine disjunkte Zerlegung von M.
Umgekehrt: wenn [mm]\Phi[/mm] eine disjunkte Zerlegung von M, dann wir dadurch eine Äquivalenzrelation auf M definiert durch:
[mm]a R b[/mm] [mm]\gdw[/mm] [mm]\exists U \in \Phi : a \in U \quad \wedge \quad b \in U[/mm] [mm] \Rightarrow \Phi = M/R [/mm].
das haben wir so formulier - ich finds komisch. Mich stört die "disjunkte Zerlegung", weil das im Zusammenhang mit M/R nie aufgetaucht ist.
Ist das in der Literature der "Zerlegungssatz"?
Also jede Äquivaenzrelation R einer Menge M bewirkt eine Zerlegung dieser Menge in M/R. Oder: Jede Zeregung M/R einer Menge M bestimmt eine Äquivalenzrelation R in M.
P.S.: Den Zeregungssatz kann ich dann für die Aufgabe gebrauchen, indem ich alle Zeregungen finde und damit alle Relationen. Wäre also nett, wenn mir dazu jemand den Begriff der "Äquivaenzklasse" näher bringen kann - das ist glaub ich mein Knackpunkt...
Danke!
|
|
|
| |
|
> 3. Für eine Menge M mit einer Äquivalenzrelation R gilt:
> [mm][a]_R := \{ x \in M | x R a \}[/mm] ist Äquivalenzklasse von [mm]a \in M [/mm].
> [mm]a^[/mm] ist der Repräsentant der Äquivalenzklasse.
Hallo,
in [a] sind alle Elemente aus M enthalten, die äquivalent sind zu a.
>
> Dann ist: [mm]M/R := \{ [a]_R | a \in M \}[/mm]
M/R ist die Menge, die aus allen Äquivalenzklassen besteht.
>
> das würde ich gerne mal sinnvoll in Worte fassen:
> "Die Menge M mit der zugehörigen Äquivalenzrelation R
die Menge M/R, "M nach R"
> ist die Menge aller Äquivalenzklassen von Elementen aus
> M"
>
> das kann ich nicht so ganz greifen. Verstehe ich das
> richtig, dass ich für meine Menge [mm]\{1,2,3,4,5\}[/mm] die
> Äquivalenzkassen [mm][1]_R , [2]_R , [3]_R , [4]_R , [5]_R[/mm]
> habe?
Ja.
Es kann aber sein, daß diese 5 Äquivalenzklassen nicht verschieden sind.
> Das ist mir allerdings nicht ganz klar. Kann ich noch
> weitere Aussagen zu diesen Klassen treffen,
Wenn Du die Relation R kennst.
> also z.B.[mm] [1]_R = \{1,2,3,4,5\} [/mm],
Das hätte man, wenn alle 5 Elemente in Relation zueinander stehen.
Es wäre dann mit [mm] M:=\{1,2,3,4,5\}
[/mm]
[mm] M/R=\{M\}
[/mm]
> weit die Relation R für alle Elemente aus M in Kombination
> mit 1 gilt oder geht das nicht,
Ich kann hier nicht antworten, weil ich nicht genau weiß, was Du meinst.
Bei einer Äquivalenzrelation muß keinesfalls die 1 in Relation zu jedem anderen Element, hier also zu 2,3,4,5 stehen.
Leider klappt das Zitieren des Restes Deines Textes nicht, weiß der Geier, weshalb...
Die 4. sagt, daß die Äquivalenzklassen zweier Elemente gleich sind, sofern die Elemente äquivalent sind, und umgekehrt.
Haben wir also eine Äquivalenzrelation mit [mm] [1]=\{1,4,5\}, [/mm] so ist [1]=[4]=[5],
und ist 1R5, so ist [1]=[5].
Zu der disjunkten Zerlegung:
ob das unter "Zerlegungssatz" läuft, weiß ich nicht.
Passen würd's ja gut.
Die 5. sagt, daß die Vereinigung der Mengen, die in M/R sind, die Menge M ergibt, und daß eben die Mengen, die in M/R sind, disjunkt sind.
"Zwei Äquivalenzklassen sind gleich oder disjunkt."
Es kann nicht sein, daß (bei unserem Beispiel) eine Äquivalenzklasse [mm] \{1,4,5\} [/mm] ist und eine andere [mm] \{2,5\}.
[/mm]
Überleg' Dir selbst, weshalb das so ist.
Gruß v. Angela
>
> genau das sagt glaub ich 4.aus:
> 4. R Relation auf M
> [mm]a R b[/mm] [mm]\gdw[/mm] [mm][a]_R = [b]_R[/mm][/b]
> [mm][b] [/b][/mm]
> [mm][b]5. R eine Äquivalenzrelation auf M. [/b][/mm]
> [mm][b]Dann ist M/R[/mm] eine disjunkte Zerlegung von M. [/b]
> [mm][b]Umgekehrt: wenn \Phi[/mm] eine disjunkte Zerlegung von M, dann [/b]
> [mm][b]wir dadurch eine Äquivalenzrelation auf M definiert [/b][/mm]
> [mm][b]durch:[/b][/mm]
> [mm][b] a R b[/mm] [mm]\gdw[/mm] [mm]\exists U \in \Phi : a \in U \quad \wedge \quad b \in U[/mm] [/b]
> [mm][b] \Rightarrow \Phi = M/R [/mm].[/b]
> [mm][b] [/b][/mm]
> [mm][b]das haben wir so formulier - ich finds komisch. Mich stört [/b][/mm]
> [mm][b]die " b]="" src="http://teximg.matheraum.de/render?d=108&s=$%2524%24$">">%5Bb%5Ddie%20$" disjunkte="" zerlegung="" ,="" weil="" das="" im="" zusammenhang="" mit="" m="" r="" [="" b]="">
> ![<span class=]() ![$[b]die](http://teximg.matheraum.de/render?d=108&s=$%2524%24$) ">%5Bb%5Ddie%20$" disjunkte="" zerlegung="" ,="" weil="" das="" im="" zusammenhang="" mit="" m="" r="" [="" b]="">
> ">%5Bb%5Ddie%20$" disjunkte="" zerlegung="" ,="" weil="" das="" im="" zusammenhang="" mit="" m="" r="" [="" b]="">
> ![<span class=]() ">%5Bb%5Ddie%20$" disjunkte="" zerlegung="" ,="" weil="" das="" im="" zusammenhang="" mit="" m="" r="" [="" b]="">
> ![$[b]nie aufgetaucht ist.[/b][/mm]lt;b>nie aufgetaucht ist.</b>[/mm]lt;b>nie aufgetaucht ist.</b>[/mm]
</font>
<br>
<font class=]() > <span class=" math=""><img class="latex" _cke_realelement="true" alt="<span class=" math=""><img class="latex" _cke_realelement="true" alt="$[b] Ist das in der Literature der " b]="" src="http://teximg.matheraum.de/render?d=108&s=$%24$">%24<img class="latex" _cke_realelement="true" alt="$">%5Bb%5D%20Ist%20das%20in%20der%20Literature%20der%20[/mm][mm][b]Zerlegung dieser Menge in M/R. Oder: Jede Zeregung M/R [/b][/mm]
> <span class=" math=""><img class="latex" _cke_realelement="true" alt="$einer Menge M bestimmt eine Äquivalenzrelation R in M.[/mm]
> <span class="math">[mm][b] [/b][/mm]
> [mm][b]P.S.: Den Zeregungssatz kann ich dann für die Aufgabe [/b][/mm]
> [mm][b]gebrauchen, indem ich alle Zeregungen finde und damit alle [/b][/mm]
> [mm][b]Relationen. Wäre also nett, wenn mir dazu jemand den [/b][/mm]
> <span class="math">[mm][b]Begriff der " b]="" src="http://teximg.matheraum.de/render?d=108&s=$">%5Bb%5DBegriff%20der%20[/mm][mm][b]Begriff der " b]="" src="http://teximg.matheraum.de/render?d=108&s=$">%5Bb%5DBegriff%20der%20[/mm][mm][b] [/b][/mm]
> <span class=" math=""><img class="latex" _cke_realelement="true" alt="$Danke! [/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:06 Fr 17.12.2010 | | Autor: | felixf |
Moin Sax!
> Du musst auch wissen, dass jede Äquivalenzrelation auf M =
> {1 ; 2 ; 3 ; 4 ; 5} eine Klasseneinteilung der Menge M
> induziert und umgekehrt.
> Die Klasseneinteilung M = {1 ; 3} [mm]\cup[/mm] {2 ; 4 ; 5} ist
> z.B. diejenige Äquivalenzrelation, in der 1 und 3
> zueinander in Relation stehen und außerdem je zwei der
> Elemente 2, 4 und 5, sowie natürlich jede Zahl zu sich
> selbst.
>
> Die Anzahl der Klasseneinteilungen ist viel einfacher
> abzuzählen.
> Wenn du nämlich oben die Mengenklammern {} durch runde
> Klammern () ersetzt, erhälst du (1 3)(2 4 5), das ist eine
> P... von M und die Anzahl der P... sollte dir bekannt
> sein.
Das ist eine schoene Idee. Allerdings gibt es ein Problem: man kann hiermit jeder Aequivalenzrelation eine Permutation zuordnen (sogar eindeutig, wenn man will). Das Problem ist, dass man damit nicht jede Permutation erwischt.
Man muss also verschiedene Permutationen identifizieren, und das macht das Zaehlen wieder kompliziert.
LG Felix
|
|
|
|
