Lösungen 2 zum Mathematik-Brückenkurs

Lösungen 2 zum Mathematik-Brückenkurs
für alle, die sich für Mathematik interessieren
Carl Hammann, µFSR, TU Dresden
Version vom 1. Oktober 2015,
Fehler und Verbesserungsvorschläge bitte an
[email protected]
2 Relationen und Funktionen
Folgendes Bild stellt die Beziehungen zwischen den Hauptfiguren von Mozarts Oper
„Così fan tutte“ dar, dabei bedeutet ein Pfeil mit einem „♥“, dass die Figur, von der
der Pfeil ausgeht, die andere Figur liebt, eine Verbindung mit einem „K“, dass die
Figuren Komplizen sind, und eine Verbindung mit einem „=“, dass die Figuren in
Wirklichkeit ein und die selbe Person sind.
=
„Albanier“ 1
♥
Ferrando
K
„Arzt“
=
Despina
Dorabella
♥
♥
K
♥
♥
K
Guglielmo
Fiordiligi
♥
=
„Albanier“ 2
Abbildung 1: Beziehungen zwischen Figuren in „Così fan tutte“
1
Aufgabe 2.1. Wie könnte man die ungerichteten Beziehungen (Komplizenschaft und Identität)
aus unserem Beispiel mengenmäßig definieren?
Lösung. Zum Beispiel könnte man ungerichtete Bezihungen als Mengen zweielementiger Mengen modellieren, weil es in Mengen keine Reihenfolge gibt. In unserem Beispiel wäre das für die Komplizenschaftsbeziehung die Menge
{{Despina, Ferrando}, {Despina, Guglielmo}, {Guglielmo, Ferrando}}.
Eine andere Möglichkeit wäre es, eine Relation zu nehmen und für jedes Paar ( a, b)
auch das Paar (b, a) zur Relation hinzuzufügen (also die andere Richtung in der wechselseitigen Beziehung).
Aufgabe 2.2. Man könnte auch meinen, dass die drei Komplizen Ferrando, Guglielmo und
Despina in einer Beziehung stehen, zu der drei Menschen gehören und nicht in drei „Paarbeziehungen“. Wie könnte man so eine mehrstellige Relation modellieren?
Lösung. Im Falle von Ferrando, Guglielmo und Despina gibt es keine in der Beziehung
ausgezeichneten Figur; alle sind als Komplizen gleich. Man könnte also die Komplizenschaftsbeziehung durch eine Menge modellieren, die für jede „Bande“ eine Menge
enthält. In unserem Beispiel gibt es nur eine solche Bande, also wäre unser Modell die
Menge {{Ferrando, Guglielmo, Despina}}.
Vielleicht gibt es aber auch mehrstellige Relationen wie „Vater, Mutter, Kind“, in
der jedem eine besondere Bedeutung zukommt. Solch eine Beziehung könnte man
zum Beispiel durch eine Menge von Tripeln der Form (<Vater>, <Mutter>, <Kind>)
darstellen. Weil es in Tupeln eine festgelegte Reihenfolge gibt, kann man die Rolle der
Person in der Beziehung an der Position im Tupel erkennen.
Aufgabe 2.3. Seien f : A → B und g : B → C Funktionen. Zeige, dass g ◦ f konstant ist,
wenn mindestens eine der Funktionen f und g konstant ist!
Gilt die Umkehrung auch, das heißt: Folgt aus der Konstanz von g ◦ f schon, dass mindestens eine der Funktionen f und g konstant ist? Begründe!
Lösung. Sei mindestens eine der Funktionen f und g konstant. Wir zeigen hier nur den
Fall, dass f konstant ist. Der Fall, das g konstant ist, geht im Wesentlichen genau so.
es gibt also ein b ∈ B, sodass f ( a) = b für alle a ∈ A. Dann gilt für alle a ∈ A, dass
g ◦ f ( a) = g( f ( a)) = g(b), also ist g ◦ f konstant g(b).
Die Umkehrung gilt nicht. Betrachte dazu A = B = C = {1, 2, 3} und die Funktionen f : A → A und g : A → A, die definiert sind durch folgende Wertetabellen:
x
f (x)
1
1
2
2
x
g( x )
3
2
1
2
2
2
3
1
Dann gilt g ◦ f ( a) = 2 für alle a ∈ A.
Aufgabe 2.4. Sei f : A → B eine Funktion und gebe es eine Funktion g : B → A mit
g ◦ f = id A . Gib ein Beispiel dafür an, dass f dann noch keine Umkehrfunktion haben muss!
2
Lösung. Sei A = {1, 2} und B = {1, 2, 3}. Betrachte die Funktionen f : A → A und
g : B → A, die durch folgende Wertetabellen gegeben sind:
x
f (x)
1
2
x
g( x )
2
3
1
1
2
1
3
2
Dann gilt g ◦ f = id A , aber es kann keine Funktion h mit f ◦ h = idB geben, weil
diese Verkettung nur zwei Werte (nämlich f (1) = 2 und f (2) = 3) annehmen kann,
aber B drei Elemente hat.
Aufgabe 2.5. Gib ein Beispiel für eine Funktion f : A → A an, wobei A eine beliebige
Menge ist, sodass f eine Involution, aber nicht die Identität ist! Gib auch ein Beispiel einer
idempotenten Funktion, die nicht die Identität ist!
Lösung. Sei A = {1, 2, 3} und f : A → A gegeben durch
x
f (x)
1
1
2
3
3
2
Dann gilt f ◦ f = id A . Jede konstante Funktion ist eine idempotente Funktion, die
(falls A mehr als ein Element hat) nicht die Identität ist.
Aufgabe 2.6. Sei f : A → A eine Funktion, die eine Umkehrfunktion f −1 und einen Fixpunkt
a ∈ A hat. Hat f −1 dann auch einen Fixpunkt und wenn ja, welchen? Begründe!
Lösung. Ja. f −1 hat auch den Fixpunkt a. Man kann das folgendermaßen sehen: Es gilt
f −1 ( f ( a)) = a, da f −1 die Umkehrfunktion von f ist. Allerdings gilt nach Voraussetzung, dass f den Fixpunkt a hat, auch f ( a) = a und damit folgt f −1 ( a) = a.
Aufgabe 2.7. Sei f : A → B eine Funktion und Ã ⊆ A. Zeige, dass dann f | Ã = f ∩ ( Ã × B)
ist! (Dabei betrachten wir die Funktion f ganz streng im Sinne von Definition 2.2 als Menge
von Paaren.)
Lösung. Sei ( a, b) ∈ f | Ã . Dann gilt nach Definition von f | Ã , dass f ( a) = b und a ∈ Ã.
Damit ist
( a, b) ∈ {( a, b)| f ( a) = b ∧ a ∈ Ã} = f ∩ ( Ã × f ( A)) ⊆ f ∩ ( Ã × B).
Andererseits sei ( a, b) ∈ f ∩ ( Ã × B). Dann gilt a ∈ Ã, b ∈ B und ( a, b) ∈ f , also
f ( a) = b. Damit ist ( a, b) ∈ f | Ã .
Aufgabe 2.8. Welche der bislang definierten Mengenoperationen „vertragen sich“ mit der
Bildmenge oder der Urbildmenge?
Genauer: Seien f : A → B eine Funktion, M, N ⊆ A und O, P ⊆ B. Gelten zum Beispiel
f ( M ∩ N ) = f ( M) ∩ f ( N ) oder f −1 (O \ P) = f −1 (O) \ f −1 ( P)? Überlege dir, welche
ähnlichen Ausdrücke (also mit anderen Mengenoperationen) gelten!
Sind Bildmenge und Urbildmenge monoton, d.h. gilt für eine beliebige Funktion f : A → B,
M, N ⊆ A und O, P ⊆ B mit M ⊆ N und O ⊆ P, dass f ( A) ⊆ B und f −1 (O) ⊆ f −1 ( P)?
3
Lösung. Von dieser sehr umfangreichen Aufgabe lösen wir hier nur beispielhafte Teile.
Bei konkreten Fragen kann man an [email protected] schreiben.
Es gilt
f ( M ∪ N ) ={b ∈ B|∃ a ∈ M ∪ N : f ( a) = b}
={b ∈ B|(∃ a ∈ M : f ( a) = b) ∨ (∃ a ∈ N : f ( a) = b)}
={b ∈ B|∃ a ∈ M : f ( a) = b} ∪ {b ∈ B|∃ a ∈ N : f ( a) = b}
= f ( M ) ∪ f ( N ).
Allerdings gilt für A = B = {1, 2, 3}, M = {1, 2}, N = {2, 3} und f entsprechend der
Wertetabelle
x
f (x)
1
1
2
2
3
,
1
dass f ( M \ N ) = {1} 6= ∅ = {1, 2} \ {1, 2} = f ( M) \ f ( N ).
Aufgabe 2.9. Sei R ⊆ A × A eine Relation. Beweise, dass R nicht antisymmetrisch sein
muss, wenn wenn R nicht symmetrisch ist und umgekehrt.
Lösung. Die Relation R := {( a, a)| a ∈ A} ist symmetrisch und antisymmetrisch zugleich.
Aufgabe 2.10. Seien R, S ⊆ A × A Relationen. Wie vertragen sich die oben definierten
Eigenschaften mit der Vereinigung und dem Durchschnitt? Das heißt: Wenn R und S zum
Beispiel reflexiv/transitiv/symmetrisch/antisymmetrisch ist, sind R ∩ S und R ∪ S dann auch
reflexiv/transitiv/symmetrisch/antisymmetrisch?
Lösung. Von dieser umfangreichen Aufgabe lösen wir hier nur beispielhafte Teile. Bei
konkreten Fragen kann man an [email protected] schreiben.
Seien R und S symmetrisch. Dann ist Die Relation R ∩ S auch symmetrisch: Sei
( a, b) ∈ R ∩ S. Dann gilt ( a, b) ∈ R und damit, dass R symmetrisch ist, folgt (b, a) ∈ R.
Genauso folgt (b, a) ∈ S, womit insgesamt (b, a) ∈ R ∩ S folgt.
Sei A := {1, 2, 3}. Dann sind die Relationen R := {(1, 2), (2, 1), (1, 1), (2, 2)} und
S := {(2, 3), (3, 2), (2, 2), (3, 3)} transitiv, aber ihre Vereinigung nicht, weil sie die Paare
(1, 2) und (2, 3), aber nicht das Paar (3, 1) enthält.
Aufgabe 2.11. Überlege dir, dass die Relation ≤ auf den reelen Zahlen eine Ordnungsrelation
ist!
Lösung. Wurde in der Übung gemeinsam gelöst.
Aufgabe 2.12. Vervollständige folgendes Bild indem du so vier Pfeilspitzen hinzufügst, dass
die Menge R, die für jeden der Pfeile ein Paar ( a, b) aus seinem Anfangspunkt a und seinem Endpunkt b und auch noch für jedes a ∈ {1, 2, 3, 4, 5, 6} das Paar ( a, a) enthält, eine
Ordnungsrelation wird!
4
2
1
3
6
5
4
Welches Prinzip fällt dir auf? (Welche Konfigurationen sind verboten)?
Lösung. Diese Aufgabe soll eine Knobelaufagbe blieben. Lösungen kann man an die
Adresse [email protected] schreiben.
Aufgabe 2.13. Überlege dir, dass die Relation = auf den reellen Zahlen eine Ordnungsrelation
ist!
Lösung. Wurde in der Übung gemeinsam gelöst.
Aufgabe 2.14. Sei S ⊆ A × A eine Ordnungsrelation. Zeige, dass dann R := {( a, b) ∈ A :
S( a, b) ∧ S(b, a)} eine Äquivalenzrelation ist.
Aufgabe 2.15. Welche der folgenden Funktionen sind surjektiv/injektiv/bijekiv? Begründe!
1. f : N → N; n 7→ n + 1
2. g : {1, 2, 3} → {1, 2}; n 7→ 1
3. h : R → {−1, 1}; x 7→
x
|x|
4. j : R → R; x 7→ x + 1
Lösung.
1. injektiv (aus n + 1 = m + 1 folgt n = m), nicht surjektiv (die 1 hat kein Urbild)
2. nicht injektiv (die 1 hat zwei Urbilder), nicht surjektiv (die 2 hat kein Urbild)
3. nicht injektiv (es gilt h(−1) = h(−2)), surjektiv (es gilt h(−1) = −1 und h(1) =
1)
4. injektiv (aus x + 1 = y + 1 folgt x = y), surjektiv (für alle x ∈ R gilt f ( x − 1) = x),
also bijektiv
5
Aufgabe 2.16. Seien f : A → B und g : B → C Funktionen. Zeige, dass, falls g ◦ f injektiv
ist, schon f injektiv sein muss! Zeige auch, dass, wenn g ◦ f surjektiv ist, schon g surjektiv
sein muss!
Lösung. Zur ersten Behauptung: Seien f und g Funktionen wie in der Aufgabe und
g ◦ f injektiv. Dann gilt für alle a, b ∈ A, dass aus g( f ( a)) = g( f (b)) schon a = b folgt.
Falls also f ( a) = f (b) gilt folgt damit, dass g eine Funktion ist, dass a = b und damit
die Behauptung.
Zur zweiten Behauptung: Seien f und g wie in der Aufgabe und g ◦ f surjektiv.
Dann gibt es für jedes c ∈ C ein a ∈ A mit g ◦ f ( a) = c. Damit gibt es also für jedes
c ∈ C ein b ∈ B, sodass g(b) = c, nämlich f ( a). Also ist auch g surjektiv.
Aufgabe 2.17. Seien A und B Mengen mit m beziehungsweise n Elementen. Wie viele injektive/surjektive/bijektive Funktionen f : A → B gibt es?
Lösung. Wir betrachten drei Fälle:
1. Falls m > n, kann es keine surjektive Funktion geben, weil jedes a ∈ A auf genau
ein b ∈ B abgebildet wird ( f ist eine Funktion!), und demzufolge nicht alle b ∈ B
„erreicht werden“.
Wir zählen jetzt, wie viele injektive Funktionen f : A → B es geben kann. Das
erste Element von A bilden wir auf ein beliebiges Element von B ab. Dafür gibt
es m Möglichkeiten. Für das zweite, weil es sich ja vom ersten unterscheiden
soll, noch m − 1, für das dritte m − 2 und so weiter. Damit hören wir auf, wenn
es keine Elemente von A mehr gibt. Für das letzte Element von A gibt es noch
m − n + 1 Möglichkeiten, also gibt es insgesamt
m · ( m − 1) · ( m − 2) · · · ( m − n + 1)
injektive Funktionen.
2. Falls n > m, kann es keine injektive Funktion A → B geben, weil in jedem Fall
mindestens ein b ∈ B mehr als ein Urbild haben muss.
Wir zählen jetzt, wie viele surjektive Funktionen f : A → B es geben kann.
Zuerst müssen wir genau einmal auf jedes Element von B abbilden: Für das
erste haben wir also m Möglchkeiten, für das zweite, weil es sich ja vom ersten
unterscheiden soll, noch m − 1, für das dritte m − 2 und so weiter. Dafür gibt es
also m · (m − 1) · (m − 2) · · · 2 · 1 Möglichkeiten. Jetzt sind noch n − m Elemente
von A übrig, die wir beliebig verteilen können dafür gibt es mn−m Möglichkeiten
(m für das erste, m für das zweite, m für das dritte und so weiter). INsegamt gibt
es also
m · ( m − 1) · ( m − 2) · · · 2 · 1 · m n − m
surjektive Funktionen.
6
3. Falls m = n, dann ist jede injektive Funktion auch surjektiv: Angenommen eine
Funktion f : A → B sei nicht injektiv. Dann gibt es a1 , a2 ∈ A mit f ( a1 ) = f ( a2 ).
Ein Element von B hat also mehr als ein Urbild. Weil aber A genau so viele Elemente wie B enthält, muss es damit auch mindestens ein Element von B geben,
das kein Urbild hat. Andersherum kann für m = n keine Funktion, die nicht
surjektiv ist, injektiv sein, denn, da f eine Funktion ist (und also jedes Element
von A ein Bild haben muss), aus der Tasache, dass es ein Element von B gibt,
das nicht von f als Funktionswert angenommen wird, folgt, dass es mindestens
ein Element von B mit mehreren Urbildern gibt.
In diesem Fall stimmen also die Anzahlen der injektiven und surjekitven Funktionen überein (und sind die Zahl der bojektiven Funktionen). Es gibt dann
m · ( m − 1) · ( m − 2) · · · 2 · 1
bijektive Funktionen.
Aufgabe 2.18. Sei f : A → B eine Funktion. Zeige, dass f eine Umkehrfunktion hat, wenn
f bijektiv ist! Du darfst dabei ohne Beweis verwenden, dass jede surjektive Funktion eine
Rechtsinverse hat, das heißt dass es für jede surjektive Funktion g : X → Y eine Funktion
h : Y → X mit g ◦ h = idY gibt. (Zum Beweis dieser Aussage benötigt man nämlich das
sogenannte Auswahlaxiom, das wir noch nicht kennen)
Lösung. Sei f : A → B eine bijektive Funktion. Als bijektive Funktion ist f insbesondere surjektiv; nach Aufgabenstellung dürfen wir also annehmen, dass f schon eine
Rechtsinverse g hat. Wir zeigen nun, dass diese Rechtsinverse auch die Linksinverse
von f ist, das heißt, dass für alle b ∈ B gilt, dass f ◦ g(b) = b, womit die Behauptung
dann bewiesen ist.
Aufgabe 2.19. Sei A eine Menge. Zeige, dass dann |P( A)| ≥ | A|.
Lösung. Für die leere Menge gilt die Behauptung, denn |P(∅)| = 1 > 0 = |∅|. Sei A
also nun nicht die leere Menge und a0 ∈ A. Die Funktion f : P( A) → A, die gegeben
ist durch f ({ a}) = a für alle a ∈ A und f ( M) = a0 für alle nicht-einelementigen
Teilmengen von A ist surjektiv, wie man leicht sieht. Also ist nach Definition |P( A)| ≥
| A |.
Aufgabe 2.20. Seien A und B Mengen, wobei A ⊆ B. Mache dir klar, das dann auch | A| ≤
| B |.
Lösung. Falls A ⊆ B, ist die Funktion f : A → B; a 7→ a injektiv, wie man sich leicht
überlegt. Nach Definition ist damit | A| ≤ | B|.
7

Download Report