Äqivalenzrelation

22.10.2009, 20:24

bomberman387

Auf diesen Beitrag antworten »

Äqivalenzrelation

Nabend,
ich hab mal eine Frage, die sich mir in meiner ersten Woche als Erstsemster in Mathe stellt.

Wir betrachtendie ganzen Zahlen $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ und eine fixierte natürliche Zahl a $\begin{eqnarray*} \geq \end{eqnarray*}$ 0.
Zeige, dass auf $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ durch
x ~ y, wenn die Differenz x-y ein Vielfaches von a ist,
eine Äquivalenzrelation definiert ist. Wie viele Äquivalenzklassen gibt es?

Zuerst zu der ersten Frage. Die Differenz ist dann ein Vielfaches von a, wenn gilt:
$\begin{eqnarray*} \frac{a}{x-y} \end{eqnarray*}$ =k wobei k $\begin{eqnarray*} \in \end{eqnarray*}$ $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ dieser Ausdruck nach y aufgelöst ergibt:
x- $\begin{eqnarray*} \frac{a}{k} \end{eqnarray*}$ =y.
Könnte man jetzt zeigen, dass x~ x- $\begin{eqnarray*} \frac{a}{k} \end{eqnarray*}$ reflexiv, symmetrisch und transitiv ist? So wirklich versteh ich jedoch nicht, wie ich dies an diesem Beispiel zeigen könnte...

22.10.2009, 20:33

heinzelotto

Auf diesen Beitrag antworten »

halt. x-y ist ein Vielfaches von a.

22.10.2009, 21:24

bomberman387

Auf diesen Beitrag antworten »

das heißt also das k= $\begin{eqnarray*} \frac{x-y}{a} \end{eqnarray*}$ und y=x-ka, jetzt könnte man doch eigentlich ka=n setzten, also müsste man überprüfen ob x~x-n eine Äqivalenzrelation ist?

23.10.2009, 08:14

heinzelotto

Auf diesen Beitrag antworten »

Entschuldige bitte meinen ersten (etwas knappen) Post. Nochmal ausführlicher:

Um zu zeigen, dass die Relation eine Äquivalenzrelation ist, musst du die 3 Eigenschaften zeigen. Also:
- Reflexivität: $\begin{eqnarray*} x-x \end{eqnarray*}$ ist Vielfaches von a
- Symmetrie: wenn $\begin{eqnarray*} x-y \end{eqnarray*}$ Vielfaches von a ist, dann ist es $\begin{eqnarray*} y-x \end{eqnarray*}$ auch
- Transitivität: Wenn $\begin{eqnarray*} x-y = n*a \end{eqnarray*}$ und $\begin{eqnarray*} y - z = n'*a \end{eqnarray*}$ , dann ist auch $\begin{eqnarray*} x-z = k*a \end{eqnarray*}$

Zeigen kannst du das, indem du das k direkt oder in Abhängigkeit von n und n' angibst.

Kennst du den Restklassenring modulo a? der hat hiermit etwas zu tun smile

smile

23.10.2009, 14:52

bomberman387

Auf diesen Beitrag antworten »

tut mir leid, dass ich nochmals nachfrage, aber ich hab noch keinen wirklichen Zugang zum Thema gefunden.
Heißt das, dass ich bei der Reflexivität also zeigen muss x-x=ka, das würde ja bedeuten, da x-x=0, dass ka=0 sein muss und somit gilt die Reflexivität, wenn k oder a 0 sind?
Das würde ja für die Symmetrie bedeuten, dass x-y=ka also x=ka+y.
Jetzt muss gelten, dass y-x auch ein Vielfaches von a ist, also y-x=k´a.
Somit gilt y-(ka+y)=k´a und -ka=k´a. Daher ist y-x=-ka also auch ein Vielfaches von a.
Ist somit die Refläxivität und die Symmetrie bewiesen?

23.10.2009, 15:47

Reksilat

Auf diesen Beitrag antworten »

Hi bomberman,

Du musst jeweils zeigen, dass es ein solches k gibt. Also um $\begin{eqnarray*} x\sim x \end{eqnarray*}$ zu zeigen, musst Du zeigen, dass es ein $\begin{eqnarray*} k \end{eqnarray*}$ gibt, mit $\begin{eqnarray*} x-x=k\cdot a \end{eqnarray*}$ . (Sollte nicht so schwer anzugeben sein ;-))

Für die Reflexivität ist $\begin{eqnarray*} x\sim y \end{eqnarray*}$ vorausgesetzt, es gibt also ein $\begin{eqnarray*} k \end{eqnarray*}$ , mit $\begin{eqnarray*} x-y=k\cdot a \end{eqnarray*}$ . Nun musst Du explizit ein $\begin{eqnarray*} k_2 \end{eqnarray*}$ angeben, so dass $\begin{eqnarray*} y-x=k_2\cdot a \end{eqnarray*}$ ist. (Auch dieses sollte nicht so schwer zu finden sein.)

