Durchschnitt Äquivalenzrelationen

17.04.2006, 19:42

Paul_H

Durchschnitt Äquivalenzrelationen

Hallo, ich soll etwas beweisen, was, glaub' ich, jeder mal beweisen musste, der das Wort Äquivalenzrelation schon mal gehört hat.
Und zwar, dass der Durchschnitt zweier Äquivalenzrelationen wieder eine Äquivalenzrelation ist.

Nun hab ich das mal, so wie ich denke der Beweis aussehen soll, einfach mal so runtergeschrieben. Jetzt frag ich euch, ob das auch wirklich so gehört, ich damit die Behauptung bewiesen habe oder ob das total falsch ist und ich doch Relationen gedanklich zu sehr mit Mengen unter einen Hut stecke.

$\begin{eqnarray*} R_1, R_1 \end{eqnarray*}$ seien Äquivalenzrelationen auf M.

$\begin{eqnarray*} \forall a \in M: a R_1 a \wedge a R_2 a \rightarrow a R_1 \cap R_2 a \end{eqnarray*}$ Reflexivität.

$\begin{eqnarray*} \forall a,b \in M: a R_1 b \rightarrow b R_1 a \wedge a R_2 b \rightarrow b R_2 a \end{eqnarray*}$ , also auch $\begin{eqnarray*} a R_1 \cap R_2 b \rightarrow b R_1\cap R_2 a \end{eqnarray*}$ , Symmetrie.

$\begin{eqnarray*} \forall a,b,c \in M: (a R_1 b \wedge b R_1 c) \rightarrow a R_1 c \wedge \end{eqnarray*}$

$\begin{eqnarray*} (a R_2 b \wedge b R_2 c) \rightarrow a R_2 c \end{eqnarray*}$ , also auch

$\begin{eqnarray*} (a R_1 \cap R_2 b \wedge b R_1 \cap R_2 c) \rightarrow a R_1 \cap R_2 c \end{eqnarray*}$ , Transitivität

Ach ja, ein Aufgabenteil war noch, dass ich zu der Menge {1,2,3} zwei Äquivalenzrelationen finden soll, so dass die Vereinigung dieser wieder eine Äquivalenzrelation ist. Muss ich dabei die Menge der Tupel angeben, die diese Bedingung erfüllt, oder eine äquivalente Operation angeben?

Danke für Tipps und Ratschläge.

17.04.2006, 22:13

Paul_H

Auf diesen Beitrag antworten »

Zum zweiten Teil der Aufgabe habe ich nun folgende Äquivalenzrelationen gefunden:

$\begin{eqnarray*} R_1 := \{(1,1),(2,2),(3,3),(1,2),(2,1)\} \end{eqnarray*}$

$\begin{eqnarray*} R_2 := \{(1,1),(2,2),(3,3),(2,3),(3,2),(1,3),(3,1)\} \end{eqnarray*}$

$\begin{eqnarray*} R_1 \cup R_2 := \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)\}. \end{eqnarray*}$

Haut das so hin?

18.04.2006, 01:16

JochenX

Auf diesen Beitrag antworten »

Zitat:

Ach ja, ein Aufgabenteil war noch, dass ich zu der Menge {1,2,3} zwei Äquivalenzrelationen finden soll, so dass die Vereinigung dieser wieder eine Äquivalenzrelation ist.

wähle doch noch einfacher R1=R2 oder R1 Teilmenge R2 oder so....

dein Beispiel: R2 ist nicht transitiv. (1,2)?

zu deinem Beweis: evtl. meinst du das rechte, aber was da steht, kann nicht das wahre sein....

gehe so vor: sei R der Schnitt zweier Äquirels R1,R2 (also ein Schnitt zweier Teilmengen von MxM für die Grundmenge M)
sei a in M: R1, R2 sind reflexiv, also ist (a,a) in beiden drin
=> (a,a) in R => R reflexiv

