matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMengenlehreTransitive Relationen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Mengenlehre" - Transitive Relationen
Transitive Relationen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Mengenlehre"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Transitive Relationen: Tipp
Status: (Frage) beantwortet Status 
Datum: 02:09 Sa 11.11.2017
Autor: TrickyDinkle

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.

        
Bezug
Transitive Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 08:06 Sa 11.11.2017
Autor: angela.h.b.


> 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].

> 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.


Bezug
                
Bezug
Transitive Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:29 Sa 11.11.2017
Autor: TrickyDinkle


> 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)

Bezug
                        
Bezug
Transitive Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 10:55 Sa 11.11.2017
Autor: angela.h.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

Bezug
                        
Bezug
Transitive Relationen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:58 Sa 11.11.2017
Autor: TrickyDinkle

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.

Bezug
                                
Bezug
Transitive Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:46 Sa 11.11.2017
Autor: TrickyDinkle

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.

Bezug
                                        
Bezug
Transitive Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:28 Sa 11.11.2017
Autor: angela.h.b.


> 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







Bezug
                                                
Bezug
Transitive Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:06 Sa 11.11.2017
Autor: TrickyDinkle


> 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$ ?


Bezug
                                                        
Bezug
Transitive Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:14 Sa 11.11.2017
Autor: angela.h.b.


> > 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

>  


Bezug
                                                                
Bezug
Transitive Relationen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:56 So 12.11.2017
Autor: TrickyDinkle

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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Mengenlehre"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 30m 13. Diophant
ULinAAb/Permutationsgr./ Transposition
Status vor 10h 36m 63. rabilein1
MSons/Kann man beim Roulette verlier
Status vor 16h 33m 6. Al-Chwarizmi
UStoc/Geordnete Stichproben mit Wdh.
Status vor 1d 18h 20m 2. matux MR Agent
DiffGlPar/Abschätzung
Status vor 1d 20h 20m 7. matux MR Agent
Algebra/Integritätsbereich Polynomring
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]