Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Repräsentantensystem zu Äquivalenzrelation

Repräsentantensystem zu Äquivalenzrelation

Universität / Fachhochschule

Relationen

Tags: Äquivalenklassen, Äquivalenzrelation, Relation., Repräsentantensystem

anonymous

14:19 Uhr, 29.10.2016

Hallo, ich habe irgendwie ein Verständnisproblem zur folgenden Aufgabe:

"Auf

ℝ \times ℝ

betrachten wir die Relation

(x_{1}, y_{1}) ~ (x_{2}, y_{2}) \Leftrightarrow (x_{1} - 2 y_{1}) - (x_{2} - 2 y_{2}) \in ℤ

. Zeigen Sie, dass dies eine Äquivalenzrelation ist und skizzieren Sie ein Repräsentantensystem."

Ich habe schon gezeigt, dass es sich um eine Äquivalenzrelation handelt (indem ich gezeigt habe, dass Reflexivität, Symmetrie und Transitivität erfüllt sind). Ich weiß aber nicht, wie ich das mit dem Repräsentantensystem machen muss, da ich die Definition davon nicht wirklich verstehe.

Mein Ansatz war: Eine Äquivalenzklasse zu bestimmen. Dann weiß ich aber nicht, wie das Repräsentantensystem aus jeder Äquivalenzklasse ein Element enthalten soll...
Ich habe beispielsweise folgende Äquivalenzklasse bestimmt (hoffentlich richtig?):

[(0,0)] = {(x, y) | x - 2 y \in ℤ} = {(x, y) | x - 2 y = z \in ℤ} = {(x, y) | y = (\frac{x}{2}) + z \in ℤ}

. Das ist ja eine Schar von Geraden. Ich habe das auch mal für andere Punkte gemacht und bemerkt, dass die Geraden alle die Steigung

\frac{1}{2}

haben. Aber wie mache ich jetzt dieses Repräsentantensystem?

Vielen Dank schon mal. :-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

tobit aktiv_icon

07:40 Uhr, 30.10.2016

Hallo empty-box!

Deine Überlegungen sind (bis auf die Notation der hinteren beiden Mengen) korrekt. :-)

Ein Repräsentantensystem ist z.B. gegeben durch

V := {(a, 0) ∣ a \in [0, 1)}

, wobei

[0, 1) := {b \in ℝ ∣ 0 \leq b < 1}

.

Wenn ich dir nachweisen soll, dass es sich tatsächlich um ein Repräsentantensystem handelt, brauche ich folgende Infos von dir:

Wie habt ihr den Begriff Repräsentantensystem genau definiert?

Ist bereits bekannt, dass

[0, 1)

ein Repräsentantensystem der Äquivalenzrelation auf

ℝ

gegeben durch

x_{1} \sim x_{2} \overset{}{\Leftrightarrow} x_{1} - x_{2} \in ℤ

ist?

Viele Grüße
Tobias

anonymous

12:01 Uhr, 30.10.2016

Hallo Tobit,
vielen Dank, ich hatte schon die Befürchtung, dass ich gar keine Antwort mehr bekomme.

Wir haben Repräsentantensystem folgendermaßen definiert:"Ein Repräsentantensystem ist eine Teilmenge von

M,

die aus jeder Äquivalenzklasse ein Element enthält. Ein solches Repräsentantensystem ist in der Regel nicht eindeutig." Also würde

M

hier

ℝ \times ℝ

entsprechen.

Ich bin mir gerade nicht ganz sicher, warum

[0,1)

ein Repräsentantensystem ist, vielleicht könntest du es zur Sicherheit noch mal kurz erklären? Also wieso ist die 1 ausgeschlossen? Oder meinst du hier

[(0,1)]

?

Vielen lieben Dank schon mal. :-)

tobit aktiv_icon

19:43 Uhr, 30.10.2016

> Ein Repräsentantensystem ist eine Teilmenge von M, die aus jeder Äquivalenzklasse ein Element enthält.

Hier fehlt ein wichtiges Wort; es muss heißen: "..., die aus jeder Äquivalenzklasse GENAU ein Element enthält."

Ein Repräsentantensystem ist also eine Teilmenge V von M mit folgenden Eigenschaften:
1. V enthält aus jeder Äquivalenzklasse mindestens ein Element.
2. V enthält aus jeder Äquivalenzklasse höchstens ein Element.