Gruß,
Reksilat.

Anzeige

25.10.2009, 18:12

bomberman387

Auf diesen Beitrag antworten »

Das bedeutet also, dass für die Reflexivität gelten muss:
x-x=k1a und das gilt nur, wenn k1=0 (für a $\begin{eqnarray*} \neq \end{eqnarray*}$ 0)

Für die Symmetrie gilt:
Wenn (1) x-y=k1a, dann (2) y-x=k2a, daraus folgt (1) ins (2) eingesetzt -k1=k2 und da k1=0 muss k2 gleich 0 sein.

Für die Tansitivität gilt:
Wenn (1) x-y=k1a und (2) y-z=k2a, dann (3) x-z=k3a, daraus folgt (1) und (2) in (3) eingesetzt: k1+k2=k3 und da k1=0 und k2=0 ist k3=0.

Das bedeutet, dass es für a $\begin{eqnarray*} \neq \end{eqnarray*}$ 0 eine Äqivalenzklasse gibt.

Ist das soweit richtig?

26.10.2009, 01:05

Reksilat

Auf diesen Beitrag antworten »

Die Beweise für Reflexivität, Transitivität und Symmetrie verlaufen unabhängig voneinander. Wenn Du bei zu Beginn k1=0 hast, so heißt das nicht, dass das jetzt immer 0 ist. Man nimmt sich nur nicht für jeden Teilschritt neue Bezeichner.

Bei der Symmetrie weißt Du, dass es ein $\begin{eqnarray*} k \end{eqnarray*}$ gibt, mit $\begin{eqnarray*} x-y=ka \end{eqnarray*}$ . Mehr weißt Du über das $\begin{eqnarray*} k \end{eqnarray*}$ nicht und benötigst auch nicht mehr.

Bei der Transitivität wird (1) und (2) vorausgesetzt. (3) ist von Dir zu zeigen - Du musst also ein k3 in Abhängigkeit von k1 und k2 angeben.

Gruß,
Reksilat.

26.10.2009, 08:16

bomberman387

Auf diesen Beitrag antworten »

ok neuer Versuch,
das heißt, dass k bei der symmetrie alle Werte aus der Definitionsmenge annehmen kann.
Für die Transitivität setzte ich also (1) in (2) ein und erhalte (k1+k2)a=x-z was ja Ähnlichkeiten zur gewünschten Form x-z=k3a aufweißt. Wenn k3=k1+k2 dann sollte die Transitivität gegeben sein (ich weiß nicht, wie ich k3 sonst in Abhängigkeit von k1 und k2 darstellen sollte).

26.10.2009, 11:08

Reksilat

Auf diesen Beitrag antworten »

Richtig, wenn man m3=k1+k2 setzt, sieht man, dass $\begin{eqnarray*} x\sim z \end{eqnarray*}$ ist.

26.10.2009, 17:06

bomberman387

Auf diesen Beitrag antworten »

Zunächst einmal Danke für alle bisherigen Hilfestellungen.

Nun bleibt noch die Frage nach der Anzahl der Äqivalenzklassen.
Heinzelotto hat mich auf die Idee gebracht dafür einen Restklassen Ring zu benutzen.
Wenn k eine ganze Zahl ist k $\begin{eqnarray*} \geq \end{eqnarray*}$ 2 dann lassen sich ganze Zahlen bei Division durch k zu Restklassen zusammenfassen. Zwei ganze Zahlen (in dieser Aufgabe x und y) sind genau dann in der gleichen Äqivalenzklasse, wenn ihr Differenz durch k teilbar ist. Die anderen Äqivalenzklassen lassen sich durch die Rest bei der Division durch k beschreiben.
Wenn man jetzt z.B. $\begin{eqnarray*} \frac{x-y}{k} \end{eqnarray*}$ gibt es k Äquivalenzklassen (die Restklasse 0,1,2,3....k-1).
Ist meine Ausführung über Restklassen soweit korrekt?
Wie könnte man die Begründung der Anzahl der Äqivalenzklassen mathematisch korrekt aufschreiben?

26.10.2009, 18:02

Reksilat

Auf diesen Beitrag antworten »

Richtig, und wenn Du jetzt $\begin{eqnarray*} k \end{eqnarray*}$ durch $\begin{eqnarray*} a \end{eqnarray*}$ ersetzt, dann passt das sogar zur Aufgabe. Augenzwinkern

Augenzwinkern

Was ist mit $\begin{eqnarray*} a=1 \end{eqnarray*}$ oder $\begin{eqnarray*} a=0 \end{eqnarray*}$ ?

