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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Funktion
Funktion[Bearbeiten]

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

Surjektivität
Surjektivität[Bearbeiten, WP, 1.65 Definition]

Jedes Element der Zielmenge tritt mindestens einmal als Funktionswert auf: \forall b\in B\ \exists a\in A: b=f(a)

Lösungsvorschlag[Bearbeiten]

(a)[Bearbeiten]

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

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

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

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

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

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

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.