Äquivalenzrelationen und Partitionen

16.03.2006, 22:34

ArminTempsarian

Äquivalenzrelationen und Partitionen

Guten Abend liebe Leute,

Ich habe da Probleme eine bestimmte Aussage meines Profs mit eindeutigem Sinn zu versehen. Und zwar den folgenden: "Jede Äquivalenzrelation auf M definiert eine Partition und umgekehrt kann man aus jeder Partition eine Äquivalenzrelation gewinnen."

Eine Partition von M ist doch eine Menge nichtleerer Teilmengen A1,...,An, für die gilt: 1. Die Vereinigung der Teilmengen = M und
2. sie sind paarweise disjunkt.

Wie definiert also eine Partition eine Äquivalenzrelation? Die Elemente der einzelnen Teilmengen müssen doch nicht in irgendeiner Äquvalenzrelation zueinander stehen.

z.B bilden die geraden vereinigt mit den ungeraden Zahlen eine Partition auf Z. Wo wird da eine Äquivalenzrelation definiert?

Umgekehrt versteh ich auch nicht,wie eine Äquiva... eine Partition definiert.

Vielleicht kann mir das ja jemand kurz erläutern.

16.03.2006, 23:07

Ben Sisko

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Partitionen

Zitat:

Original von ArminTempsarian
Die Elemente der einzelnen Teilmengen müssen doch nicht in irgendeiner Äquvalenzrelation zueinander stehen.

Genau so definierst du gerade deine Äquivalenzrelation. Zwei Elemente stehen genau dann in Relation, wenn sie in derselben Menge sind (zeig doch mal, dass das eine Äqrel. ist).
Andersrum bilden die Äquivalenzklassen die Teilmengen der Partition (sie sind disjunkt und ihre Vereinigung bilden die gesamte Menge).

Alles klar?

Gruß vom Ben

16.03.2006, 23:55

ArminTempsarian

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Partitionen
seh ich das so richtig?

Wenn M also irgendeine Menge mit ist und ~ irgendeine ÄRel. auf M.
Dann bilden die einzelnen Äquivalenzklassen die Partition von M?

Wenn z.B. M={a,b,c}, a und b sollen in irgendeiner ÄR stehen, d.h. die Äquivalenzklasse ist {a,b}; dann ist die Partition von M {{a,b},{c}}?!
Was ist mit {c}? Was ist das für eine Äquivalenzklasse? Mit was ist c äquivalent?

EDIT:Oder anders: Def. Äquivalenzklasse: Cm = x element in M; sodass x ÄqRel.y. Was ist mit den x, die nicht äq y sind, bilden die jeweils "Einer-Äq.Klassen"?

17.03.2006, 00:04

Abakus

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Partitionen

Zitat:

Original von ArminTempsarian
Was ist mit {c}? Was ist das für eine Äquivalenzklasse? Mit was ist c äquivalent?

Es gibt natürlich auch einelementige Äquivalenzklassen. c steht in Relation zu c wegen der Reflexivität.

Am besten führst du den Beweis einmal aus, dass jede Äquivalenzrelation eine Partition definiert und umgekehrt.

Grüße Abakus smile

17.03.2006, 00:09

ArminTempsarian

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Partitionen
OK das beantwortet dann wohl die Frage. Das mit der Reflexivität hab ich mir schon gedacht. (siehe Edit) Ich versuch mich dann mal an dem Beweis...

17.03.2006, 00:58

ArminTempsarian

Auf diesen Beitrag antworten »

OK.ich hab mir das jetzt angesehen. Ich hab zwar keinen richtigen Beweis, aber mal eine Skizze:

1. Dass eine Äqivalenzrelation eine Partition definiert, ist klar, weil ja Äquivalenzklassen genau jene Eigenschaften haben, die Partitionen definieren: also die Vereinigung der ÄKlassen A1,...,An=M
und alle Teilmengen sind disjunkt.

2. Für den Beweis, dass eine Partition eine ÄRel.~ definiert, muss ich mir doch ~ einfach nur so definieren, dass x~y, gdw. es einen Index i gibt, sodass x,y in Ai: also wenn x und y in irgendeiner Teilmenge von M sind, oder?!
Um die Reflexivität zu zeigen, genügt dann der Hinweis, dass die Teilmengen einer Partition nichtleer sein müssen, dass es also für a in M irgendeinen Index k geben muss, sodass a in Ak, weil A1vereinigtA2...Ak...An=M.

Aber wie zeige ich jetzt Symmetrie und Transitivität?

