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

Man zeige, dass durch $aRb\Leftrightarrow 6|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örige 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
}}

Hilfreiches

Äquivalenzrelation

Äquivalenzrelation

Eine binäre Relation R auf einer Menge A heißt Äquivalenzrelation, wenn folgende drei Eigenschaften erfüllt sind:

Reflexivität: $\forall a\,\in A:aRa$,

Symmetrie: $\forall a,b\,\in A:aRb\Rightarrow bRa$,

Transitivität: $\forall a,b,c\,\in A:(aRb\wedge bRc)\Rightarrow aRc$. Partition (Seite 38 in Mathematik für Informatik) (4. Auflage: Seite 40)
Satz 1.59: Sei R eine Äquivalenzrelation auf A. Dann bilden die (verschiedenen) Äquivalenzklassen der Elemente von A eine Partition von A. (Ebenfalls Seite 38)

Lösungsversuch

Zeigen der Äquivalenzrelation

Reflexivität

$aRa\Leftrightarrow 6|a^{2}-a^{2}$

$6|0$ 6 teilt 0 also ist es Reflexiv.

Symmetrie

$\forall a,b\,\in \mathbb {Z} :aRb\Rightarrow bRa$
$6|a^{2}-b^{2}\Leftrightarrow 6|b^{2}-a^{2}$
Wenn 6 $a^{2}-b^{2}$ teilt dann teilt es auch $b^{2}-a^{2}$ da es die selben Zahlen sind nur mit anderem Vorzeichen.

Transitivität

$\forall a,b\in \mathbb {Z} :(aRb\wedge bRc)\Rightarrow aRc$

$6|a^{2}-b^{2},\ 6|b^{2}-c^{2}$
$\Rightarrow a^{2}-b^{2}=6x,\ b^{2}-c^{2}=6y$
$\Rightarrow (a^{2}-b^{2})+(b^{2}-c^{2})=6x+6y$
$\Rightarrow a^{2}-b^{2}+b^{2}-c^{2}=6(x+y)$
$\Rightarrow a^{2}-c^{2}=6(x+y)$
$\Rightarrow 6|a^{2}-c^{2}$
Somit ist es Transitiv

Anmerkung zur Transitivität

Mir ist es der obige Nachweis nicht ganz einleuchtend, daher hier ein alternativer Weg:

Da waren ein paar Tippfehler im obigen Beweis… jetzt sollte er verständlicher sein. -- hop

$6|a^{2}-b^{2}\Leftrightarrow 6\cdot q=a^{2}-b^{2},\quad q\in \mathbb {Z}$

$6|b^{2}-c^{2}\Leftrightarrow 6\cdot p=b^{2}-c^{2},\quad p\in \mathbb {Z}$

$6\cdot q=a^{2}-b^{2}\Rightarrow b^{2}=a^{2}-6\cdot q$

$6\cdot p=b^{2}-c^{2}\Rightarrow b^{2}=c^{2}+6\cdot p$ $\Rightarrow a^{2}-6\cdot q=c^{2}+6\cdot p$

$a^{2}-c^{2}=6\cdot p+6\cdot q=6\cdot (p+q)$

$\Rightarrow 6|a^{2}-c^{2}$

Alle Vorraussetzungen sind erfüllt, somit ist es eine Äquivalenzrelation

--MatheFreak 01:29, 15. Dez. 2010 (CET)

Bestimmen der Partition

Anwendung von Satz 1.59

Allgemein

$R(a)=\{b\in \mathbb {Z} |bRa\}$
Um die Klassen bestimmen zu können, formen wir mal unsere Relation um:
$6|a^{2}-b^{2}\Leftrightarrow 6\cdot q=a^{2}-b^{2},\quad q\in \mathbb {Z}$
$6\cdot q=a^{2}-b^{2}\rightarrow a^{2}=b^{2}+6\cdot q$
Und das erinnert doch schon sehr stark an die Kongruenzrechnung. D.h. man kann die Relation auch wie folgt betrachten:
$a^{2}\equiv b^{2}{\text{ mod }}6$
$R(b)=\{a\in \mathbb {Z} |a^{2}\equiv b^{2}{\text{ mod }}6\}$

