Äquivalenzrelation < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:33 So 05.11.2006 | | Autor: | Dr.Ogen |
| Aufgabe | | Sei A={1,2,3}. Bestimmen sie alle Äquivalenzrelationen auf A x A. |
Kann mir jemand sagen, ob meine Lösung hier richtig ist? Leider finde ich für so eine vermeintlich einfache Aufgabe nirgendwo eine Lösung.
Es gilt:
A x A = {{1,1},{1,2},{1,3},{2,1},...{3,3}}
und
R [mm] \subseteq [/mm] A x A
Gesucht sind alle R die transitiv, reflexiv und symmetrisch sind. Da die Symmetrie vorraussetzt, dass {1,1},{2,2} und {3,3} in R enthalten sind bleiben ja nicht mehr viele Kombinationen übrig. Gibt es überhaupt noch andere Äquivalenzrelationen außer R= {{1,1},{2,2},{3,3}}? Und wie kann ich das ohne Text sondern mathematisch mit logischen Ausdrücken beweisen?
Ich hab das Gefühl ich sitze direkt vor der Lösung und komm nicht drauf ;)
/Edit:
Im Moment des Abschickens geht mir noch ein Licht auf:
Sind das alle Lösungen?
R= {{1,1},{2,2},{3,3}}
R= {{1,1},{1,2},{2,1},{2,2},{3,3}}
R= {{1,1},{2,1},{2,2},{3,2}{3,3}}
R= {{1,1},{1,3},{2,2},{3,1},{3,3}}
R= ganz A x A also {{1,1},{1,2},...,{3,3}}
bin gespannt was ihr dazu meint. :D
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:53 So 05.11.2006 | | Autor: | DaMenge |
Hi,
Ein Äquivalenzrelation ist auch eindeutig über ihre Partition definiert.
Also eine Äquivalenzrelation erzeugt eine Partititon und umgekehrt.
Du musst also alle Partitionen angeben.
dazu schau mal HIER
wobei zwei Elemente der Äquivalenzrelation in Relation zueinander stehen genau dann wenn sie in derselben Partition liegen.
also angenommen du hast die Partition
$P={{1,2},{3}}$
dann ist die dazu gehörige Äquivalenzrelation:
$R={ (1,1),(2,2),(1,2),(2,1) ,(3,3) }$
(beachte bitte, dass man Paare bei Relationen nicht mit geschweiften Klammern schreiben darf, denn sonst gäbe es keinen Unterschied zw. (1,2) und (2,1) .. )
ob es ausreicht einfach alle Partitionen hinzuschreiben kann ich dir aber nicht beantworten - du musst wissen, ob ihr schon einen Zusammenhang zw. Äquivalenzrelationen und Partitionen hattet - diesen solltest du dann auch verwenden bzw zitieren.
Wenn ihr diesen nicht hattet, dann musst du dir den evtl. schnell mal herleiten (zur Not googlen oder in ein gutes Buch schauen), denn alle 512 möglichen Relationen auf einer 3-elemntigen Menge willst du sicher nicht durchgehen, oder?
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:28 So 05.11.2006 | | Autor: | Dr.Ogen |
Bist du dir sicher, dass es für die Beantwortung der Frage 512 mögliche Lösungen gibt? Das wäre wirklich komisch denn die Beziehung zwischen Potenzmengen und Äquivalenzrelationen hab ich bis jetzt zwar im Heuser gelesen aber bin davon ausgegangen das man die Lösungen auf so eine Frage wirklich alle hinschreiben kann. (Ich gehe mal davon aus, dass in der Aufgabe nicht umsonst A konkret angegeben ist... Oder soll das ein Test sein?!)
Kannst du mir noch auf die Sprünge helfen warum deine Lösung für mich nach mehr als der Äquivalenzlerationen auf A x A aussieht?
Da für Äquivalenzrelationen gilt, dass sie
- symmetrisch sind
müssen (1,1), (2,2) und (3,3) ja immer in R sein.
- reflexiv sind
müssen (1,2), (2,1) und (1,3),(3,1) und (3,2), (2,3) immer paarweise vorhanden sein
-transitiv sind müssen die Paare aus "reflexiv" auch immer mit ihren dazugehörigen (a,a) Tupeln (nennt man das so?) vorhanden sein.
Außerdem müssen ja sobald zwei der Paarkombinationen aus "reflexiv" element R sind, auch das letzte Element in R sein da sonst aus (a,b) und (b,c) nicht immer (a,c) folgt.
Also sind die Kombinationen doch nur:
R= {(1,1),(2,2),(3,3)}
R= {(1,1),(1,2),(2,1),(2,2),(3,3)}
R= {(1,1),(2,2),(2,3),(3,2),(3,3)}
R= {(1,1),(1,3),(2,2),(3,1),(3,3)}
R= {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
Sag mir doch einfach noch eine weitere und erläuter das ein bischen, dass ich meinen Denkfehler verstehe...
und natürlich vielen Dank für die Antwort!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:10 So 05.11.2006 | | Autor: | DaMenge |
Hi nochmal,
> Bist du dir sicher, dass es für die Beantwortung der Frage
> 512 mögliche Lösungen gibt? Das wäre wirklich komisch denn
Nein, ich hab nicht gesagt, dass es 512 Lösungen gibt.
Ich hab gesagt, dass du 512 mögliche Relationen überprüfen müsstest.
> Kannst du mir noch auf die Sprünge helfen warum deine
> Lösung für mich nach mehr als der Äquivalenzlerationen auf
> A x A aussieht?
>
Ähm, wie meinst du das jetzt?!?
Also ja, ich habe ein wenig allgemeiner geschrieben und nicht nur den 3-elementigen Fall behandelt, das ist richtig.
Aber die eine Äquivalenzrelation, die ich angegeben habe, hast du ja auch angegeben.
> Da für Äquivalenzrelationen gilt, dass sie
>
> - symmetrisch sind
...
> - reflexiv sind
>
...
> -transitiv sind müssen die Paare aus "reflexiv" auch immer
...
> Also sind die Kombinationen doch nur:
all das glaube ich dir ja, aber hast du damit bewiesen, dass alle anderen der 512 Relationen das nicht erfüllen?
> R= {(1,1),(2,2),(3,3)}
entspricht der Partition P={{1},{2},{3}}
> R= {(1,1),(1,2),(2,1),(2,2),(3,3)}
entspricht der Partition P={{1,2},{3}}
> R= {(1,1),(2,2),(2,3),(3,2),(3,3)}
entspricht der Partition P={{1},{2,3}}
> R= {(1,1),(1,3),(2,2),(3,1),(3,3)}
entspricht der Partition P={{1,3},{2}}
> R=
> {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
entspricht der Partition P={{1,2,3}}
>
> Sag mir doch einfach noch eine weitere und erläuter das ein
> bischen, dass ich meinen Denkfehler verstehe...
Du hast zwar recht, dass es keine weiteren Äquivalenzrelationen mehr gibt, aber deine Begründung dafür finde ich nicht ausreichend, denn im Grunde steht da nur : "mir fallen keine weiteren möglichkeiten mehr ein"
(deine Nachfrage, dass jemand anderes eine weitere nennen könnte ist Beweis genug dafür, dass du nicht alle Möglichkeiten ausgeschlossen hast)
Meine Begründung ist da ein wenig allgemeiner, aber dafür auch vollständig:
Es gibt eine bijektive Abbildung zw. der Menge der Äquivalenzrelationen und der Menge der Partitionen und deshalb reicht es sich alle möglichen Partitionen zu überlegen.
(ich hab extra mal bei deinen Relationen die enstpr. Partitionen dazu geschrieben)
Im Grunde musst du natürlich selbst wissen, was du abgeben willst, aber ich würde wirklich nochmal danach ausschau halten, ob ihr in eurer Vorlesung/Mitschrift/Script nicht einen Zusammenhang zw. Partitionen und Äquivalenzrelationen hattet !
(mal abegesehen davon, dass es die Argumentation wesentlich klarer und vollständiger macht, sollte man das auch mal behandelt haben)
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:21 So 05.11.2006 | | Autor: | Dr.Ogen |
nochmal danke, dass du dich mit mir und meiner Unwissenheit hier rumschlägst.
Selbstverständlich finde ich die Begründung auch nicht ausreichend, aber genau deshalb bin ich hier: Ich will ja die anderen Partitionen nicht alle untersuchen müssen sondern formal sagen warum diese 5 Lösungen die einzigen sein können. Aber da fehlt mir der Ansatz: Ich sollte ja offensichtlich am besten mit Quantoren jonglieren und ein paar logische Operatoren verwenden um das allgemein und mathematisch richtig auszudrücken.
Aber wie mache ich das?
Vielleicht so?
[mm] \forall [/mm] a element A : (a,a) element R (symmetrie)
[mm] \forall [/mm] a,b element A (a,b) element R : (b,a) element R (reflexivität)
[mm] \forall [/mm] a,b,c element A (a,b) element R (b,c) element R : (a,c) element R (transitivität)
aber während ich das schreibe fällt mir schonwieder auf, dass das ja eigentlich nur nochmal die Definition ist... :( Wie komme ich denn von da auf den konkreten Fall für A = {1,2,3} ?
(unabhängig davon hast du ja auch gesagt, dass die 5 Lösungen richtig und gleichzeitig die einzigen sind, was mir ja schonmal eine gewisse Erleichterung verschafft.)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:22 Di 07.11.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
