Transitive Relationen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei M eine Menge und [mm]S \subseteq M \times M[/mm] transitiv.
Zeigen Sie: Falls für die drei Elemente [mm]x, y, z \in M[/mm] gilt:
[mm]\{(x, y), (x, z), (y, z)\} \cap (\overline{S \cup S^-}) = \{(x, y)\},[/mm]
dann gilt:
[mm](\{(x, z), (y, z)\} \cap S = \emptyset) \vee (\{(x, z), (y, z)\} \cap S^- = \emptyset)[/mm] |
Zu meinem Problem: Ich habe keine Ahnung wie ich anfangen soll.
Grundsätzlich ist [mm](\overline{S \cup S^-})[/mm] mein Problem. Die Menge enthält (x, y), aber kein (x, z) oder (y, z).
Wenn ich versuche es umzuwandeln komme ich auf [mm](M \times M) \backslash (S \cup S^-)[/mm].
Mit [mm]S^-[/mm] kann ich auch nicht wirklich etwas anfangen. Klar, das ist das Inverse also [mm](b, a) \in S^-[/mm] sofern [mm](a, b) \in S[/mm].
Dann müsste [mm](S \cup S^-)[/mm] prinzipiell (x, z), (z, x), (y, z) und (z, y) enthalten, Damit die im Komplement dann rausfallen und (x, y) reinkommt. Das kann aber eigentlich nicht passieren, da ja y rausfliegt. (oder vielleicht nur z rauswerfen, damit dann x und y wieder reinkommen?)
Die Sache, die meiner Meinung nach überflüssig ist, ist die Information, dass die Menge transitiv ist. Aber da die Information gegeben ist und scheint sie wohl wichtig zu sein.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Es sei M eine Menge und [mm]S \subseteq M \times M[/mm] transitiv.
> Zeigen Sie: Falls für die drei Elemente [mm]x, y, z \in M[/mm]
> gilt:
>
> [mm]\{(x, y), (x, z), (y, z)\} \cap (\overline{S \cup S^-}) = \{(x, y)\},[/mm]
>
> dann gilt:
>
> [mm](\{(x, z), (y, z)\} \cap S = \emptyset) \vee (\{(x, z), (y, z)\} \cap S^- = \emptyset)[/mm]
>
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
> Zu meinem Problem: Ich habe keine Ahnung wie ich anfangen
> soll.
Du hast doch schon angefangen!
Das Sortieren der Zutaten ist ein guter Beginn, finde ich.
>
> Grundsätzlich ist [mm](\overline{S \cup S^-})[/mm] mein Problem.
Diese Menge enthält alle Paare, die nicht in der Relation S oder in der Umkehrrelation sind.
> Die Menge enthält (x, y), aber kein (x, z) oder (y, z).
> Wenn ich versuche es umzuwandeln komme ich auf [mm](M \times M) \backslash (S \cup S^-)[/mm].
Ja.
>
> Mit [mm]S^-[/mm] kann ich auch nicht wirklich etwas anfangen. Klar,
> das ist das Inverse also [mm](b, a) \in S^-[/mm] sofern [mm](a, b) \in S[/mm].
Also kannst Du doch etwas damit anfangen.
Wir wissen also, daß (x,y) weder in S noch in S^- ist.
Und da (x,z),(y,z) nicht in [mm] \overline{S \cup S^-} [/mm] sind, müssen sie in S [mm] \cup [/mm] S^- sein, also in S oder [mm] S^{-}
[/mm]
>
> Dann müsste [mm](S \cup S^-)[/mm] prinzipiell (x, z), (z, x), (y,
> z) und (z, y) enthalten, Damit die im Komplement dann
> rausfallen und (x, y) reinkommt.
Dem kann ich gerade nicht gut folgen.
Bleiben wir lieber bei dem, was wir sicher wissen:
(x,y) ist nicht in [mm] S\cup [/mm] S^-, und (x,z),(y,z) sind in [mm] S\cup [/mm] S^-.
Das ist zusammen mit der Transitivität vorausgesetzt, und nun sollen wir zeigen, daß
daß (x,z),(y,z) beide nicht in S oder beide nicht in S^- liegen.
Man kann es mit einem Widerspruch versuchen:
Angenommen, es wären [mm] \{(x, z), (y, z)\} \cap [/mm] S und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- beide nichtleer.
Sei etwa (x,z) [mm] \in [/mm] S.
Nach Voraussetzung ist (y,z) in S oder in S^-.
Nun kannst Du die Fälle durchspielen.
i. Seien (x,z) und (y,z) beide in S.
Nach Annahme ist [mm] \{(x, z), (y, z)\} \cap [/mm] S^- nichtleer,
sei etwa [mm] (x,z)\in [/mm] S^-.
Nun ziehe Schlüsse und finde einen Widerspruch
ii. Sei [mm] (x,z)\in [/mm] S, (y,z) [mm] \not\in [/mm] S.
Dann ist [mm] (y,z)\in [/mm] usw.
Versuch's!
LG Angela
> Das kann aber eigentlich
> nicht passieren, da ja y rausfliegt. (oder vielleicht nur z
> rauswerfen, damit dann x und y wieder reinkommen?)
>
> Die Sache, die meiner Meinung nach überflüssig ist, ist
> die Information, dass die Menge transitiv ist. Aber da die
> Information gegeben ist und scheint sie wohl wichtig zu
> sein.
>
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
> Angenommen, es wären [mm] \{(x, z), (y, z)\} \cap [/mm] S und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- beide nichtleer.
Wenn beide nicht leer sind wäre das kein Widerspruch. Den gäbe es nur wenn beide leer sind. [mm](\{(x, z), (y, z)\} \cap S = \emptyset) \vee (\{(x, z), (y, z)\} \cap S^- = \emptyset)[/mm]
[mm]Aussage \vee \overline{Aussage}[/mm] ist immer wahr.
Wenn [mm](a,b) \in S[/mm] dann [mm](a,b) \notin S^-[/mm] (unter der Annahme a [mm] \not= [/mm] b)
|
|
|
| |
|
> > Angenommen, es wären [mm]\{(x, z), (y, z)\} \cap[/mm] S und [mm]\{(x, z), (y, z)\} \cap[/mm]
> S^- beide nichtleer.
>
> Wenn beide nicht leer sind wäre das kein Widerspruch. Den
> gäbe es nur wenn beide leer sind. [mm](\{(x, z), (y, z)\} \cap S = \emptyset) \vee (\{(x, z), (y, z)\} \cap S^- = \emptyset)[/mm]
???
Du sollst zeigen, daß mindestens eine von beiden leer ist.
>
> [mm]Aussage \vee \overline{Aussage}[/mm] ist immer wahr (unter der
> Annahme x [mm]\not=[/mm] z)
Worum geht es?
S ist eine transitive Relation und es gilt
$ [mm] \{(x, y), (x, z), (y, z)\} \cap (\overline{S \cup S^-}) [/mm] = [mm] \{(x, y)\}. [/mm] $
Das ist Deine Voraussetzung.
Zeigen sollst Du nun, daß unter dieser Voraussetzung mindestens eine der Mengen [mm] \{(x, z), (y, z)\} \cap [/mm] S oder [mm] \{(x, z), (y, z)\} \cap [/mm] S^- leer ist.
Mein Vorschlag war, einen Beweis durch Widerspruch zu führen, indem man annimmt (!), daß diese beiden Mengen nicht leer sind und dann zeigt, daß dies nicht sein kann.
Wenn es nicht sein kann, daß beide Mengen ein Element enthalten, dann muß ist folglich eine der Mengen leer sein.
Aus der Voraussetzung folgte ja, daß (x,z) und (y,z) in [mm] S\cup S^{-} [/mm] sind.
1. Möglichkeit
beide in S.
Kann es sein, daß eines der Paare auch in [mm] S^{-} [/mm] ist?
2. Möglichkeit
nur ein Paar in S.
Dann muß das andere in [mm] S^{-}sein.
[/mm]
Kann das sein?
LG Angela
|
|
|
| |
|
Ich kann meinen vorherigen Artikel leider nicht editieren, da irgendein Bearbeitungskonflikt besteht.
Ich bin jetzt soweit:
[mm](x,z) \in S \wedge (y,z) \in S \Rightarrow (\{(x,z),(y,z)\} = \emptyset) \vee (\emptyset = \emptyset)[/mm]. Diese Aussage ist wahr.
[mm](x,z) \in S \wedge (y,z) \in S^- \Rightarrow (\{(x,z)\} = \emptyset) \vee (\{(y,z)\} = \emptyset)[/mm]. Diese Aussage ist offensichtlich falsch.
Die beiden Umkehrfälle analog.
Daraus kann ich dann irgendwie nichts sinnvolles mehr folgern.
|
|
|
| |
|
Vorgabe ist ja eine transitive Relation, also wenn $(x,y),(y,z) [mm] \in [/mm] S$, dann $(x,z) [mm] \in [/mm] S$.
Wir wissen aber schon, dass $(x,y) [mm] \notin [/mm] S [mm] \cup [/mm] S^-$ da $(x,y) [mm] \in \overline{S \cup S^-}$
[/mm]
Deshalb kann ich auch eigentlich nicht folgern, ob $(x,z) [mm] \in [/mm] S [mm] \wedge [/mm] (y,z) [mm] \in [/mm] S$ oder $(x,z) [mm] \in [/mm] S [mm] \wedge [/mm] (y,z) [mm] \in [/mm] S^-$ vorliegen kann oder nicht.
|
|
|
| |
|
> Vorgabe ist ja eine transitive Relation, also wenn
> [mm](x,y),(y,z) \in S[/mm], dann [mm](x,z) \in S[/mm].
Ja.
>
> Wir wissen aber schon, dass [mm](x,y) \notin S \cup S^-[/mm] da
> [mm](x,y) \in \overline{S \cup S^-}[/mm]
Richtig. Und dies ist für den zu führenden Beweis von großer Bedeutung.
>
> Deshalb kann ich auch eigentlich nicht folgern, ob [mm](x,z) \in S \wedge (y,z) \in S[/mm]
> oder [mm](x,z) \in S \wedge (y,z) \in S^-[/mm] vorliegen kann oder
> nicht.
Du hast etwas nicht richtig verstanden.
Ob [mm] (x,z)\in [/mm] S ist, habe ich nicht gefolgert!
Ich habe es einfach angenommen.
Ich skizziere Dir nochmal kurz den Weg meiner Gedanken:
Wir haben eine Aussage, aus welcher folgt, daß eine von zwei Mengen A und B leer ist.
Dies möchten wir beweisen.
Die Idee:
Ich nehme an, daß die zu zeigende Folgerung nicht stimmt,
und zeige, daß dies zu einem Widerspruch zur Voraussetzung führt.
Also kann es nicht sein, daß die Folgerung nicht stimmt.
Also stimmt sie.
Nochmal.
Voraussetzung:
$ [mm] \{(x, y), (x, z), (y, z)\} \cap (\overline{S \cup S^-}) [/mm] = [mm] \{(x, y)\}, [/mm] $
zu zeigen:
Dann gilt
$ [mm] (\{(x, z), (y, z)\} \cap [/mm] S = [mm] \emptyset) \vee (\{(x, z), (y, z)\} \cap [/mm] S^- = [mm] \emptyset) [/mm] $
Beweis:
Sei [mm] \{(x, y), (x, z), (y, z)\} \cap (\overline{S \cup S^-}) [/mm] = [mm] \{(x, y)\}.
[/mm]
Dann ist (x,y) weder in S noch in [mm] S^{-},
[/mm]
(x,z) ist in S oder [mm] S^{-},
[/mm]
(y,z) ist in S oder [mm] S^{-}.
[/mm]
Angenommen, beide der Mengen [mm] \{(x, z), (y, z)\} \cap [/mm] S und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- würden ein Element enthalten.
Es müßte dann sein
i. [mm] \{(x, z), (y, z)\} \cap S=\{(x,z)\} [/mm] und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- nichtleer
oder
i'. [mm] \{(x, z), (y, z)\} \cap S=\{(y,z)\} [/mm] und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- nichtleer
oder
ii. [mm] \{(x, z), (y, z)\} \cap S=\{(x,z),(y,z)\} [/mm] und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- nichtleer
Hast Du bis hierher folgen können?
Jetzt untersuche ich die drei Fälle:
i. [mm] \{(x, z), (y, z)\} \cap S=\{(x,z)\}
[/mm]
==> [mm] (y,z)\in S^{-}. [/mm] (Warum?)
==> [mm] (z,y)\in [/mm] S (Warum?)
==> [mm] (x,y)\in [/mm] S (Warum)
(x,y) ist aber nach Voraussetzung nicht in S. Widerspruch.
Also kann dieser Fall nicht eintreten.
i'. Für Dich.
ii. [mm] \{(x, z), (y, z)\} \cap S=\{(x,z),(y,z)\}
[/mm]
Wenn [mm] \{(x, z), (y, z)\} \cap S^-\not=\emptyset, [/mm] ist (x,z) oder (y,z) ind dieser Menge.
a. Angenommen, (x,z) wäre drin.
Dann ist [mm] (x,z)\in S^{-}, [/mm] also ... ... ...
b. Angenommen (y,z) wäre drin. Dann ... ... ...
Die Annahme, daß beide Mengen [mm] \{(x, z), (y, z)\} \cap [/mm] S und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- ein Element enthalten, führt zum Widerspruch.
Also ist eine der beiden Mengen [mm] \{(x, z), (y, z)\} \cap [/mm] S und [mm] \{(x, z), (y, z)\} \cap [/mm] S^- leer.
LG Angela
|
|
|
| |
|
> Hast Du bis hierher folgen können?
Ja
> Jetzt untersuche ich die drei Fälle:
>
> i. [mm]\{(x, z), (y, z)\} \cap S=\{(x,z)\}[/mm]
> ==> [mm](y,z)\in S^{-}.[/mm]
> (Warum?)
Wäre (y,z) in S, läge es auch im Schnitt.
> ==> [mm](z,y)\in[/mm] S (Warum?)
Wenn $(x,y) [mm] \in [/mm] S^-$, dann $(y,x) [mm] \in [/mm] S$ laut Definition. Aber was bringt mir diese Information hier?
> ==> [mm](x,y)\in[/mm] S (Warum)
Meiner Meinung nach gibt es keine Informationen über (x,y) an dieser Stelle. Wodurch würde denn impliziert, dass $(x,y) [mm] \in [/mm] S$ ?
|
|
|
| |
|
> > Hast Du bis hierher folgen können?
> Ja
Sehr gut!
>
> > Jetzt untersuche ich die drei Fälle:
> >
> > i. [mm]\{(x, z), (y, z)\} \cap S=\{(x,z)\}[/mm]
> > ==> [mm](y,z)\in S^{-}.[/mm]
> > (Warum?)
> Wäre (y,z) in S, läge es auch im Schnitt.
Nach Voraussetzung ist es in S oder [mm] S^{-}, [/mm] und wenn's wie hier nicht in S ist, dann also in [mm] S^{-}.
[/mm]
Man muß sich hier auf die Folgerungen aus der Voraussetzung berufen.
>
> > ==> [mm](z,y)\in[/mm] S (Warum?)
> Wenn [mm](x,y) \in S^-[/mm], dann [mm](y,x) \in S[/mm] laut Definition.
Genau.
> Aber
> was bringt mir diese Information hier?
"Bringen" tut sie nichts, aber Du kannst sie nutzen...
Du hast jetzt [mm] (x,z)\in [/mm] S und [mm] (z,y)\in [/mm] S.
>
> > ==> [mm](x,y)\in[/mm] S (Warum)
> Meiner Meinung nach gibt es keine Informationen über
> (x,y) an dieser Stelle. Wodurch würde denn impliziert,
> dass [mm](x,y) \in S[/mm] ?
Tja, das ist die große Frage... Was weißt Du denn über die Relation S???
LG Angela
>
|
|
|
| |
|
Ah, jetzt ist es mir das klar geworden. Hatte die ganze Zeit versucht die transitive Eigenschaft an irgendwelchen Stellen zu prüfen die mir nichts brachten. Danke.
|
|
|
|
