TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 105

From VoWi
Jump to navigation Jump to search

Man zeige, daß durch a R b \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.

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, \pm7, \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.

Links