Wie berechne ich die Anzahl reflexiven, symmetrischen und antisymmetrischen Relationen?
Hallo, sagen wir mal ich habe eine Menge gegeben mit 5 Elementen wie würde ich hier die Anzahl der reflexiven, symmetrischen und antisymmetrischen Relationen berechnen? Gibt es da eine Formel, die man sich merken kann?
2 Antworten
Wenn M die Menge ist, dann Jede Relation R entspricht einer Teilmenge von M². Da M 5 Elemente hat, hat M² 25 Elemente. Damit gibt es
Relationen insgesamt.
Reflexiv ist eine Relation dann, wenn sie alle Paare (a,a), a Element von M enthält. Das sind 5. Die restlichen Elemente von M² sind also noch 20, aus denen du wieder frei wählen kannst (denn weitere Eigenschaften sind ja nicht festgelegt), also gibt es
reflexive Elemente insgesamt.
Symmetrisch ist eine Relation, wenn aus (a,b) in R auch (b,a) in R folgt. (in Arbeit, sorry, war ein Haken drin)
Deine Wahlfreiheit wird durch die Symmetrie insofern eingeschränkt, als du nur das Paar (a,b) wählen kannst und damit dann bereits entschieden ist, dass auch (b,a) drin liegt. Man kann sich das so vorstellen: Ordne die Elemente der Menge in einer nxn-Tabelle an:
(a,a) (a,b) (a,c) (a,d) (a,e)
(b,a) (b,b) (b,c) (b,d) (b,e)
(c,a) (a,b) (c,c) (c,d) (c,e)
(d,a) (d,b) (d,c) (d,d) (d,e)
(e,a) (e,b) (e,c) (e,d) (e,e)
Wenn jetzt ein bestimmtes Element drin ist (z. B. (a,b)) dann ist automatisch auch das Elemente (b,a) drin. Wahlfreiheit hast du nur auf der Hälfte, nämlich dieser:
(a,a) (a,b) (a,c) (a,d) (a,e)
(b,a) (b,b) (b,c) (b,d) (b,e)
(c,a) (a,b) (c,c) (c,d) (c,e)
(d,a) (d,b) (d,c) (d,d) (d,e)
(e,a) (e,b) (e,c) (e,d) (e,e)
Aus diesen 15 Elemente darfst du auswählen, die anderen kommen dann automatisch dazu, oder eben nicht. Also hast du
symmetrische Relationen. Die antisymmetrischen überlasse ich jetzt dir, die sind allerdings auch wieder tricky. Zunächst einmal kannst du da sagen, dass eine beliebige Teilmenge der Paare (a,a) enthalten sind. Und dann wird es eben etwas tricky.
Da gibt es kein allgemeingültiges Rezept für beliebige Relationen. Das hängt von der konkreten Relation und den Zahlen in der Menge ab. Also z.B. ob Du eine grösser-als, kleiner-als oder "gleich" Relation (Operator) hast.
Schau mal hier, unter dem Abschnitt "Relationen". Da gibt es ein paar Beispiele.
https://www.grund-wissen.de/mathematik/mengenlehre/abbildungen.html