Relationen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe:
Gegeben ist die auf der Menge M = {a0 , . . . , an } mit n ≥ 2 definierte Relation R: [mm] \bigcup_{i=0}^{n-1} [/mm] {ai, ai+1}
Die Relation R ist weder symmetrisch noch reflexiv noch transitiv. Geben Sie die Anzahl der Elemente an, die zur Relation R hinzugenommen werden müssen, damit sie
a) symmetrisch . . . . . . . . . N =
b) reflexiv . . . . . . . . . . . N =
c) irreflexiv und antitransitiv . N =
d) transitiv . . . . . . . . . . N =
wird.
Hinweis: Zählen Sie nur die Elemente, die tatsächlich benötigt werden. Die in R bereits vorhandenen Elemente werden nicht mitgezählt. Sie können gegebenenfalls die Anzahl der Elemente nicht explizit angeben, sondern eine entsprechende Formel mit der diese Anzahl berechnet werden kann. |
Hallo könnte mir einer bei der Aufgabe so n bisschen helfen als bei der b.) glaube ich es muss immer n sein, bei der a.) auch n, c weis ich nicht und bei der d.) n-1 aber ich weis nicht ob das stimmt wäre nett wenn mir jemand helfen könnte!
Danke!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Aufgabe:
>
> Gegeben ist die auf der Menge M = {a0 , . . . , an } mit n
> ≥ 2 definierte Relation R: [mm]\bigcup_{i=0}^{n-1}\{(ai, ai+1)\}[/mm]
>
> Die Relation R ist weder symmetrisch noch reflexiv noch
> transitiv. Geben Sie die Anzahl der Elemente an, die zur
> Relation R hinzugenommen werden müssen, damit sie
>
> a) symmetrisch . . . . . . . . . N =
[mm] $N=\big|\bigcup_{i=0}^{n-1}\{(a_{i+1},a_i)\}\big|= n-1$\;?
[/mm]
> b) reflexiv . . . . . . . . . . . N =
[mm] $N=\big|\bigcup_{i=0}^n\{(a_i,a_i)\}\big|=n$\;?
[/mm]
> c) irreflexiv und antitransitiv . N =
[mm] $N=|\{\}|=0$\;?
[/mm]
> d) transitiv . . . . . . . . . . N =
[mm] $N=\big|\bigcup_{i=0}^n\; \bigcup_{k=i+2}^n \{(a_i,a_k)\}\big|=\sum_{i=0}^n \big|\bigcup_{k=i+2}^n \{(a_i,a_k)\}\big|=(n-2)+(n-3)+(n-4)+\cdots [/mm] +1 = [mm] \frac{(n-2)(n-1)}{2}$\;?
[/mm]
> wird.
>
> Hinweis: Zählen Sie nur die Elemente, die tatsächlich
> benötigt werden. Die in R bereits vorhandenen Elemente
> werden nicht mitgezählt. Sie können gegebenenfalls die
> Anzahl der Elemente nicht explizit angeben, sondern eine
> entsprechende Formel mit der diese Anzahl berechnet werden
> kann.
Ich will nun nicht behaupten, die obigen Vorschläge seien der Weisheit letzter Schluss: aber vielleicht ist es eine Diskussionsgrundlage? In jedem Falle denke ich, dass man zuerst einmal die betreffende Menge von Paaren hinschreiben und erst in einem zweiten Schritt deren Kardinalität bestimmen sollte.
|
|
|
| |
|
Hab mir das mal überlegt also:
a.) für symetrie muss gelten: (a,b) => (b,a) also n Tupel müssen hinzugenommen werden
b.) für reflexivität gilt doch: wenn (a,b) => (a,b) also wir haben n mögliche Tupel also müssen auch n Tupel hinzugenommen werden.
c.) da transitivität und reflexivität nicht gegben ist ist diese frage eine fangfrage und es müssen 0 elemente hinzugenommen werden
d.) bei trasitivität muss gelten (a,b) und (b,c) => (a,c), da n >= 2 also wenn ich folgendes hab: (a1,a2) (a2,a3) (a3,a4) (a4,a5) benötige ich folgende elemente: (a1,a3) (a2,a4) (a3,a5) und dies geht ja immer so weiter für größere n also brauche ich hier n-1 elemente
Also mal eine Idee von mir obs stimmt keine Ahnung!!!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:04 Fr 03.08.2007 | | Autor: | Somebody |
> Hab mir das mal überlegt also:
>
> a.) für symetrie muss gelten: (a,b) => (b,a) also n Tupel
> müssen hinzugenommen werden
Du hast recht: ich habe die Kardinalität von [mm] $\big|\bigcup_{i=0}^{n-1}\{(a_{i+1},a_i)\}\big|$ [/mm] falsch berechnet: die ist natürlich $=n$ ("Fencepost-Error").
> b.) für reflexivität gilt doch: wenn (a,b) => (a,b) also
> wir haben n mögliche Tupel also müssen auch n Tupel
> hinzugenommen werden.
Hier sind wir uns einig.
> c.) da transitivität und reflexivität nicht gegben ist ist
> diese frage eine fangfrage und es müssen 0 elemente
> hinzugenommen werden
Hier sind wir uns einig.
>
> d.) bei trasitivität muss gelten (a,b) und (b,c) => (a,c),
> da n >= 2 also wenn ich folgendes hab: (a1,a2) (a2,a3)
> (a3,a4) (a4,a5) benötige ich folgende elemente: (a1,a3)
> (a2,a4) (a3,a5) und dies geht ja immer so weiter für
> größere n also brauche ich hier n-1 elemente
Dies verstehe ich nicht. Für diejenigen Paare, die als erste Koordinate [mm] $a_1$ [/mm] haben, hast Du doch schon $n-2$, die Du hinzufügen musst, nämlich [mm] $(a_1,a_3),(a_1,a_4),\ldots,(a_1,a_n)$ [/mm] (sofern [mm] $n\geq [/mm] 3$). Für erste Koordinate [mm] $a_2$ [/mm] sind es noch $n-3$, nämlich [mm] $(a_2,a_4),(a_2,a_5),\ldots,(a_2,a_n)$. [/mm] Und so weiter: bis hinunter zu $1$. Diese Summe der ersten $n-2$ natürlichen Zahlen ist (wie bekanntlich schon der kleine C.F. Gauss herausfand) [mm] $\frac{(n-2)(n-1)}{2}$.
[/mm]
|
|
|
| |
|
ja bei transitivität hast du recht es können ja alle möglichen kombinationen auftauchen hmm hmm
also bei n = 2 = 1 element und bei n > 2 muss man n-1! berechnen, da
n=4 also 4 tupel und darunter gibt es 4-1! = 6 Möglichkeiten ?!
Erneuter Ansatz ?!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:34 Fr 03.08.2007 | | Autor: | Somebody |
> ja bei transitivität hast du recht es können ja alle
> möglichen kombinationen auftauchen hmm hmm
>
> also bei n = 2 = 1 element und bei n > 2 muss man n-1!
> berechnen, da
>
> n=4 also 4 tupel und darunter gibt es 4-1! = 6
> Möglichkeiten ?!
>
> Erneuter Ansatz ?!
>
Ich verstehe nicht, wie Du auf Fakultäten kommst. Für mich ist im Moment für diese Teilaufgabe noch immer folgender Ansatz [mm] $N=\big|\bigcup_{i=0}^{n-1}\; \bigcup_{k=i+2}^{n-1} \{(a_i,a_k)\}\big|=\sum_{i=0}^{n-1} \big|\bigcup_{k=i+2}^{n-1} \{(a_i,a_k)\}\big|=(n-2)+(n-3)+(n-4)+\cdots [/mm] +1 = [mm] \frac{(n-2)(n-1)}{2} [/mm] $
das Beste, was ich Dir zur Zeit bieten kann. Du musst doch einfach für erste Koordinate [mm] $a_0$, [/mm] dann [mm] $a_1$, [/mm] dann usw. zählen, wieviele Paare Du hinzufügen musst. Und dies sind meiner Meinung für erste Koordinate [mm] $a_i$ [/mm] die Paare [mm] $(a_i,a_{i+2}), (a_i,a_{i+3}),\ldots (a_i,a_{n-1})$. [/mm] Dies sind jeweils $(n-2)-i$ Paare (siehe oben). Wenn man dies alles zusammenzählt, erhält man für $N$ die Summe [mm] $N=(n-2)+(n-3)+(n-4)+\cdots+1 [/mm] = [mm] \frac{(n-2)(n-1)}{2}$.
[/mm]
|
|
|
| |
|
du hast recht das mit der Fakultät war n schnellschuss der daneben ging!
aber es können auch nicht alle kombinationen verwendet werden denke ich weil du pro transitivität bedingung eines tupels lediglich 1 element hineinnehmen musst darum...
...also wenn ich n = 4 habe:
R = {(a0,a1),(a1,a2),(a2,a3),(a3,a4)}
hier gibt es folgende Möglichkeiten für die Transitivität:
(a0,a1) [mm] \wedge [/mm] (a1,a2) => (a0,a2)
(a1,a2) [mm] \wedge [/mm] (a2,a3) => (a1,a3)
(a2,a3) [mm] \wedge [/mm] (a3,a4) => (a2,a4)
also
3 Elemente bei n = 4
--------------------------------------------------------------------------
n = 6:
R = {(a0,a1),(a1,a2),(a2,a3),(a3,a4),(a4,a5),(a5,a6)}
hier gibt es folgende Möglichkeiten für die Transitivität:
(a0,a1) [mm] \wedge [/mm] (a1,a2) => (a0,a2)
(a1,a2) [mm] \wedge [/mm] (a2,a3) => (a1,a3)
(a2,a3) [mm] \wedge [/mm] (a3,a4) => (a2,a4)
(a3,a4) [mm] \wedge [/mm] (a4,a5) => (a3,a5)
(a4,a5) [mm] \wedge [/mm] (a5,a6) => (a4,a6)
also
5 Elemente bei n = 6
---------------------------------------------------------------------------
Vermutung Transitivität: n - 1
---------------------------------------------------------------------------
Formal:
R = {(ai,ai+1),(ai+1,ai+2),(ai+2,ai+3),(ai+3,ai+4),(ai+4,ai+5),(ai+5,ai+6)...()...}
hier gibt es folgende Möglichkeiten für die Transitivität:
(ai,ai+1) [mm] \wedge [/mm] (ai+1,ai+2) => (ai,ai+2)
(ai+1,ai+2) [mm] \wedge [/mm] (ai+2,ai+3) => (ai+1,ai+3)
(ai+2,ai+3) [mm] \wedge [/mm] (ai+3,ai+4) => (ai+2,ai+4)
(ai+3,ai+4) [mm] \wedge [/mm] (ai+4,ai+5) => (ai+3,ai+5)
(ai+4,ai+5) [mm] \wedge [/mm] (ai+5,ai+6) => (a4,ai+6)
....
....
(ai+n,ai+n+1) [mm] \wedge [/mm] (ai+n,ai+n+1) => (ai+n,ai+n+1)
----------------------------------------------------------------------
Hier Enden meine Mathe Kenntnisse
lol
----------------------------------------------------------------------
irgendwas => n-1 Elemente
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:21 Sa 04.08.2007 | | Autor: | Somebody |
> du hast recht das mit der Fakultät war n schnellschuss der
> daneben ging!
>
> aber es können auch nicht alle kombinationen verwendet
> werden denke ich weil du pro transitivität bedingung eines
> tupels lediglich 1 element hineinnehmen musst darum...
>
> ...also wenn ich n = 4 habe:
>
> R = {(a0,a1),(a1,a2),(a2,a3),(a3,a4)}
Aha, ich sehe gerade, dass ich mit der Definition von $R$ wieder um 1 daneben war. Daher müsste die von mir vorgeschlagene Lösung so lauten:
$ [mm] N=\big|\bigcup_{i=0}^{n-2}\; \bigcup_{k=i+2}^n \{(a_i,a_k)\}\big|=\sum_{i=0}^{n-2} \big|\bigcup_{k=i+2}^n \{(a_i,a_k)\}\big|=(n-1)+(n-2)+(n-3)+\cdots [/mm] +1 = [mm] \frac{(n-1)n}{2}$
[/mm]
> hier gibt es folgende Möglichkeiten für die
> Transitivität:
> (a0,a1) [mm]\wedge[/mm] (a1,a2) => (a0,a2)
Nachdem Du dieses Paar [mm] $(a_0,a_2)$ [/mm] dazu genommen hast, musst Du eben weil nun [mm] $(a_0,a_2)$ [/mm] und [mm] $(a_2,a_3)$ [/mm] in der so erweiterten Relation stehen auch noch das Paar [mm] $(a_0,a_3)$ [/mm] dazunehmen usw. usf.
> (a1,a2) [mm]\wedge[/mm] (a2,a3) => (a1,a3)
> (a2,a3) [mm]\wedge[/mm] (a3,a4) => (a2,a4)
Deine vorgeschlagenen drei Erweiterungen von $R$ ergeben noch keine transitive Relation.
Ich bin der Meinung, dass $R$ um folgende Paare erweitert werden muss: [mm] $(a_0,a_2), (a_0,a_3), (a_0,a_4)$ [/mm] und [mm] $(a_1,a_3), (a_1,a_4)$ [/mm] und [mm] $(a_2,a_4)$. [/mm] Also ist $N=6$, was Deiner Lösung $N=n-1=4-1=3$ widerspricht, aber mit meiner obigen Formel übereinstimmt: [mm] $\frac{(4-1)\cdot 4}{2}=6$.
[/mm]
Zur Illustration noch folgendes Bild des gerichteten Graphen $R$ (blaue Pfeile) und seiner Erweiterung durch Bildung der transitiven Hülle (rote Pfeile):
[Dateianhang nicht öffentlich]
> also
>
> 3 Elemente bei n = 4
>
> --------------------------------------------------------------------------
>
> n = 6:
>
> R = {(a0,a1),(a1,a2),(a2,a3),(a3,a4),(a4,a5),(a5,a6)}
> hier gibt es folgende Möglichkeiten für die
> Transitivität:
> (a0,a1) [mm]\wedge[/mm] (a1,a2) => (a0,a2)
> (a1,a2) [mm]\wedge[/mm] (a2,a3) => (a1,a3)
> (a2,a3) [mm]\wedge[/mm] (a3,a4) => (a2,a4)
> (a3,a4) [mm]\wedge[/mm] (a4,a5) => (a3,a5)
> (a4,a5) [mm]\wedge[/mm] (a5,a6) => (a4,a6)
Auch hier erhalte ich einen viel grösseren Wert für $N$. Meiner Meinung nach müssen, um die transitive Hülle von $R$ zu bilden, folgende Paare zu $R$ hinzugenommen werden:
[mm] $(a_0,a_2), (a_0,a_3), (a_0,a_4), (a_0,a_5), (a_0,a_6)$ [/mm] und [mm] $(a_1,a_3), (a_1,a_4), (a_1,a_5), (a_1,a_6)$ [/mm] und [mm] $(a_2,a_4), (a_2,a_5), (a_2,a_6)$ [/mm] und [mm] $(a_3,a_5), (a_3,a_6)$ [/mm] und [mm] $(a_4,a_6)$.
[/mm]
Ergibt, in Übereinstimmung mit der oben vorgeschlagenen Formel, [mm] $N=\frac{(n-1)n}{2}$, $N=\frac{(6-1)\cdot 6}{2}=15$. [/mm] Also deutlich mehr als $n-1=6-1=5$.
Zur Illustration nochmals ein Bild des gerichteten Graphen $R$ (blaue Pfeile) und seiner Erweiterung durch Bildung der transitiven Hülle (rote Pfeile):
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:21 Mo 06.08.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