Gruß,
Reksilat.

26.10.2009, 18:10

bomberman387

Auf diesen Beitrag antworten »

Bei a=1 gibt es eine Äqivalenzklasse, da jede ganze Zahl durch 1 dividiert wieder eine ganze Zahl ergibt (somit den Rest 0 hat und damit liegen allle Zahlen in der glechen Klasse)
Da die Division durch 0 nicht definiert ist, ist die Anzahl der Äquivalenzklassen auch nicht definiert.

26.10.2009, 18:21

Reksilat

Auf diesen Beitrag antworten »

Für $\begin{eqnarray*} a=1 \end{eqnarray*}$ hast Du recht.

Zitat:

Da die Division durch 0 nicht definiert ist, ist die Anzahl der Äquivalenzklassen auch nicht definiert.

Es ist zwar richtig, dass die Division durch 0 nicht definiert ist, aber in der Aufgabenstellung steht auch kein Wort von Division.
Da musst Du noch mal nachdenken.

Gruß,
Reksilat.

26.10.2009, 19:18

bomberman387

Auf diesen Beitrag antworten »

mhhh...wenn a=0 dann würde aus x-y=ka folgen x=y...könnte man die Zahlen die, die Bedingung x=y erfüllen in eine eigene Äquivalenzklasse packen?

26.10.2009, 20:22

Reksilat

Auf diesen Beitrag antworten »

Welche Zahlen sind denn zum Beispiel für a=0 äquivalent zu 5?

26.10.2009, 21:42

bomberman387

Auf diesen Beitrag antworten »

die Äquivalenzbeziehung ist ja x-y=ka und meinst du das jetzt so, dass ich für x 5 einsetzte, welchen Wert y dann annehmen muss, oder hab ich das falsch verstanden?

26.10.2009, 21:47

Reksilat

Auf diesen Beitrag antworten »

Genau. Welche y sind zu x=5 äquivalent?

27.10.2009, 12:02

bomberman387

Auf diesen Beitrag antworten »

y kann dann nur den Wert 5 annehmen...

27.10.2009, 12:23

Reksilat

Auf diesen Beitrag antworten »

Richtig, die Äquivalenzklassen sind für a=0 dann also...?

27.10.2009, 12:43

bomberman387

Auf diesen Beitrag antworten »

Dann müsste es doch eigentlich für a=0 genau eine Äquivalenzklasse geben, in der alle x=y enthalten sind, oder kann man nur aus diesem Zusammenhang keine Äqivalenzklasse bilden?

27.10.2009, 12:46

Reksilat

Auf diesen Beitrag antworten »

Wieso eine? Die Äquivalenzklasse von 5 ist {5}, das haben wir eben festgestellt. Wie sieht die Äquivalenzklasse von 4 aus? u.s.w.

27.10.2009, 12:59

bomberman387

Auf diesen Beitrag antworten »

upps...da also jeder Zahl eine eigene Äquivalenzklasse zugeordnet wird, gibt es unendlich viele Äquivalenzklassen für a=0 (da x und y $\begin{eqnarray*} \in \mathbb Z \end{eqnarray*}$ )

27.10.2009, 13:02

Reksilat

Auf diesen Beitrag antworten »

Richtig, die Äquivalenzklassen sind gerade alle Mengen $\begin{eqnarray*} \{x\} \end{eqnarray*}$ für $\begin{eqnarray*} x\in \mathbb{Z} \end{eqnarray*}$

27.10.2009, 13:44

RS

Auf diesen Beitrag antworten »

Äquivalenzrelation erkennen.
sry woltte eig neues thema aufmcahen^^

27.10.2009, 14:54

bomberman387

Auf diesen Beitrag antworten »

danke Reksilat, jetzt ist mir das ganze schon um einiges klarer geworden...nur weiß ich noch nicht so richtig wie ich das mit den Äquivalenzklassen aufschreiben soll, ist eine so stark erklärende Form, wie ich sie gewählt habe in Ordnung?

27.10.2009, 15:05

Reksilat

Auf diesen Beitrag antworten »

Du kannst die Klassen für $\begin{eqnarray*} a>1 \end{eqnarray*}$ zum Beispiel so schreiben:
$\begin{eqnarray*} A_k=\{r\cdot a+k|r\in\mathbb{Z}\} \end{eqnarray*}$ , $\begin{eqnarray*} k=0..a-1 \end{eqnarray*}$

Für $\begin{eqnarray*} a=1 \end{eqnarray*}$ ist die einzige Klasse $\begin{eqnarray*} A=\mathbb{Z} \end{eqnarray*}$

Die Anzahl der Klassen gibt man einfach an, indem man sämtliche Klassen aufschreibt.

Gruß,
Reksilat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »