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

Auf den Mengen $A=\mathbb {N} ,\mathbb {Z} ,\mathbb {Q} ,\mathbb {R} ,\mathbb {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)|\exists 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

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

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

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 {x}{2}}$

Daher kann $g_{A}$ nur eine Funktion auf den Mengen sein, die $\mathbb {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\exists a\in A:f(a)=b$ Das gilt wiederum nur für die Mengen die $\mathbb {Q}$ enthalten.

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

Wie man leicht erkennt, existiert das in $\mathbb {N} ,\mathbb {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 $\mathbb {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.