17.03.2006, 01:24

Ace Piet

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Partitionen
> Am besten führst du den Beweis einmal aus,
Ich auch üben wollen... (1 Std. gewartet)

(eine Richtung) $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$
Sei also $\begin{eqnarray*} \mathfrak M \neq \emptyset \end{eqnarray*}$ (beliebig) und mit $\begin{eqnarray*} \sim: \quad \mathfrak M^2 \to \mathfrak M \end{eqnarray*}$ eine ÄquivalenzRelation (ÄR) erklärt.
Dann ist $\begin{eqnarray*} \quad \mathfrak M = \bigcup_{a \in \mathfrak M } \{a\} \subseteq \bigcup_{a \in \mathfrak M } \lbrack a\rbrack \subseteq \bigcup_{a \in \mathfrak M } \mathfrak M = \mathfrak M \end{eqnarray*}$ (simple Inklusion).
Dabei sei $\begin{eqnarray*} \lbrack a\rbrack \end{eqnarray*}$ die zu a gehörige Äquivalenzklasse (ÄK), die wg. der Reflexivität mind. 1-elementig ist und für jeden Index zu $\begin{eqnarray*} \mathfrak M \end{eqnarray*}$ gehört, deshalb bislang... $\begin{eqnarray*} \mathfrak M &=& \bigcup_{a \in \mathfrak M } \lbrack a\rbrack \end{eqnarray*}$
...noch zu zeigen: ÄKs sind paarweise disjunkt.
Sei also $\begin{eqnarray*} b \in \lbrack a\rbrack \end{eqnarray*}$ , d.h. $\begin{eqnarray*} b \sim a \end{eqnarray*}$ . - Dann folgt aus der Transitivität und Symmetrie von $\begin{eqnarray*} \sim \end{eqnarray*}$ , daß für jedes $\begin{eqnarray*} x \sim b \end{eqnarray*}$ gilt $\begin{eqnarray*} a \sim x \sim b \end{eqnarray*}$ und umgekehrt, d.h. $\begin{eqnarray*} \lbrack a\rbrack = \lbrack b\rbrack \end{eqnarray*}$ . - ÄKs sind also gleich oder paarweise disjunkt (das ist dieses $\begin{eqnarray*} \bigcup^{D} \end{eqnarray*}$ ). Damit: $\begin{eqnarray*} \mathfrak M &=& \bigcup_{a \in \mathfrak M }^{D} \lbrack a\rbrack \end{eqnarray*}$

(andere Richtung) $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$
Nun sei $\begin{eqnarray*} \emptyset \neq \mathfrak M &=& \bigcup_{j \in J}^{D} A_j \end{eqnarray*}$ ; d.h. dieses $\begin{eqnarray*} \mathfrak M \end{eqnarray*}$ paarweise disjunkte Zerlegung / Partition von irgendwelchen $\begin{eqnarray*} \emptyset \neq A_i \subseteq \mathfrak M \end{eqnarray*}$ .

Nun definiere die ÄR $\begin{eqnarray*} \sim \end{eqnarray*}$ auf $\begin{eqnarray*} \mathfrak M \end{eqnarray*}$ mit $\begin{eqnarray*} \sim: \quad \mathfrak M^2 \to \mathfrak M \end{eqnarray*}$ durch...
$\begin{eqnarray*} a \sim b \quad :\Leftrightarrow \quad a, b \in A_j \quad \text{für ein} \quad j\in J \end{eqnarray*}$

Diese $\begin{eqnarray*} A_j \end{eqnarray*}$ spielen also die Rolle von ÄKs und wir gehen die 3 Forderungen einer ÄR durch...
(R) - Jedes $\begin{eqnarray*} a \in \mathfrak M \end{eqnarray*}$ gehört zu einem $\begin{eqnarray*} A_j \end{eqnarray*}$ . - $\begin{eqnarray*} a \sim a \end{eqnarray*}$ ist daher trivial.
(S) - Wenn $\begin{eqnarray*} a, b \in A_j \end{eqnarray*}$ , dann auch $\begin{eqnarray*} b, a \in A_j \end{eqnarray*}$ .
(T) - Wenn $\begin{eqnarray*} a, b \in A_j \end{eqnarray*}$ und wenn $\begin{eqnarray*} b, c \in A_j \end{eqnarray*}$ , dann sind $\begin{eqnarray*} a, c \in A_j \end{eqnarray*}$ .
Damit ist $\begin{eqnarray*} \sim \end{eqnarray*}$ eine ÄR.

