Äquivalenzrelation 2 < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:33 Di 28.05.2013 | | Autor: | ne1 |
| Aufgabe | Definitionsmenge: Menge aller Äquivalenzrelationen auf der Menge $X$.
Wertemenge: Menge aller Partitionen der Menge $X$.
Beweise, dass die Funktion $F$, definiert durch $F(R) = ^X / _R$ eine Bijektion ist. |
Mein Ansatz.
Injektion.
Ich nehme zwei beliebige unterschiedliche Elemente der Definitionsmenge [mm] $R_1, R_2$. [/mm] Die Funktion ordnet jeweils den beiden Elemente die Elemente $^X / [mm] _{R_1}$ [/mm] und $^X / [mm] _{R_2}$ [/mm] zu. Wir wissen auch [mm] $\{y \in X: yR_1 x\} \in [/mm] ^X / [mm] _{R_1}$ [/mm] und [mm] $\{y \in X: y R_2 x \} \in [/mm] ^X / [mm] _{R_2}$. [/mm] Wir haben zwei unterschiedliche Elemente [mm] $R_1$ [/mm] und [mm] $R_2$ [/mm] genommen also wir haben $(a,b) [mm] \in R_1$ [/mm] und (a,b) [mm] \notin R_2 [/mm] (oder umgekehrt). Wegen der Äquivalenzrelation wissen wir, dass $a,b [mm] \in [/mm] A$, wobei $A [mm] \in [/mm] ^X / [mm] _{R_1}$. [/mm] Jetzt reicht es zu zeigen, dass es kein Element der Menge $^X / [mm] _{R_2}$ [/mm] gibt, der die Elemente $a$ und $b$ enthält. Ich nehme an, es gibt so ein Element $B [mm] \in [/mm] ^X / [mm] _{R_2}$. [/mm] Es müsste also sein, dass $(a,c) [mm] \in R_2$ [/mm] und $(b,c) [mm] \in R_2$. [/mm] Aus der Transitivität und Symmetrie erhalten wir $(a,b) [mm] \in R_2$, [/mm] aber wir haben angenommen $(a,b) [mm] \notin R_2$, [/mm] deshalb haben wir ein Widerspruch und so ein $B$ gibt es nicht also sind $^X / [mm] _{R_1}$ [/mm] und $^X / [mm] _{R_2}$ [/mm] unterschiedlich.
Surjektion
Sei $S$ eine beliebige Partition der Menge $X$. Ich muss zeigen [mm] $(\forall S)(\exists [/mm] R)F(R) = S$. Aus einem Satz in meinem Skript weiß ich, dass $S = ^X / [mm] _{R_S}$, [/mm] also [mm] $F(R_S) [/mm] = ^X / [mm] _{R_S} [/mm] = S$.
Bitte kontrollieren.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:17 Mi 29.05.2013 | | Autor: | tobit09 |
Hallo ne1,
> Definitionsmenge: Menge aller Äquivalenzrelationen auf der
> Menge [mm]X[/mm].
> Wertemenge: Menge aller Partitionen der Menge [mm]X[/mm].
>
> Beweise, dass die Funktion [mm]F[/mm], definiert durch [mm]F(R) = ^X / _R[/mm]
> eine Bijektion ist.
> Mein Ansatz.
> Injektion.
> Ich nehme zwei beliebige unterschiedliche Elemente der
> Definitionsmenge [mm]R_1, R_2[/mm]. Die Funktion ordnet jeweils den
> beiden Elemente die Elemente [mm]^X / _{R_1}[/mm] und [mm]^X / _{R_2}[/mm]
> zu. Wir wissen auch [mm]\{y \in X: yR_1 x\} \in ^X / _{R_1}[/mm] und
> [mm]\{y \in X: y R_2 x \} \in ^X / _{R_2}[/mm].
Für jedes [mm] $x\in [/mm] X$, ja.
> Wir haben zwei
> unterschiedliche Elemente [mm]R_1[/mm] und [mm]R_2[/mm] genommen also wir
> haben [mm](a,b) \in R_1[/mm] und (a,b) [mm]\notin R_2[/mm] (oder umgekehrt).
> Wegen der Äquivalenzrelation wissen wir, dass [mm]a,b \in A[/mm],
> wobei [mm]A \in ^X / _{R_1}[/mm].
Ja, mit [mm] $A:=[a]_{R_1}=[b]_{R_1}$.
[/mm]
> Jetzt reicht es zu zeigen, dass es
> kein Element der Menge [mm]^X / _{R_2}[/mm] gibt, der die Elemente [mm]a[/mm]
> und [mm]b[/mm] enthält. Ich nehme an, es gibt so ein Element [mm]B \in ^X / _{R_2}[/mm].
> Es müsste also sein, dass [mm](a,c) \in R_2[/mm] und [mm](b,c) \in R_2[/mm].
Für ein [mm] $c\in [/mm] X$, ja.
> Aus der Transitivität und Symmetrie erhalten wir [mm](a,b) \in R_2[/mm],
> aber wir haben angenommen [mm](a,b) \notin R_2[/mm], deshalb haben
> wir ein Widerspruch und so ein [mm]B[/mm] gibt es nicht also sind [mm]^X / _{R_1}[/mm]
> und [mm]^X / _{R_2}[/mm] unterschiedlich.
![[ok]](/images/smileys/ok.gif "[ok]")
> Surjektion
> Sei [mm]S[/mm] eine beliebige Partition der Menge [mm]X[/mm]. Ich muss
> zeigen [mm](\forall S)(\exists R)F(R) = S[/mm]. Aus einem Satz in
> meinem Skript weiß ich, dass [mm]S = ^X / _{R_S}[/mm], also [mm]F(R_S) = ^X / _{R_S} = S[/mm].
Viele Grüße
Tobias
|
|
|
|
