Äquivalenzrel. Wo Beweisfehler < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:10 Mo 23.07.2007 | | Autor: | Merle23 |
| Aufgabe | Behauptung: Wenn eine Relation symmetrisch und transitiv ist, ist sie auch reflexiv, also eine Äquivalenzrelation.
(falscher) Beweis: Sei ~ eine symmetrische und transitive Relation auf einer Menge X. Sei x [mm] \in [/mm] X beliebig, und sei x ~ y. Wegen der Symmetrie ist dann auch y ~ x und aufgrund der Transitivität folgt dann auch x ~ x. Also ist ~ reflexiv. |
Ich hab erstmal ein Gegenbeispiel, dass das nicht stimmt: In [mm] \IZ [/mm] sei folgende Relation definiert: xRy [mm] :\gdw [/mm] "x-y ist eine gerade Zahl [mm] \not= [/mm] 0". Die ist symmetrisch und transitiv aber nicht reflexiv.
Jetzt find ich aber den Fehler im Beweis nicht. Bei den Definitionen von symmetrisch und transitiv steht nirgends, dass x,y,z verschieden sein müssen (davor steht sogar immer ein Allquantor).
Ich hab mir nur überlegt, dass der Beweis davon ausgeht, dass x in Relationen zu einem y steht, was aber nicht immer der Fall sein muss - x kann ja auch in keiner Relation zu anderen Elementen stehen - damit gilt der Beweis schon mal nicht für alle x, aber das sagt mir jetzt nicht wo der Fehler im Beweis steckt.
Danke schon mal im Vorraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Behauptung: Wenn eine Relation symmetrisch und transitiv
> ist, ist sie auch reflexiv, also eine Äquivalenzrelation.
> (falscher) Beweis: Sei ~ eine symmetrische und transitive
> Relation auf einer Menge X. Sei x [mm]\in[/mm] X beliebig, und sei x
> ~ y. Wegen der Symmetrie ist dann auch y ~ x und aufgrund
> der Transitivität folgt dann auch x ~ x. Also ist ~
> reflexiv.
> Ich hab erstmal ein Gegenbeispiel, dass das nicht stimmt:
> In [mm]\IZ[/mm] sei folgende Relation definiert: xRy [mm]:\gdw[/mm] "x-y ist
> eine gerade Zahl [mm]\not=[/mm] 0". Die ist symmetrisch und
> transitiv aber nicht reflexiv.
> Jetzt find ich aber den Fehler im Beweis nicht. Bei den
> Definitionen von symmetrisch und transitiv steht nirgends,
> dass x,y,z verschieden sein müssen (davor steht sogar immer
> ein Allquantor).
> Ich hab mir nur überlegt, dass der Beweis davon ausgeht,
> dass x in Relationen zu einem y steht, was aber nicht immer
> der Fall sein muss - x kann ja auch in keiner Relation zu
> anderen Elementen stehen - damit gilt der Beweis schon mal
> nicht für alle x, aber das sagt mir jetzt nicht wo der
> Fehler im Beweis steckt.
Doch, ich denke, gerade diese versteckte Annahme ist der Fehler. Und diese Einsicht erlaubt Dir ganz problemlos (denke ich) ein Gegenbeispiel zu konstruieren. Dabei brauchst Du auch überhaupt keine Rücksicht auf Eleganz zu nehmen: Du musst einfach nur diese "Pathologie" (zumindest eines Elementes $x$, das zu keinem anderen in der fraglichen Relation steht und für das die Relation auch nicht reflexiv ist) ins Zentrum stellen. So könntest Du sogar ein Gegenbeispiel auf einer einelementigen Menge konstruieren. $R$ wäre dann die Relation, die immer falsch ist. In diesem Falle sind die Prämissen von Symmetrie und Transitivität nie erfüllt und somit sind diese Implikationen trivialerweise wahr (ex falso quodlibet).
Zudem gilt auch $xRx$ nicht, also gilt Reflexivität nicht.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:06 Mo 23.07.2007 | | Autor: | Merle23 |
Das durch den einen Fehler den ich gefunden hab, der ganze Beweis "in sich zusammenstürzt" ist mir klar, nur ist mir noch nicht so ganz klar wieso, weil wenn man sich mal das eine Gegenbeispiel ansieht, welches ich gegeben hab, da steht jede ganze Zahl in Relation zu mindestens einer anderen (genauer gesagt jede gerade zu jeder geraden und jede ungerade zu jeder ungeraden - mit Ausnahme sich selbst eben).
Mein "Gegenargument" war jetzt aber, dass in dem Beweis davon ausgegangen wird, dass jedes x in Relation zu mindestens einem anderem steht... was bei meinem Gegenbeispiel aber genau der Fall ist! Und deswegen ist mir nicht klar, warum der Beweis bei diesem Gegenbeispiel trotzdem falsch ist (da ja mein Argument jetzt nicht mehr gilt).
|
|
|
| |
|
> Das durch den einen Fehler den ich gefunden hab, der ganze
> Beweis "in sich zusammenstürzt" ist mir klar, nur ist mir
> noch nicht so ganz klar wieso, weil wenn man sich mal das
> eine Gegenbeispiel ansieht, welches ich gegeben hab, da
> steht jede ganze Zahl in Relation zu mindestens einer
> anderen (genauer gesagt jede gerade zu jeder geraden und
> jede ungerade zu jeder ungeraden - mit Ausnahme sich selbst
> eben).
> Mein "Gegenargument" war jetzt aber, dass in dem Beweis
> davon ausgegangen wird, dass jedes x in Relation zu
> mindestens einem anderem steht... was bei meinem
> Gegenbeispiel aber genau der Fall ist! Und deswegen ist mir
> nicht klar, warum der Beweis bei diesem Gegenbeispiel
> trotzdem falsch ist (da ja mein Argument jetzt nicht mehr
> gilt).
Du kannst doch mit Deinem Gegenbeispiel (das eben keines ist!), den angeblichen Beweis, dass aus Transitivität und Symmetrie auch Reflexivität folge, Schritt für Schritt hindurch gehen und schauen, an welcher exakten Stelle dieser Beweis mit Deiner Relation $R$ nicht funktioniert: er funktioniert nicht, weil für Deine Relation $R$ Transitivität nicht gilt.
Beispiel: Es ist $4 R 2$, da $4-2=2$ gerade und [mm] $\neq [/mm] 0$ ist. Es ist aber auch $2 R 4$, da $2-4=-2$ gerade und [mm] $\neq [/mm] 0$ ist. Jedoch gilt $4 R 4$ nicht, weil zwar $4-4=0$ gerade, aber leider nicht [mm] $\neq [/mm] 0$ ist. Die Transitivität Deiner Relation $R$ wird daher wegen "$4 R 2$ und $2 R 4$ [mm] $\not\Rightarrow$ [/mm] $4 R 4$" widerlegt.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:04 Mo 23.07.2007 | | Autor: | dormant |
Hi!
Der Knackpunkt ist die Definition der Transivität:
Eine Relation ist transitiv, wenn für drei VERSCHIEDENE a, b, c gilt: [mm] a\sim [/mm] b, [mm] b\sim [/mm] c => [mm] a\sim [/mm] c.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:28 Mo 23.07.2007 | | Autor: | Somebody |
> Hi!
>
> Der Knackpunkt ist die Definition der Transivität:
>
> Eine Relation ist transitiv, wenn für drei VERSCHIEDENE
Nein, "Verschiedenheit" von $a,b,c$ wird in der Definition von Transitivität einer Relation nicht verlangt (siehe ![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Transitivit%C3%A4t_%28Mathematik%29).
> a, b, c gilt: [mm]a\sim[/mm] b, [mm]b\sim[/mm] c => [mm]a\sim[/mm] c.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:00 Mo 23.07.2007 | | Autor: | dormant |
Hi!
Das stimmt, da steht aber [mm] \forall [/mm] x, y, z [mm] \in [/mm] M, also auch für diejenigen, die paarweise verschieden sind.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:08 Mo 23.07.2007 | | Autor: | Somebody |
> Hi!
>
> Das stimmt, da steht aber [mm]\forall[/mm] x, y, z [mm]\in[/mm] M, also auch
> für diejenigen, die paarweise verschieden sind.
Ja klar: auch. Aber (ich dachte) Du wolltest doch darauf hinweisen, dass der zur Diskussion stehende angebliche Beweis, dass aus Transitivität und Symmetrie auch Reflexivität folge, wegen der Nichtbeachtung der Bedingung des Verschiedenseins der Elemente, auf die die Transitivität angewandt wird, falsch sei. Und, wie gesagt, Verschiedenheit der Elemente, auf die das Transitivitätsgesetz (bzw. die entsprechende Schlussweise) angewandt wird, ist nicht verlangt. Einzig unzulässiger Schritt des angeblichen Beweises ist, wie Merle23 bereits selbst bemerkt hat, die Annahme, dass es zu jedem Element $x$ ein Element $y$ gebe, das zu $x$ in der Relation [mm] $\sim$ [/mm] steht.
|
|
|
|