Betrachten wir zunächst nicht die Äquivalenzrelation aus der Aufgabe, sondern die etwas einfachere Äquvialenzrelation

R^{ʹ}

auf

ℝ

gegeben durch

x_{1} R^{ʹ} x_{2} \overset{}{\Leftrightarrow} x_{1} - x_{2} \in ℤ

.
Hier behaupte ich, dass

V^{ʹ} := [0, 1)

ein Repräsentantensystem darstellt.
Die Menge [0,1) bezeichnet das Intervall aller reellen Zahlen, die

\geq 0

und

< 1

sind.

Ich habe bewusst die 1 nicht in die Menge V' aufgenommen.
Sonst hätten wir

0, 1 \in V^{ʹ}

. Die Elemente 0 und 1 liegen aber in der gleichen Äquivalenzklasse (denn wegen

1 - 0 = 1 \in ℤ

gilt

1 R^{ʹ} 0

). Damit wäre 2. verletzt.

Folgende Aussage über reelle Zahlen möchte ich voraussetzen, ohne sie zu beweisen (falls du doch einen Beweis möchtest, frage bitte danach):
(*) Jede reelle Zahl x lässt sich eindeutig in der Form

x = n + a

mit

n \in ℤ

und

a \in [0, 1)

schreiben.
(Idee: Für n nehme man die x am nächsten gelegene ganze Zahl

n \leq x

. Im Falle

x \geq 0

ist n einfach der "Vorkommaanteil" von x und

a

der "Nachkommaanteil".)

Warum ist nun V' ein Repräsentantensystem?
Dazu sind 1. und 2. zu zeigen.

Zu 1.:
Sei

A

irgendeine Äquivalenzklasse bezüglich

R^{ʹ}

.
Wir suchen ein Element

a \in A

mit

a \in V^{ʹ}

.
Als Äquivalenzklasse hat

A

die Gestalt

A = [x]_{R^{ʹ}}

für ein

x \in ℝ

.
Nach (*) existieren

n \in ℤ

und

a \in [0, 1) = V^{ʹ}

mit

x = n + a

.
Wegen

x - a = n \in ℤ

gilt

x R^{ʹ} a

und damit wie gewünscht

a \in [x]_{R^{ʹ}} = A

.

Zu 2.:
Sei

A

irgendeine Äquivalenzklasse bezüglich

R^{ʹ}

und seien

a, b \in A

mit

a, b \in V^{ʹ}

.
Zu zeigen ist

a = b

.
Da a und b in der gleichen Äquivalenzklasse A sind, gilt

a R^{ʹ} b

, d.h.

a - b \in ℤ

.
Nun ist

0 + a = a = (a - b) + b

.
Wegen

0, a - b \in ℤ

und

a, b \in V^{ʹ} = [0, 1)

folgt aus der Eindeutigkeits-Aussage von (*) wie gewünscht a=b.

Damit ist nachgewiesen, dass V' tatsächlich ein Repräsentantensystem darstellt.

Für die eigentliche Aufgabe schreibe ich der Übersicht halber eine separate Antwort.
Hast du soweit schon einmal Fragen?

anonymous

19:58 Uhr, 30.10.2016

Hallo Tobias,

vielen Dank schon mal für die Erklärung zu deiner ersten Antwort, die habe ich jetzt glaube ich verstanden :-)

tobit aktiv_icon

20:13 Uhr, 30.10.2016

Nun betrachten wir die Äquivalenzrelation auf

ℝ \times ℝ

aus der Aufgabe.
Hier behaupte ich, dass

V := {(a, 0) ∣ a \in [0, 1)}

ein Repräsentantensystem darstellt.
(Die Schreibweise (a,0) steht hier natürlich nicht für ein Intervall, sondern für das Paar mit a in erster Komponente und 0 in zweiter Komponente.)

Weisen wir also wieder unsere Eigenschaften 1. und 2. eines Repräsentantensystems nach:

Zu 1.:

Sei A eine beliebige Äquivalenzklasse bezüglich

\sim

.
Gesucht ist ein

v \in V

mit

A = [v]_{\sim}

.
Als Äquivalenzklasse hat A die Gestalt

