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

From VoWi
Jump to navigation Jump to search

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).

Hilfreiches[edit]

Funktion
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 .

Injektivität
Injektivität[Bearbeiten, Wikipedia, 1.65 Definition]

"Verschiedene Elemente der Definitionsmenge werden auf verschiedene Elemente der Zielmenge abgebildet": oder äquivalent:

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

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