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

Auf den Mengen $A=\mathbb{N},\mathbb{Z},\mathbb{Q},ℝ,ℂ$ 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: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)|\mathrm{\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:A\to A$ definiert, sofern $f:A\to A$ (f also selbst eine Funktion ist).

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

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 $a{R}_{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\ne a_2\Rightarrow f(a_1)\ne 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: $\mathrm{\forall }b\in B\mathrm{\exists }a\in A:b=f(a)$

Lösungsvorschlag

(a)

Aus der Angabe der Relation folgt

$g_A(2x)=x⟺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

$\mathrm{\forall }b\in B\mathrm{\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: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\ge 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.