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

Man zeige, dass durch $aRb\iff 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: $\mathrm{\forall }a\in A:aRa$,

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

Transitivität: $\mathrm{\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\iff 6|a^2-a^2$

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

Symmetrie

$\mathrm{\forall }a,b\in \mathbb{Z}:aRb\Rightarrow bRa$
$6|a^2-b^2\iff 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

$\mathrm{\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\iff 6\cdot q=a^2-b^2,q\in \mathbb{Z}$

$6|b^2-c^2\iff 6\cdot p=b^2-c^2,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\iff 6\cdot q=a^2-b^2,q\in \mathbb{Z}$
$6\cdot q=a^2-b^2\to 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\to \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\to \text{ es kann keine Elemente in R(5) geben, weil alle diese in R(1) verschoben werden}$

Äquivalenzklasse 0

$aR0\iff 6|a^2-0$
$R_0=\{a\in \mathbb{Z}|a^2\equiv 0\text{ mod }6\}=\{0+k\ast 6|k\in \mathbb{Z}\}$
$R_0=\{0,\pm 6,\pm 12,\pm 18,\mathrm{...}\mathrm{\infty }\}(=0mod6)$

Äquivalenzklasse 1

$aR1\iff 6|a^2-1$
$R_1=\{a\in \mathbb{Z}|a^2\equiv 1\text{ mod }6\}=\{-1+k\ast 6|k\in \mathbb{Z}\}$
$R_1=\{\pm 1,\pm 5,\pm 7,\pm 11,\pm 13,\mathrm{...}\mathrm{\infty }\}(=1mod6)$

Äquivalenzklasse 2

$aR2\iff 6|a^2-2$
$R_2=\{a\in \mathbb{Z}|a^2\equiv 2\text{ mod }6\}=\mathrm{\varnothing }$

Äquivalenzklasse 3

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

Äquivalenzklasse 4

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

Äquivalenzklasse 5

$aR5\iff 6|a^2-5$
$R_5=\{a\in \mathbb{Z}|a^2\equiv 5\text{ mod }6\}=\mathrm{\varnothing }$

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