[Deynorus]

Guten Tag,

Angenommen ich habe eine Menge mit 2 Elementen. Wie hoch ist dann die Anzahl der möglichen Relationen auf A?

Eine Relation ist ja definiert als eine Teilmenge des Kartesischen Produktes einer Menge.

Wenn A={a,b}, dann ist ja A x A ={(a,a), (a,b), (b,a), (b,b)}

Wie viele Mögliche Relationen habe ich nun? Ist die Anzahl der möglichen Relationen auf A nun 4 (s.o), oder sind noch die verschiedenen Kombinationen relevant, da ja eigentlich auch die Kombinationen untereinander noch Teilmengen sind. Um das zu verdeutlichen ersetze ich die obigen Paare durch Buchstaben:
(a,a)=a; (a,b) = b; (b,a)= c; (b,b)= d.

{a}; {a,b}; {a,c}; {a,d}; {a,b,c}; {a,b,d}; {a,c,d}; {b}; {b,c}; {b,d}; {b,c,d}; {c}; {c,d}; {d}; {a,b,c,d}

Ich hoffe, ich habe keine vergessen, außerdem bin ich unschlüssig, ob ich die leere Menge auch mitnehmen müsste.
Also zurück zur Frage, wie hoch ist also die Anzahl der möglichen Relationen der Menge A? Liegt sie bei 4, s.o., oder aber bei 15, bzw. 16 mit der Leeren Menge (s.u.)?

lG. Deynorus.

Edit:
Außerdem frage ich mich noch, welche der Relationen Reflexiv sind und welche Symmetrisch. Irgendwie habe ich das auch noch nicht ganz verstanden...:/
Wenn ich mich nicht irre, wären z.B. die Paare (a,b) und (b,a) symmetrisch. Wäre das richtig?

Wäre super, wenn mir jemand helfen könnte.

[Thoronador]

Eine Relation ist ja definiert als eine Teilmenge des Kartesischen Produktes einer Menge.
[...]
Wie viele Mögliche Relationen habe ich nun?

Die Antwort darauf ergibt sich doch eigentlich aus der oberen Aussage. Oder anders gesagt: Wie viele Teilmenge des kartesischen Produkts einer Menge existieren? Damit hast du dann auch die Antwort auf die Frage nach den möglichen Relationen. So viel sei schon mal verraten: 4 ist es im obigen Beispiel nicht.

Außerdem frage ich mich noch, welche der Relationen Reflexiv sind und welche Symmetrisch. Irgendwie habe ich das auch noch nicht ganz verstanden...:/

Ist M eine Menge und R ⊆ M⨯M eine zweistellige Relation, dann heißt R reflexiv, wenn für jedes Element x der Menge (x,x) Teil der Relation ist.
Auf deiner Menge A={a,b} wäre dann jede Relation reflexiv, die (a,a) und (b,b) enthält.

Ist M eine Menge und R ⊆ M⨯M eine zweistellige Relation, dann ist R symmetrisch, falls für alle x, y aus M aus xRy auch yRx folgt.
(Die Schreibweise xRy bedeutet, dass (x,y) zur Relation R gehört.)

[Deynorus]

Somit müsste es dann 16 Relationen auf die Menge A geben, da die leere Menge {} ja Teilmenge jeder Menge ist?

Damit man eine Relation als reflexiv oder symmetrisch bezeichnet, muss die Vorraussetzung dann ja für alle Elemente gelten, nicht wahr? Es wären also 3 Relationen reflexif und zwar:
{(a,a)}; {(b,b)}; {(a,a),(b,b)}?

Außerdem müssten dann die Relation

{(a,b),(b,a)} symmetrisch sein.

Oder gilt ein Paar (a,a) auch zu sich selbst als symmetrisch?
Sonst wären es natürlich noch ein paar mehr.
Würde man die Teilmenge {(a,a), (a,b), (b,a)} auch als symmetrisch bezeichnen?

Auf deiner Menge A={a,b} wäre dann jede Relation reflexiv, die (a,a) und (b,b) enthält.

Wenn ich das wörtlich verstehe, dann müsste ja jede Relation reflexiv sein, die sowohl das Paar (a,a), als auch das Paar (b,b) enthält, genau genommen sogar unabhängig von den Paaren, die sonst noch so dabei sind. Aber das wäre nun sehr verwirrend für mich...