A = [(x, y)]_{\sim}

für ein Paar

(x, y) \in ℝ \times ℝ

.
Sei

z := x - 2 y \in ℝ

.
Sei

a \in V^{ʹ} = [0, 1)

der Repräsentant der Äquivalenzklasse

[z]_{R^{ʹ}}

von z bezüglich der Äquivalenzrelation R' aus meiner vorherigen Antwort.
Dann ist

v := (a, 0) \in V

und wegen

z R^{ʹ} a

gilt

x - 2 y - (a - 2 \cdot 0) = z - a \in ℤ

, also

(x, y) \sim v

.
Es folgt wie gewünscht

A = [(x, y)]_{\sim} = [v]_{\sim}

.

Zu 2.:

Sei A eine beliebige Äquivalenzklasse bezüglich

\sim

und seien

v_{1}, v_{2} \in A

mit

v_{1}, v_{2} \in V

.
Zu zeigen ist

v_{1} = v_{2}

.
Wegen

v_{1}, v_{2} \in V

existieren

a_{1}, a_{2} \in [0, 1)

mit

v_{1} = (a_{1}, 0)

und

v_{2} = (a_{2}, 0)

.
Da

v_{1}

und

v_{2}

in der gleichen Äquivalenzklasse A liegen, gilt

v_{1} \sim v_{2}

, d.h.

(a_{1} - 2 \cdot 0) - (a_{2} - 2 \cdot 0) \in ℤ

, also

a_{1} - a_{2} \in ℤ

und damit

a_{1} R^{ʹ} a_{2}

.
Also

a_{1}, a_{2} \in [a_{1}]_{R^{ʹ}}

und somit wegen

a_{1}, a_{2} \in [0, 1) = V^{ʹ}

bereits

a_{1} = a_{2}

(da V' ein Repräsentantensystem ist und somit nur ein Element von

[a_{1}]_{R^{ʹ}}

enthält).

Damit ist auch dieser Beweis abgeschlossen.

Das ist jetzt leider etwas länglich geworden... ;-)
Wahrscheinlich ist diese Aufgabe nicht gerade die ideale erste Aufgabe zu Repräsentantensystemen.

Die grobe Idee dahinter ist jedenfalls: Wir müssen aus jeder der "Geradenscharen", die die Äquivalenzklassen darstellen, genau einen Repräsentanten (d.h. genau ein Element) wählen.
Wie ich nachgewiesen habe, bilden die Paare der Form

(a, 0)

mit

a \in [0, 1)

gerade ein solches Repräsentantensystem.
Es gibt natürlich noch viele weitere Repräsentantensysteme.

anonymous

20:43 Uhr, 30.10.2016

Vielen lieben Dank, Tobias. Das hat mir sehr geholfen.

tobit aktiv_icon

20:48 Uhr, 30.10.2016

Vielleicht noch ein wenig zur Idee zum Finden des Repräsentantensystems:

Du hattest die Äquivalenzklasse von (0,0) bestimmt.
Entscheide dich für einen Repräsentanten (z.B. (0,0) selbst).
Damit darf kein weiteres Element dieser Äquivalenzklasse, also kein weiterer Punkt der ermittelten "Geradenschar" mehr ins Repräsentantensystem aufgenommen werden.

Gegeben eine beliebige Äquivalenzklasse, also eine gewisse "Geradenschar", müssen wir uns irgendwie für einen Punkt auf ihr entscheiden.
Eine mögliche Idee ist nun: Man nimmt aus jeder "Geradenschar" den rechts von (0,0) gelegenen nächsten Punkt der "Geradenschar".
So kann man auf das Repräsentantensystem kommen, das ich dir präsentiert habe.

Alternativ hätte man z.B. auch aus jeder "Geradenschar" den nächsten Punkt der "Geradenschar" oberhalb von (0,0) nehmen können und hätte das Repräsentantensystem

{(0, b) ∣ b \in [0, ½)}

erhalten.

P.S.: In deinem Ausgangspost muss es am Ende

{(x, y) ∣ \exists z \in ℤ : y = \frac{x}{2} + \frac{z}{2}}

heißen. Sorry, da habe ich nicht richtig aufgepasst.

1331590

1331179

	Status: nicht eingeloggt	Noch nicht registriert?