Beweis Äquivalenzrelation < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:16 Sa 01.11.2008 | | Autor: | Theta |
| Aufgabe | | Man zeige, sind [mm] R_{1} [/mm] und [mm] R_{2} [/mm] Äquivalenzrelationen auf der Menge X, also insbesondere [mm] R_{1,2} \subset [/mm] X [mm] \times [/mm] X, so ist [mm] R_{1} \cap R_{2} [/mm] eine Äquivalenzrelation. Gilt dies auch für die Vereinigung? Beweisen Sie Ihre Aussage. Wie sieht es bei Ordnungsrelationen aus? Beweisen Sie Ihre Aussage. |
Hallo alle zusammen,
zu oben genannter Frage habe ich den Beweis für die Schnittmenge der Äquivalenzrelationen meiner Meinung nach fertig, bin mir jedoch beim Beweis der Vereinigungsmenge nicht sicher. Es würde mich sehr freuen, wenn ihr meinen Ansatz kommentieren könntet. Mein Ansatz ist folgender:
Grundsätzlich sind drei Varianten denkbar:
1. [mm] R_{1} [/mm] = [mm] R_{2}, [/mm] in diesem Fall ist die Vereinigung trivialerweise auch eine Äquivalenzrelation.
2. ObdA ist [mm] R_{1} \subset R_{2}, [/mm] auch in diesem Fall ist die Vereinigung Trivialerweise eine Äquivalenzrelation, da gilt:
[mm] R_{1} \cup R_{2} [/mm] = [mm] R_{2}
[/mm]
3. [mm] R_{1} \not= R_{2} [/mm] hierzu betrachten wir folgende Annahme:
Annahme:
Sei [mm] R_{1} \cup R_{2} [/mm] eine Äquivalenzrelation. Dann gilt:
(x,y) [mm] \in R_{1} \cup R_{2} \Rightarrow [/mm] (x,y) [mm] \in R_{1}\vee [/mm] (x,y) [mm] \in R_{2}
[/mm]
ObdA sei nun (x,y) [mm] \in R_{1}\backslash R_{2}. [/mm] Und sei (y,b) [mm] \in R_{2}\backslash R_{1}. [/mm] Da die Vereinigung nach Annahme eine Äquivalenzrelation ist gilt:
(x,y) [mm] \in R_{1} \cup R_{2} \wedge [/mm] (y,b) [mm] \in R_{1} \cup R_{2} \gdw [/mm] (x,b) [mm] \in R_{1} \cup R_{2}.
[/mm]
(x,b) [mm] \in R_{1} \cup R_{2} \Rightarrow [/mm] (x,b) [mm] \in R_{1} \vee R_{2}
[/mm]
(x,b) [mm] \in R_{1} \vee R_{2} \Rightarrow [/mm] (y,b) [mm] \in R_{1} \vee [/mm] (x,y) [mm] \in R_{2}
[/mm]
Widerspruch zur Annahme.
Ist dieser Beweis so schlüssig und gültig, oder habe ich mich da vollkommen verrant?
Wie gesagt, über Rückmeldungen würde ich mich freuen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:56 Sa 01.11.2008 | | Autor: | pelzig |
> Grundsätzlich sind drei Varianten denkbar:
> 1. [mm]R_{1}[/mm] = [mm]R_{2},[/mm] in diesem Fall ist die Vereinigung
> trivialerweise auch eine Äquivalenzrelation.
> 2. ObdA ist [mm]R_{1} \subset R_{2},[/mm] auch in diesem Fall ist
> die Vereinigung Trivialerweise eine Äquivalenzrelation, da
> gilt:
> [mm]R_{1} \cup R_{2}[/mm] = [mm]R_{2}[/mm]
Richtig.
> 3. [mm]R_{1} \not= R_{2}[/mm] hierzu betrachten wir folgende
> Annahme:
>
> Annahme:
> Sei [mm]R_{1} \cup R_{2}[/mm] eine Äquivalenzrelation. Dann gilt:
> (x,y) [mm]\in R_{1} \cup R_{2} \Rightarrow[/mm] (x,y) [mm]\in R_{1}\vee[/mm]
> (x,y) [mm]\in R_{2}[/mm]
Schreibe deutlicher auf, was genau deine Annahme ist! Hier könnte man mißverständlich annehmen, deine Annahme sei "Ist ... eine ÄR, dann gilt ...".
> ObdA sei nun (x,y) [mm]\in R_{1}\backslash R_{2}.[/mm] Und sei $(y,b) [mm] \in R_{2}\backslash R_{1}$
[/mm]
Was soll das oBdA? Es ist überhaupt nicht klar, dass solche (x,y) und (y,b) für beliebige ÄR [mm] $R_1$ [/mm] und [mm] $R_2$ [/mm] existieren!
Dennoch, die Idee ist genau richtig. Wenn es solche Paare gibt, dann:
> Da die Vereinigung nach Annahme
> eine Äquivalenzrelation ist gilt:
> (x,y) [mm]\in R_{1} \cup R_{2} \wedge[/mm] (y,b) [mm]\in R_{1} \cup R_{2} \red{\gdw}(x,b)\in R_{1} \cup R_{2}[/mm]
Die Rückrichtung gilt hier i.A. nicht! Für dieses Beispiel ist das zum Glück unwichtig, aber schreibe auch nur was du wirklich meinst - konzentriere dich auf das Wesentliche.
> (x,b) [mm]\in R_{1} \cup R_{2} \Rightarrow[/mm]
> (x,b) [mm]\in R_{1} \vee R_{2}[/mm]
Was soll das bedeuten? Du meinst [mm] $(x,b)\in R_1\vee (x,b)\in R_2$!
[/mm]
> (x,b) [mm]\in R_{1} \vee R_{2} \Rightarrow[/mm]
> (y,b) [mm]\in R_{1} \vee[/mm] (x,y) [mm]\in R_{2}[/mm]
>
> Widerspruch zur Annahme
... Richtig.
> Ist dieser Beweis so schlüssig und gültig, oder habe ich
> mich da vollkommen verrant?
Also die Idee ist zweifellos genau richtig. Die Ausführung noch nicht ganz perfekt. Das Hauptproblem ist eben, dass dein Gegenbeispiel nur klappt, wenn du $(x,y)$ und $(y,b)$ so wählen kannst wie du es oben gemacht hast. Vielleicht geht das ja niemals?!? Konstruiere also lieber ein konkretes Gegenbeispiel. Deine Notation hat auch noch einige Schwächen, aber das kommt mit der Zeit von ganz allein...
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:11 Sa 01.11.2008 | | Autor: | Theta |
Danke für die schnelle Antwort. Ist beruhigend, dass der Grundgedanke immerhin nicht vollkommen verkehrt ist.
Wäre als ein Gegenbeispiel folgendes ausreichend:
Gegenbeispiel:
[mm] X=\{1,2,3\}
[/mm]
[mm] R_{1}=\{(1,1), (1,2), (2,1), (2,2)\}
[/mm]
[mm] R_{2}=\{(1,1), (1,3), (3,1), (3,3)\}
[/mm]
[mm] R_{1}\cup R_{2}=\{(1,1), (1,2), (2,1), (2,2), (1,3), (3,1), (3,3) \}
[/mm]
Hier sind zwar die Relationen [mm] R_{1,2} [/mm] Äquivalenzrelationen, aber die Vereinigung scheitert, wie bei meinem Versuch eines Beweises an der Transitivität.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:18 Sa 01.11.2008 | | Autor: | pelzig |
> Danke für die schnelle Antwort. Ist beruhigend, dass der
> Grundgedanke immerhin nicht vollkommen verkehrt ist.
>
> Wäre als ein Gegenbeispiel folgendes ausreichend:
>
> Gegenbeispiel:
> [mm]X=\{1,2,3\}[/mm]
> [mm]R_{1}=\{(1,1), (1,2), (2,1), (2,2)\}[/mm]
> [mm]R_{2}=\{(1,1), (1,3), (3,1), (3,3)\}[/mm]
>
> [mm]R_{1}\cup R_{2}=\{(1,1), (1,2), (2,1), (2,2), (1,3), (3,1), (3,3) \}[/mm]
>
> Hier sind zwar die Relationen [mm]R_{1,2}[/mm] Äquivalenzrelationen,
> aber die Vereinigung scheitert, wie bei meinem Versuch
> eines Beweises an der Transitivität.
Richtig. Klappt es auch für eine zwei-elementige Menge X?
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:42 Sa 01.11.2008 | | Autor: | Theta |
Bei einer zwei-elementigen Mengen X dürften die Relationen [mm] R_{1} [/mm] und [mm] R_{2} [/mm] nur jeweils ein Element enthalten, nämlich das Element der Form (x,x).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:52 Sa 01.11.2008 | | Autor: | pelzig |
Nee. Auf zwei-elementigen Mengen X gibt es genau zwei ÄR, nämlich [mm] $\{(x,y)\in X^2|x=y\}$ [/mm] und [mm] $X^2$. [/mm] Jedenfalls ist die Vereinigung stets wieder eine ÄR...
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:00 Sa 01.11.2008 | | Autor: | Theta |
Ja, das ergibt Sinn. Ich muss aber unbedingt an meiner Ausdrucksweise arbeiten... ist nicht eindeutig genug. Ich meinte nämlich genau die Relationen die oben beschrieben sind.
Jedenfalls vielen Dank für die Hilfe.
Hast du vielleicht noch einen Tipp ob oder wie man den formalen Beweis sauber abschließen könnte?
|
|
|
|
