TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 135
Auf den Mengen
seien die binären Relationen und gegeben.(a) Für welche A gilt
, d.h. wann handelt es sich bei um eine Funktion?(b) Für welche A ist
eine Funktion, wann sogar injektiv, surjektiv, bijektiv?(c) Sind
und Relationen, so ist (analog zur Komposition von Abbildungen) das Relationenprodukt definiert als Relation .
Beschreiben Sie .(d) Sei
eine Relation auf A. Begründen Sie mittels Induktion, dass die rekursive Definition der Iterationen , , durch und für alleFunktionen definiert, sofern (f also selbst eine Funktion ist).
Hilfreiches[edit]
Funktion[edit]
Eine Funktion oder Abbildung
von nach ist eine Relation mit der Eigenschaft, dass zu jedem genau ein mit existiert. Man schreibt dafür . Der Graph einer Funktion ist die Menge ."Verschiedene Elemente der Definitionsmenge werden auf verschiedene Elemente der Zielmenge abgebildet":
oder äquivalent:Jedes Element der Zielmenge tritt mindestens einmal als Funktionswert auf:
Lösungsvorschlag[edit]
(a)[edit]
Aus der Angabe der Relation folgt
Daher kann
nur eine Funktion auf den Mengen sein, die beinhalten.(b)[edit]
Aus der Angabe der Relation folgt
Das ist eine Relation, die auf allen der angegeben Mengen eine Funktion darstellt.
Injektivität[edit]
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[edit]
Das gilt wiederum nur für die Mengen die enthalten.
Für z. B.
wäre das korrespondierendeWie man leicht erkennt, existiert das in
nicht. Daher kann es in diesen Mengen nicht für alle Elemente aus B ein geben.Bijektivität[edit]
Gilt in all jenen Mengen, wo die Funktion sowohl injektiv als auch surjektiv ist.
Und das sind die Mengen, die
als Teilmenge enthalten.(c)[edit]
Das ist nicht anderes als die identische Funktion, die in allen Mengen bijektiv ist.
(d)[edit]
, also wieder die identische Funktion
Sehen wir uns erst einmal den Induktionsstart an:
für n = 0:
Nachdem wir lt. Angabe davon ausgehen dürfen, dass
eine Funktion ist, ist auch eine Funktionfür n = 1:
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
bereits gültige Aussagen sind. Damit schliesst man dann auf P(n+1)In diesem Fall sieht dass dann so aus:
ist eine Funktion (das nimmt man als gültig an)
ist wieder eine Funktion (Hintereinanderausführung von zwei Funktionen)
ist aber auch
Damit wäre gezeigt dass
eine Funktion ist und damit die Behauptung, dass die rekursive Definition der Iteration immer Funktionen als Ergebnis hat, als wahr bestätigt.