Zusammenfassung:
Für jedes $\begin{eqnarray*} \mathfrak M \neq \emptyset \end{eqnarray*}$ definiert $\begin{eqnarray*} \mathfrak M &=& \bigcup_{j \in J}^{D} A_j \end{eqnarray*}$ eine ÄR $\begin{eqnarray*} \sim \end{eqnarray*}$ auf $\begin{eqnarray*} \mathfrak M \end{eqnarray*}$ und(!) umgekehrt.
Wink

-Ace-

17.03.2006, 01:43

Ben Sisko

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Partitionen
Hallo Ace Piet,

bis hierher ist dein Beweis ok.
Vielleicht kannst du Armin ja seine Fragen beantworten(Edit: am besten mit Tipps und Hinweisen und nicht gleich dem kompletten Beweis), sobald du die andere Richtung für dich aufgeschrieben hast.

Gruß vom Ben

17.03.2006, 01:53

ArminTempsarian

Auf diesen Beitrag antworten »

Ich hab gestern das erste mal von dem ganzen Zeug gehört, kann also noch bis 3, 4 dauern...
Zunächst mal, wie komme ich zu all diesen wunderbaren Symbolen?

17.03.2006, 02:11

Ben Sisko

Auf diesen Beitrag antworten »

Diesen Thread sollte sowieso jeder gelesen haben Augenzwinkern

Darin findest du einen Link zur Erklärung des Formeleditors/LaTeX.

17.03.2006, 02:53

ArminTempsarian

Auf diesen Beitrag antworten »

Hier ein erster Versuch: Bitte etwas Geduld mit mir, ich bin etwas langsam...

Gegeben sei eine Partition $\begin{eqnarray*} Ai, i\in I \end{eqnarray*}$ von M

$\begin{eqnarray*} xTildey:gdw. \exists i\in I: x,y \in Ai \end{eqnarray*}$

wobei "Tilde" eine Relation auf M ist.

Für ein x in M gibt es wegen $\begin{eqnarray*} \bigcup_{i\in I}Ai= M \end{eqnarray*}$ ein j aus I, sodass $\begin{eqnarray*} x\in Aj \end{eqnarray*}$
also x~x, Reflexivität ist erfüllt.

Symmetrie folgt aus Definition von Tilde.

Angenommen x~y und y~z, dann $\begin{eqnarray*} \exists k,j\in I \end{eqnarray*}$ , sodass (x~y in Ak) und (y~z in Aj) und weil für Partitionen gilt: ((Ak geschnitten Aj) ist nicht Leermenge) äquivalent (Ak=Aj); gilt $\begin{eqnarray*} x,y,z \in Aj \end{eqnarray*}$ .
und deshalb x~z, also Transitivität.

So in etwa?!?!

EDIT: Verdammt, bin wohl wirklich etwas langsam...

17.03.2006, 03:12

Ace Piet

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Partitionen
Hi Ben,

die Rückrichtung war simpel. So simpel, daß ich sie einfach der Vollständigkeit halber "draneditiert" habe, nachdem keine Antwort kam. - Vorschlag: Armin hat den kompletten Beweis "zum Üben".

Interessant wäre, wo Armin im Bereich Gruppentheorie (oder überhaupt) steht ... Indexsatz(?!) - Ich könnte auch noch ein bisschen schwafeln über $\begin{eqnarray*} \sim \end{eqnarray*}$ ist eine Verallgemeinerung von =, nämlich bzgl. einer (gröberen) Eigenschaft. - Falls er das wissen will.

Wink

______________

PS.: > wunderbare Symbole
Ich sammle...
aus http://de.wikipedia.org/wiki/Wikipedia:TeX
in meiner TXT-Referenz

Ich klaue... *Re.MausTaste* auf die Formel + *klick* + Eigenschaften... kann man mit CTRL+C wegkopieren + mit CTRL+V in einen Texteditor einfügen oder man fährt mit der Maus drauf (nixmachen) und bekommt eine Idee im flüchtigen Popup.

Z.B.:
"Tilde" = \sim
<=> \Leftrightarrow (großes L)
geschnitten \cap
verenigt \cup (an Hüte + Tassen denken)

17.03.2006, 03:35

Ace Piet

Auf diesen Beitrag antworten »

Wenn der Ben erlaubt (etwas Korrektur)...

