Mächtigkeit einer Äquivalenzrelation

18.08.2012, 13:47

Johnnny

Mächtigkeit einer Äquivalenzrelation

Meine Frage:
Hallo Leute,
ich habe folgendes Problem. Gegeben ist eine Äquivalenzrelation $\begin{eqnarray*} \mathcal{R} \end{eqnarray*}$ auf einer Menge $\begin{eqnarray*} A \end{eqnarray*}$ , von der man weiß, dass alle Äquivalenzklassen $\begin{eqnarray*} [x]_i \end{eqnarray*}$ gleiche Größe $\begin{eqnarray*} k \end{eqnarray*}$ haben. Da $\begin{eqnarray*} A= \overset{\bullet} {\bigcup_{i}}[x]_i \end{eqnarray*}$ , folgt doch $\begin{eqnarray*} |A|=n \cdot k \end{eqnarray*}$ für ein gewisses $\begin{eqnarray*} n \end{eqnarray*}$ . Wenn ich jetzt die Mächtigkeit von $\begin{eqnarray*} \mathcal{R} \end{eqnarray*}$ bestimmen möchte, dann ist doch $\begin{eqnarray*} |\mathcal{R}|=2 \cdot \sum_i \left|[x]_i \right| \end{eqnarray*}$ aufgrund der Symmetrie von $\begin{eqnarray*} \mathcal{R} \end{eqnarray*}$ . Demenach ist doch nun $\begin{eqnarray*} |\mathcal{R}|=2 \cdot n \cdot k=2 \cdot |A| \end{eqnarray*}$ . \\ Dieses erscheint mir merkwürdig. Wo ist der Fehler, falls es falsch ist?

Vielen Dank schon einmal.

Meine Ideen:
steht schon oben

18.08.2012, 14:39

Mazze

Auf diesen Beitrag antworten »

Zitat:

Da $\begin{eqnarray*} A= \overset{\bullet} {\bigcup_{i}}[x]_i \end{eqnarray*}$ , folgt doch $\begin{eqnarray*} |A|=n \cdot k \end{eqnarray*}$ für ein gewisses $\begin{eqnarray*} n \end{eqnarray*}$ .

Das stimmt so nicht, da die Menge A auch unendlich sein kein. Etwa

$\begin{eqnarray*} A = \mathbb{R}, x \sim y \Leftrightarrow x = y \end{eqnarray*}$
Dann sind die Äquivalenzklassen gerade

$\begin{eqnarray*} \{[x] | x \in A\} \end{eqnarray*}$
und jede Äquivalenzklasse hat die Mächtigkeit 1.

allerdings gibt es kein $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$

für das

$\begin{eqnarray*} |A| = n*1 \end{eqnarray*}$ gelten könnte, da $\begin{eqnarray*} |A| = \infty \end{eqnarray*}$

Zitat:

Wenn ich jetzt die Mächtigkeit von $\begin{eqnarray*} \mathcal{R} \end{eqnarray*}$ bestimmen möchte, dann ist doch $\begin{eqnarray*} |\mathcal{R}|=2 \cdot \sum_i \left|[x]_i \right| \end{eqnarray*}$ aufgrund der Symmetrie von $\begin{eqnarray*} \mathcal{R} \end{eqnarray*}$ .

Das ist auch nicht richtig, und mein obiges Beispiel ist auch ein Gegenbeispiel dafür, da die Mächtigkeit von R hier gleich der von A ist. Für die Mächtigkeit der Äquivalenzrelation gilt :

$\begin{eqnarray*} |R| = \sum_{i}|[x]_i| \end{eqnarray*}$

sofern die Äquivalenzklassen abzählbar sind. Die Symmetrie steckt schon in den Äquivalenzklassen selbst drin.

18.08.2012, 15:14

Johnnny

Auf diesen Beitrag antworten »

Hey danke Mazze,
ja mit der Unendlichkeit hast recht. Aber die Formel $\begin{eqnarray*} |R|=\sum_i |[x]_i| \end{eqnarray*}$ seh ich noch nicht ganz ein. Falls $\begin{eqnarray*} (x,y) \in R \end{eqnarray*}$ , dann ist doch auch $\begin{eqnarray*} (y,x) \in R \end{eqnarray*}$ also sagen wir mal, es sind schon zwei Elemente in $\begin{eqnarray*} R \end{eqnarray*}$ . Durch $\begin{eqnarray*} |[x]|=|\{z \in A \mid (x,z) \in R \}| \end{eqnarray*}$ wird doch nun nur ein Element quasi gezählt. Außerdem würde das doch auch bedeuten, dass $\begin{eqnarray*} |R|=|A| \end{eqnarray*}$ . Eigentlich ist doch aufgrund der Reflexivität sowieso $\begin{eqnarray*} (x,x) \in R \ \forall x \in A \end{eqnarray*}$ . Falls aber andere Elemente mit x in Relation stehen, so ist doch $\begin{eqnarray*} |R| >|A| \end{eqnarray*}$ . Oder denk ich jetzt total quer.

LG

18.08.2012, 15:18

