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

Auf den Mengen $A = \N, \Z,\Q,\R,\C$ seien die binären Relationen $f_A := \{(x, 2x) | x \in A\}$ und $g_A := \{(2x, x) | x \in A\}$ gegeben.

(a) Für welche A gilt $g_A \colon A \to A$, d.h. wann handelt es sich bei $g_A$ um eine Funktion?

(b) Für welche A ist $f_A$ eine Funktion, wann sogar injektiv, surjektiv, bijektiv?

(c) Sind $f \subseteq A \times B$ und $g \subseteq B \times C$ Relationen, so ist (analog zur Komposition von Abbildungen) das Relationenprodukt $g\circ f \subseteq A \times C$ definiert als Relation $\{(a, c) | \exist b \in B : (a, b) \in f, (b, c) \in g \}$.
Beschreiben Sie $g_A \circ f_A$.

(d) Sei $f \subseteq A \times A$ eine Relation auf A. Begründen Sie mittels Induktion, dass die rekursive Definition der Iterationen $f^n$, $n \in N$, durch $f^0 := \{(x, x)| x \in A\}$ und $f^{n+1} := f \circ f^n$ für alle

$n \in N$ Funktionen $f^n \colon A \to A$ definiert, sofern $f \colon A \to A$ (f also selbst eine Funktion ist).

Hilfreiches

Funktion

Eine Funktion oder Abbildung $f : A \to B$ von $A$ nach $B$ ist eine Relation $R_{f} \subseteq A \times B$ mit der Eigenschaft, dass zu jedem $a \in A$ genau ein $b \in B$ mit $aR_{f}b$ existiert. Man schreibt dafür $b = f(a)$. Der Graph einer Funktion $f : A \to B$ ist die Menge $\{(a, f(a))|a \in A\} \subseteq A \times B$.

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

Surjektivität

Jedes Element der Zielmenge tritt mindestens einmal als Funktionswert auf:

$\forall b\in B\ \exists a\in A: b=f(a)$

Lösungsvorschlag

(a)

Aus der Angabe der Relation folgt

$g_A(2x) = x \Longleftrightarrow g_A(x) = \frac x2$

Daher kann $g_A$ nur eine Funktion auf den Mengen sein, die $\Q$ beinhalten.

(b)

Aus der Angabe der Relation folgt

$f_A(x) = 2x$

Das ist eine Relation, die auf allen der angegeben Mengen eine Funktion darstellt.

Injektivität

$f(a) = f(b) \Rightarrow a=b$ Das gilt wieder für alle der angegeben Mengen

(Mir fällt zumindest in keiner Menge ein Beispiel ein, für dass das nicht gelten würde)

Surjektivität

$\forall b \in B \exist a\in A: f(a) = b$ Das gilt wiederum nur für die Mengen die $\Q$ enthalten.

Für z. B. $b = 3$ wäre das korrespondierende $a = \frac 32$

Wie man leicht erkennt, existiert das in $\N, \Z$ nicht. Daher kann es in diesen Mengen nicht für alle Elemente aus B ein $a \in A$ geben.

Bijektivität

Gilt in all jenen Mengen, wo die Funktion sowohl injektiv als auch surjektiv ist.

Und das sind die Mengen, die $\Q$ als Teilmenge enthalten.

(c)

$(g_A \circ f_A)(x) = g_A(f_A(x)) = g_A(2x) = \frac {2x}{2} = x$

Das ist nicht anderes als die identische Funktion, die in allen Mengen bijektiv ist.

(d)

$f^0(x)=x$, also wieder die identische Funktion

Sehen wir uns erst einmal den Induktionsstart an:

für n = 0:

$f^{1}(x) = (f \circ f^0)(x) = f(f^0(x)) = f(x)$

Nachdem wir lt. Angabe davon ausgehen dürfen, dass $f \colon A \to A$ eine Funktion ist, ist auch $f^1$ eine Funktion

für n = 1:

$f^{2}(x) = (f \circ f^1)(x) = f(f^1(x)) = f(f(x))$

Die Hintereinanderausführung von zwei Funktionen ergibt immer wieder eine Funktionen, daher gilt die Induktionsvorraussetzung auch für den Fall n = 1.

Bei der Beweisführung der Induktion gibt es eine Variante, wo man davon ausgeht, dass die Vorraussetztung P(n) für alle $k \geq n$ bereits gültige Aussagen sind. Damit schliesst man dann auf P(n+1)

In diesem Fall sieht dass dann so aus:

$f^n$ ist eine Funktion (das nimmt man als gültig an)

$f \circ f^n$ ist wieder eine Funktion (Hintereinanderausführung von zwei Funktionen)

$f \circ f^n$ ist aber auch $f^{n+1}$

Damit wäre gezeigt dass $f^{n+1}$ eine Funktion ist und damit die Behauptung, dass die rekursive Definition der Iteration immer Funktionen als Ergebnis hat, als wahr bestätigt.