Wenn eine Partition von $\begin{eqnarray*} M \end{eqnarray*}$ durch die $\begin{eqnarray*} A_i \end{eqnarray*}$ gegeben ist, dann existiert GENAU ein $\begin{eqnarray*} i \in J \end{eqnarray*}$ ... denn 2 verschiedene Indizes i wären für die Reflexivität tödlich.

> Symmetrie folgt aus Definition von Tilde.
Es folgt aus der Definition / Symmetrie von $\begin{eqnarray*} \in \end{eqnarray*}$ -Sein. - Bedenke: Das $\begin{eqnarray*} \in \end{eqnarray*}$ -Sein ist die definierende Eigenschaft für $\begin{eqnarray*} \sim \end{eqnarray*}$ , weshalb ich unten dieses $\begin{eqnarray*} :\Leftrightarrow \end{eqnarray*}$ benutzt habe (links-durch-rechts definiert).

> Transitivität
Ist (für mich) o.k.

> Verdammt, bin wohl wirklich etwas langsam...
Bleib locker. - Ich quäle mich auch.

Wink

_____________________________

Anmerkungen:

Deine Eingangsfrage $\begin{eqnarray*} A_1, \ldots ,A_n \end{eqnarray*}$ suggeriert, daß die Indexmenge abzählbar ist. - Das muß sie nicht sein.
Betrachte $\begin{eqnarray*} \mathbb R = \bigcup_{x \in \mathbb R}^{D} \{ x \} \end{eqnarray*}$ . - Diese (disj.) Vereinigung von je 1 Element definiert die ÄR = auf $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ . - Du kannst den allg. Beweis für diesen Spez.Fall analog aufschreiben. - $\begin{eqnarray*} \sim \end{eqnarray*}$ ist eine Verallgemeinerung von = bzgl. einer Eigenschaft (Merksatz).

> gerade und ungerade Zahlen...
unterscheiden sich durch ihre Reste 0 und 1, jeweils nach dem Teilen durch 2. - Bildet man bei einem Typ eine Differenz, verschwindet dieser Rest.
$\begin{eqnarray*} x \sim y :\Leftrightarrow x - y = 2 \cdot k \end{eqnarray*}$ für ein $\begin{eqnarray*} k \in \mathbb Z \end{eqnarray*}$ definiert eine ÄR auf $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ mit 2 ÄK... solche, die sich als $\begin{eqnarray*} z = 2 \cdot k \end{eqnarray*}$ schreiben lassen oder solche mit $\begin{eqnarray*} z = 2 \cdot k +1 \end{eqnarray*}$ , daher $\begin{eqnarray*} \mathbb Z = 2 \mathbb Z \quad \bigcup^{D} \quad 2 \mathbb Z +1 \end{eqnarray*}$ .
Statt $\begin{eqnarray*} x \sim y \end{eqnarray*}$ schreibt man übrigens $\begin{eqnarray*} x \equiv y \end{eqnarray*}$ , wenn klar ist, daß durch gleiches n geteilt wurde (oben war n = 2) oder ausführlicher $\begin{eqnarray*} x \equiv y \mod n \end{eqnarray*}$ . - Jedes $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ erzeugt eine ÄR...

17.03.2006, 03:57

Ben Sisko

Auf diesen Beitrag antworten »

Zitat:

Original von Ace Piet
Bedenke: Das $\begin{eqnarray*} \in \end{eqnarray*}$ -Sein ist die definierende Eigenschaft für $\begin{eqnarray*} \sim \end{eqnarray*}$ ,

Eben, deswegen war "nach Definition von $\begin{eqnarray*} \sim \end{eqnarray*}$ " für mich ok.

17.03.2006, 22:41

ArminTempsarian

Auf diesen Beitrag antworten »

Vielen Dank für die ausführlichen Antworten.
Wenn man man einmal akzeptiert hat, dass $\begin{eqnarray*} \in \end{eqnarray*}$ -Sein die definierende Eigenschaft ist, ist das folgendende kein Problem mehr. Aber das zu verinnerlichen, erfordert bei mir schon mal ein bißchen Zeit...
Ich denk, ich hab das jetzt einigermaßen intus, aber man merkt, Armin steht im Bereich Gruppentheorie (oder überhaupt!) gaaaanz am Anfang...

18.03.2006, 02:28

Ace Piet

Auf diesen Beitrag antworten »

Hi Armin,

ich mache jetzt mal ein freche Behauptung. - Falls Du bzgl. Grp.Theorie folgende 2 Dinge verstanden hast...