Johnnny

Auf diesen Beitrag antworten »

Ach so ich seh gerad was du meintest, also vergiss das was geschrieben habe.

Trotzdem würd ich gerne wissen, wie ich im endlichen Fall von $\begin{eqnarray*} A \end{eqnarray*}$ die Mächtigkeit von $\begin{eqnarray*} R \end{eqnarray*}$ bestimme, falls die Voraussetzungen meines ersten Beitrages gelten.

18.08.2012, 15:38

Mazze

Auf diesen Beitrag antworten »

Es gibt durchaus Fälle wo $\begin{eqnarray*} |R| > | A \end{eqnarray*}$ ist,

etwa

$\begin{eqnarray*} A = \{1,2\} \end{eqnarray*}$

$\begin{eqnarray*} R = \{(1,2),(2,1),(1,1),(2,2)\} \end{eqnarray*}$

In dem Fall ist |A| = 2 und |R| = 4

Man kann aber genauso folgendes betrachten :

$\begin{eqnarray*} A = \{1,2,3\} \end{eqnarray*}$

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

Dann ist von A die Mächtigkeit 3 , die Mächtigkeit von R ist 5. Die Äquivalenzklassen wären {1,2},{3}, die Summe der Mächtigkeiten wäre 3. Im übrigen ist auch

$\begin{eqnarray*} |R| = \sum_{i}|[x]_i| \end{eqnarray*}$

falsch wie man bei dem Beispiel sieht. Tatsächlich gilt nur

$\begin{eqnarray*} |A| = \sum_{i}|[x]_i| \end{eqnarray*}$

So wie ich das sehe kann man keine allgemeingültige Formel für die Mächtigkeit der Äquivalenzrelation angeben, man muss also explizit an der Konkreten Relation die Mächtigkeit bestimmen.

edit : Kannst Du eventuel mal den Originalwortlaut der Aufgabe angeben?

18.08.2012, 16:24

Johnnny

Auf diesen Beitrag antworten »

Hey Mazze,

ja kann ich machen. Das ist keine Aufgabe, nur ein paar Überlegungen die aufgetaucht sind.

Sei $\begin{eqnarray*} E_k:=\{0, \ldots , k-1\}, P_{k,l}:=\{ f \colon E_k \longrightarrow E_l \mid f \textrm{ist beliebig stellig}\} \end{eqnarray*}$ für $\begin{eqnarray*} k>l, P_l:=\{ f \colon E_l\longrightarrow E_l \mid f \textrm{ist beliebig stellig}\} \end{eqnarray*}$ und $\begin{eqnarray*} \varphi \colon P_{k,l} \longrightarrow P_l \end{eqnarray*}$ definiert durch $\begin{eqnarray*} \varphi(f):= f_{\mid E_l} \end{eqnarray*}$ und $\begin{eqnarray*} \kappa_\varphi \end{eqnarray*}$ die von dem Homomorphismus $\begin{eqnarray*} \varphi \end{eqnarray*}$ induzierte Kongruenz auf $\begin{eqnarray*} P_{k,l} \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} |f / \kappa_\varphi |=l^{k^n-l^n} \end{eqnarray*}$ für eine n-stellige Funktion. Sei außerdem $\begin{eqnarray*} \kappa_\varphi^{(n)} =\kappa_\varphi \cap P_{k,l}^n \times P_{k,l}^n \end{eqnarray*}$ , wobei $\begin{eqnarray*} P_{k,l}^n \end{eqnarray*}$ die Menge aller Funktionen aus $\begin{eqnarray*} P_{k,l} \end{eqnarray*}$ ist, welche Stelligkeit n besitzt. Dann ist vorerst
$\begin{eqnarray*} \kappa_\varphi= \overset{\bullet}{\bigcup_{n \ge 1}} \kappa_\varphi^{(n)} \end{eqnarray*}$ .

Ich weiß, dass $\begin{eqnarray*} \kappa_\varphi \end{eqnarray*}$ unendlich groß ist, aber $\begin{eqnarray*} \kappa_\varphi^{(n)} \end{eqnarray*}$ nicht, und deshalb möchte ich dessen Mächtigkeit bestimmen.

18.08.2012, 16:42

Mazze

Auf diesen Beitrag antworten »

Was verstehst Du unter der Stelligkeit einer Funktion? Laut Wikipedia ist es die Anzahl der Argumente an die Funktion. Dann wäre eine Funktion

$\begin{eqnarray*} f : E_k \to E_l \end{eqnarray*}$

aber immer einstellig womit der Zusatz f ist beliebig stellig keine neue Information bringt.

18.08.2012, 17:33

Johnnny

Auf diesen Beitrag antworten »

ja ich weiß. Da haben sich Fehler eingeschlichen^^.

