TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 109

Man zeige, daß durch $aRb\iff 3|a^2-b^2$ für alle $a,b\in \mathbb{Z}$ eine Äquivalenzrelation $R$ in der Menge $\mathbb{Z}$ erklärt wird, und bestimme die zugehörende Partition.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösung

Um eine Äquivalenzrelation zu sein, muss R reflexiv, symmetrisch und transitiv sein:

Reflexivität($aRa$)

$aRa\iff 3|a^2-a^2\iff 3|0$

3 teilt 0

Symmetrie($aRb\iff bRa$)

$aRb\iff 3|a^2-b^2\iff 3|b^2-a^2\iff bRa$

wenn 3 $a^2-b^2$ teilt, teilt 3 ja auch $-(a^2-b^2)$

Transitivität($aRb\wedge bRc\Rightarrow aRc$)

1.$aRb\iff 3|a^2-b^2\iff \mathrm{\exists }k\in \mathbb{Z}:(a^2-b^2)=k\cdot 3$
2.$bRc\iff 3|b^2-c^2\iff \mathrm{\exists }l\in \mathbb{Z}:(b^2-c^2)=l\cdot 3$

wenn 1. und 2. gilt folgt: $(a^2-c^2)=\underset{=k\cdot 3}{\underbrace{(a^2-b^2)}}+\underset{=l\cdot 3}{\underbrace{(b^2-c^2)}}=\underset{\in \mathbb{Z}}{\underbrace{(k+l)}}\cdot 3$

...3 teilt also $a^2-c^2$...

$(a^2-c^2)=m\cdot 3,m\in \mathbb{Z}\Rightarrow 3|a^2-c^2\Rightarrow aRc$

...und damit hätte man auch die Transitivität gezeigt

Jetzt muss man noch die zugehörende Partition bestimmen:

Ich fang mal an mit der Äquivalenzklasse für 0(also alle Zahlen, welche in Relation zu 0 stehen)

$aR0\iff 3|a^2$

daraus liest man ab, dass die Partition $R_0:=\{0,\pm 3,\pm 6,\pm 9,\pm 12,\dots \}(=0mod3)$

Jetzt die Äquivalenzklasse für 1:

$aR1\iff 3|a^2-1\iff 3|(a+1)(a-1)$

...also muss entweder a+1 oder a-1 ein Vielfaches von 3 sein:

einerseits kann, wegen $3|a+1$, a aus dieser Menge sein: $\{-1+k\cdot 3|k\in \mathbb{Z}\}(=2mod3)$

andererseits kann a, wegen $3|a-1$, auch aus dieser Menge sein: $\{1+k\cdot 3|k\in \mathbb{Z}\}(=1mod3)$

...wenn man diese Mengen vereinigt folgt:

$R_1:=\{\pm 1,\pm 2,,\pm 4,\pm 5,\pm 7,\pm 8,,\pm 10,\pm 11,\dots \}=\mathbb{Z}\mathrm{\setminus }{R}_0$

Damit hat man alle Äquivalenzklassen, denn $R_0\cup R_1=\mathbb{Z}$

--PurpleHaze 20:58, 10. Nov 2008 (CET)

Variante zur Partition

Viel einfacher: aus dem Satz über die durch Äquivalenzklassen gebildete Partitionen und der zuvor bewiesene Aussage, dass R Relation auf $\mathbb{Z}$ ist, folgt sofort, dass $\mathbb{Z}\mathrm{\setminus }R=$$\{\{a|aRb\}|b\in \mathbb{Z}\}$ die gesuchte Partition ist.