[Blubbler]

Oder gilt ein Paar (a,a) auch zu sich selbst als symmetrisch?

EDIT: "symmetrisch" bezieht sich nicht auf Paare, sondern auf Relationen. {(a,a)} ist natürlich symmetrisch.

Wenn ich das wörtlich verstehe, dann müsste ja jede Relation reflexiv sein, die sowohl das Paar (a,a), als auch das Paar (b,b) enthält, genau genommen sogar unabhängig von den Paaren, die sonst noch so dabei sind. Aber das wäre nun sehr verwirrend für mich...

Eine Relation R auf M ist reflexiv auf M, wenn für jedes m€M (m,m)€R gilt. Ob noch irgendetwas zusätzlich gilt, ist völlig irrelevant.

[Thoronador]

Damit man eine Relation als reflexiv oder symmetrisch bezeichnet, muss die Vorraussetzung dann ja für alle Elemente gelten, nicht wahr? Es wären also 3 Relationen reflexif und zwar:
{(a,a)}; {(b,b)}; {(a,a),(b,b)}?

Nein. Weder {(a,a)} noch {(b,b)} sind reflexive Relationen auf A={a,b}. Allerdings wären beide symmetrisch.
Jedoch liegst du mit {(a,a),(b,b)} richtig, diese Relation ist reflexiv auf A={a,b}.

Außerdem müssten dann die Relation

{(a,b),(b,a)} symmetrisch sein.

Korrekt.
Das ist allerdings nicht die einzige symmetische Relation, wie schon aus dem vorigen Absatz hervorgeht.

Oder gilt ein Paar (a,a) auch zu sich selbst als symmetrisch?
Sonst wären es natürlich noch ein paar mehr.
Würde man die Teilmenge {(a,a), (a,b), (b,a)} auch als symmetrisch bezeichnen?

Du musst nochmal an den Begriffen arbeiten. Ein Paar an sich kann nicht symmetrisch sein, da "symmetrisch sein" im zuvor genannten Sinne eine Eigenschaft von Relationen ist. Nun ist (a,a) aber keine Relation. Hingegen ist {(a,a)} eine Relation, und die wäre dann symmetrisch.

Wenn ich das wörtlich verstehe, dann müsste ja jede Relation reflexiv sein, die sowohl das Paar (a,a), als auch das Paar (b,b) enthält, genau genommen sogar unabhängig von den Paaren, die sonst noch so dabei sind.

Genau das steht doch da. Oder besser gesagt: Ja, das darfst (und sollst) du wörtlich nehmen. Was zusätzlich zu den beiden genannten Paaren noch in der Relation ist, spielt keine Rolle. Genau das sagt "Auf deiner Menge A={a,b} wäre dann jede Relation reflexiv, die (a,a) und (b,b) enthält." auch aus. Jede binäre Relation auf A={a,b}, die eine Obermenge von {(a,a), (b,b)} ist, ist auch reflexiv. Die Relation {(a,a), (a,b), (b,b)} wäre beispielsweise auch reflexiv.

[Deynorus]

Erstmal vielen Dank für Eure Mühe.
Wäre es vllt möglich, dass mir jemand aufschreibt, was alle möglichen Relation auf der Menge A={a,b} sind, welche davon reflexiv, symmetrisch und wenn wir schon dabei sind auch transitiv sind? Ich habe da ein klares Verständnisproblem. Vllt würde mir das helfen.
Ich will euch zwar nicht überstrapazieren, aber ein kurzer Satz zur leeren Menge als mögliche Relation würde mir ebenfalls ungemein weiterhelfen.

lG.

PS: Als ich vom Paar (a,a) schrieb, meinte ich natürlich eigentlich die Menge oder Relation {(a,a)}. Mir fehlt da noch etwas die Praxis vom Formulieren mathematischer Strukturen.

[Blubbler]

Wäre es vllt möglich, dass mir jemand aufschreibt, was alle möglichen Relation auf der Menge A={a,b} sind, welche davon reflexiv, symmetrisch und wenn wir schon dabei sind auch transitiv sind? Ich habe da ein klares Verständnisproblem. Vllt würde mir das helfen.

