binäre Relationen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Ich habe die Frage in keinem anderen Forum gestellt!
Eigendlich wäre meine Frage erstmal: Kann ich mit Relationen genau so rechnen, wie mit Mengen. Meine Aufgabe ist:
[mm] R\subseteq M^{2} [/mm] sei eine binäre Relation über die Menge M. Die reflexive Hülle von R ist definiert mit
[mm] R^{r} [/mm] = R [mm] \cup [/mm] {(x,x) | x [mm] \in [/mm] M }
Die transitive Hülle von R ist definiert als
[mm] R^{+} [/mm] = [mm] \bigcup_{i \ge 1} R^{i} [/mm] mit [mm] R^{1} [/mm] = R
und [mm] R^{i+1} [/mm] = [mm] R^{i} \circ [/mm] R für i [mm] \ge [/mm] 1
Jetzt sollen wir für 2 Relationen R,S [mm] \subseteq M^{2} [/mm] folgenden Behauptungen beweisen:
1. (R [mm] \cup S)^{r} [/mm] = [mm] R^{r} \cup S^{r}
[/mm]
Da dachte ich mir das so, ihr könnt mir ja sagen, wenn ich komplett falsch liege:
[mm] R^{r} \cup S^{r} [/mm] =
= (R [mm] \cup [/mm] {(x,x) | x [mm] \in [/mm] M }) [mm] \cup [/mm] (S [mm] \cup [/mm] {(x,x) | x [mm] \in [/mm] M })
Vereinigungen isnd assoziativ, also:
= R [mm] \cup [/mm] S [mm] \cup [/mm] {(x,x) | x [mm] \in [/mm] M } [mm] \cup [/mm] {(x,x) | x [mm] \in [/mm] M }
A [mm] \cup [/mm] A = A, also:
= (R [mm] \cup [/mm] S) [mm] \cup [/mm] {(x,x) | x [mm] \in [/mm] M }
=(R [mm] \cup S)^{r}
[/mm]
Ist das richtig so?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:24 Fr 27.04.2007 | | Autor: | statler |
Guten Morgen!
> Eigentlich wäre meine Frage erstmal: Kann ich mit
> Relationen genau so rechnen, wie mit Mengen.
Ja, kannst du, Relationen sind doch Mengen!
> Meine Aufgabe
> ist:
>
> [mm]R\subseteq M^{2}[/mm] sei eine binäre Relation auf der Menge M.
> Die reflexive Hülle von R ist definiert mit
>
> [mm]R^{r}[/mm] = R [mm]\cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{(x,x) | x [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
M }
>
> Die transitive Hülle von R ist definiert als
> [mm]R^{+}[/mm] = [mm]\bigcup_{i \ge 1} R^{i}[/mm] mit [mm]R^{1}[/mm] = R
> und [mm]R^{i+1}[/mm] = [mm]R^{i} \circ[/mm] R für i [mm]\ge[/mm] 1
>
> Jetzt sollen wir für 2 Relationen R,S [mm]\subseteq M^{2}[/mm]
> folgenden Behauptungen beweisen:
>
> 1. (R [mm]\cup S)^{r}[/mm] = [mm]R^{r} \cup S^{r}[/mm]
>
> Da dachte ich mir das so, ihr könnt mir ja sagen, wenn ich
> komplett falsch liege:
>
> [mm]R^{r} \cup S^{r}[/mm] =
> = (R [mm]\cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{(x,x) | x [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
M }) [mm]\cup[/mm] (S [mm]\cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{(x,x) | x [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
M
> })
>
> Vereinigungen isnd assoziativ, also:
>
> = R [mm]\cup[/mm] S [mm]\cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{(x,x) | x [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
M } [mm]\cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{(x,x) | x [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
M }
>
> A [mm]\cup[/mm] A = A, also:
>
> = (R [mm]\cup[/mm] S) [mm]\cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{(x,x) | x [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
M }
>
> =(R [mm]\cup S)^{r}[/mm]
>
> Ist das richtig so?
Du liegst nicht nur nicht komplett falsch, sondern sogar vollständig richtig ![[ok]](/images/smileys/ok.gif "[ok]")
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Cool, danke schon mal. Hab mich über alle Maße gefreut!
Wie sieht es denn aus wenn:
S,R [mm] \in M^{2}
[/mm]
Angenommen, S und R bestehen aus nur jeweils einem Element:
[mm] (a,b)\inS, (c,d)\inR
[/mm]
Wenn ich jetzt S [mm] \cup [/mm] R sage, muss ich dann die elemente a und c zB auch in Relation setzen? Wäre das dann sowas wie:
S [mm] \cup [/mm] R = {(a,b), (c,d), (a,c).....} ????
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:11 Fr 27.04.2007 | | Autor: | statler |
> Wie sieht es denn aus wenn:
>
> S,R [mm]\in M^{2}[/mm]
Wir sind uns jetzt darüber einig, daß Relationen Mengen sind. Dann muß das S, R [mm]\subset M^{2}[/mm] heißen.
> Angenommen, S und R bestehen aus nur jeweils einem
> Element:
>
> (a,b) [mm] \in [/mm] S, (c,d) [mm] \in [/mm] R
besser: S = {(a,b)}, R = {(c,d)}; nur diese Schreibweise macht deutlich, was du meinst, daß nämlich S genau ein Element enthält.
> Wenn ich jetzt S [mm]\cup[/mm] R sage,
Sagen kannst du, was du willst, wir sind ein freies Land. Wenn du allerdings S [mm]\cup[/mm] R bildest, dann steht gaaaanz genau fest, wie das Resultat aussieht.
> muss ich dann die elemente a
> und c zB auch in Relation setzen? Wäre das dann sowas wie:
>
> S [mm]\cup[/mm] R = {(a,b), (c,d), (a,c).....} ????
So nämlich nicht, das Element (a,c) hat da nix zu suchen.
Gruß
Dieter
|
|
|
| |
|
Verzeih mir meine Flüchtigkeitsfehler und meine Ungenauigkeit :D
Wenn ich also zwei Relationen/Mengen vereinige, muss ich nicht die Elemente untereinander in irgendeine Beziehung setzen, sondern einfach nur die Elemetne in einen Topf schmeissen?!
Dann ist mir bei folgender aufgabe aber etwas nicht ganz klar:
(R [mm] \cup S)^{+} \supseteq R^{+} \cup S^{+}
[/mm]
Wenn das was Du sagst, stimmt (woran ich nicht zweifle!!!) dann müsste doch
(R [mm] \cup S)^{+} [/mm] = [mm] R^{+} \cup S^{+}
[/mm]
sein, oder? Bzw. dann weiss ich nicht, wie ich die transitive Hülle
(R [mm] \cup S)^{+} [/mm] bilden soll ... vlt kannste mir ja auf die Sprünge helfen
danke Dir für Deine Hilfe!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:47 Fr 27.04.2007 | | Autor: | komduck |
Ein Gegenbeispiel:
R = {(a,b)}
S = {(b,c)}
dann ist:
[mm] R^{+} [/mm] = {(a,b)}
[mm] S^{+} [/mm] = {(b,c)}
aber
(R [mm] \cup S)^{+} [/mm] = {(a,b),(b,c),(a,c)}
komduck
|
|
|
| |
|
ja, so dachte ich mir das nach der letzten Antwort auch, nur. Aber ich hab da ein Verständnisproblem:
R und S beschreiben doch Relationen. Z.B. Größer oder kleiner ...
Wäre jetzt zB R größer und S kleiner, was wäre denn dann R [mm] \cup [/mm] S.
in welcher Relation stehen dann a und c
wäre das dann "gößer oder kleiner"
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:16 Fr 27.04.2007 | | Autor: | statler |
Hi!
> ja, so dachte ich mir das nach der letzten Antwort auch,
> nur. Aber ich hab da ein Verständnisproblem:
>
> R und S beschreiben doch Relationen. Z.B. Größer oder
> kleiner ...
>
> Wäre jetzt zB R größer und S kleiner, was wäre denn dann R
> [mm]\cup[/mm] S.
>
> in welcher Relation stehen dann a und c
>
> wäre das dann "gößer oder kleiner"
Weder noch. Nicht jede mathematische Relation hat eine umgangssprachliche Entsprechung. Man kann i. a. nur so formulieren: a steht in Relation R zu b genau dann wenn (a,b) Element von R ist.
Wie würdest du die 'volle' Relation (auf der Menge der Menschen) umgangssprachlich ausdrücken? Vielleicht: Jeder ist mit jedem verwandt? Oder jeder kennt jeden? Jeder hat was mit jedem?
Gruß
Dieter
|
|
|
| |
|
wie gesagt, bin ich echt dankbar für die Hilfe, denn ich stehe vollkommen aufm Schlauch
ich hab hier 2 Aufgaben an denen ich hänge. ich soll zeigen:
1. (R [mm] \cup S)^{+} \supseteq R^{+} \cup S^{+}
[/mm]
und
2. (R [mm] \cup S)^{+} \not= R^{+} \cup S^{+}
[/mm]
aber die beiden sind doch widersprüchlich, oder? Vor allem beim 2. bin ich mir nicht so sicher, ob das stimmt....
ich weiss auch nciht recht wie ich da rangehn soll, das zu beweise. Kann ich das über Beispiele machen (0 Elemente, 1 Element, 2 Elemente und was für 2 Elemente gilt, gilt ja dann auch für alles größe 2 Elemente)
Vlt habt ihr n Ansatz, auf dem ich aufbauen kann.
Vielen Dank schonmal im Voraus und im Nachhinein!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:52 Fr 27.04.2007 | | Autor: | statler |
Hi!
> ich hab hier 2 Aufgaben an denen ich hänge. ich soll
> zeigen:
>
> 1. (R [mm]\cup S)^{+} \supseteq R^{+} \cup S^{+}[/mm]
>
> und
>
> 2. (R [mm]\cup S)^{+} \not= R^{+} \cup S^{+}[/mm]
Da fehlt etwas Text. Die erste Aussage stimmt immer, und sie ist auch mengentheoretisch leicht zu beweisen.
> aber die beiden sind doch widersprüchlich, oder? Vor allem
> beim 2. bin ich mir nicht so sicher, ob das stimmt....
Die 2. Aussage gilt so natürlich nicht immer. Behauptet wird vielmehr, daß es Fälle gibt, wo sie stimmt, und so einen hat comduck dir geliefert.
Gruß
Dieter
|
|
|
| |
|
was fehlt denn? das ist natürlich alles bezogen auf das, was ich in meiner ersten Frage schrieb, sorry, wenn ich zu ungenau schreibe
Also mir ist das ja alles recht klar geworden, aber wie gehe ich da formal und mengentheoretisch ran? Mir fehlt einfach der Ansatz.
Und zu 2. wie kann ich denn eine Behauptung beweisen, die nur eingeschränkt stimmt?!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:13 Fr 27.04.2007 | | Autor: | statler |
Hi!
> Also mir ist das ja alles recht klar geworden, aber wie
> gehe ich da formal und mengentheoretisch ran? Mir fehlt
> einfach der Ansatz.
zu 1: Ein Element (a,b) aus der rechten Menge liegt in [mm] R^{+} [/mm] oder in [mm] S^{+}. [/mm] Betrachten wir mal den Fall, daß es in [mm] R^{+} [/mm] liegt. Dann liegt es in einem [mm] R^{i}. [/mm] Das heißt, es gibt eine Kette von i Elementen in R, die a mit b verbinden, also [mm] (a,x_{1}), (x_{1}, x_{2}), [/mm] ..., [mm] (x_{i-1}, [/mm] b). Aber genau diese Kette tut es auch auf der linken Seite. Wenn die Paare in R liegen, liegen sie erst recht in der Vereinigung von R und S.
> Und zu 2. wie kann ich denn eine Behauptung beweisen, die
> nur eingeschränkt stimmt?!
Die Behauptung ist: Es gibt Fälle, wo das Ungleichheitszeichen gilt. So stimmt die Behauptung uneingeschränkt, und bewiesen wird sie, indem ich einen Fall nenne!
Echt nicht schwer...
Dieter
|
|
|
| |
|
so wie das da steht, ist das ja ne ziemlich gute antwort auf die aufgabe. vielen vielen dank, mir ist das alles ein ganzes stück klarer geworden!
|
|
|
|
