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 alle
Funktionen
definiert, sofern
(f also selbst eine Funktion ist).
Inhaltsverzeichnis
Hilfreiches[Bearbeiten]
Funktion[Bearbeiten]
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[Bearbeiten]
(a)[Bearbeiten]
Aus der Angabe der Relation folgt
Daher kann nur eine Funktion auf den Mengen sein, die
beinhalten.
(b)[Bearbeiten]
Aus der Angabe der Relation folgt
Das ist eine Relation, die auf allen der angegeben Mengen eine Funktion darstellt.
Injektivität[Bearbeiten]
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]
Das gilt wiederum nur für die Mengen die
enthalten.
Für z. B. wäre das korrespondierende
Wie man leicht erkennt, existiert das in nicht. Daher kann es in diesen Mengen nicht für alle Elemente aus B ein
geben.
Bijektivität[Bearbeiten]
Gilt in all jenen Mengen, wo die Funktion sowohl injektiv als auch surjektiv ist.
Und das sind die Mengen, die als Teilmenge enthalten.
(c)[Bearbeiten]
Das ist nicht anderes als die identische Funktion, die in allen Mengen bijektiv ist.
(d)[Bearbeiten]
, 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 Funktion
fü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.