(a) - Briefkasten-Prinzip ( je reine Mengen.OPs)
(b) - Die ÄR / ÄK -Geschichte
... fallen Dir die restlichen Teile in den Schoß.

Grp.Theorie besteht zu IMHO 95% daraus... - *sheissendrekken* [1] hab ich wohl im Thread geleistet. - Und da mach ich noch ein [2] dran.
_________________

[1] Wie man das mit den ÄR/ ÄKs handelt...
[2] Das BriefkastenPrinzip...

_________________

[2]Das Briefkasten-Prinzip
...besagt etwas völlig simples UND Einsehbares... Verteilt man in n Briefkästen m > n Briefe, dann enthält ein Briefkasten (mindestens) 2 Briefe.

"Abfälle"

- (I)

Gegeben sei eine Abb. $\begin{eqnarray*} f: M \to M \end{eqnarray*}$ mit endlichem M;
kurz: Es sei $\begin{eqnarray*} M = \{ x_1,..., x_n\} \end{eqnarray*}$

Wenn f surjektiv ist, gibt es für jedes $\begin{eqnarray*} y \in M \end{eqnarray*}$ ein $\begin{eqnarray*} x \in M \end{eqnarray*}$ mit y = f (x), d.h. die n (verschiedenen) Bilder $\begin{eqnarray*} y_i \in M \end{eqnarray*}$ müssen als Urbilder $\begin{eqnarray*} x_i \in M \end{eqnarray*}$ auftauchen. - Wäre also $\begin{eqnarray*} y_i = y_j \end{eqnarray*}$ , dann fehlt für ein $\begin{eqnarray*} x_i \end{eqnarray*}$ im Urbildraum nach Durchzählen das entsprechende $\begin{eqnarray*} y_i \end{eqnarray*}$ . - Es müssen ja schliesslich JE n (verschiedene) Stück sein. - f ist ergo injektiv.

Wenn f injektiv ist, sind die Bilder der $\begin{eqnarray*} x_i \in M \end{eqnarray*}$ sämtlich verschieden. Es müssen also n verschiedene sein, sprich: jedes $\begin{eqnarray*} y_i \in M \end{eqnarray*}$ hat ein $\begin{eqnarray*} x_i \in M \end{eqnarray*}$ mit $\begin{eqnarray*} y_i = f(x_i) \end{eqnarray*}$ . - Ergo ist f surjektiv.

- (II)

Wie im Fall (I) sei jetzt G = M eine endliche Gruppe und $\begin{eqnarray*} a_0 \in G \end{eqnarray*}$ irgendein Element.

Mit der auf G gegebenen Verknüpfung " $\begin{eqnarray*} \circ \end{eqnarray*}$ " definiere die Abb. $\begin{eqnarray*} f: G \to G \quad; f(x) := a_0 \circ x \end{eqnarray*}$ . - Die Bilder sind also $\begin{eqnarray*} U:= \{a_0\circ x_1,..., a_0\circ x_n \} \subseteq G \end{eqnarray*}$ und es ist $\begin{eqnarray*} a_0 \circ x = a_0 \circ y \end{eqnarray*}$ <=> x = y (gem. Streichregel), d.h. ein solches f ist stets bijektiv (weil, wie gezeigt injektiv). - Es gibt also für jedes $\begin{eqnarray*} y \in G \end{eqnarray*}$ die Lösung der Gleichung $\begin{eqnarray*} y = a_0 \circ x \end{eqnarray*}$ mit einem $\begin{eqnarray*} x \in G \end{eqnarray*}$ (und umgekehrt), ergo $\begin{eqnarray*} U = G \end{eqnarray*}$ .

Anmerkung: Genauso ist ein $\begin{eqnarray*} g(x) := x \circ a_0 \end{eqnarray*}$ stets bijektiv vermöge $\begin{eqnarray*} V:= \{x_1 \circ a_0,..., x_n \circ a_0 \} = G = U \end{eqnarray*}$ .

...
- (X)

Falls $\begin{eqnarray*} \mid M \mid = \infty \end{eqnarray*}$ , gelten "injektiv = surjektiv = bijektiv" für ein $\begin{eqnarray*} f: M \to M \end{eqnarray*}$ nicht mehr, wie $\begin{eqnarray*} f(x) := 2 \cdot x^2 -1 \end{eqnarray*}$ mit $\begin{eqnarray*} M := [-1; +1] \end{eqnarray*}$ zeigen.

Neue Frage »

Antworten »

Äquivalenzrelationen und Partitionen

Verwandte Themen