Das bedeutet, man würde auf jeden Fall 6 Äquivalenzklassen erwarten. Wenn man sich das aber genauer überlegt erkennt man, dass manche von diesen leer sind. Das liegt daran, dass hier das Quadrat im Spiel ist. z. B. für 2: $2\equiv 2{\text{ mod }}6$ aber
$2^{2}\equiv 4{\text{ mod }}6$.

Das muss man für alle Möglichkeiten durchspielen, um zu sehen, in welchen Mengen tatsächlich Elemente enthalten sein werden:
$0^{2}\equiv 0{\text{ mod }}6$
$1^{2}\equiv 1{\text{ mod }}6$
$2^{2}\equiv 4{\text{ mod }}6\rightarrow {\text{ es kann keine Elemente in R(2) geben, weil alle diese in R(4) verschoben werden}}$
$3^{2}\equiv 3{\text{ mod }}6$
$4^{2}\equiv 4{\text{ mod }}6$
$5^{2}\equiv 1{\text{ mod }}6\rightarrow {\text{ es kann keine Elemente in R(5) geben, weil alle diese in R(1) verschoben werden}}$

Äquivalenzklasse 0

$aR0\Leftrightarrow 6|a^{2}-0$
$R_{0}=\{a\in \mathbb {Z} |a^{2}\equiv 0{\text{ mod }}6\}=\{0+k*6|k\in \mathbb {Z} \}$
$R_{0}=\{0,\pm 6,\pm 12,\pm 18,...\infty \}(=0\mod 6)$

Äquivalenzklasse 1

$aR1\Leftrightarrow 6|a^{2}-1$
$R_{1}=\{a\in \mathbb {Z} |a^{2}\equiv 1{\text{ mod }}6\}=\{-1+k*6|k\in \mathbb {Z} \}$
$R_{1}=\{\pm 1,\pm 5,\pm 7,\pm 11,\pm 13,...\infty \}(=1\mod 6)$

Äquivalenzklasse 2

$aR2\Leftrightarrow 6|a^{2}-2$
$R_{2}=\{a\in \mathbb {Z} |a^{2}\equiv 2{\text{ mod }}6\}=\emptyset$

Äquivalenzklasse 3

$aR3\Leftrightarrow 6|a^{2}-3$
$R_{3}=\{a\in \mathbb {Z} |a^{2}\equiv 3{\text{ mod }}6\}=\{-3+k*6|k\in \mathbb {Z} \}$
$R_{3}=\{\pm 3,\pm 9,\pm 15,\pm 21,...\infty \}$

Äquivalenzklasse 4

$aR4\Leftrightarrow 6|a^{2}-4$
$R_{4}=\{a\in \mathbb {Z} |a^{2}\equiv 4{\text{ mod }}6\}=\{-2+k*6|k\in \mathbb {Z} \}$
$R_{4}=\{\pm 2,\pm 4,\pm 8,\pm 10,\pm 14,...\infty \}$

Äquivalenzklasse 5

$aR5\Leftrightarrow 6|a^{2}-5$
$R_{5}=\{a\in \mathbb {Z} |a^{2}\equiv 5{\text{ mod }}6\}=\emptyset$

Partition

$R_{0}+R_{1}+R_{3}+R_{4}=\mathbb {Z}$

Edit: Wie oben bewiesen sind $R_{2}$ und $R_{5}$ leere Teilmengen, die Partition ist jedoch ein System von nichtleeren Teilmengen.

Links zu anderen Lösungen des gleichen Beispiels

TU Wien:Mathematik 1 UE (diverse)/Übungen SS10/Beispiel 18