Anzahl der Relationen

Neue Frage »

21.04.2009, 20:05	Duedi	Auf diesen Beitrag antworten »
Anzahl der Relationen Sei A eine Menge mit 4 Elementen. Bestimmen Sie die Anzahl a) aller Relationen auf A b) aller reflexiven Relationen auf A ... ... Irre ich mich oder ist das wirklich so knifflig wie ich denke? Ich habe jedenfalls für a) die Anzahl $\begin{eqnarray} 2^{16} \end{eqnarray}$ heraus. Stimmt das?
21.04.2009, 20:41	Duedi	Auf diesen Beitrag antworten »
(Sry für den Doppelpost, aber editieren nach so langer Zeit ist wahrscheinlich nicht so ideal) Gehe nur kurz darauf ein, wie ich vorgegangen bin. Es sei R eine Relation (ganz allgemein), also dementsprechend {R} die Menge aller Relationen (nicht bloß die Menge über eine spezielle Relation, ich kenne kein passenderes Zeichen). $\begin{eqnarray} R \subset A \times A\\ \{R\}=\mathcal P(A\times A)\\ \|\{R\}\| = \|\mathcal P(A\times A)\|=2^{\|A\times A\|}=2^{4^2}=2^{16} \end{eqnarray}$ Stimmt das so? Wenn ja, kann ich mich nämlich an die Spezialfälle machen
21.04.2009, 20:53	Felix	Auf diesen Beitrag antworten »
Ja, das dürfte stimmen.
21.04.2009, 20:55	Duedi	Auf diesen Beitrag antworten »
Yeah, ich melde mich, wenn ich was Neues weiß
21.04.2009, 21:00	Felix	Auf diesen Beitrag antworten »
Hast du schon eine Idee wie du b) machst ?
21.04.2009, 21:20	Duedi	Auf diesen Beitrag antworten »
jetzt also die b): Anzahl aller reflexiven Relationen auf A Ich bezeichne mit $\begin{eqnarray} R_r \end{eqnarray}$ die reflexiven Relationen, geschweift umklammert bedeutet es wieder die Menge aller dieser refl. Rel. Wenn $\begin{eqnarray} A=\{1,2,3,4\} \end{eqnarray}$ , so lässt sich jede reflexive Relation folgendermaßen genauer definieren: $\begin{eqnarray} &&R_r = \{(1,1),(2,2),(3,3),(4,4)\} \cup M~\text{, wobei}\\&&M\subset M' = \{(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)\}\subset A\times A \end{eqnarray}$ Mein Gedanke hierzu ist, dass jede reflexive Relation ein "Grundgerüst" der 4 Tupel besitzt und nur noch eine beliebige Kombination der Anderen Tupel dazukommt. Nächster Schritt: Allgemeiner darstellen: $\begin{eqnarray} &&\{R_r\} = \{\{(1,1),(2,2),(3,3),(4,4)\} \cup M\} \end{eqnarray}$ Anzahl berechnen: $\begin{eqnarray} &&\|\{R_r\}\| = \|\mathcal P(M)\|=2^{16-4}=2^{12} \end{eqnarray}$ Passt das?
Anzeige

21.04.2009, 21:52	Felix	Auf diesen Beitrag antworten »
Nein. Ich würde ab deiner Stelle die Anzahl der nichtreflexiven Relationen betrachten.
21.04.2009, 22:05	Duedi	Auf diesen Beitrag antworten »
Die nichtreflexiven Relationen besitzen in ihrer Mengenschreibweise mindestens ein Tupel der Form $\begin{eqnarray} (k,k) \end{eqnarray}$ nicht. Dieses "mindestens" finde ich schwer zu fassen.
21.04.2009, 22:16	Felix(Gast)	Auf diesen Beitrag antworten »
Du hattest recht. Mir ist da ein Denkfehler unterlaufen. Entschuldige Bitte ...
21.04.2009, 22:17	Duedi	Auf diesen Beitrag antworten »
Ist doch kein Problem . Ist mein Ergebnis ( $\begin{eqnarray} 2^{12} \end{eqnarray}$ ) richtig?
22.04.2009, 00:06	Felix	Auf diesen Beitrag antworten »
Ja. Allerdings ist die Formulierung mit dem Grundgerüst vielleicht etwas ungeschickt, da es auch Äquivalenzrelationen gibt, die nicht alle 4 genannten Paare besitzen.
22.04.2009, 09:46	Felix	Auf diesen Beitrag antworten »
Ich muss mich, fürchte ich ein weiteres Mal korrigieren Du hast nämlich nur jene reflexiven Relationen gezählt, die alle Paare $\begin{eqnarray} (k,k) \end{eqnarray}$ enthalten. Du musst jetzt auch noch diese Relationen mitzählen die nur Teilmengen von $\begin{eqnarray} \{(1,1),(2,2),(3,3),(4,4)\} \end{eqnarray}$ enthalten. lg
22.04.2009, 12:54	Duedi	Auf diesen Beitrag antworten »
Ist es dann überhaupt noch eine reflexive Relation? Denn: $\begin{eqnarray} \text{R reflexiv} \Leftrightarrow \forall a\in A: ~~ aRa \end{eqnarray}$ (Meine vor allem das "für alle")
22.04.2009, 13:08	Felix	Auf diesen Beitrag antworten »
Du hast Recht. Langsam wird das peinlich Da habe ich die Definition schlampig gelesen ...
22.04.2009, 13:17	Duedi	Auf diesen Beitrag antworten »
mach dir keinen Kopf, du hast mir trotzdem geholfen

Neue Frage »

Antworten »

Anzahl der Relationen

Verwandte Themen