Äquivalenzrelation beweisen (x, y) ∈ R_M : ⇐⇒ x, y ∈ M ∧ Q(x) = Q(y).

Question

Aufgabe:

Sei Q(n) die Quersumme der natürlichen Zahl n. Ferner sei M eine beliebige nichtleere Menge von natürlichen Zahlen. Mit RM werde die folgende Relation in M bezeichnet:

(x, y) ∈ R_M : ⇐⇒ x, y ∈ M ∧ Q(x) = Q(y).

Man zeige:
(a) R_M ist eine Äquivalenzrelation in M.
(b) Es existiert eine unendliche Menge M, die in genau 5 Äquivalenzklassen zerfällt.
(c) Es existiert eine unendliche Menge M, bei der alle Äquivalenzklassen endlich sind.

Problem/Ansatz:

Bei a muss ich ja nachweisen, dass es reflexiv, symmetrisch und transitiv ist.

Da kommt mir meine Lösung viel zu simpel/kurz vor.

reflexiv, also xRx für alle x∈M: (x,x)∈R_M ⇐⇒ Q(x)=Q(x)

symmetrisch, also xRy⇒yRz für alle x,y∈M:  Q(x)=Q(y)⇒Q(y)=Q(x) dann (x,y)⇒(y,z)∈R_M

transitiv, also xRy∧yRz für alle x,y,z∈M: Q(x)=Q(y)=Q(z) ⇒ (x,z)∈R_M

Und bei den Äquivalenzklassen hab ich keine Ahnung.

Ich wäre sehr dankbar über eine ausführliche Erklärung mit Lösung, damit ich es auch wirklich fürs nächste mal verstehe.

Answer 1

a) ist jedenfalls richtig.

Für b) brauchst du eine unendliche Menge, in der nur nat. Zahlen vorkommen,

bei denen die Quersumme nur 5 verschiedene Werte annehmen kann. Bedenke, dass z.B.

1, 10 , 100, 1000, etc alle die Quersumme 1 haben.

also M1={10^n | n∈ℕ}.

Entsprechend M2={2*10^n | n∈ℕ}. etc.

Und die Vereinigung von M1 bis M5 liefert eine Lösung.

Für c) betrachte vielleicht die Menge mit den Elementen

1, 11, 111, 1111, etc.

Da ist in jeder Äquivalenzklasse (Darin sind ja die Elemente mit gleicher Quersumme.)

genau ein Element.

Formal könnte man die Menge wohl so aufschreiben:$$ \left\{ \sum \limits_{n=0}^{k}10^n\right | k\in \mathbb{N} \} $$