Mit deinen a,b,c,d von oben. (a,a)=a; (a,b) = b; (b,a)= c; (b,b)= d
alle Relationen: {}, {a}, {b}, {c}, {d}, {a,a}, {a,b} usw. Da sollten 20 (1 0-elementige, 4 1-elementige, 12 2-elementige, 4 3-elementige, 1 4-elementige) insgesamt sein.
reflexiv: {a,d}, {a,d,b}, {a,d,c}, {a,d,b,c}
symmetrisch: {}, {a}, {d}, {a, d}, {b,c}, {a,d,b,c}, {a,b,c}, {d,b,c}
transitiv: alle bis auf {a,b,c}, {b,c,d} und {b,c}

Ich will euch zwar nicht überstrapazieren, aber ein kurzer Satz zur leeren Menge als mögliche Relation würde mir ebenfalls ungemein weiterhelfen.

Ich kenne die Definitionen, mit denen du arbeiten musst, nicht, aber die Wikipedia-Definition der Symmetrie ist z.B.:
Sei M eine Menge. Sei R eine Relation auf M.
R ist symmetrisch. :<=> Für alle x,y€M gilt: (x,y)€R => (y,x)€R
Setzt du hier die leere Menge für R ein, ist die Aussage (x,y)€{} immer falsch und die Implikation somit immer wahr (aus Falschem folgt beliebiges). {} ist also symmetrisch.
Auch alle Aussagen der Form
Für alle x€M gilt: A(x)
sind unabhängig von A wahr, wenn M die leere Menge ist.


Etwas, das mir bei Relationen Schwierigkeiten bereitete war, dass der Name gleichzeitig für zwei Sachen verwendet wurde:
- die Teilmengen eines Cartesischen Produktes (und nur hier ist es auch richtig)
- Aussagen wie (x,y)€R bzw. anders geschrieben xRy
Am besten unterscheidest du die beiden Sachen immer streng.

[Der Metzger]

Mit deinen a,b,c,d von oben. (a,a)=a; (a,b) = b; (b,a)= c; (b,b)= d
alle Relationen: {}, {a}, {b}, {c}, {d}, {a,a}, {a,b} usw. Da sollten 20 (1 0-elementige, 4 1-elementige, 12 2-elementige, 4 3-elementige, 1 4-elementige) insgesamt sein.

Es sind 16. 1 mit 0 Elementen, 4 mit 1 Element, 6 mit 2 Elementen, 4 mit 3 Elementen und 1 mit 4 Elementen.

[Thoronador]

Da sollten 20 (1 0-elementige, 4 1-elementige, 12 2-elementige, 4 3-elementige, 1 4-elementige) insgesamt sein.

Falsch.

Es sind 16.

Richtig.

Die Menge aller zweistelligen Relationen auf A={a,b} ist die Menge aller Teilmengen von A x A ={(a,a), (a,b), (b,a), (b,b)}, die leere Menge eingeschlossen. (Allerdings wäre das dann eine sehr langweilige Relation.)

Nebenbemerkung: Die Menge aller Teilmengen einer Menge M ist die sogenannte Potenzmenge P(M). Für endliche Mengen M gilt, dass |P(M)|=2^|M|. Dabei bezeichnet |M| die Mächtigkeit oder Kardinalität der Menge M. Für endliche Mengen ist die Kardinalität die Anzahl der Elemente in der Menge. |AxA| = |{(a,a), (a,b), (b,a), (b,b)}| = 4, womit sich |P(AxA)|=2^|AxA|=2⁴=16 ergibt. Damit ist 16 die Anzahl der möglichen zweistelligen Relationen auf A.

Wäre es vllt möglich, dass mir jemand aufschreibt, was alle möglichen Relation auf der Menge A={a,b} sind, welche davon reflexiv, symmetrisch und wenn wir schon dabei sind auch transitiv sind? Ich habe da ein klares Verständnisproblem. Vllt würde mir das helfen.

Mögliche Relationen auf A=(a,b) sind:
{},
{(a,a)}, {(a,b)}, {(b,a)}, {(b,b)},
{(a,a), (a,b)}, {(a,a), (b,a)}, {(a,a), (b,b)}, {(a,b), (b,a)}, {(a,b), (b,b)}, {(a,b), (b,b)}
{(a,a), (a,b), (b,a)}, {(a,a), (a,b), (b,b)}, {(a,a), (b,a), (b,b)}, {(a,b), (b,a), (b,b)},
{(a,a), (a,b), (b,a), (b,b)}

