Wieviele Relationen gibt es < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Wieviele Relationen gibt es in einer endlichen menge S?
a) Wieviele reflexive Relationen
b) wieviele symmetrische Relationen
c) wieviele reflexive und symmetrische Relationen
d) wieviele relationen |
Hallo,
also ich habe ein Problem mit der Anzahl der Relationen für eine Menge.
Nun ich weiß, dass es nach dem Prinzip von Inklusion und Exklusion immer die Möglichkeit "in" der Menge der Relationen oder "nicht in" der Menge der Relationen gibt, also ist die Anzahl immer 2^{blubb}.
Ich habe hier auch die antworten. für reflexive Relationen heißt es dort zum Beipsiel (vorausgesetzt mal stellt sich das kartesische Produkt SxS also Quadrat vor):
Anzahl der Teilmengen die die Diagonale enthalten mit $ \Delta s:={(s,s):s \in S $ Daraus ergibt sich dann für die menge der reflexiven Relationen 2^{|SxS|- \Delta s}=2^{|S|^2-|S|} .
Kann jemand ein wenig Licht in mein Dunkel bringen ? Ich weiß z.B. nicht wieso, diese Anz. nun die Diagonale enthält, wenn ich |S| abziehe, dann ist die diagonale doch nicht enthalten, oder ?
Lg,
exeqter
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:18 Mo 11.01.2010 | | Autor: | MontBlanc |
Hi,
also ich hätte noch Interesse an einer Antwort, falls jemand doch noch eine Idee hat, wie es gehen könnte.
lg,
exe
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:29 Mo 11.01.2010 | | Autor: | tobit09 |
Hallo exeqter,
die Antworten scheinen in der Tat nur Antworten und keine begründeten Lösungen zu sein. Übel...
> Nun ich weiß, dass es nach dem Prinzip von Inklusion und
> Exklusion immer die Möglichkeit "in" der Menge der
> Relationen oder "nicht in" der Menge der Relationen gibt,
> also ist die Anzahl immer [mm]2^{blubb}.[/mm]
Das verstehe ich nicht so richtig. Eine sinnvolle Möglichkeit, hier das ![[]](/images/popup.gif) Prinzip von Inklusion und Exklusion anzuwenden, sehe ich nicht. Das [mm] $2^n$ [/mm] hat einen anderen Ursprung: Wenn $M$ eine n-elementige [mm] ($n\in\IN$) [/mm] Menge ist, so hat $M$ genau [mm] $2^n$ [/mm] Teilmengen (jedes der $n$ Elemente von $M$ kann in einer Teilmenge von M enthalten sein oder nicht).
Fangen wir mal mit d) an, die dürfte am einfachsten sein. Die Relationen auf S sind ja gerade die Teilmengen von [mm] $S\times [/mm] S$. Wie viele Elemente hat [mm] $S\times [/mm] S$? [mm] $|S|\cdot|S|=|S|^2$ [/mm] viele ($|S|$ Möglichkeiten für die erste Komponente, $|S|$ Möglichkeiten für die zweite Komponente). Also hat [mm] $S\times [/mm] S$ genau [mm] $2^{|S|^2}$ [/mm] Teilmengen. [mm] $2^{|S|^2}$ [/mm] ist also die gesuchte Anzahl der Relationen auf $S$.
Zu a): Die reflexiven Relationen sind gerade die Teilmengen von [mm] $S\times [/mm] S$, die die Diagonale [mm] $\Delta [/mm] S$ umfassen. Diese Teilmengen entsprechen eins zu eins allen Teilmengen von [mm] $M:=(S\times S)\setminus \Delta [/mm] S$. (Um von einer Teilmenge von [mm] $S\times [/mm] S$, die die Diagonale umfasst, zu einer Teilmenge von $M$ zu gelangen, streiche man einfach alle Elemente der Diagonalen. Um umgekehrt von einer Teilmenge von $M$ zu einer Teilmenge von [mm] $S\times [/mm] S$, die die Diagonale umfasst, zu gelangen, füge man alle Elemente der Diagonalen hinzu.) $M$ hat [mm] $|S\times S|-|\Delta S|=|S|^2-|S|$ [/mm] viele Elemente. Somit ist die Anzahl aller Teilmengen von $M$ gerade [mm] $2^{|S|^2-|S|}$. [/mm] Dies ist die gesuchte Anzahl der reflexiven Relationen auf $S$.
Zur b): Hier nummerieren wir uns am besten die Elemente von $S$ durch: Sei also [mm] $S=\{s_1,\ldots,s_n\}$ [/mm] mit [mm] $s_1,\ldots,s_n$ [/mm] paarweise verschieden. Eine Möglichkeit, die symmetrischen Relationen zu charakterisieren: Das sind die Teilmengen $R$ von [mm] $S\times [/mm] S$ mit [mm] $(s_j,s_i)\in R\gdw (s_i,s_j)\in [/mm] R$ für alle [mm] $i,j\in \{1,\ldots,n\}$ [/mm] mit $i<j$. Diese entsprechen eins zu eins den allen Teilmengen von [mm] $M:=\{(s_i,s_j)\; | \; i,j\in \{1,\ldots,n\} \mbox{ mit } i\le j\}$. [/mm] (Um von einer symmetrischen Relation zu einer Teilmenge von $M$ zu gelangen, streiche man alle Elemente [mm] $(s_j,s_i)$ [/mm] mit $i<j$ heraus. Um umgekehrt von einer Teilmenge von $M$ zu einer symmetrischen Relation zu gelangen, füge man zu jedem [mm] $(s_i,s_j)$ [/mm] in der Teilmenge das Paar [mm] $(s_j,s_i)$ [/mm] hinzu.) $M$ hat [mm] $n+(n-1)\ldots+1=\bruch{n(n+1)}{2}$ [/mm] viele Elemente ($n$ Paare mit [mm] $s_1$ [/mm] in der ersten Komponente, $n-1$ Paare mit [mm] $s_2$ [/mm] in der ersten Komponente,..., $1$ Paar mit [mm] $s_n$ [/mm] in der ersten Komponente). Also hat M genau [mm] $2^{\bruch{n(n+1)}{2}}$ [/mm] Teilmengen. Die gesuchte Anzahl der symmetrischen Relationen auf $S$ ist also [mm] $2^{\bruch{|S|(|S|+1)}{2}}$.
[/mm]
Die c) überlasse ich dir. 
Ist die Aufgabe damit etwas klarer geworden? Sonst bitte nachfragen!
Viele Grüße
Tobias
|
|
|
| |
|
Hi tobi,
danke, dass Du Dir Zeit genommen hast und eine so ausführliche Antwort erstellt hast.
Dann will ich mal meine Fragen loswerden:
> Hallo exeqter,
>
> die Antworten scheinen in der Tat nur Antworten und keine
> begründeten Lösungen zu sein. Übel...
>
> > Nun ich weiß, dass es nach dem Prinzip von Inklusion und
> > Exklusion immer die Möglichkeit "in" der Menge der
> > Relationen oder "nicht in" der Menge der Relationen gibt,
> > also ist die Anzahl immer [mm]2^{blubb}.[/mm]
> Das verstehe ich nicht so richtig. Eine sinnvolle
> Möglichkeit, hier das
> Prinzip von Inklusion und Exklusion
> anzuwenden, sehe ich nicht. Das [mm]2^n[/mm] hat einen anderen
> Ursprung: Wenn [mm]M[/mm] eine n-elementige ([mm]n\in\IN[/mm]) Menge ist, so
> hat [mm]M[/mm] genau [mm]2^n[/mm] Teilmengen (jedes der [mm]n[/mm] Elemente von [mm]M[/mm] kann
> in einer Teilmenge von M enthalten sein oder nicht).
>
> Fangen wir mal mit d) an, die dürfte am einfachsten sein.
> Die Relationen auf S sind ja gerade die Teilmengen von
> [mm]S\times S[/mm]. Wie viele Elemente hat [mm]S\times S[/mm]?
> [mm]|S|\cdot|S|=|S|^2[/mm] viele ([mm]|S|[/mm] Möglichkeiten für die erste
> Komponente, [mm]|S|[/mm] Möglichkeiten für die zweite Komponente).
> Also hat [mm]S\times S[/mm] genau [mm]2^{|S|^2}[/mm] Teilmengen. [mm]2^{|S|^2}[/mm]
> ist also die gesuchte Anzahl der Relationen auf [mm]S[/mm].
Okay, das habe ich verstanden!
> Zu a): Die reflexiven Relationen sind gerade die Teilmengen
> von [mm]S\times S[/mm], die die Diagonale [mm]\Delta S[/mm] umfassen.
Das bedeutet, ich habe die Auswahl für [mm] x_i [/mm] aber mein zugehöriges [mm] y_i [/mm] ist ja wieder [mm] x_i [/mm] weil es sich um eine reflexice relation handelt, wobei [mm] x_i [/mm] und [mm] y_i [/mm] beide in S sind und $ [mm] (x_i [/mm] , [mm] y_i)\in S\times [/mm] S $
>Diese
> Teilmengen entsprechen eins zu eins allen Teilmengen von
> [mm]M:=(S\times S)\setminus \Delta S[/mm]. (Um von einer Teilmenge
> von [mm]S\times S[/mm], die die Diagonale umfasst, zu einer
> Teilmenge von [mm]M[/mm] zu gelangen, streiche man einfach alle
> Elemente der Diagonalen.
Das verstehe ich nicht ganz... Von einer Teilmenge die die Diagonale enthält zu einer Teilmenge zu kommen. Über was für eine Teilmenge sprechen wir ?
> Um umgekehrt von einer Teilmenge
> von [mm]M[/mm] zu einer Teilmenge von [mm]S\times S[/mm], die die Diagonale
> umfasst, zu gelangen, füge man alle Elemente der
> Diagonalen hinzu.)
Okay logisch, aber s.o.
> [mm]M[/mm] hat [mm]|S\times S|-|\Delta S|=|S|^2-|S|[/mm]
> viele Elemente. Somit ist die Anzahl aller Teilmengen von [mm]M[/mm]
> gerade [mm]2^{|S|^2-|S|}[/mm]. Dies ist die gesuchte Anzahl der
> reflexiven Relationen auf [mm]S[/mm].
Aber ich denke die Diagonale ist enhalten, warum zieht man sie dann ab ?
>
> Zur b): Hier nummerieren wir uns am besten die Elemente von
> [mm]S[/mm] durch: Sei also [mm]S=\{s_1,\ldots,s_n\}[/mm] mit [mm]s_1,\ldots,s_n[/mm]
> paarweise verschieden. Eine Möglichkeit, die symmetrischen
> Relationen zu charakterisieren: Das sind die Teilmengen [mm]R[/mm]
> von [mm]S\times S[/mm] mit [mm](s_j,s_i)\in R\gdw (s_i,s_j)\in R[/mm] für
> alle [mm]i,j\in \{1,\ldots,n\}[/mm] mit [mm]i
Mhh... warum $ i<j $ ?
> Diese entsprechen eins
> zu eins den allen Teilmengen von [mm]M:=\{(s_i,s_j)\; | \; i,j\in \{1,\ldots,n\} \mbox{ mit } i\le j\}[/mm].
> (Um von einer symmetrischen Relation zu einer Teilmenge von
> [mm]M[/mm] zu gelangen, streiche man alle Elemente [mm](s_j,s_i)[/mm] mit [mm]i
> heraus.
Das wäre quasi das Gegenteil von dem, was wir hier machen wollen ?
> Um umgekehrt von einer Teilmenge von [mm]M[/mm] zu einer
> symmetrischen Relation zu gelangen, füge man zu jedem
> [mm](s_i,s_j)[/mm] in der Teilmenge das Paar [mm](s_j,s_i)[/mm] hinzu.) [mm]M[/mm] hat
> [mm]n+(n-1)\ldots+1=\bruch{n(n+1)}{2}[/mm] viele Elemente ([mm]n[/mm] Paare
> mit [mm]s_1[/mm] in der ersten Komponente, [mm]n-1[/mm] Paare mit [mm]s_2[/mm] in der
> ersten Komponente,..., [mm]1[/mm] Paar mit [mm]s_n[/mm] in der ersten
> Komponente).
Warum n paare mit [mm] s_1 [/mm] , (n-1) mit [mm] s_2 [/mm] usw. Da komm ich noch nicht ganz dahinter.
> Also hat M genau [mm]2^{\bruch{n(n+1)}{2}}[/mm]
> Teilmengen. Die gesuchte Anzahl der symmetrischen
> Relationen auf [mm]S[/mm] ist also [mm]2^{\bruch{|S|(|S|+1)}{2}}[/mm].
Das ist mir dann klar, wenn man erstmal die anderen Schritte begriffen hätte.
> Die c) überlasse ich dir.
Da mache ich mich dann auch sofort morgen früh ran !
>
> Ist die Aufgabe damit etwas klarer geworden? Sonst bitte
> nachfragen!
Schon viel besser, nochmals vielen Dank für die ausführliche und sehr hilfreiche Antwort !
> Viele Grüße
> Tobias
Gute Nacht und liebe Grüße,
exeqter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:52 Di 12.01.2010 | | Autor: | tobit09 |
Hallo nochmal,
Danke auch dir für die ausführliche Reaktion! So macht das Fragen Beantworten am meisten Spaß!
> > Zu a): Die reflexiven Relationen sind gerade die Teilmengen
> > von [mm]S\times S[/mm], die die Diagonale [mm]\Delta S[/mm] umfassen.
>
> Das bedeutet, ich habe die Auswahl für [mm]x_i[/mm] aber mein
> zugehöriges [mm]y_i[/mm] ist ja wieder [mm]x_i[/mm] weil es sich um eine
> reflexice relation handelt, wobei [mm]x_i[/mm] und [mm]y_i[/mm] beide in S
> sind und [mm](x_i , y_i)\in S\times S[/mm]
Wenn du mit dieser Beschreibung die Diagonale meintest, kann ich herauslesen, was du meintest. Falls du damit reflexive Relationen beschreiben wolltest, scheinst du den Begriff reflexiv missverstanden zu haben: Eine Relation $R$ auf $S$ heißt reflexiv, wenn für alle [mm] $s\in [/mm] S$ gilt [mm] $(s,s)\in [/mm] R$. Die Reflexivität bedeutet NICHT, dass alle Elemente von R die Gestalt $(s,s)$ haben.
Zu a): Ich schreibe zum einen meine Lösung nochmal formaler auf. Zum anderen gebe ich noch eine weitere weniger formale Lösung. Vielleicht klärt das die offenen Fragen.
Sei [mm] $A:=\{R\subset S\times S\;|\; R\supset\Delta S\}$ [/mm] die Menge der Relationen auf $S$, die die Diagonale umfassen, also die Menge der reflexiven Relationen auf $S$. Gesucht ist die Anzahl der Elemente von $A$. Sei [mm] $B:=\{R\subset S\times S;|\; R\cap\Delta S=\emptyset\}$ [/mm] die Menge aller Relationen auf $S$, die KEIN Element der Diagonale enthalten.
Wir zeigen nun zwei Dinge:
1. Es gibt eine Bijektion zwischen $A$ und $B$ (also stimmen die Anzahlen der Elemente von $A$ bzw. $B$ überein).
2. $B$ enthält genau [mm] $2^{|S|^2-|S|}$ [/mm] Elemente.
Also enthält auch $A$ genau [mm] $2^{|S|^2-|S|}$ [/mm] Elemente (und diese Anzahl war gesucht).
Der entscheidende Trick besteht also darin, dass man, anstatt direkt die Anzahl der Relationen zu zählen, die die Diagonale enthalten ($|A|$), die Anzahl der Relationen ermittelt, die KEIN Element der Diagonalen enthalten ($|B|$). Das ist leichter, weil wir dann ALLE Teilmengen einer gewissen Menge $M$ zu zählen haben, wie aus dem Beweis von 2. hervorgeht.
Zu 1.: [mm] $\varphi:A\to [/mm] B, [mm] R\mapsto R\setminus \Delta [/mm] S$ (Streichen aller Elemente der Diagonalen) und [mm] $\psi:B\to [/mm] A, [mm] R\mapsto R\cup\Delta [/mm] S$ (Hinzufügen aller Elemente der Diagonalen) bilden zueinander inverse Bijektionen.
Zu 2.: Es gilt [mm] $B=\{R\subset M\}$ [/mm] mit [mm] $M:=(S\times S)\setminus\Delta [/mm] S$. Da die Anzahl der Elemente von $M$ gerade [mm] $|S\times S|-|\Delta S|=|S|^2-|S|$ [/mm] ist, folgt, dass die Anzahl der Elemente von $B$ genau [mm] $2^{|S|^2-|S|}$ [/mm] ist.
Falls du es lieber anschaulich und weniger formal magst: Um zu einer reflexiven Relation $R$ auf $S$ zu gelangen, kann man für jedes Element $(s,t)$ mit [mm] $s,t\in [/mm] S$, [mm] $s\not= [/mm] t$ frei entscheiden, ob es zu $R$ gehören soll oder nicht (für die Elemente [mm] $(s,s)\in\Delta [/mm] S$ hat man dagegen keine Wahl: Sie müssen zu $R$ gehören, damit $R$ reflexiv wird). Dies gibt [mm] $2^m$ [/mm] mögliche Wahlen, wenn $m$ die Anzahl der Paare $(s,t)$ mit [mm] $s,t\in [/mm] S$, [mm] $s\not= [/mm] t$ ist. Es gilt [mm] $m=|S|\cdot|S|-|\Delta S|=|S|^2-|S|$.
[/mm]
> > Zur b): Hier nummerieren wir uns am besten die Elemente von
> > [mm]S[/mm] durch: Sei also [mm]S=\{s_1,\ldots,s_n\}[/mm] mit [mm]s_1,\ldots,s_n[/mm]
> > paarweise verschieden. Eine Möglichkeit, die symmetrischen
> > Relationen zu charakterisieren: Das sind die Teilmengen [mm]R[/mm]
> > von [mm]S\times S[/mm] mit [mm](s_j,s_i)\in R\gdw (s_i,s_j)\in R[/mm] für
> > alle [mm]i,j\in \{1,\ldots,n\}[/mm] mit [mm]i
>
> Mhh... warum [mm]i
Nach Definition von $R$ symmetrisch muss zunächst mal [mm](s_j,s_i)\in R\gdw (s_i,s_j)\in R[/mm] für alle [mm]i,j\in \{1,\ldots,n\}[/mm] gelten. Es genügt jedoch, dies nur für $i<j$ zu fordern: Für $i=j$ ist [mm](s_j,s_i)\in R\gdw (s_i,s_j)\in R[/mm] trivial und für $i>j$ folgt [mm](s_j,s_i)\in R\gdw (s_i,s_j)\in R[/mm] unmittelbar aus [mm](s_i,s_j)\in R\gdw (s_j,s_i)\in R[/mm] (was wegen $j<i$ gegeben ist).
Zu b): Auch hier deute ich kurz an, wie man analog zu a) meinen Beweis formaler führen könnte. Dann gebe ich wieder einen weniger formalen Beweis.
Man definiert wieder eine Menge [mm] $A:=\{R\subset S\times S\;|\; (s_j,s_i)\in R\gdw (s_i,s_j)\in R\mbox{ für alle }i,j\in \{1,\ldots,n\}\mbox{ mit }i
Dann zeigt man:
1. Es gibt eine Bijektion zwischen $A$ und $B$.
2. Die Anzahl der Elemente von $B$ ist [mm] $2^\bruch{|S|*(|S|+1)}{2}$.
[/mm]
Beim Beweis von 2. taucht dann u.a. die dir noch unklare Stelle auf, dass $M$ gerade [mm] $n+(n-1)+\ldots+1$ [/mm] Elemente hat. Warum das? Listen wir mal die Elemente Menge $M$ auf:
[mm] $(s_1,s_1),(s_1,s_2),\ldots,(s_1,s_n)$ [/mm] ($n$ Elemente mit [mm] $s_1$ [/mm] in der ersten Komponente)
[mm] $(s_2,s_2),\ldots,(s_2,s_n)$ [/mm] ($n-1$ Elemente mit [mm] $s_2$ [/mm] in der ersten Komponente)
[mm] $\vdots$
[/mm]
[mm] $(s_n,s_n)$ [/mm] ($1$ Element mit [mm] $s_n$ [/mm] in der ersten Komponente)
Indem wir die Anzahlen der Elemente in den einzelnen Zeilen aufaddieren, erhalten wir die Gesamtzahl der Elemente von $M$.
Der weniger formale Beweis: Um zu einer symmetrischen Relation $R$ auf $S$ zu gelangen, kann man für Elemente [mm] $(s_i,s_j)$ [/mm] mit [mm] $i\le [/mm] j$ frei entscheiden, ob sie zu $R$ gehören sollen oder nicht. Ob die Elemente [mm] $(s_j,s_i)$ [/mm] mit $i<j$ zu $R$ gehören oder nicht, steht damit fest. Die Anzahl der symmetrischen Relationen auf $S$ ist somit [mm] $2^m$, [/mm] wenn $m$ die Anzahl der Paare [mm] $(s_i,s_j)$ [/mm] mit [mm] $i\le [/mm] j$ ist. Es gilt [mm] $m=n+(n-1)+\ldots+1$ [/mm] ($m$ ist gerade die Anzahl der Elemente von obiger Menge $M$), also ...
Ich wäre sehr daran interessiert, ob dir eher der formale oder eher der weniger formale Teil weiterhilft!
Viele Grüße
Tobias
EDIT: Die Frage sollte eigentlich als beantwortet markiert werden. Ich bin mir sicher, nichts an dieser Standardeinstellung verändert zu haben. Was mache ich falsch, dass von mir beantwortete Fragen neuerdings manchmal als unbeantwortet markiert bleiben?
EDIT: Danke exeqter für die Markierung als beantwortet. Ich glaube ich habe des Rätsels Lösung: In beiden Fällen, in denen von mir beantwortete Fragen als unbeantwortet markiert blieben, hatte ich die Bearbeitungszeit um mehr als 30 Minuten überschritten. Damit scheint das Problem zusammenzuhängen (und damit lösbar zu sein).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:00 Do 14.01.2010 | | Autor: | MontBlanc |
Hi tobi,
vielen Dank für die zweite, phänomenal ausführliche antwort. Ich bin dir wirklich sehr dankbar. Ich brauche nur etwas zeit mich dort durchzuschlagen und es wirklich zu durchdringen. Ich melde mich sobald ich da durch bin!!
Vielen Dank nochmal,
exeqter
|
|
|
| |
|
Hallo,
ich sitze gerade wieder vor demselben Problem und raffe es immer noch nicht. Damals dachte ich es verstanden zu haben, aber anscheinend nicht !
Um mal mit den reflexiven Relationen anzufangen:
Enthält die Menge der reflexiven Relationen nun die Diagonale oder nicht ? Mal wird sie abgezogen, mal hinzugefügt. Ich bin veriwrrt. Die Anzahl aller Relationen ist gegeben durch [mm] 2^{|S|^2} [/mm] . Wie kann ich mir jetzt von dort anschaulich klar machen, welche streichen muss und welche nicht ? Wir haben das mal in einem Diagramm gemacht, im Prinzip ein Qudrat mit S auf der y-Achse und S auf der x-Achse. Dann wurde die Diagonale eingezeichnet. Wo würden sich dort die relfexiven Relationen befinden ? Kann man das darüber machen ?
Lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:51 Do 20.05.2010 | | Autor: | tobit09 |
Hallo,
> Um mal mit den reflexiven Relationen anzufangen:
>
> Enthält die Menge der reflexiven Relationen nun die
> Diagonale oder nicht ?
Es geht bei dem "Enthalten der Diagonale" gar nicht um die Menge ALLER reflexiven Funktionen. Vielmehr enthält jede EINZELNE reflexive Relation die gesamte Diagonale [mm] $\Delta S=\{(s,s)|s\in S\}$ [/mm] als Teilmenge.
> Mal wird sie abgezogen, mal
> hinzugefügt. Ich bin veriwrrt.
Genaue Argumentationen findest du ja in meiner vorherigen Antwort. Wenn Unklarheiten bleiben, könnte es sinnvoll sein, dass du genauer schilderst, wo in dieser Antwort die Unklarheit ist. Ersteinmal probiere ich es mit einer weniger exakten Erläuterung der Idee an einem weniger abstrakten Beispiel:
Ein Tourist möchte sich entscheiden, welche von 10 für ihn in Frage kommenden Sehenswürdigkeiten er sich anschauen möchte. 3 dieser Sehenswürdigkeiten möchte er in jedem Fall besuchen, für die 7 anderen Sehenswürdigkeit hat er noch nicht entschieden, ob er sie besuchen möchte. Wie viele "Sehenswürdigkeiten-Auswahlen" sind für ihn denkbar?
Jede einzelne für den Touristen denkbare Sehenswürdigkeiten-Auswahl enthält die 3 für ihn feststehenden Sehenswürdigkeiten. Und gerade deshalb spielen sie für seine Entscheidung überhaupt keine Rolle! Er muss nur für jede der 7 übrigen Sehenswürdigkeiten entscheiden, ob er sie besucht. Die gesuchte Anzahl ist [mm] $2^7=2^{10-3}$. [/mm] Die Anzahl 3 der zu jeder einzelnen Auswahl stets dazugehörigen Sehenswürdigkeiten wird also sozusagen abgezogen!
Analog enthält jede reflexive Relation alle Elemente der Diagonalen. Und deshalb ist die Diagonale für das Abzählen genauso uninteressant wie die 3 ohnehin feststehenden Sehenswürdigkeiten des Touristen. Interessant sind dagegen die Entscheidungen pro oder kontra für jede der 7 übrigen Sehenswürdigkeiten bzw. die Entscheidungen pro oder kontra für jedes NICHT zur Diagonale gehörende Element von [mm] $S\times [/mm] S$.
> Die Anzahl aller Relationen
> ist gegeben durch [mm]2^{|S|^2}[/mm] .
> Wie kann ich mir jetzt von
> dort anschaulich klar machen, welche streichen muss und
> welche nicht ?
Im Sehenswürdigkeiten-Beispiel könntest du zunächst alle Auswahlen von gewissen der 10 Sehenswürdigkeiten betrachten und anschließend alle streichen, in denen mindestens eine der 3 feststehenden Sehenswürdigkeiten fehlt. Aber die Anzahl der zu streichenden Auswahlen ist zunächst schwieriger zu ermitteln als die eigentlich gesuchte Anzahl (bei der man ja die betreffenden 3 Sehenswürdigkeiten außer Acht lassen kann).
Um analog von allen Relationen zu den reflexiven Relationen zu gelangen, müsstest du alle Relationen streichen, in denen mindestens ein Element der Diagonale fehlt. Auch hier ist die Anzahl der zu streichenden Relationen zunächst schwieriger zu ermitteln als die eigentlich gesuchte Anzahl der reflexiven Relationen.
> Wir haben das mal in einem Diagramm gemacht,
> im Prinzip ein Qudrat mit S auf der y-Achse und S auf der
> x-Achse. Dann wurde die Diagonale eingezeichnet. Wo würden
> sich dort die relfexiven Relationen befinden ? Kann man das
> darüber machen ?
Auf diese Weise kann man sich eine EINZELNE Relation (nicht die Gesamtheit ALLER Relationen) über S veranschaulichen: Man markiert die Punkte im Quadrat, die Element der Relation seien sollen. Eine so veranschaulichte Relation ist genau dann reflexiv, wenn alle Punkte der Diagonalen markiert sind.
Viele Grüße
Tobias
P.S.: Dein Benutzername hat sich in der Zwischenzeit geändert? Wusste gar nicht, dass das möglich ist...
|
|
|
|
