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

Aus VoWi
Zur Navigation springen Zur Suche springen

Sei f \colon \Z \to \R eine beliebige Funktion. Welche der Eigenschaften Reflexivität, Symmetrie und Transitivität hat die folgende Relation auf \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 \Z für die Funktionen

(a) f(x) = 3x,

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

(c) f(x) = x^2.

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.

Antisymmetrie[Bearbeiten, WP, 1.60 Definition]

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

Äquivalenzklasse[Bearbeiten]

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[Bearbeiten, WP, 1.65 Definition]

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

Reflexivität[Bearbeiten]

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

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

Symmetrie ist also auch gegeben

Transitivität[Bearbeiten]

\forall a, b, c \in \Z: aRb \and 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[Bearbeiten]

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

\forall a,b \in \Z: aRb \and 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[Bearbeiten]

(a) f(x) = 3x \quad[Bearbeiten]


aRb \Longleftrightarrow 3a = 3b  \Longleftrightarrow a=b
K(a) = \{ b \in \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 \Z: \left| K(a) \right| = 1

(b) f(x) = x \mod 3[Bearbeiten]


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 \Z_3 liegt.

aRb \Longleftrightarrow (a \mod 3) = (b \mod 3) \Longleftrightarrow \overline a = \overline b

K(\overline a) = \{ b \in \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[Bearbeiten]


aRb \Longleftrightarrow a ^2 = b ^2  \Longleftrightarrow a=b

Hier gilt das gleiche wie in (a)

Anmerkung zu (c)[Bearbeiten]

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 \N\}