Relationen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:16 Do 06.01.2005 | | Autor: | Reaper |
Bsp.: Zeigen oder widerlegen Sie:
a.) Jede transitive und symmetrische Relation auf einer Menge A ist reflexiv
Tja und wie zeig ich das?
b.)Wenn eine Relation auf einer Menge A sowohl Äquivalenz- als auch Ordnungsrelation ist, dann gilt R = {(a,a) | a [mm] \in [/mm] A}
Muss ich hierbei nur prüfen ob die Relation reflexiv, symmetrisch, antisymmetrisch und transitiv ist und es ist beiesen oder geht das Beispiel komplizierter?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:43 Do 06.01.2005 | | Autor: | Micha |
Hallo Reaper!
> Bsp.: Zeigen oder widerlegen Sie:
> a.) Jede transitive und symmetrische Relation auf einer
> Menge A ist reflexiv
> Tja und wie zeig ich das?
Der erste Teil ist nicht schwer.
Du weisst, das gilt: $aRb [mm] \wedge [/mm] bRc [mm] \Rightarrow [/mm] aRc$ (Transitivität)
und ausserdem: $aRb [mm] \gdw [/mm] bRa$ (Symmetrie)
Nun musst du nur c=a setzen. Dann gilt:
$aRb [mm] \wedge [/mm] bRa [mm] \Rightarrow [/mm] aRa$ (das ist das Reflexive)
>
> b.)Wenn eine Relation auf einer Menge A sowohl Äquivalenz-
> als auch Ordnungsrelation ist, dann gilt [mm]R = \{(a,a) | a
\in A\}[/mm]
> Muss ich hierbei nur prüfen ob die Relation reflexiv,
> symmetrisch, antisymmetrisch und transitiv ist und es ist
> beiesen oder geht das Beispiel komplizierter?
>
Dazu vergleichst du am besten die andere Frage, die du gestellt hast. Bei den Ordnungsrelationen gibt es im Prinzip 5 Klassen:
$<, [mm] \le, [/mm] =, [mm] \ge, [/mm] >$
Dabei sind "komplementär": < und >, sowei [mm] $\le$ [/mm] und [mm] $\ge$. [/mm] Das "=" ist zu sich selbst das Komplement, und gleichzeitig symmetrisch. Klingt jetzt bisschen dumm, aber du kannst auch sagen, es ist antisymmetrisch und symmetrisch, was auch nicht besser klingt. Ist halt ziemlich trivial die Angelegenheit. Verbal umformuliert, ist das was du stehen hast, dass eine Relation, die sowohl Ordnungsrelation, als auch Äquivlenzrelation ist, nur das = sein kann.
Ansonsten wüsste ich nicht, wie man das noch ausformulieren könnte.
Grüße, Micha 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:05 Do 06.01.2005 | | Autor: | Philipp-ER |
Hi.
Dein "Beweis" für a) sieht nett aus, aber leider steckt der Fehler im Detail. Man findet ganz einfach ein Beispiel für eine transitive und symmetrische Relation auf einer Menge, die nicht reflexiv ist; irgendetwas an dem Beweis kann also nicht stimmen.
Ich überlasse euch selbst, nach dem Fehler zu suchen. Versucht mal, den Beweis wirklich sauber aufzuschreiben, dann werdet ihr merken, dass es an einer Stelle einen Haken gibt, den man leicht übersehen kann und der der Grund dafür ist, dass es nicht funktioniert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:33 Do 06.01.2005 | | Autor: | moudi |
Es hat etwas mit der Anzahl Elemente zu tun.
mfG Moudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:36 Fr 07.01.2005 | | Autor: | Micha |
Hallo nochmal!
Mir war irgendwie dieses Gegen-Beispiel noch im Hinterkopf, aber ich hatte das wohl vergessen:
Angenommen meine Relation aRb ist leer, d.h. a steht in keiner Relation zu einem anderen Element, dann ergibt sich ein Widerspruch. Man kann sich das so verdeutlichen:
Man stelle eine Relationsmatrix mit Elementen des [mm] $\IF_{2}$ [/mm] auf. Dabei repräsentiert eine 1 "steht in Relation mit" und eine 0 für "steht nicht in Relation mit".
Dann ergibt sich für transitive und symmetrische Matrizen etwa ein Schema wie dieses (für einen 3-Elementigen Körper):
[mm] \begin{pmatrix}
R & a & b & c \\
a & 1 & 0 & 0 \\
b & 0 & 1 & 1 \\
c & 0 & 1 & 1 \\
\end{pmatrix} [/mm]
Symmetrisch heißt jetzt, dass die Matrix symmetrisch ist, also wenn ich sie an der Hauptdiagonalen stürze, kommt die gleich raus.
Transitiv heißt in dem Fall, dass die Matrix mit sich selbst "malgenommen" wieder sich selbst ergibt. Dabei sei aber 1+1 = 1 (!)
Ansonsten funktioniert das wie eine Matrixmultiplikation. Ich hab das jetzt für die Beispielmatrix nicht überprüft...
Jetzt kommt der Punkt: Reflexiv würde bedeuten, dass auf der Hauptdiagonalen überall eine 1 steht. (Mache dir das logisch klar.)
Ich kann aber auch die leere Relation wählen. Sie hat die Darstellung:
[mm] \begin{pmatrix}
R & a & b & c \\
a & 0 & 0 & 0 \\
b & 0 & 0 & 0 \\
c & 0 & 0 & 0 \\
\end{pmatrix} [/mm]
Diese Matrix erfüllt die Symmetrie und Transitivitätseigenschaft der Relationsmatrizen. Aber wohl nicht die Symmetrieeigenschaft.
Mit anderen Worten: Ist die Relationsklasse für jedes Element leer, so ergibt sich ein Widerspruch, weil meine Transitivität keinen Sinn macht. Es sind nur triviale Mengen, nämlich leere Mengen, mit denen man da arbeitet.
Ich hoffe ich hab meinen Kopf nochmal aus der Schlinge ziehen können.
Gruß Micha
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:20 Fr 07.01.2005 | | Autor: | Reaper |
OK nehmen wir nun ein Beispiel her z.b. die Menge A = {1,2,3}
So damit ich nun Relationen bilden kann muss ich das kartesische Produkt dieser Menge bilden
A x A = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
und jetzt auf Symmetrie und Transitivität vergleichen
Transitivität: {(1,2),(1,3),(2,3)}
...
Wie prüfe ich nun auf Reflexivität?
Für mich ist alles irgendwie reflexiv :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:40 Fr 07.01.2005 | | Autor: | moudi |
> OK nehmen wir nun ein Beispiel her z.b. die Menge A =
> {1,2,3}
> So damit ich nun Relationen bilden kann muss ich das
> kartesische Produkt dieser Menge bilden
> A x A =
> {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
> und jetzt auf Symmetrie und Transitivität vergleichen
Eine Relation R ist nur eine Teilmenge von A x A .
Eine Relation R für die Menge A={1,2,3} ist reflexiv genau dann wenn die Paare (1,1), (2,2) und (3,3) in R liegen.
Eine Relation R ist symmetrisch genau dann, wenn mit jedem Paar (a,b) das in R liegt, auch das Paar (b,a) in R liegt.
z.B [mm]R=\{(1,2), (2,3), (2,2), (1,3), (3,2), (3,3) \}[/mm] ist transitiv, nicht reflexiv (es fehlt (1,1)) und nicht symmetrisch (es fehlt (2,1)).
z.B [mm]R=\{(1,2), (2,1), (1,1), (3,3) \}[/mm] ist symmetrisch, aber nicht transitiv und reflexiv.
A propos: Die Transitivität nachzuweisen ist in der Regel das mühsamste.
> Transitivität: {(1,2),(1,3),(2,3)}
> ...
> Wie prüfe ich nun auf Reflexivität?
> Für mich ist alles irgendwie reflexiv :)
>
>
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:39 Fr 07.01.2005 | | Autor: | Reaper |
> Bsp.: Zeigen oder widerlegen Sie:
> a.) Jede transitive und symmetrische Relation auf einer
> Menge A ist reflexiv
Ja stimmt schon was du da sagst nur is mir nicht ganz klar wie ich das jetzt zum obigen Beispiel anwenden soll. Ich will ein Beispiel finden mit der Menge A = {1,2,3} welches zeigt dass jede transitive und symmetrische Relation auf einer Menge A reflexiv ist oder nicht. Doch wie stelle ich das an wo nehme ich die Relation her, wenn es nciht das kartesiche Produkt ist, sondern nur ein Teil davon. Welcher Teil?
Vielleicht nur der symmetrische, transitive und reflexive? Wenn dem so ist dann müssen woll (1,1) (2,2) (3,3) im symmetrischen Teil vorhanden sein als auch im transitiven, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:06 Sa 08.01.2005 | | Autor: | moudi |
> > Bsp.: Zeigen oder widerlegen Sie:
> > a.) Jede transitive und symmetrische Relation auf einer
>
> > Menge A ist reflexiv
>
Gemäss Philipp-ER ist die obige Aussage falsch. Das heisst um die Aussage zu widerlegen muss man ein Gegenbeispiel angeben.
Hier ist eines (wiederum mit A={1,2,3}
Sei R={(1,1),(1,2),(2,1),(2,2)}
Dann ist R transitiv und symmetrisch, aber nicht reflexiv (dazu müsste auch (3,3) zu R gehören.
> Ja stimmt schon was du da sagst nur is mir nicht ganz klar
> wie ich das jetzt zum obigen Beispiel anwenden soll. Ich
> will ein Beispiel finden mit der Menge A = {1,2,3} welches
> zeigt dass jede transitive und symmetrische Relation auf
> einer Menge A reflexiv ist oder nicht. Doch wie stelle ich
Mit einem Beispiel kann man höchstens eine Aussage widerlegen. Aber mit einem Beispiel kann man keine allgemeine Aussage beweisen.
> das an wo nehme ich die Relation her, wenn es nciht das
> kartesiche Produkt ist, sondern nur ein Teil davon. Welcher
> Teil?
>
> Vielleicht nur der symmetrische, transitive und reflexive?
> Wenn dem so ist dann müssen woll (1,1) (2,2) (3,3) im
> symmetrischen Teil vorhanden sein als auch im transitiven,
> oder?
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:47 Sa 08.01.2005 | | Autor: | Reaper |
Sei R={(1,1),(1,2),(2,1),(2,2)}
Dann ist R transitiv und symmetrisch, aber nicht reflexiv (dazu müsste auch (3,3) zu R gehören.
Ja schon aber wie kommst du auf (1,1),(1,2),(2,1),(2,2). Bitte erkläre es mir in Einzelschritten wie du da rangehst. Denn wenn ich eine transitive sowie
symmetrische Relation bestimmen möchte komme ich auf
(1,2),(1,3),(1,1),(2,2),(2,3). Hach denn wenn du oben jetzt noch (2,3),(3,3)
und (3,2) hinzufügst dann ist das ganze plötzlich reflexiv also erkläre mir bitte warum du diese 3 Paare nicht hinzufügst und wie du überhaupt auf dein Ergebnis kommst danke.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:01 Sa 08.01.2005 | | Autor: | moudi |
Das Ziel ist ja ein Gegenbeispiel zu finden zur Aussage
R transitiv und R symmetrisch [mm] \Rightarrow [/mm] R reflexiv.
Jetzt habe ich mir den (falschen) Beweis von Hathorman angeschaut und folgendes geschlossen:
Sei R transitiv und symmetrisch und für ein a existiere ein b so, dass a R b.
Dann muss auch b R a gelten, weil R symmetrisch ist. Also haben wir a R b und b R a. Weil R transitiv ist, muss auch a R a gelten.
Alles in allem wurde gezeigt: Gibt es ein Element b, dass in Relation zu a ist, dann ist (a,a) ein Element der Relation. (Hoffe du konntest soweit folgen).
Um jetzt ein Gegenbeispiel zu konstruieren, müssen wir also ein Element c haben, dass mit keinem anderen Element in der Relation R ist. In meinem Beispiel ist c=3 dieses Element. Deshalb durfte ich auf keinen Fall eines der Elemente (1,3), (3,1), (2,3), (3,2), (3,3) in die Relation aufnehmen. Denn Rest habe ich so gewählt, dass es eine "schöne" transitive und symmetrisch Relation geworden ist. Ich hätte aber für den Rest auch andere Möglichkeiten gehabt.
mfG Moudi
|
|
|
|