usf.

18.04.2006, 15:09

Paul_H

Auf diesen Beitrag antworten »

Zitat:

Original von LOED
dein Beispiel: R2 ist nicht transitiv. (1,2)?

Hmm, dann müsste ja $\begin{eqnarray*} R_1 \end{eqnarray*}$ genauso falsch sein.

Die Def. für Transitivität lautet ja wie folgt:

$\begin{eqnarray*} \forall a,b,c \in M: (aRb \wedge bRc) \rightarrow aRc \end{eqnarray*}$

Nun dachte ich, es heisse dies:

Gibt es a,b,c, für die gilt: $\begin{eqnarray*} aRb \wedge bRc \end{eqnarray*}$ ,

dann muss für sie auch gelten: $\begin{eqnarray*} aRc. \end{eqnarray*}$

Deines Beitrags nach zufolge, heisst es aber eher das:

Für alle a,b,c MUSS gelten: $\begin{eqnarray*} aRb \wedge bRc. \end{eqnarray*}$

Daraus folgt dann $\begin{eqnarray*} aRc \end{eqnarray*}$

Wenn das so stimmt, gibt es aber nur eine einzige Äquivalenzrelation auf M:={1,2,3}, nämlich R:={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)}.

Denn nur dann ist diese symmetrisch, reflexiv und transitiv. Das würde die Aufgabe meiner Meinung nach zu trivial erscheinen lassen. verwirrt

18.04.2006, 20:26

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von Paul_H
Deines Beitrags nach zufolge, heisst es aber eher das:

Für alle a,b,c MUSS gelten: $\begin{eqnarray*} aRb \wedge bRc. \end{eqnarray*}$

Daraus folgt dann $\begin{eqnarray*} aRc \end{eqnarray*}$

nö, das sage ich nirgendwo, deine Def. ist schon richtig

aber in R2 liegt eben (1,3) und (3,2)
also MÜSSTE auch (1,2) drinliegen
a=1, b=3, c=2

18.04.2006, 20:39

Paul_H

Auf diesen Beitrag antworten »

achso, jetzt verstehen was du meinen. Hammer

19.04.2006, 00:51

Ace Piet

Auf diesen Beitrag antworten »

Ich biete mal ff. (zur Gegenkorrektur) an.:

Sei *bla bla* $\begin{eqnarray*} M \neq \emptyset \end{eqnarray*}$ und $\begin{eqnarray*} \mathcal R := A^2 \subseteq M^2 \end{eqnarray*}$ ÄR mit diesen (gewissen) Eigenschaften.
Ist also $\begin{eqnarray*} \mathcal A \subseteq M^2 \end{eqnarray*}$ (sog. TrägerMenge) OHNE Eigenschaften, so ist:

$\begin{eqnarray*} \mathcal H (\mathcal A) := \bigcap_{\emptyset \neq \mathcal A \subseteq \mathcal R_{j}} ~\{ \text{ ÄR } \mathcal R_j \mid j \in J \} \end{eqnarray*}$ kleinste $\begin{eqnarray*} \mathcal A \end{eqnarray*}$ umfassende ÄR von M

Dabei: Die Bezeichnung $\begin{eqnarray*} \mathcal H \end{eqnarray*}$ erinnert mich an die VR-Hüllen-Eigenschaft...
Kleinstes scheint nach Konstrukt. klar.

Bew.:
(1) $\begin{eqnarray*} \forall ~j \in J \end{eqnarray*}$ ist $\begin{eqnarray*} \text{Diag} (M \times M) \subseteq \mathcal R_j \end{eqnarray*}$ , insb.: $\begin{eqnarray*} \mathcal H (\mathcal A) \not \supset \emptyset \end{eqnarray*}$ ... (R)
(2) Die (übl.) Reduktion auf Teilmengen:
Wenn $\begin{eqnarray*} \sim \end{eqnarray*}$ in $\begin{eqnarray*} \mathcal H (\mathcal A) \end{eqnarray*}$ gültig,
dann für jeden Index $\begin{eqnarray*} j \in J \end{eqnarray*}$ ,
dann gilt (S)+(T) für bel. IndexMenge J,
also auch für $\begin{eqnarray*} \mathcal H (\mathcal A) \end{eqnarray*}$ . ... #-(fertich)

