Äquiv,Ordnungsrelation < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:51 Mi 06.02.2013 | | Autor: | Coup |
| Aufgabe | Sei M eine Menge und P(M) die Potenzmenge von M.
Untersuche, ob die Relation R c P(M) x P(M) , UTV [mm] \gdw [/mm] U [mm] \subseteq [/mm] V
eine Äquivalenz oder Ordnungsrelation auf P(M) ist. |
Hi !
Die Begriffe sind mir denke ich klar.
Um differenzieren zu können muss ich ja eigentlich nur schauen ob gegen Symmetrie oder Antisymmetrie verstoßen wird, da dies ja die einzigen Unterschiede bezüglich Ordnungs und Äquivalenzrelation sind oder ?
Also Transitivität ist ja ( sollte doch) :
Seien UTV [mm] \in [/mm] P(M) [mm] \Rightarrow [/mm] U [mm] \subseteq [/mm] T ^ T [mm] \subseteq [/mm] V [mm] \Rightarrow [/mm] U [mm] \subseteq [/mm] V
aber betrachte ich mir die Definition der Antisymmetrie von Ordnungsrelationen
gilt ja xRy^yRx [mm] \Rightarrow [/mm] x=y
Und hier sehe ich einen Widerspruch.
Die Relation kann Symmetrisch sein, denn xRy [mm] \gdw [/mm] yRx. U [mm] \subseteq [/mm] V und umgekehrt aber nicht antisymmetrisch.
Liege ich völlig daneben oder gehts in die richtige Richtung ?
lg
Micha
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:22 Mi 06.02.2013 | | Autor: | Marcel |
Hallo,
> Sei M eine Menge und P(M) die Potenzmenge von M.
> Untersuche, ob die Relation R c P(M) x P(M) , UTV [mm]\gdw[/mm] U
> [mm]\subseteq[/mm] V
da steht sicher
$$U [mm] \; \red{\text{R}}\ \; [/mm] V [mm] \iff [/mm] U [mm] \subseteq [/mm] V$$
> eine Äquivalenz oder Ordnungsrelation auf P(M) ist.
> Hi !
> Die Begriffe sind mir denke ich klar.
> Um differenzieren zu können muss ich ja eigentlich nur
> schauen ob gegen Symmetrie oder Antisymmetrie verstoßen
> wird, da dies ja die einzigen Unterschiede bezüglich
> Ordnungs und Äquivalenzrelation sind oder ?
Na, generell hast Du einfach Axiome nachzuprüfen! Ich kann Dir aber
schonmal sagen, dass es KEINE ÄR ist:
$X [mm] \subseteq [/mm] X$ gilt zwar für alle $X [mm] \in P(M)\,,$ [/mm] also ist [mm] $R\,$ [/mm] reflexiv.
Und auch die Transitivität folgt wegen
[mm] $(\*)$ [/mm] $X [mm] \subseteq [/mm] Y$ und $Y [mm] \subseteq [/mm] Z$ [mm] $\Rightarrow$ [/mm] $X [mm] \subseteq Z\,.$
[/mm]
(Genauer: Wenn $X [mm] \text{ R }Y$ [/mm] gilt, d.h. wenn $X,Y [mm] \in [/mm] P(M)$ mit $X [mm] \subseteq [/mm] Y$
existieren, und wenn zudem $Y [mm] \text{ R }Z$ [/mm] gilt, d.h. wenn zudem ein $Z [mm] \in [/mm] P(M)$ mit $Y [mm] \subseteq [/mm] Z$
existiert, dann folgt auch $X [mm] \text{ R }Z$ [/mm] wegen $X [mm] \subseteq [/mm] Z$ gemäß [mm] $(\*)$!)
[/mm]
Aber wie sieht's denn mit der Symmetrie aus, etwa wenn $M [mm] \not=\emptyset$:
[/mm]
Sicherlich gilt dann doch [mm] $\emptyset \text{ R }M\,,$ [/mm] denn es gilt ja [mm] $\emptyset \subseteq M\,.$ [/mm]
Aber gilt auch $M [mm] \text{ R }\emptyset$? [/mm] (Beachte $M [mm] \not=\emptyset\,.$)
[/mm]
> Also Transitivität ist ja ( sollte doch) :
Eigentlich habe ich das ja schon oben geschrieben, aber dann hier nochmal:
> Seien UTV [mm]\in[/mm] P(M)
Oo, bitte mitte Komma trennen: UTV würde man als $U [mm] \cdot [/mm] T [mm] \cdot [/mm] V$ lesen,
und dann wäre die Frage, wie [mm] $\cdot$ [/mm] definiert wäre (zudem sollte dann
die Assoziativität bzgl. des [mm] $\cdot$ [/mm] dabei gelten).
> [mm]\Rightarrow[/mm] U [mm]\subseteq[/mm] T ^ T
> [mm]\subseteq[/mm] V
Vorsicht: Aus $U,T,V [mm] \in [/mm] P(M)$ folgt erst mal gar nichts, außer $U [mm] \subseteq [/mm] M, T [mm] \subseteq [/mm] M$ und $V [mm] \subseteq M\,.$ [/mm]
Die sollen nun zudem
$$U [mm] \text{ R }T$$
[/mm]
und
$$T [mm] \text{ R }V$$
[/mm]
erfüllen (das ist eine VORAUSSETZUNG!), und dann kannst Du so
weitermachen:
> [mm]\Rightarrow[/mm] U [mm]\subseteq[/mm] T ^ T
> [mm]\subseteq[/mm] V
Das ^ kannst Du [mm] $\wedge$ [/mm] schreiben (fahr' mit der Maus über das Symbol!)
> [mm]\Rightarrow[/mm] U [mm]\subseteq[/mm] V
>
> aber betrachte ich mir die Definition der Antisymmetrie von
> Ordnungsrelationen
> gilt ja xRy^yRx [mm]\Rightarrow[/mm] x=y
> Und hier sehe ich einen Widerspruch.
> Die Relation kann Symmetrisch sein, denn xRy [mm]\gdw[/mm] yRx. U
> [mm]\subseteq[/mm] V und umgekehrt aber nicht antisymmetrisch.
>
> Liege ich völlig daneben oder gehts in die richtige
> Richtung ?
Ich sehe da überhaupt keinen Widerspruch zur Antisymmetrie:
Sind $X,Y [mm] \in [/mm] P(M)$ derart, dass
sowohl $X [mm] \text{ R }Y$ [/mm] als auch $Y [mm] \text{ R }X$
[/mm]
gilt, so gelten doch:
$X [mm] \text{ R }Y \Rightarrow [/mm] X [mm] \subseteq [/mm] Y$ und $Y [mm] \text{ R }X \Rightarrow [/mm] Y [mm] \subseteq X\,.$
[/mm]
Aus $X [mm] \subseteq [/mm] Y$ und $Y [mm] \subseteq [/mm] X$ (kurz: $X [mm] \subseteq [/mm] Y [mm] \subseteq [/mm] X$) folgt dann aber [mm] $X=X\,.$
[/mm]
In der Tat gilt also
$X [mm] \text{ R } [/mm] Y$ und $Y [mm] \text{ R }X$ $\Rightarrow$ $X=X\,.$
[/mm]
P.S. Man beacht übrigens die Unterschiede in der Definition - etwa beim Begriff der ÄR (Äquivalenzrelation) [mm] $\sim$ [/mm] auf einer Menge [mm] $M\,$:
[/mm]
Bei der Refelexivität steht: Für alle $x [mm] \in [/mm] M$ muss $x [mm] \sim [/mm] x$ gelten!
Bei etwa der Transitivität steht: Falls $x,y,z [mm] \in [/mm] M$ SO EXISTIEREN, DASS
SOWOHL $x [mm] \sim [/mm] y$ ALS AUCH $y [mm] \sim [/mm] z$ gilt, dann muss $x [mm] \sim [/mm] z$ gelten!
So gibt's oft die Aufgabe: Was ist an folgender Überlegung falsch?
Aussage: Jede symmetrische und transitive Relation ist stets reflexiv.
Beweis: Aus $x [mm] \sim [/mm] y$ folgt wegen der Symmetrie $y [mm] \sim [/mm] x$ und damit wegen der
Transitivität $x [mm] \sim x\,.$
[/mm]
Die Überlegung ist richtig: Was ist aber das Entscheidende, was hierbei
nicht berücksichtigt wird - bzw. anders gefragt: Wieso ist der Beweis
"nicht vollständig zu Ende gedacht"?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:51 Mi 06.02.2013 | | Autor: | Coup |
Hi Marcel,
Danke für die umfassende Antwort.
In der alten Klausuraufgabe stand tatsächlich UTV.
Ich wusste nichtmehr genau, dass bzgl. der AntiSymmetrie gilt das wenn U [mm] \subseteq [/mm] V [mm] \wedge [/mm] V [mm] \subseteq [/mm] U [mm] \Rightarrow [/mm] U=V
Somit wird einiges klarer. Ich danke dir
> >So gibt's oft die Aufgabe: Was ist an folgender Überlegung falsch?
> >Aussage: Jede symmetrische und transitive Relation ist stets reflexiv.
> >Beweis: Aus folgt wegen der Symmetrie und damit wegen der
> >Transitivität
Ich weis nicht genau..
Müsste nicht demnach automatisch sofern Reflexivität und Transitivität erfüllt ist auch die Symmetrie folgen ? Das MUSS ja nicht zwingen sein. Es kann ja auch Antisymmetrisch sein.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:00 Mi 06.02.2013 | | Autor: | Marcel |
Hallo,
> Hi Marcel,
> Danke für die umfassende Antwort.
> In der alten Klausuraufgabe stand tatsächlich UTV.
das ist aber Quatsch, es sei denn, die Relation würde [mm] $T\,$ [/mm] heißen!
> Ich wusste nichtmehr genau, dass bzgl. der AntiSymmetrie
> gilt das wenn U [mm]\subseteq[/mm] V [mm]\wedge[/mm] V [mm]\subseteq[/mm] U
> [mm]\Rightarrow[/mm] U=V
Wann sind denn zwei Mengen [mm] $A,B\,$ [/mm] gleich? Genau dann, wenn...?
> Somit wird einiges klarer. Ich danke dir
>
>
> > >So gibt's oft die Aufgabe: Was ist an folgender
> Überlegung falsch?
> > >Aussage: Jede symmetrische und transitive Relation ist
> stets reflexiv.
> > >Beweis: Aus folgt wegen der Symmetrie und damit wegen
> der
> > >Transitivität
>
> Ich weis nicht genau..
> Müsste nicht demnach automatisch sofern Reflexivität und
> Transitivität erfüllt ist auch die Symmetrie folgen ?
![[haee]](/images/smileys/haee.gif "[haee]") Wie sollte das denn gehen?
> Das
> MUSS ja nicht zwingen sein. Es kann ja auch Antisymmetrisch
> sein.
Was ist "es"? Und (zweistellige) Relationen können vieles sein, sonst bräuchte
man wohl nicht mehr als den Begriff der zweistelligen Relation.
Das SYMMETRISCHE und TRANSITIVE zweistellige Relationen nicht notwendig
schon reflexiv sein müssen, abgesehen von der Tatsache, dass man sich
auch ein Beispiel basteln kann, erkennt man, wenn man sich mal den
"Beweis" komplett hinschreibt, der oben geführt wurde.
Zu zeigen ist dort nämlich: Für ALLE $x [mm] \in [/mm] M$ gilt $x [mm] \sim x\,.$
[/mm]
Im Beweis wird aber nur gezeigt:
Wenn es $x,y [mm] \in [/mm] M$ so gibt, dass $x [mm] \sim y\,,$ [/mm] dann muss auch $x [mm] \sim [/mm] x$
gelten.
Dies' kann das "zu zeigende" nicht gänzlich bewiesen haben, weil es doch
durchaus auch ein $x [mm] \in M\,$ [/mm] geben kann, dass in [mm] $\sim$ [/mm] "nirgends auftaucht".
(Das ist jetzt 'grob formuliert'!)
Beispiel:
[mm] $M:=\{1,2,3\}$ [/mm] und [mm] $\sim:=\{(1,2),(2,1),(1,1),(2,2)\}$
[/mm]
Warum ist [mm] $\sim\,$ [/mm] sowohl symmetrisch als auch transitiv, aber KEINESWEGS reflexiv?
P.S. Beachte auch, dass man für $a,b [mm] \in [/mm] M$ notiert: $a [mm] \sim [/mm] b [mm] {\;\;\;:\!\! \iff} \;\;(a,b) \in \sim\,.$ [/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:17 Mi 06.02.2013 | | Autor: | Coup |
Du hast ja das ALLE besonders hervorgehoben.
Demnach nehme ich an es bezieht sich auf die 3.
Also x [mm] \in [/mm] M als 3 taucht halt nicht in der Relation auf ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:19 Mi 06.02.2013 | | Autor: | Marcel |
Hallo,
> Du hast ja das ALLE besonders hervorgehoben.
> Demnach nehme ich an es bezieht sich auf die 3.
> Also x [mm]\in[/mm] M als 3 taucht halt nicht in der Relation auf
> ?
ich frage jetzt einfach mal anders: Welches Paar müßte denn in [mm] $M\,$ [/mm] noch
stehen, damit [mm] $M\,$ [/mm] (wenigstens) reflexiv wäre?
P.S. Was würdest Du übrigens zu folgender Behauptung sagen: Ist [mm] $\sim$
[/mm]
eine (zweistellige) Relation auf [mm] $M\,$ [/mm] derart, dass [mm] $\sim$ [/mm] sowohl symmetrisch
als auch transitiv ist und gilt zudem: Für alle $m [mm] \in [/mm] M$ gibt es ein $n [mm] \in [/mm] M$
so, dass $(m,n) [mm] \in \sim\,$ [/mm] (bzw. $m [mm] \sim [/mm] n$).
Dann gilt: [mm] $\sim$ [/mm] auch reflexiv,;also ist [mm] $\sim$ [/mm] eine ÄR.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:21 Mi 06.02.2013 | | Autor: | Coup |
(3,3) würd ich sagen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:26 Mi 06.02.2013 | | Autor: | Marcel |
Hallo,
> (3,3) würd ich sagen
genau. Und es gibt halt kein Paar $(a,b) [mm] \in \;\sim\;:=\,\{(1,2),(2,1),(1,1),(2,2)\}$ [/mm]
so, dass [mm] $a=3\,$ [/mm] oder [mm] $b=3\,.$ [/mm] Hätte ich nun etwa $(3,1)$ in [mm] $\sim$ [/mm] noch
aufgenommen, dann hätte ich auch, wenn die Symmetrie erhalten bleiben
soll, [mm] $(1,3)\,$ [/mm] aufnehmen müssen, und wenn ich die Transitivität dann
erhalten will, müsste schlussendlich auch [mm] $(3,3)\,$ [/mm] aufgenommen werden
[mm] ($(1,1)\,$ [/mm] war ja eh schon vorhanden)...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:37 Mi 06.02.2013 | | Autor: | Coup |
Ich danke dir .
Mathenachhilfe online ist toll und du machst das super !
lg
|
|
|
|