Davon sind reflexiv:
{(a,a), (b,b)}, {(a,a), (a,b), (b,b)}, {(a,a), (b,a), (b,b)}, {(a,a), (a,b), (b,a), (b,b)}

Symmetrisch sind:
{}, {(a,a)}, {(b,b)}, {(a,a), (b,b)}, {(a,b), (b,a)}, {(a,a), (a,b), (b,a)}, {(a,b), (b,a), (b,b)}, {(a,a), (a,b), (b,a), (b,b)}

Transitiv sind alle Relationen R, bei denen für alle x,y,z aus M gilt, dass aus xRy und yRz auch xRz folgt. Oder anders gesagt: wenn (x,y) und (y,z) Teil der Relation sind, muss auch (x,z) Teil der Relation sein.
Das im Einzelnen für jede der Relationen zu überprüfen, ist mir aber zu viel.


Dann noch eine Sache:

Um das zu verdeutlichen ersetze ich die obigen Paare durch Buchstaben:
(a,a)=a; (a,b) = b; (b,a)= c; (b,b)= d.

Sowas hilft vielleicht, wenn man wenig(er) schreiben will, aber zur Verdeutlichung ist es eher ungeeignet, weil man dann immer erst nachsehen muss, wofür a, b, c und d im Einzelnen stehen. Außerdem ist a für (a,a) und b für (a,b) ungünstig gewählt, weil man so auf den ersten Blick nicht weiß, welches a bzw. b gemeint sein soll, wenn irgendwo a oder b auftaucht, was schnell mal zu Fehlern führen kann. Letztlich erschwert diese verkürzte Schreibweise also den Umgang mit Relationen und hilft auch nicht gerade dabei, die Sache übersichtlich zu halten. Deshalb rate ich dir von dieser "a,b,c,d-Schreibweise" auch ab - verursacht nur unnötig Kopfschmerzen, die den eingesparten Schreibaufwand nicht rechtfertigen.

[ojas]

..., die leere Menge eingeschlossen. (Allerdings wäre das dann eine sehr langweilige Relation.)

Findest du? Dabei ist sie die einzige Relation, die sowohl symmetrisch als auch antisymmetrisch ist.

[Deynorus]

Erst einmal vielen Dank für die tolle Hilfe, das hat wirklich weiter geholfen.

Die Bestimmung der Anzahl der möglichen Relationen ist mir jetzt klar, ich bilde erst alle möglichen Tupel einer Menge (z.B. M) und kann dann mit der Potenzmenge (2^n) wobei "n" die Mächtigkeit (oder wie auch immer man das nennen mag, gemeint ist die Anzahl der Elemente) des Kartesischen Produktes ist, die Anzahl der möglichen Relationen bestimmen.

Aber schon bei einer Menge M mit 3 oder mehr Elementen komme ich mit Aufschreiben und zählen nicht mehr sehr weit, da es ja 512 mögliche Relationen gibt.
Gibt es eine Formel, mit der ich die Anzahl der reflexiven, bzw. symmetrischen Relationen auf einer Menge M bestimmen kann?

Edit: Zum Thema des Ersetzens der Tupel durch andere Buchstaben muss ich sagen, dass mir diese Problematik ziemlich schnell selbst aufgefallen ist, als ich wiederum auf den Beitrag antwortete. War nur so ne Überlegung, die sich als nicht allzu alltagstauglich herausstellte.

[Der Metzger]

Da muss man kombinatorisch rechnen. Es sei n = |A|. Dann sind die reflexiven Relationen genau diejenigen Ralationen, die alle Paare der Form (a, a) enthalten. Davon gibt es 2^(n^2 - n) Stück.


Dass diese Formel gilt, kann man sich anhand einer einfachen Codierung klarmachen. Jedes Element von A bekommt eine Nummer von 1 bis n. In einer n x n Matrix schreiben wir dann and er Stelle (i, j) eine 1, wenn (i, j) in der Relation enthalten ist [und sonst 0]. Nun müssen die n Elemente auf der Diagonalen 1 sein, die restlichen n^2 - n sind frei wählbar. Dafür gibt es genau 2^(n^2 - n) Möglichkeiten.

