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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Hilfreiches[Bearbeiten]

Äquivalenzrelation[Bearbeiten]

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[Bearbeiten]

Zeigen der Äquivalenzrelation[Bearbeiten]

Reflexivität[Bearbeiten]

 aRa\Leftrightarrow 6|a^2-a^2

 6|0 6 teilt 0 also ist es Reflexiv.

Symmetrie[Bearbeiten]

\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[Bearbeiten]

\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[Bearbeiten]

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[Bearbeiten]

Anwendung von Satz 1.59

Allgemein[Bearbeiten]

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[Bearbeiten]

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,\pm6,\pm12,\pm18,...\infty \} (= 0 \mod 6)

Äquivalenzklasse 1[Bearbeiten]

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=\{\pm1,\pm5,\pm7,\pm11,\pm13,...\infty \}(= 1 \mod 6)

Äquivalenzklasse 2[Bearbeiten]

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

Äquivalenzklasse 3[Bearbeiten]

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=\{\pm3,\pm9,\pm15,\pm21,...\infty \}

Äquivalenzklasse 4[Bearbeiten]

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=\{\pm2,\pm4,\pm8,\pm10,\pm14,...\infty \}

Äquivalenzklasse 5[Bearbeiten]

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

Partition[Bearbeiten]

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[Bearbeiten]

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