 |
 |
 |
 |
 |
 |
Startseite » Forum » Anzahl von Relationen, Äquivalenzrelationen, ...
Anzahl von Relationen, Äquivalenzrelationen, ...
Universität / Fachhochschule
Relationen
Rekursives Zählen
Tags: Bellsche Zahl, Kartesisches Produkt, Potenzmenge, Rekursives Zählen, Relation.
 
|
  |
|---|
|
Hallo zusammen Ich habe mich ein wenig mit Mengenlehre und Relationen befasst. Dabei hat sich mir die Frage gestellt, wie viele Relationen es eigentlich gibt von A auf B. Dazu habe ich mir überlegt, dass eine Relation eine Teilmenge des Kartesischen Produkts der beiden Mengen ist. Das Kartesische Produkt von A und hat Elemente, quasi eine |A|x|B|-Matrix. Für jede Komponente dieser Matrix kann ich nun entscheiden, ob sie 0 oder 1 sein soll, oder anders gesagt, ich nehme die Potenzmenge des Kartesischen Produkts und erhalten . Ist das die korrekte Anzahl von Relationen, die es zwischen der Menge A und der Menge gibt? Nun hat sich die Frage gestellt, wie viele Äquivalenzrelationen auf eine Menge A es dann geben könnte. Äquivalenzrelation muss reflexiv sein (also in der Diagonale alles ich kann dann Komponenten nicht mehr frei wählen, ich kann also nur noch Komponenten wählen.) Dann muss sie symmetrisch sein und transitiv.. und dann wird es schwierig.. möglich wäre es aber auch, über die Partitionen zu gehen, doch auch das ist recht schwierig.. finde ich.. ich habe das googlen wollen und habe nur etwas über die Bellsche Zahl gesehen, kann aber auch fast nicht glauben, dass es gerade wieder so schweirig ist. Ist die Bellsche Zahl wirklich die Antwort, wenn es darum geht, zu wissen, wie viele Äquivalenzrelationen es auf eine Menge gibt? Vielen Dank für eure Antworten, wäre euch echt dankbar.. |
|
 |
|
Moin. Als Tipp: Eine Aquivalenzrelation auf A induziert eine Partition von da jedes Element aus in genau einer Äquivalenzklasse enthalten ist. Umgekehrt induziert jede Partition von A eine Äquivlanzrelation durch und liegen in derselben "Klasse". Also musst du "bloß" die Anzahl der Partitionen einer n-elementigen Menge zählen. |
 |
|
Und somit entspricht die Anzahl der Äquivalenzrelationen also der Bellschen Zahl? |
|
|
|
Habe jetzt nochmals gegoogelt, und noch einige Artikel zum Thema Stirlingszahlen gefunden, und ich denke, es müsste sich um diese (respektive die Bellschen Zahlen) handeln. Stimmt so, oder? Bin aber eben gerade mit Mengenlehre/Kombinatorik beschäftigt, und habe mir deshalb die Frage gestellt, wie viele reflexive, symmetrische, antisymmetrische, asymmetrische, transitive Relationen es gibt auf eine Menge mit Elementen. Wäre froh, wenn ihr mir sagen könntet, ob meine Überlegungen stimmen und dort, wo ich nicht weiter weiss, mir weiter helfen könntet. reflexiv: Die Elemente in der Diagonale der nxn-Matrix sind auf 1 gesetzt, den Rest kann ich frei wählen. Es gibt also mögliche reflexive Relationen. symmetrisch: Ich kann eine Hälfte der Matrix (inklusive Diagonale) beliebig ausfüllen, die andere ist einfach symmetrisch dazu. Ich habe also Möglichkeiten für eine symmetrische Relation. Aber ich glaube, irgend was stimmt da nicht. Diese Formel ist jedenfalls schon bei kleinen Beispielen gescheitert. antisymmetrisch: eigentlich müsste ja das analog zu symmetrisch sein. Die beiden Hälften einer Matrix sind genauso abhängig voneinander wie bei einer symmetrischen, nur einfach "umgekehrt".. Diagonale? Unterschied zu asymmetrisch? transitiv? ?? keine Ahnung.. Wäre wirklich dankbar um jede Hilfe/jeden Ansatz.. |
|
|
|
Reflexiv: Stimmt, Symmetrisch, antisymmetrisch: Transitiv ist wirklich knifflig und keine allgemeien Formel bekannt. Siehe etwa oeis.org/A006905 Bei www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html gibt es ein PDF, das diese und andere Ergebnisse zusammenfasst |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
952970
952477