Auf Äquivalenzrelation prüfen < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:44 So 09.11.2014 | | Autor: | Ceriana |
| Aufgabe | Entscheide jeweils, ob folgende Relation R auf X reflexiv, symmetrisch und/oder transitiv sind und bestimme im Fall einer Äquivalenzrealtion alle Äquivalenzklassen.
a) Es sei M eine nicht-leere Menge und X := P(M) ihre Potenzmenge. Wir definieren die Relation R := [mm] \{(A, B) \in X\times{X} | A \cap B = \emptyset\}
[/mm]
b) Es sei M eine nicht-leere Menge und X := {f: M [mm] \to [/mm] M bijektiv}. Wir definieren die Relation R := [mm] \{(f, g) \in X\times{X} | f \circ g^{-1} = \mbox{id}_{M}\} [/mm] |
Hallo,
diesmal geht es bei mir um Relationen.
zu a):
Grundsätzlich komme ich mit den Begriffen reflexiv, symmetrisch und transitiv klar.
Für die Reflexivität muss zu jedem x [mm] \in [/mm] M ein Element y [mm] \in [/mm] R mit (x, x) existieren. Zuerst: Stimmt diese Definition? Bei der betrachteten Relation ergibt sich aber das Problem, dass A [mm] \cap [/mm] B nur die leere Menge [mm] \emptset [/mm] ergeben darf. Das heißt nach meinem Verständnis, dass die Potenzmenge zwar die Paare (x, x) oder Paare, mit sich überschneidenden Mengen enthält (immer), aber durch die Selektion A [mm] \cap [/mm] B die beiden Elemente des Paares keine gleichen Elemente enthalten dürfen. Damit ist die Relation R nicht reflexiv.
Damit eine Relation symmetrisch ist, muss für jedes (x, y) [mm] \in [/mm] R auch (y, x) [mm] \in [/mm] R gelten. Das gilt, weil durch das kartesische Produkt der Potenzmenge alle möglichen Kombinationen existieren. Selbst die durch die Bedingung A [mm] \cap [/mm] B ausgeschlossenen Elemente erfülle diese Bedingung (irrelevant).
Für die Transitivität muss für jedes a, b, c [mm] \in [/mm] M gelten, dass (a, b) [mm] \in [/mm] R und (b, c) [mm] \in [/mm] R. Da weiß ich ehrlichgesagt nicht wirklich wie ich vorgehen soll, ich habe mir zum "Testen" eine Grundmenge M = {1, 2} genommen, davon die Potenzmenge gebildet und nacheinander alle Elemente rausgestrichen, die die Bedingung A [mm] \cap [/mm] B = [mm] \emptyset [/mm] nicht erfüllen. Bei den übrigen kann ich die Transitivität nicht finden.
(Ich hoffe meine Darstellung war verständlich.)
Da mind. 1 Kriterium nicht erfüllt ist, ist R keine Äquivalenzrelation.
Jetzt habe ich zum Herausfinden der Eigenschaften immer mit einer Testmenge M = {1, 2} gearbeitet. Aber wie geht man vor, wenn man das im allgemeinen Fall entscheiden muss?
zu b):
Hier muss ich leider zugeben, dass ich absolut keinerlei Ansätze habe. Kann mir jemand erklären, woher das g kommt, und was genau die Bedingung für die Relation ist? Damit komme ich garnicht klar.
Vielen Dank,
Ceriana
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:05 Mo 10.11.2014 | | Autor: | Marcel |
Hallo,
> Entscheide jeweils, ob folgende Relation R auf X reflexiv,
> symmetrisch und/oder transitiv sind und bestimme im Fall
> einer Äquivalenzrealtion alle Äquivalenzklassen.
>
> a) Es sei M eine nicht-leere Menge und X := P(M) ihre
> Potenzmenge. Wir definieren die Relation R := [mm]\{(A, B) \in X\times{X} | A \cap B = \emptyset\}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> b) Es sei M eine nicht-leere Menge und X := {f: M [mm]\to[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
M
> bijektiv}. Wir definieren die Relation R := [mm]\{(f, g) \in X\times{X} | f \circ g^{-1} = \mbox{id}_{M}\}[/mm]
>
>
> Hallo,
>
> diesmal geht es bei mir um Relationen.
>
> zu a):
>
> Grundsätzlich komme ich mit den Begriffen reflexiv,
> symmetrisch und transitiv klar.
>
> Für die Reflexivität muss zu jedem x [mm]\in[/mm] M ein Element y
> [mm]\in[/mm] R mit (x, x) existieren.
das macht keinen Sinn.
> Zuerst: Stimmt diese Definition?
Die Definition lautet hier: Für alle $x [mm] \in [/mm] X=P(M)$ muss
$(x,x) [mm] \in [/mm] R$
sein.
> Bei der betrachteten Relation ergibt sich aber
> das Problem, dass A [mm]\cap[/mm] B nur die leere Menge [mm]\emptset[/mm]
> ergeben darf. Das heißt nach meinem Verständnis, dass die
> Potenzmenge zwar die Paare (x, x) oder Paare, mit sich
> überschneidenden Mengen enthält (immer), aber durch die
> Selektion A [mm]\cap[/mm] B die beiden Elemente des Paares keine
> gleichen Elemente enthalten dürfen. Damit ist die Relation
> R nicht reflexiv.
Was Du da mit überschneidenden Mengen bei Reflexivität sagen willst, weiß
ich nicht. Aber: Für $x [mm] \not=\varnothing$ [/mm] ist
$x [mm] \cap [/mm] x=x [mm] \not=\varnothing$ [/mm] und daher $(x,x) [mm] \textbf{ ? }R$ [/mm]
(Ergänze das [mm] $\textbf{ ?}$ [/mm] bitte!)
Beachte übrigens: $x [mm] \in P(M)\,,$ [/mm] d.h. oben ist [mm] $x\,$ [/mm] eine TEILMENGE von [mm] $M\,.$ [/mm] Du
kannst aber auch ein anderes Symbol verwenden, wenn Du magst...
> Damit eine Relation symmetrisch ist, muss für jedes (x, y)
> [mm]\in[/mm] R auch (y, x) [mm]\in[/mm] R gelten. Das gilt, weil durch das
> kartesische Produkt der Potenzmenge alle möglichen
> Kombinationen existieren.
Das Argument verstehe ich nicht. Ich sehe das so:
Sei $(x,y) [mm] \in R\,.$ [/mm] Dann ist
$x [mm] \in [/mm] P(M)$ und $y [mm] \in [/mm] P(M)$ und $x [mm] \cap y=\varnothing\,.$
[/mm]
(Dass das alles gilt, folgt aus der Voraussetzung!)
Was haben wir zu zeigen, um $(y,x) [mm] \in [/mm] R$ einzusehen? Es sind die Bedingungen
$y [mm] \in [/mm] P(M)$ und $x [mm] \in [/mm] P(M)$ und $y [mm] \cap x=\varnothing$
[/mm]
zu prüfen!
> Selbst die durch die Bedingung A
> [mm]\cap[/mm] B ausgeschlossenen Elemente erfülle diese Bedingung
> (irrelevant).
?
> Für die Transitivität muss für jedes a, b, c [mm]\in[/mm] M
> gelten, dass (a, b) [mm]\in[/mm] R und (b, c) [mm]\in[/mm] R. Da weiß ich
> ehrlichgesagt nicht wirklich wie ich vorgehen soll, ich
> habe mir zum "Testen" eine Grundmenge M = {1, 2} genommen,
> davon die Potenzmenge gebildet und nacheinander alle
> Elemente rausgestrichen, die die Bedingung A [mm]\cap[/mm] B =
> [mm]\emptyset[/mm] nicht erfüllen. Bei den übrigen kann ich die
> Transitivität nicht finden.
>
> (Ich hoffe meine Darstellung war verständlich.)
Ne, da weiß ich gar nicht, was Du sagen willst. Es ist zu zeigen, dass stets aus
[mm] $(a,\red{b}) \in [/mm] R$ und [mm] $(\red{b},c) \in [/mm] R$ auch $(a,c) [mm] \in [/mm] R$
folgt. (Durch Übereinanderlegen der roten b's lösen sich diese auf und verschmelzen
die beiden Paare zu einem; wenn Du da eine bildliche Vorstellung haben
willst.)
Für
$(a,b) [mm] \in [/mm] R$ folgt $a [mm] \in P(M)\,,$ [/mm] $b [mm] \in [/mm] P(M)$ und $a [mm] \cap b=\varnothing\,.$
[/mm]
Für
$(b,c) [mm] \in [/mm] R$ folgt $b [mm] \in P(M)\,,$ [/mm] $c [mm] \in [/mm] P(M)$ und $b [mm] \cap c=\varnothing\,.$
[/mm]
Nun gilt hier nach Def. von [mm] $R\,$
[/mm]
$(a,c) [mm] \in [/mm] R$ [mm] $\iff$ [/mm] ($a [mm] \in P(M)\,,$ [/mm] $c [mm] \in [/mm] P(M)$ und $a [mm] \cap c=\varnothing$).
[/mm]
Was wäre also noch zu zeigen, wenn [mm] $R\,$ [/mm] transitiv wäre?
(Hinweis: Betrachte aber mal
[mm] $M=\{1,2,3,4,5\}$
[/mm]
und [mm] $a:=\{1,2\}, b:=\{3\}$ [/mm] und [mm] $c:=\{1,4\}\,.$)
[/mm]
> Da mind. 1 Kriterium nicht erfüllt ist, ist R keine Äquivalenzrelation.
Okay. Von Deinen Begründungen her konnte ich aber nur bei der ersten
einen Hauch von Korrektheit erkennen.
> Jetzt habe ich zum Herausfinden der Eigenschaften immer mit
> einer Testmenge M = {1, 2} gearbeitet. Aber wie geht man
> vor, wenn man das im allgemeinen Fall entscheiden muss?
Naja, von der Aufgabenstellung her ist die Frage, ob das für jede beliebige
Menge gilt. Du kannst da durchaus mit der Testmenge argumentieren, dass
man mit dieser sieht, was i.a. nicht(!) gilt (Reflexivität etwa). (Die Symmetrie,
die ja immer gilt, kannst Du nicht nur mit der Testmenge beweisen - da muss
ein allgemeingültiger Beweis her!)
Und generell kannst Du natürlich gucken:
Wie sieht die Aussage für [mm] $M=\varnothing$ [/mm] aus? (Dort haben wir nämlich
eine ÄR!)
Wie sieht die Aussage für $M [mm] \not=\varnothing$ [/mm] aus. (Bei manchen Aufgaben
muss man dann aufpassen: evtl. hängt die Aussage von der "Größe" im
Sinne von "Anzahl der Elemente" der Menge [mm] $M\,$ [/mm] ab!)
> zu b):
>
> Hier muss ich leider zugeben, dass ich absolut keinerlei
> Ansätze habe. Kann mir jemand erklären, woher das g
> kommt, und was genau die Bedingung für die Relation ist?
> Damit komme ich garnicht klar.
Du hast $M [mm] \not=\varnothing$ [/mm] und
[mm] $X=\{f \colon M \to M \text{ bijektiv}\}$
[/mm]
als die Menge der bijektiven Selbstabbildungen von [mm] $M\,.$ [/mm]
Nun ist
[mm] $R:=\{(f,g) \in X \times X \mid f \circ g^{-1}=\text{id}_M\}$
[/mm]
mit
[mm] $\text{id}_M \colon [/mm] M [mm] \to [/mm] M$ ist definiert durch [mm] $\text{id}_M(x):=x$ [/mm] für alle $x [mm] \in M\,.$
[/mm]
Es gilt daher nun:
$(u,v) [mm] \in [/mm] R$
[mm] $\iff$ [/mm] ($(u,v) [mm] \in [/mm] X [mm] \times [/mm] X$ mit $u [mm] \circ v^{-1}=\text{id}_M$)
[/mm]
[mm] $\iff$ [/mm] ($u [mm] \in [/mm] X$ und $v [mm] \in [/mm] X$ mit $u [mm] \circ v^{-1}=\text{id}_M$)
[/mm]
[mm] $\iff$ ($u,v\,$ [/mm] sind bijektive Abbildungen $M [mm] \to [/mm] M$ mit $u [mm] \circ v^{-1}=\text{id}_M\,.$)
[/mm]
Beachte dabei: $v [mm] \in [/mm] X$ liefert
$v [mm] \colon [/mm] M [mm] \to [/mm] M$ ist bijektiv
[mm] $\Rightarrow$ $\exists v^{-1} \colon [/mm] M [mm] \to [/mm] M$ mit $v [mm] \circ v^{-1}=v^{-1} \circ v=\text{id}_M\,.$
[/mm]
Zu wissen, dass ein bijektives $v [mm] \colon [/mm] M [mm] \to [/mm] M$ auch eine Umkehrabbildung
[mm] $v^{-1} \colon [/mm] M [mm] \to [/mm] M$ hat, ist oben schon sinnvoll, damit man weiß, dass man
für $u,v [mm] \in [/mm] X$ auch
$u [mm] \circ v^{-1} \colon [/mm] M [mm] \to [/mm] M$
überhaupt hinschreiben darf.
P.S. Die Reflexivität ist hier klar (warum?). Ich zeige Dir mal, wie man die
Symmetrie behandelt:
Sei $(f,g) [mm] \in R\,.$ [/mm] Dann gilt
$f,g [mm] \colon [/mm] M [mm] \to [/mm] M$ sind bijektiv und $f [mm] \circ g^{-1}=\text{id}_M\,.$
[/mm]
Um die Wahrheit der Aussage
$(g,f) [mm] \in [/mm] R$
beurteilen zu können, haben wir zu prüfen, ob alles folgende gilt:
Sind $g,f [mm] \colon [/mm] M [mm] \to [/mm] M$ bijektiv und ist $g [mm] \circ f^{-1}=\text{id}_M$?
[/mm]
Wegen $f,g [mm] \in [/mm] X$ haben wir $g,f [mm] \colon [/mm] M [mm] \to [/mm] M$ beide bijektiv. Weiter gilt
[mm] $(\text{id}_M)^{-1}=\text{id}_M\,.$ [/mm] (Warum?)
Es folgt somit
[mm] $\text{id}_M=(\text{id}_M)^{-1}=(f \circ g^{-1})^{-1}\,.$
[/mm]
Jetzt Du (beachte, dass wir zu $g [mm] \circ f^{-1}=\text{id}_M$ [/mm] hinwollen, wenn das
geht - beachte dabei auch Rechenregeln aus der Algebra, die Du mal
kennengelernt hast: [mm] $(ab)^{-1}=b^{-1}a^{-1}$ [/mm] und [mm] $(a^{-1})^{-1}=a\,.$
[/mm]
Unter welchen (genauen) Voraussetzungen sowas gilt, kannst Du nachschlagen...)
Wenn Du das hinbekommen hast: Schreibe mal genau hin, was man bei
der Transitivität zu tun hat...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 04:44 Mo 10.11.2014 | | Autor: | tobit09 |
Hallo Marcel!
> > a) Es sei M eine nicht-leere Menge und X := P(M) ihre
> > Potenzmenge. Wir definieren die Relation R := [mm]\{(A, B) \in X\times{X} | A \cap B = \emptyset\}[/mm]
> Und generell kannst Du natürlich gucken:
> Wie sieht die Aussage für [mm]M=\varnothing[/mm] aus? (Dort haben
> wir nämlich
> eine ÄR!)
Diese Fallunterscheidung hat einem der Aufgabensteller erspart, indem er M als nichtleer vorausgesetzt hat.
Viele Grüße
Tobias
|
|
|
|
