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

Man zeige, daß durch $aRb\Leftrightarrow 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\Leftrightarrow 3|a^{2}-a^{2}\Leftrightarrow 3|0$

3 teilt 0

Symmetrie($aRb\Leftrightarrow bRa$)

$aRb\Leftrightarrow 3|a^{2}-b^{2}\Leftrightarrow 3|b^{2}-a^{2}\Leftrightarrow 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\Leftrightarrow 3|a^{2}-b^{2}\Leftrightarrow \exists k\in \mathbb {Z} :\ (a^{2}-b^{2})=k\cdot 3$
2.$bRc\Leftrightarrow 3|b^{2}-c^{2}\Leftrightarrow \exists l\in \mathbb {Z} :\ (b^{2}-c^{2})=l\cdot 3$

wenn 1. und 2. gilt folgt: $(a^{2}-c^{2})=\underbrace {(a^{2}-b^{2})} _{=k\cdot 3}+\underbrace {(b^{2}-c^{2})} _{=l\cdot 3}=\underbrace {(k+l)} _{\in \mathbb {Z} }\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\Leftrightarrow 3|a^{2}$

daraus liest man ab, dass die Partition $R_{0}:=\{0,\pm 3,\pm 6,\pm 9,\pm 12,\ldots \}(=0\mod 3)$

Jetzt die Äquivalenzklasse für 1:

$aR1\Leftrightarrow 3|a^{2}-1\Leftrightarrow 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} \}(=2\mod 3)$

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

...wenn man diese Mengen vereinigt folgt:

$R_{1}:=\{\pm 1,\pm 2,,\pm 4,\pm 5,\pm 7,\pm 8,,\pm 10,\pm 11,\ldots \}=\mathbb {Z} \backslash 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} \backslash R=$$\{\{a|aRb\}|b\in \mathbb {Z} \}$ die gesuchte Partition ist.