Bei den symmetrischen Relationen geht man ähnlich vor, hier muss die Matrix symmetrisch sein. Überleg dir mal, wie viele Möglichkeiten es da gibt.

[Blubbler]

Ja, bei der Gesamtanzahl der Relationen habe ich mich vertan.

kann dann mit der Potenzmenge (2^n) wobei "n" die Mächtigkeit (oder wie auch immer man das nennen mag, gemeint ist die Anzahl der Elemente) des Kartesischen Produktes ist, die Anzahl der möglichen Relationen bestimmen.

Das musst du erstmal beweisen.

[Thoronador]

Das musst du erstmal beweisen.

Komisch, bei meiner "Nebenbemerkung" weiter oben hast du das nicht gefordert, weil die ja genau darauf hinausläuft:

Nebenbemerkung: Die Menge aller Teilmengen einer Menge M ist die sogenannte Potenzmenge P(M). Für endliche Mengen M gilt, dass |P(M)|=2^|M|. Dabei bezeichnet |M| die Mächtigkeit oder Kardinalität der Menge M. Für endliche Mengen ist die Kardinalität die Anzahl der Elemente in der Menge. |AxA| = |{(a,a), (a,b), (b,a), (b,b)}| = 4, womit sich |P(AxA)|=2^|AxA|=2⁴=16 ergibt. Damit ist 16 die Anzahl der möglichen zweistelligen Relationen auf A.

Sobald man sich darüber im Klaren ist, dass die Menge aller Teilmengen (=Potenzmenge) von A⨯A die Menge aller möglichen zweistelligen Relationen auf A ist (und das ist eigentlich recht offensichtlich), ist der Weg über die Potenzmenge A⨯A von eigentlich auch direkt ersichtlich. Das einzige, was also noch zu beweisen wäre, wäre die Gültigkeit der Gleichung |P(M)|=2^|M| für alle endlichen Mengen M. Mittels vollständiger Induktion lässt sich das aber schnell beweisen.

Für eine einelementige Menge M={m} gilt diese Beziehung offenbar, denn die Potenzmenge davon ist die Menge, welche die leere Menge und M selbst enthält: P(M)={{}, {m}}. Es gilt also |M|=1, |P(M)|=2 und damit 2=|P(M)|=2^|M|=2¹. Damit hätte man den Induktionsanfang.

Der Induktionsschritt läuft so ab, dass man der n-elementigen Menge M_n ein weiteres Element hinzufügt und damit die (n+1)-elementigen Menge M_n+1 erhält. Offensichtlich sind alle Teilmengen von M_n auch Teilmengen von M_n+1. Jetzt hat man durch das zusätzliche Element in M_n+1 aber nochmal die Möglichkeit, zu allen Teilmengen von M_n auch noch das neue Element aus M_n+1 hinzuzufügen. Dies sind dann ebenfalls Teilmengen von M_n+1, die Anzahl dieser Teilmengen mit dem neuen Element ist ebenso groß wie die Anzahl der Teilmengen von M_n. Damit hat man also für M_n+1 doppelt so viele Teilmengen wie für M_n. Oder als Gleichung ausgedrückt:
|P(M_n+1)|=2*2^|M_n|=2^|M_n|+1=2^|M_n+1|
Sprich: |P(M_n+1)|=2^|M_n+1|
Dass es nicht noch weitere Teilmengen von M_n+1 gibt, ist auch klar, denn zu deren Konstruktion müsste man noch weitere Elemente aus M_n+1 haben, aber die sind ja alle schon in Benutzung.

Damit ist also die Aussage |P(M)|=2^|M| für endliche Mengen M bewiesen.
(Beim Induktionsanfang könnte man ebenso mit der leeren Menge beginnen: P({})={{}}, d.h. die Menge, welche die leere Menge enthält. Deren Kardinalität ist 1, die Kardinalität der leeren Menge ist 0, und damit gilt 1=|P({})|=2^|{}|=2⁰.)

[Blubbler]

Komisch, bei meiner "Nebenbemerkung" weiter oben hast du das nicht gefordert, weil die ja genau darauf hinausläuft:

Ich meine nur, dass man es nicht unbewiesen auf eine Übungsabgabe oder Ähnliches schreiben soll.