Anwendung: *blub* Liesst sich für $\begin{eqnarray*} J := \{1,2\} \end{eqnarray*}$ so, daß $\begin{eqnarray*} \mathcal R_1 \cap \mathcal R_2 \end{eqnarray*}$ stets ÄR.

Darf DAS?
Edit: Alle \mathFRAK durch \mathCAL ersetzt (s.u.)

Wink

19.04.2006, 01:26

JochenX

Auf diesen Beitrag antworten »

deine altdeutschen Buchstaben bringen mich um Augenzwinkern

wieso eigentlich die Bezeichnung $\begin{eqnarray*} A^2 \end{eqnarray*}$ ? ist natürlich auch nur eine Bezeichnung, aber ich verstehe sie nicht.

zum Beweis:
1) ist korrekt (die Bezeichnung "Diag usf" ist mir das fremd, aber ich denke, es ist klar, was gemeint ist), hinten meinst du natürlich nicht "... ist KEINE OBERMENGE der leeren Menge", sondern einfach "UNGLEICH"
die einfache Formulierung überlassen wir hierbei natürlich Paul, bleibt auch da ein Einzeiler
2) überrascht mich ein wenig und da muss ich drüber nachdenken:
Symmetrie springt dabei eigentlich tatsächlich "fast" nebenbei ab, eine Formulierung für Paul wäre ja sowas wie "wenn (a,b) in der Schnitt-Rel liegt, dann liegt es in allen Einzelrels und somit liegt auch (b,a) in denen drin (weil die symmetrisch sind) und damit....."
Hmmm, auch die Transitivität folgt natürlich durch leichtes logisches Denken.....

Also ICH kann auf jeden Fall folgen (muss aber noch nachdenken, ist also eher als wenn du mir das Handwerkszeugs gibst, statt direkt zu beweisen *), was du meinst, mit Formulierungen wie "Die (übl.) Reduktion auf Teilmengen" würde ich aber in Zusammenhang mit gültigen Eigenschaften nicht bringen.
Immerhin sind diese Eigenschaften keine üblichen Mengeneigenschaften......

Gruß, Jochen

* hier sagt der Prof dann "Wieso das daraus folgt, ist eine leichte Übung"
für einen eigenen vollständigen Beweis halte ichs hier für etwas knapp...

19.04.2006, 02:42

Ace Piet

Auf diesen Beitrag antworten »

@LOED
Buchstaben sind doch SO knapp...

Die Elemente einer ÄR sind Paare (x,y) *äähh* woraus? - Das kommt so aus $\begin{eqnarray*} A \times A \end{eqnarray*}$ durch ein definiertes $\begin{eqnarray*} := \mathfrak A \end{eqnarray*}$ .

Mit dieser Buchstabenschelte stelle bitte mein $\begin{eqnarray*} \mathfrak H (\mathfrak A) \end{eqnarray*}$ mal (per LaTex) dar!?
(komm lass sehen...)

Ich wechsele nun mal gerne die Art der Buchstaben, wenn die Dim. der Mathe es nötigt... *sorry*

... snip

> 2) überrascht mich ein wenig
Überrascht mich.

Ich habe Deine Grp.-/ Untergrp.-Kriterien verfolgt (ungenannter Thread)... Lassen wir mal AbgeschlossenheitsKrit. (Prod. + Inv.) zur Seite... Verliert ein (Ass.G) + (ggfs. Komm.) seine Gültigkeit auf TEILMENGEN? - Ist die 1 vom Großen, was anderes "im Kleinen"? - nix nix nix. - Was bleibt zu prüfen? ... => *scheissdrecken* WENN-DANN.