Nein es gilt:
$\begin{eqnarray*} P_{k,l}:=\{ f \colon E_k^{a(f)} \longrightarrow E_l \} \end{eqnarray*}$ ,
wobei $\begin{eqnarray*} a(f) \end{eqnarray*}$ die Arität oder auch Stelligkeit von $\begin{eqnarray*} f \end{eqnarray*}$ ist. Also genau das, was du bei Wiki gefunden hast. Analog ist
$\begin{eqnarray*} P_l:=\{ f \colon E_l^{a(f)} \longrightarrow E_l \} \end{eqnarray*}$ und $\begin{eqnarray*} \varphi \colon P_{k,l} \longrightarrow P_l \end{eqnarray*}$ mit $\begin{eqnarray*} \varphi (f):= f_{\mid E_l^{a(f)}} \end{eqnarray*}$ .

Achso $\begin{eqnarray*} P_{k,l} \end{eqnarray*}$ und $\begin{eqnarray*} P_l \end{eqnarray*}$ sind Funktionenalgebren mit den üblichen Mal' Cev Operationen, welche hier aber unwichtig sind. Daher ist $\begin{eqnarray*} \varphi \end{eqnarray*}$ auch ein Homomorphismus.

Vielleicht noch zur Unterstützung:
$\begin{eqnarray*} \kappa_\varphi:=\{(f,g) \in P_{k,l} \times P_{k,l} \mid \varphi(f)=\varphi(g) \} \end{eqnarray*}$ , also der Kern der homomorphen Abbildung.

$\begin{eqnarray*} f / \kappa_\varphi \end{eqnarray*}$ ist die Äquivalenzklasse von $\begin{eqnarray*} f \end{eqnarray*}$ .

LG

19.08.2012, 12:51

Mazze

Auf diesen Beitrag antworten »

Hm danke. Da kann ich Dir leider nicht weiter helfen, da ich soweit in der Algebra nie gekommen bin. Was ich sagen kann :

Beispiele :

$\begin{eqnarray*} A = \{1,2,3,4\} \end{eqnarray*}$

$\begin{eqnarray*} R_1 = \{(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)\} \end{eqnarray*}$ und $\begin{eqnarray*} |R_1| = 8 \end{eqnarray*}$ (2 ÄQ)

$\begin{eqnarray*} R_2 = \{(1,1),(2,2),(3,3),(4,4)\} \end{eqnarray*}$ und $\begin{eqnarray*} |R_2| = 4 \end{eqnarray*}$ (4 ÄQ)

$\begin{eqnarray*} R_3 = \{(x,y) | x,y \in A\} \end{eqnarray*}$ und $\begin{eqnarray*} |R_3| = 4 + 6 + 4 + 2 = 16 \end{eqnarray*}$ (1 ÄQ)

Ich hab dann mal ein wenig rumgerechnet, sei A eine Menge mit $\begin{eqnarray*} |A| = n \end{eqnarray*}$ und sei R eine Äquivalenzrelation auf A, so dass alle Äquivalenzklassen die gleiche Mächtigkeit besitzen, also

$\begin{eqnarray*} |[x]| = k ~ \forall x \in A \end{eqnarray*}$

Man betrachte die Abbildung

$\begin{eqnarray*} f:A/R \to B \subset R \end{eqnarray*}$ mit $\begin{eqnarray*} f([x]) = \{(a,b)| a,b \in [x]\} \end{eqnarray*}$ . Die Abbildung ist Wohldefiniert ( kann man sich leicht klar machen ). Dann ist

$\begin{eqnarray*} R = \bigcup_{x \in A}f([x]) \end{eqnarray*}$ , also ist

$\begin{eqnarray*} |R| = \sum_{i = 1}^{|A/R|}|f([i])| \end{eqnarray*}$

Es ist $\begin{eqnarray*} |f([i])| = k + 2*\sum_{l=1}^{k-1}l = k + (k-1)*k = k^2 \end{eqnarray*}$ , also ist

$\begin{eqnarray*} |R| = \sum_{i=1}^{|A/R|}k^2 = |A/R|*k^2 \end{eqnarray*}$

19.08.2012, 14:58

Johnnny

Auf diesen Beitrag antworten »

Hey Mazze,

das ist echt ne geile Sache mit der Abbildung. Das beantwortet auf jeden Fall meine Frage.
Vielen Dank

19.08.2012, 15:07

Mazze

Auf diesen Beitrag antworten »

Man muss eventuel den Aufschrieb noch ändern, das hier ist nicht ganz korrekt formuliert

$\begin{eqnarray*} |R| = \sum_{i = 1}^{|A/R|}|f([i])| \end{eqnarray*}$

(wenngleich das richtige gemeint ist)

Besser ist $\begin{eqnarray*} A/R = \{x_1,x_2,...,x_ {|A/R|}\} \end{eqnarray*}$

also insgesamt

$\begin{eqnarray*} |R| = \sum_{i = 1}^{|A/R|}|f(x_i)| \end{eqnarray*}$

edit :

Man muss auch die Abbildung f besser beschreiben, richtig wäre

$\begin{eqnarray*} f: A/R \to P(R) \end{eqnarray*}$ (Potenzmenge)

Die Argumente bleiben aber die selben.

Neue Frage »

Antworten »

Mächtigkeit einer Äquivalenzrelation

Verwandte Themen