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

Sei $f\colon \mathbb {Z} \to \mathbb {R}$ eine beliebige Funktion. Welche der Eigenschaften Reflexivität, Symmetrie und Transitivität hat die folgende Relation auf $\mathbb {Z}$?

$mRn\Leftrightarrow f(m)=f(n)$

Unter welcher Voraussetzung an die Funktion f ist die Relation R auch antisymmetrisch? Ist R eine Äquivalenzrelation? Falls ja, bestimmen Sie auch die durch R induzierte Partition auf $\mathbb {Z}$ für die Funktionen

(a) $f(x)=3x$,

(b)$f(x)=x\mod 3$,

(c) $f(x)=x^{2}$.

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$.

Antisymmetrie

Antisymmetrie

$\forall a,b\in M:\quad aRb\wedge bRa\Longrightarrow a=b$

Äquivalenzklasse

Äquivalenzklasse

Sei R eine Äquivalenzklasse auf A. Für $a\in A$ heißt die Menge

$K(a)=\{b\in A|bRa\}$

die von a erzeugte Äquivalenzklasse.

Injektivität

Injektivität

"Verschiedene Elemente der Definitionsmenge werden auf verschiedene Elemente der Zielmenge abgebildet": $a_{1},a_{2}\in A,a_{1}\neq a_{2}\Rightarrow f(a_{1})\neq f(a_{2})$ oder äquivalent: $a_{1},a_{2}\in A,f(a_{1})=f(a_{2})\Rightarrow a_{1}=a_{2}$

Lösungsvorschlag

Reflexivität

$\forall a\in \mathbb {Z} :aRa\Leftrightarrow f(a)=f(a)$

Gilt auf jeden Fall, weil eine Funktion für einen bestimmten Wert immer das gleiche Ergebnis haben muss (ansonsten wäre es keine Funktion)

Symmetrie

$\forall a,b\in \mathbb {Z} :aRb\Rightarrow bRa$
$aRb\Longleftrightarrow f(a)=f(b)\Longleftrightarrow f(b)=f(a)\Longleftrightarrow bRa$

Symmetrie ist also auch gegeben

Transitivität

$\forall a,b,c\in \mathbb {Z} :aRb\land bRc\Rightarrow aRc$
Formel hier einfügen
$aRb\Longleftrightarrow f(a)=f(b)$
$bRc\Longleftrightarrow f(b)=f(c)$
jetzt setzt man in die obere Gleichung die untere ein
$\Rightarrow f(a)=f(c)\Longleftrightarrow aRc$

Daher ist auch Transitivität gegeben.

Äquivalenzrelation

Nachdem wie oben gezeigt sowohl Reflexivität, Symmetrie und Transitivität gegeben ist sind alle Vorraussetzungen für eine Äquivalenzrelation gegeben.
Daher ist R eine Äquivalenzrelation.

Antisymmetrie

$\forall a,b\in \mathbb {Z} :aRb\land bRa\Rightarrow a=b$

$aRb\Longleftrightarrow f(a)=f(b)$
$bRa\Longleftrightarrow f(b)=f(a)$ (diese Gleichung tut hier nichts zur Sache weil sie die Gleiche ist wie aRb)
Nun muss man sich überlegen, welche Eigenschaft die Funktion haben muss damit folgendes gilt
$f(a)=f(b)\Rightarrow a=b$
Das ist aber nichts anderes als eine Abwandlung der Definition von Injektivität.
Daher muss die Funktion injektiv sein, damit die Relation antisymmetrisch ist.

Partitionnierungen

(a) $f(x)=3x\quad$

---

$aRb\Longleftrightarrow 3a=3b\Longleftrightarrow a=b$
$K(a)=\{b\in \mathbb {Z} |a=b\}$

Hier alle Mengen niederschreiben zu wollen wäre relativ mühsam, weil es unendlich viele gibt. Es steckt nämlich jedes einzelne Element aus den ganzen Zahlen in einer eigene Menge.

$\Rightarrow \forall a\in \mathbb {Z} :\left|K(a)\right|=1$

Anmerkung: mMn ist f(x) = 3 injektiv. Was bedeuten würde das diese Relation Anti-Symmetrisch ist. Demnach auch keine Ä-relation woruch es auch keine Klassen zubestimmen gibt

(b)$f(x)=x\mod 3$

---

Die Funktion $f(x)=x\mod 3$ liefert den Rest einer Zahl x modulo 3 zurück.

D.h. in userem Fall stehen zwei Zalen a,b in Relation, wenn jeweils der Rest der Zahlen modulo drei gleich groß ist, wenn also a und b in der gleichen Restklasse von $\mathbb {Z} _{3}$ liegt.

$aRb\Longleftrightarrow (a\mod 3)=(b\mod 3)\Longleftrightarrow {\overline {a}}={\overline {b}}$

$K({\overline {a}})=\{b\in \mathbb {Z} |{\overline {a}}={\overline {b}}\}$

Daraus ergeben sich folgende drei Klassen:
$K({\overline {0}})=\{{\overline {0}}\}=\{\ldots ,-9,-6,-3,0,3,6,9,\ldots \}$
$K({\overline {1}})=\{{\overline {1}}\}=\{\ldots ,-8,-5,-2,1,4,7,10,\ldots \}$
$K({\overline {2}})=\{{\overline {2}}\}=\{\ldots ,-7,-4,-1,2,5,8,11,\ldots \}$

(c) $f(x)=x^{2}$

---

$aRb\Longleftrightarrow a^{2}=b^{2}\Longleftrightarrow a=b$

Hier gilt das gleiche wie in (a)

Anmerkung zu (c)

Zwei Elemente (Zahlen) sind in der selben Klasse, wenn das Quadrat beider Zahlen gleich ist. Für die natürlichen Zahlen stimmt obige Lösung. Für die ganzen Zahlen muss man allerdings die negativen Zahlen berücksichtigen zB.:

$(-2)^{2}=4=2^{2}$

Daher folgt, dass die Zerlegung aussieht wie folgt:

$\{\{0\},\{-1,1\},\{-2,2\},\ldots \}=\{\{x,-x\}|x\in \mathbb {N} \}$