Konsequenz: Man prüft $\begin{eqnarray*} \neq \emptyset \end{eqnarray*}$ UND Abgeschlossenheit von " $\begin{eqnarray*} \circ \end{eqnarray*}$ " und den Inversen. *peng* (letzteres kann man sich im endl.Fall kneifen - Stichwort: Es war nur eine Permutation)

Wink

_________________________

PS.: Danke. - Ich hätte keine Antwort erwartet.

19.04.2006, 02:57

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von Ace Piet
PS.: Danke. - Ich hätte keine Antwort erwartet.

bin jetzt sogar extra noch kurz im Netz geblieben, um deine Antwort noch zu lesen....

Zitat:

@LOED
Buchstaben sind doch SO knapp...

gibt ja nur 26 "normale" davon, dann zur Not das ganze in klein und sooo viele schöne griechische Buchstaben Augenzwinkern

Zitat:

Die Elemente einer ÄR sind Paare (x,y) *äähh* woraus? - Das kommt so aus $\begin{eqnarray*} A \times A \end{eqnarray*}$ durch ein definiertes $\begin{eqnarray*} := \mathfrak A \end{eqnarray*}$ .

das hast du aber schon allgemein durch "Teilmenge von MxM"=M^2.
hier von GANZ A^2 (mit einer gewählten Teilmenge A von R) zu reden ist doch irgendwie Unsinn!?
und so kommts mir halt rüber...... als sei jede (Äqui)Relation auf M GANZ AxA für ein A (Teilmenge M)....

Zitat:

Mit dieser Buchstabenschelte stelle bitte mein $\begin{eqnarray*} \mathfrak H (\mathfrak A) \end{eqnarray*}$ mal (per LaTex) dar!?
(komm lass sehen...)

wollte nicht schelten, aber dann dauerts eben länger bei mir (bin konservativ und doof!)
es hätte genauso auch H(A) heißen können..... smile

Zitat:

Ich wechsele nun mal gerne die Art der Buchstaben, wenn die Dim. der Mathe es nötigt... *sorry*

na gut, verziehen smile

=> mathematischer Teil:

Zitat:

> 2) überrascht mich ein wenig
Überrascht mich.

Ich habe Deine Grp.-/ Untergrp.-Kriterien verfolgt (ungenannter Thread)...

(usf.)
tatsächlich muss aber auch beim Untergruppenkriterium für die Teilmenge noch was nachgewiesen werden, alles fällt da leider nicht gleich ab.
Die Existenz der Inversen z.B. und sofort.
vergleiche ein wenig bei diesem Kriterium (danke für das Beispiel, das passt):
für alle a,b,c aus... gilt (a*b)*c=a*(b*c) überträgt sich
für alle x gibt es ein x' in .... (Zusatzbed., die die kleinere Menge nicht erfüllen muss!) mit xx'=e (neutrales El.) überträgt sich nicht.

Also sehe ich (wenn ich mich dumm stelle und das sollte man hier tun!) nicht, dass aus (a,b) und (b,c) in deiner Schnittrelation direkt auch von oben "(a,c) drin" übertragen wird.
ich sehs nicht...... wenn ich mir dann aber den Satz "(a,b) und (b,c) liegen in jedem ..... => (a,c) liegt in jedem ..... =>......" dazuschreibe, DANN wird's auch mir klar. smile

Gruß, Jochen und bedenke: alles nur meine bescheidene Meinung
ich tue mich einfach schwerst....

19.04.2006, 03:05

Poff

Auf diesen Beitrag antworten »

Ein Glück, dass ich das Zeug nicht lesen MUSS mir würde übel werden

Neue Frage »

Antworten »

Durchschnitt Äquivalenzrelationen

Verwandte Themen