Embed Size (px)
Citation preview
Injektiv, Surjektiv, Bijektiv
Aufgabe 1. Geben Sie einen ausfuhrlichen Beweis fur folgende Aussage: Wennf ∈ A → B surjektiv ist und RA ⊆ A × A eine reflexive Relation auf Aist, dann ist
RB ={(
f(x), f(y))| (x, y) ∈ RA
}eine reflexive Relation auf B.
Losung von Aufgabe 1.
• Sei f ∈ A → B beliebig aber fest und RA ⊆ A×A beliebig aber fest.Sei weiterhin
RB ={(
f(x), f(y))| (x, y) ∈ RA
}.
Zu zeigen: Wenn f surjektiv und RA reflexiv auf A ist, dann ist RB
reflexiv auf B.
• Annahme f ist surjektiv und RA reflexiv auf A. Zu zeigen RB istreflexiv auf B.
• Definition von reflexiv: Zu zeigen ist, dass fur jedes b ∈ B gilt (b, b) ∈RB .
• Sei b ∈ B beliebig aber fest. Da f surjektiv ist, gibt es ein a ∈ A sodass f(a) = b.
• Da RA reflexiv auf A ist, gilt (a, a) ∈ RA.
• Laut Definition von RB ist somit(f(a), f(a)
)∈ RB .
• Da f(a) = b ist somit (b, b) ∈ RB .
Aufgabe 2. Seien A und B Mengen und
π1 =(A×B,A,
{((a, b), a
)| a ∈ A, b ∈ B
})π2 =
(A×B,B,
{((a, b), b
)| a ∈ A, b ∈ B
}).
Begrunden Sie unter Verwendung der Eigenschaften von Paaren, dass π1
und π2 Funktionen sind und beschreiben Sie anschaulich, was π1 bzw. π2
tun. Sei nun A = N und B = Z. Berechnen Sie
π1(1,−1), π2(1,−1), π1(3, 3), π2(3, 3).
Sind π1 und π2 injektiv bzw. surjektiv? Finden Sie ein Gegenbeispiel odergeben Sie einen Beweis. Hinweis: Es handelt sich bei π1 und π2 um dieProjektionsfunktionen auf die erste bzw. zweite Komponente.
Losung von Aufgabe 2. Da sich π1 und π2 analog verhalten, wird nur eineLosung fur π1 gegeben. Sei
R1 ={(
(a, b), a)| a ∈ A, b ∈ B
}.
1
• Offensichtlich gilt R1 ⊆ (A×B)×A.
• Es wurde gezeigt, dass es zu jedem Paar p ∈ A×B genau ein a ∈ Aund genau ein b ∈ B gibt, so dass p = (a, b). Folglich gibt es zu jedemp ∈ A×B genau ein a ∈ A so dass pR1a.
Damit ist bewiesen, dass π1 eine Funktion ist. Die Funktion π1 ∈ A×B →A ordnet jedem Paar p ∈ A×B seine erste Komponente zu. Analog ordnetπ2 ∈ A×B → B jedem Paar p ∈ A×B seine zweite Komponente zu.
Fur A = N und B = Z erhalt man
π1(1,−1) = 1, π2(1,−1) = −1, π1(3, 3) = 3, π2(3, 3) = 3.
• π1 ist nicht injektiv, da z.B. π1(1, 1) = π1(1, 2).
• Zu zeigen: π1 ist surjektiv.Zu zeigen: Fur alle a ∈ N gibt es ein p ∈ N× Z so dass π1(p) = a.Sei a ∈ N beliebig aber fest.Zu zeigen: Es gibt ein p ∈ N×Z so dass π1(p) = a. Beispielsweise furp = (a, 42) gilt π1(p) = a.
Aufgabe 3. Die Funktion f ∈ (Z× N) → Q ist definiert durch
f(x, y) = x/y.
Ist f injektiv bzw. surjektiv? Geben Sie jeweils einen Satz Begrundung.
Losung von Aufgabe 3. Die Funktion ist nicht injektiv, da z.B.
f(1, 1) = f(2, 2) aber (1, 1) 6= (2, 2).
Die Funktion ist surjektiv, da man zu jeder rationalen Zahl q ∈ Q einenZahler x ∈ Z und einen Nenner y ∈ N finden kann so dass
q = x/y.
Aufgabe 4. Seif = (N, N → N, R)
eine Funktion mit dem Graphen
R ={
(a, b) | a ∈ N, b =(N, N, {(x, y) | x, y ∈ N, y = x + a}
)}.
• Uberlegen Sie sich anschaulich was die Funktion f “macht” und be-rechnen Sie dann f(3).
• Ist f injektiv bzw. surjektiv? Jeweils ein Satz Begrundung.
Losung von Aufgabe 4.
2
• Die Funktion f nimmt als Input eine naturliche Zahl a und liefert alsOutput die Funktion g ∈ N → N mit g(x) = x + a. Folglich ist f(3)die Funktion
f(3) = (N, N, {(x, y) | x, y ∈ N, y = x + 3}),
• f ist injektiv. Ist a1 6= a2 dann sind auch die Funktionen f(a1)(x) =x + a1 und f(a2)(x) = x + a2 unterschiedlich.
• f ist nicht surjektiv. Es gibt z.B. kein a ∈ N so dass z.B. f(a)(x) = 2x.
Aufgabe 5. Finden Sie eine Relation R so dass das Tripel
f = ({1, 2, 3}, {4, 5}, R)
eine Funktion ist, die aber nicht surjektiv ist.
Losung von Aufgabe 5. Zum Beispiel
R = {(1, 4), (2, 4), (3, 4)}.
Aufgabe 6. Sei ≤N die kleiner gleich Relation auf N und
f ∈ N → P (N) mit f(x) = {y | y ≤N x}.
• Berechnen Sie f(3).
• Ist f injektiv? Ist f surjektiv? Geben Sie jeweils einen ausfuhrlichenBeweis oder nennen Sie ein Gegenbeispiel.
Losung von Aufgabe 6.
• f(3) = {1, 2, 3}.• f ist nicht surjektiv da z.B.
{2} ∈ P (N)
aber es gibt kein x ∈ N so dass f(x) = {2}.• f ist injektiv.
– Zu zeigen:
∀x1, x2 ∈ N x1 6= x2 → f(x1) 6= f(x2).
– Sei x1, x2 ∈ N beliebig aber fest. Zu zeigen:
x1 6= x2 → f(x1) 6= f(x2).
– Annahme:x1 6= x2.
Zu zeigen:f(x1) 6= f(x2).
3
– Definition von f . Zu zeigen:
{y | y ≤N x1} 6= {y | y ≤N x2}.
– Definition der Mengengleichheit. Zu zeigen:
{y | y ≤N x1} 6⊆ {y | y ≤N x2} ∨ {y | y ≤N x2} 6⊆ {y | y ≤N x1}.
– Aussagenlogische Umformung. Zu zeigen:
{y | y ≤N x1} ⊆ {y | y ≤N x2} → {y | y ≤N x2} 6⊆ {y | y ≤N x1}.
– Annahme:{y | y ≤N x1} ⊆ {y | y ≤N x2}.
Zu zeigen:{y | y ≤N x2} 6⊆ {y | y ≤N x1}.
– Definition der Teilmengenbeziehung. Annahme:
∀z z ∈ {y | y ≤N x1} → z ∈ {y | y ≤N x2}.
Zu zeigen:
∃w w ∈ {y | y ≤N x2} ∧ w 6∈ {y | y ≤N x1}.
– Definition der Mengen. Zu zeigen:
∀z z ≤N x1 → z ≤N x2.
Zu zeigen:∃w w ≤N x2 ∧ w 6≤N x1.
– Spezialfall. Wahle x1 fur z. Annahme:
x1 ≤N x1 → x1 ≤N x2.
– Da x1 ≤N x1 folgt mit Modus Ponens dass
x1 ≤N x2.
Da weiterhin x1 6= x2 folgt
x1 < x2
bzw.x2 6≤N x1.
– Es gilt somitw ≤N x2 ∧ w 6≤N x1
fur die Wahl w = x2.
4
Aufgabe 7. Schreiben Sie auf wann ein Tripel (A,B, R) eine partielle Funkti-on, eine totale Funktion, eine injektive, surjektive bzw. bijektive Funktionist. Fullen Sie dabei jeweils die Lucken auf in dem Satz
Zu jedem . . . ∈ . . . existiert mindestens/hochstens/genau ein . . . ∈ . . . sodass aRb.
Losung von Aufgabe 7.
• Partielle Funktion: Zu jedem a ∈ A existiert hochstens ein b ∈ B sodass aRb.
• Totale Funktion: Zu jedem a ∈ A existiert genau ein b ∈ B so dassaRb.
• Injektiv: Zu jedem b ∈ B existiert hochstens ein a ∈ A so dass aRb.
• Surjektiv: Zu jedem b ∈ B existiert mindestens ein a ∈ A so dassaRb.
• Bijektiv: Zu jedem b ∈ B existiert genau ein a ∈ A so dass aRb.
Aufgabe 8. Finden Sie jeweils 3 Beispiele von Funktionen, die
• weder injektiv noch surjektiv,
• injektiv aber nicht surjektiv,
• surjektiv aber nicht injektiv,
• injektiv und surjektiv
sind.
Losung von Aufgabe 8.
• weder injektiv noch surjektiv:
– f ∈ R → R, f(x) = x2
– f ∈ R → R, f(x) = sin(x)– f ∈ R → R, f(x) = |x|
• injektiv aber nicht surjektiv:
– f ∈ R+ → R, f(x) = x2
– f ∈ [0, π/2] → R, f(x) = sin(x)– f ∈ R+ → R, f(x) = |x|
• surjektiv aber nicht injektiv:
– f ∈ Z2 → Z, f(x, y) = x + y
– f ∈ R2 → R, f(x, y) = xy
– f ∈ R → [−1, 1], f(x) = sin(x)
• injektiv und surjektiv:
5
– f ∈ R+ → R+, f(x) = x2
– f ∈ R → R, f(x) = x3
– f ∈ [0, π/2] → [0, 1], f(x) = sin(x)
Aufgabe 9. Finden Sie ein Beispiel zweier Mengen A und B und einer RelationR ⊆ A×B aus der “wirklichen Welt” fur die (A,B, R)
• keine partielle Funktion
• eine partielle aber nicht totale Funktion
• eine weder injektive noch surjektive Funktion
• eine injektive aber nicht surjektive Funktion
• eine surjektive aber nicht injektive Funktion
• eine bijektive Funktion
ist. Wenn z.B. A die Menge der Hauser und B die Menge der Turen und
R = {(a, b) | b ist Eingangstur von a}
ist, dann ist (A,B, R) keine Funktion, da manche Hauser zwei Eingangehaben. Andererseit ist mit
R−1 = {(b, a) | b ist Eingangstur von a}
das Tripel (B,A, R−1) eine partielle Funktion, da jede Tur hochstens zueinem Haus gehoren kann. Sie ist deshalb nicht total, weil es auch Turengibt, die nicht nach draußen fuhren.
Losung von Aufgabe 9.
• keine partielle Funktion ist: A Menge der Menschen, B Menge derAutos, aRb wenn a besitzt b. Es gibt Menschen, die zwei Autos haben.
• eine partielle aber nicht totale Funktion ist: A Menge der Prozes-soren, B Menge der Rechner, aRb wenn a in b eingebaut ist. JederProzessor ist in hochstens einen Rechner eingebaut, es gibt aber auchProzessoren, die so herumliegen.
• eine weder injektive noch surjektive Funktion ist: A Menge der Bal-kone, B Menge der Hauser. aRb wenn Balkon a zu Haus b gehort.Jeder Balkon gehort zu genau einem Haus, daher Funktion. Nichtinjektiv weil es Hauser mit zwei Balkonen gibt. Nicht surjektiv weiles Hauser ohne Balkon gibt.
• eine injektive aber nicht surjektive Funktion ist: A Menge der Blu-men, B Menge der Namen. aRb wenn a Name von b ist. Nicht sur-jektiv, da Hans ein Name ist, aber keine Blume Hans heißt. Injektiv,da keine Blume zwei unterschiedliche Namen hat.
6
• eine surjektive aber nicht injektive Funktion ist: A Menge der Kinder,B Menge der Mutter, aRb wenn a Kind von b ist. Jede Mutter hatein Kind, d.h. surjektiv. Zwei Kinder konnen die selbe Mutter haben,d.h. nicht injektiv.
• eine bijektive Funktion ist: A Menge der Tage, B Menge der Nachte,aRb wenn a der Tag vor der Nacht b ist. Bijektiv, zu jedem a gehortgenau ein b und umgekehrt.
Aufgabe 10. Gegeben ist die Funktion f ∈ Z× Z → N0 × Z durch
f(x, y) = (x2, x + y).
Ist f injektiv bzw. surjektiv? Falls nicht, finden Sie jeweils ein Gegenbei-spiel.
Losung von Aufgabe 10.
• Nicht surjektiv, da z.B. (2, 3) 6∈ bild(f) weil 2 keine Quadratzahl ist.
• Nicht injektiv, da z.B. f(2, 2) = f(−2, 6).
Aufgabe 11. Ist die Funktion f ∈ Z × N → Q, f(x, y) = x/y injektiv bzw.surjektiv?
Losung von Aufgabe 11. f ∈ Z × N → Q, f(x, y) = x/y ist surjektiv abernicht injektiv, da z.B. 2/3 = 4/6.
Aufgabe 12. Uberlegen Sie sich eine bijektive Funktion
f ∈ N → Z2,
beschreiben Sie, wie die Funktionswerte zu berechnen sind (mit einemBild oder Formeln) und geben Sie die f(1), f(2), f(3), f(4) und f(5) an.Hinweis: Uberlegen Sie sich eine graphische Darstellung und denken Siean quadratische Schneckenhauser.
Losung von Aufgabe 12.
Bijektive Funktion f ∈ N → Z2: f(1) = (0, 0), f(2) = (0, 1), f(3) =(−1, 1), f(4) = (−1, 0), f(5) = (−1,−1) usw., siehe Bild 1.
Aufgabe 13. Uberlegen Sie sich zwei injektive Funktionen f, g ∈ N → N. Be-rechnen Sie f ◦g und g◦f und untersuchen Sie, ob diese beiden Funktionenauch injektiv sind.
Beweisen Sie dann allgemein, dass wenn f ∈ A → B und g ∈ B → Cinjektiv sind, auch g ◦ f injektiv ist.
7
�
� �
�
� � ��
�
�� �������
���
Abbildung 1: Bijektive Funktion f ∈ N → Z2.
Losung von Aufgabe 13. Beispiel: f, g ∈ N → N,
f(x) = x + 1g(x) = 2x
(g ◦ f)(x) = 2(x + 1)(f ◦ g)(x) = 2x + 1.
Sowohl g ◦ f als auch f ◦ g sind injektiv.
• Zu zeigen:
∀A,B ∀f ∈ A → B ∀g ∈ B → C((injektiv(f) ∧ injektiv(g)) → injektiv(g ◦ f)
)• Seien A,B beliebig aber fest. Seien f ∈ A → B und g ∈ B → C
beliebig aber fest. Zu zeigen:
(injektiv(f) ∧ injektiv(g)) → injektiv(g ◦ f).
• Annahme: f und g sind injektiv. Zu zeigen: g ◦ f ist injektiv.
• Einsetzen der Definition von injektiv: Zu zeigen:
∀a1, a2 ∈ A(a1 6= a2 → (g ◦ f)(a1) 6= (g ◦ f)(a2)
).
• Sei a1, a2 ∈ A beliebig aber fest. Zu zeigen:
a1 6= a2 → (g ◦ f)(a1) 6= (g ◦ f)(a2).
• Einsetzen der Definition von ◦. Zu zeigen
a1 6= a2 → g(f(a1)) 6= g(f(a2)).
8
• Annahmea1 6= a2.
Zu zeigen:g(f(a1)) 6= g(f(a2)).
• Die Annahme, dass f injektiv ist, besagt
∀x1, x2 ∈ A(x1 6= x2 → f(x1) 6= f(x2)
).
Mit dem Spezialfall x1 = a1 und x2 = a2 folgt hieraus
a1 6= a2 → f(a1) 6= f(a2).
• Mit modus ponens folgt
f(a1) 6= f(a2).
• Die Annahme, dass g injektiv ist, besagt
∀x1, x2 ∈ B(x1 6= x2 → g(x1) 6= g(x2)
).
Mit dem Spezialfall x1 = f(a1) und x2 = f(a2) folgt hieraus
f(a1) 6= f(a2) → g(f(a1)) 6= g(f(a2)).
• Mit modus ponens folgt
g(f(a1)) 6= g(f(a2)).
Aufgabe 14. Angenommen die Funktion g ist Erweiterung der Funktion f .Zeigen Sie, dass wenn g injektiv ist, auch f injektiv ist.
Losung von Aufgabe 14.
• Zu zeigen:
∀f, g((erweiterung(g, f) ∧ injektiv(g)) → injektiv(f)
).
• Seien f, g beliebig aber fest. Zu zeigen:
(erweiterung(g, f) ∧ injektiv(g)) → injektiv(f).
• Annahme:erweiterung(g, f) ∧ injektiv(g).
Zu zeigen:injektiv(f).
9
• Da f und g Funktionen sind, existieren A,B, R,A′, B′, R′ so dass
f = (A,B, R)g = (A′, B′, R′).
Da g Erweiterung von f ist, gilt
A ⊆ A′, B ⊆ B′, R ⊆ R′.
• Definition von injektiv. Zu zeigen:
∀a1, a2 ∈ A(a1 6= a2 → f(a1) 6= f(a2)
).
• Seien a1, a2 ∈ A beliebig aber fest. Zu zeigen:
a1 6= a2 → f(a1) 6= f(a2).
• Annahme:a1 6= a2.
Zu zeigen:f(a1) 6= f(a2).
• Die Annahme, dass g injektiv ist, besagt
∀x1, x2 ∈ A′ (x1 6= x2 → g(x1) 6= g(x2)
).
Da A ⊆ A′ ist a1, a2 ∈ A′. Mit dem Spezialfall x1 = a1 und x2 = a2
folgt hierausa1 6= a2 → g(a1) 6= g(a2).
• Mit modus ponens folgt
g(a1) 6= g(a2).
• Da g Erweiterung von f ist, gilt
f(a1) = g(a1)f(a2) = g(a2).
Folglich istf(a1) 6= f(a2).
Aufgabe 15. Sei wieder g Erweiterung von f .
• Wenn f surjektiv ist, ist dann auch g surjektiv?
• Wenn g surjektiv ist, ist dann auch f surjektiv?
Finden Sie einen Beweis oder ein Gegenbeispiel.
10
Losung von Aufgabe 15.
• Die Erweiterung einer surjektiven Funktion ist nicht notwendig sur-jektiv: So ist z.B. f ∈ N0 → N, f(x) = x + 1 surjektiv. Weiter istg ∈ N0 → Z, g(x) = x + 1 Erweiterung von f . Die Funktion g istaber nicht surjektiv.
• Auch die Einschrankung einer surjektiven Funktion ist nicht notwen-dig surjektiv. So ist z.B. g ∈ Z → Z, g(x) = x + 1 surjektiv. Weiterist f ∈ N → N, f(x) = x + 1 Einschrankgung von g. Die Funktion fist aber nicht surjektiv, da 1 6∈ bild(f).
Aufgabe 16. Sei A = {1, 2, 3}. Finden Sie eine Relation R so dass
(A,A, R)
eine Funktion ist, die weder surjektiv noch injektiv ist.
Losung von Aufgabe 16.
R = {(1, 1), (2, 1), (3, 1)}
Aufgabe 17. Gegeben ist die Funktion f ∈ Z2 → Z2 durch
f(x, y) = (x + y, x− y).
Ist f injektiv bzw. surjektiv?
Losung von Aufgabe 17.
• Injektiv: Aus (x1 + y1) = (x2 + y2) und (x1 − y1) = (x2 − y2) folgtdurch Addition der beiden Gleichungen 2x1 = 2x2, somit x1 = x2.Durch Subtraktion folgt 2y1 = 2y2, somit y1 = y2. Also ist f injektiv.
• Da (3, 2) 6∈ bild(f), ist f nicht surjektiv. Wenn f(x, y) = (3, 2) ware,mußte (x, y) = (5/2, 1/2) sein, was aber nicht in Z2 ist.
Aufgabe 18. Gegeben ist die Relation
R = {(x, y) | x, y ∈ R, y2 = x}.
• Ist (R, R, R) eine Funktion?
• Finden Sie zwei Mengen A,B ⊆ R so dass
f =(A,B, R ∩ (A×B)
)eine bijektive Funktion ist.
Losung von Aufgabe 18.
11
• (R, R, R) ist noch nicht einmal eine partielle Funktion, da es z.B. furx = 1 zwei y’s gibt (y = 1, y = −1) so dass xRy.
• f ist eine bijektive Funktion z.B. fur
A = R+0
B = R+0
Aufgabe 19. Sei Z2 = {0, 1} und ⊕2 ∈ Z2 × Z2 → Z2 definiert durch
x⊕2 y = (x + y) mod 2
• Ist ⊕2 injektiv, surjektiv oder bijektiv? (Ohne Beweis, nur “ja” oder“nein”.)
• Sei weiterhin
f =(Z2, Z2, {(x, y) | x, y ∈ Z2, x⊕2 y = 1}
)Ist f eine Funktion, eine partielle Funktion oder keins von beidem?(Ohne Beweis.)
• Sei nun Z3 = {0, 1, 2} und
g =(Z2, Z3, {(x, y) | x ∈ Z2, y ∈ Z3, (x + y) mod 2 = 1}
)Ist g eine Funktion, eine partielle Funktion oder keins von beidem?Geben Sie eine Begrundung.
Losung von Aufgabe 19.
• ⊕2 ist– nicht injektiv,– surjektiv und– nicht bijektiv.
• f ist eine Funktion.• g ist keine partielle Funktion. Sei
R =(Z2, Z3, {(x, y) | x ∈ Z2, y ∈ Z3, (x + y) mod 2 = 1}
)Dann ist z.B. sowohl (1, 0) ∈ R als auch (1, 2) ∈ R. Um eine partielleFunktion zu sein, darf aber zu jedem x ∈ Z2 hochstens ein y ∈ Z3
existieren mit (x, y) ∈ R.
Aufgabe 20. Entscheiden Sie von jeder der folgenden Funktionen ob sie in-jektiv bzw. surjektiv ist. (Ohne Beweis.)
f ∈ N → N, f(x) ={
x− 1 falls x geradex + 1 falls x ungerade
f ∈ Z → Z, f(x) = 2x
f ∈ R → R, f(x) = sin(x)
12
Losung von Aufgabe 20.
•f ∈ N → N, f(x) =
{x− 1 falls x geradex + 1 falls x ungerade
ist injektiv, surjektiv und bijektiv.
• f ∈ Z → Z, f(x) = 2x ist injektiv, nicht surjektiv, nicht bijektiv.
• f ∈ R → R, f(x) = sin(x) ist nicht injektiv, nicht surjektiv, nichtbijektiv.
Aufgabe 21. Finden Sie zwei Beispiele von bijektiven Funktion aus N3 → N3.
Losung von Aufgabe 21.
f(x, y, z) = (x, y, z)f(x, y, z) = (z, x, y)
Aufgabe 22. Geben Sie einen ausfuhrlichen Beweis, dass wenn die Funktionen
f ∈ A1 → B1
g ∈ A2 → B2
surjektiv sind, auch die Funktion
h ∈ A1 ×A2 → B1 ×B2
mith(x, y) = (f(x), g(y))
surjektiv ist.
Losung von Aufgabe 22. Seien
f ∈ A1 → B1
g ∈ A2 → B2
surjektiv undh ∈ A1 ×A2 → B1 ×B2
mith(x, y) = (f(x), g(y)).
• Zu zeigen: h ist surjektiv.
Einsetzen der Definition von surjektiv:
• Zu zeigen: Fur alle (b1, b2) ∈ B1×B2 existiert ein (a1, a2) ∈ A1×A2
so dassh(a1, a2) = (b1, b2).
13
Sei (b1, b2) ∈ B1 ×B2 beliebig aber fest.
• Zu zeigen: Es existiert ein Paar (a1, a2) ∈ A1 × A2 mit h(a1, a2) =(b1, b2).
Konstruktion eines Paars (a1, a2) ∈ A1 × A2 mit h(a1, a2) = (b1, b2). Daf surjektiv ist, existiert ein a1 ∈ A1 mit f(a1) = b1. Da g surjektiv ist,existiert ein a2 ∈ A2 mit g(a2) = b2. Folglich existiert ein (a1, a2) ∈A1 ×A2 mit
h(a1, a2) = (f(a1), g(a2))= (b1, b2).
Aufgabe 23. Geben Sie einen ausfuhrlichen Beweis, dass wenn
f, g ∈ A → B
zwei injektive Funktionen sind, auch
h ∈ A×A → B ×B
mith(x, y) = (f(x), g(y))
injektiv ist.
Losung von Aufgabe 23. Zu zeigen: Fur alle Funktionen f, g ∈ A → B gilt:Wenn f, g injektiv sind, dann auch
h ∈ A×A → B ×B mit h(x, y) = (f(x), g(y)).
• Sei f, g ∈ A → B beliebig aber fest. Zu zeigen: Wenn f, g injektivsind, dann ist h auch injektiv.
• Annahme: Sei f, g injektiv. Zu zeigen h ist injektiv.
• Einsetzen der Definition von injektiv.Annahme:
∀x1, x2 ∈ A x1 6= x2 → f(x1) 6= f(x2)∀y1, y2 ∈ A y1 6= y2 → g(y1) 6= g(y2)
Zu zeigen:
∀(x1, y1), (x2, y2) ∈ A×A (x1, y1) 6= (x2, y2) → h(x1, y1) 6= h(x2, y2).
• Sei (x1, y1), (x2, y2) beliebig aber fest. zu zeigen:
(x1, y1) 6= (x2, y2) → h(x1, y1) 6= h(x2, y2).
• Annahme (x1, y1) 6= (x2, y2). Zu zeigen: h(x1, y1) 6= h(x2, y2).
14
• Da (x1, y1) 6= (x2, y2) ist entweder x1 6= x2 oder y1 6= y2.
• Aus der Injektivitat von f und g folgt somit
f(x1) 6= f(x2) oder g(y1) 6= g(y2).
Somit ist(f(x1), g(y1)) 6= (f(x2), g(y2))
und daher h(x1, y1) 6= h(x2, y2).
Aufgabe 24. Gegeben ist die Funktion f ∈ N → N durch
f(x) ={
2x falls x ungeradex/2 falls x gerade.
Ist f injektiv bzw. surjektiv? (Jeweils ein Satz Begrundung.)
Losung von Aufgabe 24.
• f ist surjektiv, denn zu jedem y ∈ N ist x = 2y gerade und somitf(x) = y.
• f ist nicht injektiv, denn z.B. f(1) = 2 und f(4) = 2.
Aufgabe 25. Definieren Sie eine injektive Funktion aus der Menge
R → (R× {0, 1}).
Losung von Aufgabe 25. Die Funktion f ∈ R → (R× {0, 1}) mit
f(x) = (x, 0)
ist injektiv: Wenn x 6= y dann ist f(x) 6= f(y).
Aufgabe 26. Fur a ∈ N0 und b ∈ N bezeichnet amod b den Rest bei derganzzahligen Division von a durch b. So ist z.B.
7 mod 2 = 1
da 7 geteilt durch 2 gleich 3 Rest 1 ist. Ist die Funktion f ∈ N → N0
f(x) = xmod42
injektiv bzw. surjektiv? Geben Sie eine kurze Begrundung.
Losung von Aufgabe 26.
• Nicht injektiv. Als Funktionswerte konnen nur die Zahlen 0, 1, . . . , 41auftreten. Somit mussen zwei unterschiedliche naturliche Zahlen denselben Funktionswert bekommen.
• Nicht surjektiv. Es gilt 42 ∈ N0 aber 42 6∈ bild(f).
15
Aufgabe 27. Formulieren Sie die Aussage
“Zu jeder Menge A gibt es eine Menge B mit der Eigenschaft,dass es eine injektive Funktion von A nach B gibt”
in der Sprache der Pradikatenlogik. Hinweis: Definieren Sie zunachst durcheinen pradikatenlogischen Ausdruck wann eine Funktion von A nach Binjektiv ist.
Losung von Aufgabe 27. f ∈ A → B ist injektiv wenn
∀a1, a2 ∈ A a1 6= a2 → f(a1) 6= f(a2).
Die Aussage, dass es zu jeder Menge A eine Menge B gibt so dass es eineinjektive Funktion von A nach B gibt, ist dann
∀A ∃B ∃f ∈ A → B ∀a1, a2 ∈ A a1 6= a2 → f(a1) 6= f(a2).
Aufgabe 28. Sei A eine Menge mit drei Elementen.
• Wieviele bijektive Funktionen gibt es in der Menge A → A?
• Wieviele Elemente hat die Menge A → A2?
Losung von Aufgabe 28. Sei A = {a1, a2, a3}.
• Wenn man den Elementen a1, a2, a3 nacheinander Funktionswertezuordnet, dann hat man zunachst fur a1 drei Moglichkeiten. Fur a2
bleiben danach nur noch zwei Moglichkeiten ubrig und a3 hat nurnoch eine einzige. Also gibt es 3× 2× 1 = 6 bijektive Funktionen inder Menge A → A.
• Fur jeden der 3 Inputs aus A hat man 3 × 3 = 9 Outputs in A2.Somit ist
|A → A2| = 93 = 81.
Aufgabe 29. Sei[1, 2] = {x | x ∈ R, 1 ≤ x ≤ 2}.
Definieren Sie eine injektive Funktion
f ∈ N → [1, 2].
Losung von Aufgabe 29. Die Funktion f ∈ N → [1, 2] mit
f(n) = 1 + 1/n
ist injektiv.
16
Aufgabe 30. Sei f ∈ R2 → R3 definiert durch
f(x, y) = (1, x, y).
Ist f injektiv bzw. surjektiv? Geben Sie jeweils einen Satz Begrundungoder ein Gegenbeispiel.
Losung von Aufgabe 30.
• f ist injektiv. Ist (x1, y1) 6= (x2, y2) dann auch (1, x1, y1) 6= (1, x2, y2).
• f ist nicht surjektiv. Fur (2, 1, 1) ∈ R3 gibt es kein (x, y) ∈ R2 sodass f(x, y) = (2, 1, 1).
Aufgabe 31. Der Datentyp double wird in der Praxis als Ersatz fur reelleZahlen verwendet. Konkret bedeutet das, dass jeder Gleitkommazahl x ∈double eine reelle Zahl x′ ∈ R zugeordnet wird.
• Handelt es sich bei dieser Zuordnung um eine Funktion oder um einepartielle Funktion?
• Sei double′ die Menge der Gleitkommazahlen doppelter Genauigkeitohne die Spezialzahlen wie ±infinity und not a number. Ist dann dieZuordnung von Gleitkommazahlen aus double′ zu reellen Zahlen eineFunktion? Falls ja, ist diese surjektiv bzw. injektiv?
Losung von Aufgabe 31.
• Es handelt sich um eine partielle Funktion. Zu jeder “normalen”Gleitkommazahl x ∈ double gibt es genau eine entsprechende reelleZahl. Fur die Gleitkommazahlen ±infinity und not a number gibt eskeine zugehorige reelle Zahl.
• Die Zuordnung von double′ nach R ist eine Funktion. Zu jeder “nor-malen” Gleitkommazahl gibt es genau eine reelle Zahl. Die Funktionist nicht injektiv, da es zwei unterschiedliche Gleitkommazahlen furdie reelle Zahl 0 gibt (jeweils mit unterschiedlichem Vorzeichenbit).Die Funktion ist auch nicht surjektiv, da es unendlich viele reelle Zah-len gibt aber double endlich ist. Es gibt z.B. keine Gleitkommazahl,die der reellen Zahl π oder
√2 entspricht.
Aufgabe 32. Beweisen Sie ausfuhrlich: Fur jede Funktion f ∈ A → B undfur jede Funktion g ∈ B → C gilt:
Wenn f nicht injektiv ist, dann ist auch die Komposition g ◦ fnicht injektiv.
Stellen Sie die Aussage zunachst anschaulich durch ein Mengendiagrammdar.
Losung von Aufgabe 32.
17
• Zu zeigen:
∀f ∈ A → B ∀g ∈ B → C ¬injektiv(f) → ¬injektiv(g ◦ f).
• Seien f ∈ A → B und g ∈ B → C beliebig aber fest. Zu zeigen
¬injektiv(f) → ¬injektiv(g ◦ f).
• Umformung der wenn dann Aussage. Zu zeigen:
injektiv(g ◦ f) → injektiv(f).
• Annahme: g ◦ f ist injektiv.Zu zeigen: f ist injektiv.
• Definition injektiv. Annahme
∀x, y ∈ A x 6= y → g(f(x)) 6= g(f(y)).
Zu zeigen:∀a, b ∈ A a 6= b → f(a) 6= f(b).
• Seien a, b ∈ A beliebig aber fest. Zu zeigen
a 6= b → f(a) 6= f(b).
• Annahme a 6= b, zu zeigen f(a) 6= f(b).
• Aus der Annahme folgt durch Spezialisierung mit a fur x und b fur y
a 6= b → g(f(a)) 6= g(f(b)).
• Modus Ponensg(f(a)) 6= g(f(b)).
• Da g Funktion ist, gilt
∀x, y g(x) 6= g(y) → x 6= y.
• Spezialisierung mit f(a) fur x und f(b) fur y:
g(f(a) 6= g(f(b)) → f(a) 6= f(b).
• Modus Ponensf(a) 6= f(b).
Aufgabe 33. Sei
f ∈ P (N) → P (N), f(M) = M ∪ {1}.
• Berechnen Sie f({3, 5, 7}).
18
• Ist f injektiv? (Kurze Begrundung oder Gegenbeispiel)
• Ist f surjektiv? (Kurze Begrundung oder Gegenbeispiel)
• Finden Sie Mengen X, Y, Z so dass f = (X, Y, Z).
Losung von Aufgabe 33.
• f({3, 5, 7}) = {1, 3, 5, 7}.• f ist nicht injektiv.
f({1}) = f(∅) obwohl {1} 6= ∅.
• f ist nicht surjektiv, da z.B.
{3, 4} 6∈ bild(f).
• X = P (N), Y = P (N),
Z = {(A,B) | A,B ⊆ N ∧B = A ∪ {1}}.
Aufgabe 34. Beweisen Sie dass wenn f ∈ A → B und g ∈ B → C surjektivsind, auch g ◦ f surjektiv ist.
Losung von Aufgabe 34.
• Zu zeigen:
∀A,B ∀f ∈ A → B ∀g ∈ B → C((surjektiv(f) ∧ surjektiv(g)) → surjektiv(g ◦ f)
)• Seien A,B beliebig aber fest. Seien f ∈ A → B und g ∈ B → C
beliebig aber fest. Zu zeigen:
(surjektiv(f) ∧ surjektiv(g)) → surjektiv(g ◦ f).
• Annahme: f und g sind surjektiv. Zu zeigen: g ◦ f ist surjektiv.
• Einsetzen der Definition von surjektiv: Zu zeigen:
∀c ∈ C ∃a ∈ A (g ◦ f)(a) = c.
• Sei c ∈ C beliebig aber fest. Zu zeigen:
∃a ∈ A (g ◦ f)(a) = c.
• Einsetzen der Definition von ◦. Zu zeigen
∃a ∈ A g(f(a)) = c.
19
• Die Annahme, dass g surjektiv ist, besagt
∀y ∈ C ∃b ∈ B g(b) = y.
Mit dem Spezialfall y = c folgt hieraus
∃b ∈ B g(b) = c.
• Sei b ∈ B so dassg(b) = c.
• Die Annahme, dass f surjektiv ist, besagt
∀x ∈ B ∃a ∈ A f(a) = x.
Mit dem Spezialfall x = b folgt hieraus
∃a ∈ A f(a) = b.
• Sei a ∈ A so dassf(a) = b.
Folglich istg(f(a)) = g(b) = c.
Aufgabe 35. Seien f, g ∈ A → B und h ∈ A → B2 mit
h(x) =(f(x), g(x)
).
Entscheiden Sie ob folgende Aussagen wahr sind:
• Wenn f und g injektiv sind dann ist auch h injektiv.
• Wenn f und g surjektiv sind, dann ist auch h surjektiv.
Begrunden Sie Ihre Antwort durch einen ausfuhrlichen Beweis oder einGegenbeispiel.
Losung von Aufgabe 35. Wenn f und g injektiv sind, dann ist auch h injek-tiv.
• Seien A,B beliebige Mengen und f, g ∈ A → B beliebig aber fest.Sei h ∈ A → B2 mit
h(x) =(f(x), g(x)
).
Zu zeigen:
(injektiv(f) ∧ injektiv(g)) → injektiv(h).
20
• Annahme:injektiv(f) und injektiv(g).
Zu zeigen:injektiv(h).
• Zu zeigen:∀x, y ∈ A x 6= y → h(x) 6= h(y).
• Seien x, y ∈ A beliebig aber fest. Zu zeigen:
x 6= y → h(x) 6= h(y).
• Annahme: x 6= y. Zu zeigen: h(x) 6= h(y).
• Da f injektiv ist, gilt
∀a, b ∈ A a 6= b → f(a) 6= f(b).
• Mit dem Spezialfall a = x und b = y gilt
x 6= y → f(x) 6= f(y).
• Mit modus ponens folgt
f(x) 6= f(y).
• Aus der Definition der Gleichheit von Paaren folgt
(f(x), g(x)) 6= (f(y), g(y)).
Folglich isth(x) 6= h(y).
Die Injektivitat von g hat man im Beweis gar nicht gebraucht.
Wenn f und g surjektiv sind, dann ist h nicht notwendigerweise surjektiv.Ein Gegenbeispiel ist f, g ∈ N → N mit
f(x) = x
g(x) = x.
Dann ist h ∈ N → N2,h(x) = (x, x)
keine surjektive Funktion, da z.B.
(1, 2) ∈ N2 aber(1, 2) 6∈ bild(h).
21
Aufgabe 36. Beweisen Sie ausfuhrlich, dass fur jede injektive Funktion
f ∈ A2 → B
und fur jede Funktiong ∈ A → A
die Funktionh ∈ A → B mit h(x) = f(x, g(x))
injektiv ist.
Losung von Aufgabe 36.
• Seien f ∈ A2 → B und g ∈ A → A beliebig aber fest. Sei h ∈ A → Bdefiniert durch
h(x) = f(x, g(x)).
Zu zeigen:injektiv(f) → injektiv(h).
• Zu zeigen:∀x, y ∈ A (x 6= y → h(x) 6= h(y)).
• Seien x, y ∈ A beliebig aber fest. Zu zeigen:
x 6= y → h(x) 6= h(y).
• Annahme x 6= y. Zu zeigen h(x) 6= h(y).
• Aus der Injektivitat von f folgt
∀u, v ∈ A2 (u 6= v → f(u) 6= f(v)).
• Mit dem Spezialfall u = (x, g(x)) und v = (y, g(y)) folgt
(x, g(x)) 6= (y, g(y)) → f(x, g(x)) 6= f(y, g(y)).
• Da x 6= y folgt(x, g(x)) 6= (y, g(y)).
• Mit modus ponens folgt
f(x, g(x)) 6= f(y, g(y)).
• Folglich gilt h(x) 6= h(y).
Aufgabe 37. Sei f ∈ N2 → N2 definiert durch
f(x, y) = (xy, 2x).
Beweisen Sie ausfuhrlich, dass f injektiv ist.
22
Losung von Aufgabe 37.
• Zu zeigen:
∀(x1, y1), (x2, y2) ∈ N2 f(x1, y1) = f(x2, y2) → (x1, y1) = (x2, y2).
• Seien (x1, y1), (x2, y2) ∈ N2 beliebig aber fest. Zu zeigen:
f(x1, y1) = f(x2, y2) → (x1, y1) = (x2, y2).
• Annahme:f(x1, y1) = f(x2, y2).
Zu zeigen:(x1, y1) = (x2, y2).
• Annahme:(x1y1, 2x1) = (x2y2, 2x2).
• Annahme:x1y1 = x2y2, 2x1 = 2x2.
• Aus 2x1 = 2x2 folgt x1 = x2.
• Aus x1 = x2 und x1y1 = x2y2 folgt
x1y1 = x1y2.
• Da x1 ∈ N und damit x1 6= 0 folgt
y1 = y2.
• Aus x1 = x2 und y1 = y2 folgt
(x1, y1) = (x2, y2).
Aufgabe 38. Seien f, g ∈ N → N definiert durch
f(x) = x + 1
g(x) ={
x− 1 falls x > 11 falls x = 1
Entscheiden Sie von jeder der folgenden Aussagen ob sie wahr oder falschist.
• f ◦ g ist injektiv.
• f ◦ g ist surjektiv.
• g ◦ f ist injektiv.
• g ◦ f ist surjektiv.
23
Losung von Aufgabe 38. Es gilt
f(g(x)) ={
x falls x > 12 falls x = 1
g(f(x)) = x.
Damit folgt:
• f ◦ g ist nicht injektiv da f(g(2)) = f(g(1)).
• f ◦ g ist nicht surjektiv da 1 6∈ bild(f ◦ g).
• g ◦ f ist injektiv.
• g ◦ f ist surjektiv.
Aufgabe 39. Sei A = {1, 2, 3} und B = {4, 5}. Finden Sie
• eine surjektive Funktion aus A → B und
• eine nicht injektive Funktion aus B → A.
Beschreiben Sie die Funktionen jeweils als Tripel bestehend aus zwei Men-gen und einer Relation.
Losung von Aufgabe 39.
• Surjektive Funktion aus A → B:
({1, 2, 3}, {4, 5}, {(1, 4), (2, 5), (3, 5)}).
• Nicht injektive Funktion aus B → A:
({4, 5}, {1, 2, 3}, {(4, 1), (5, 1)}).
Aufgabe 40. Die Funktion f ∈ P (N) → P (N) ist definiert durch
f(x) = x ∪ {1}.
Untersuchen Sie ob diese Funktion injektiv bzw. surjektiv ist. Geben Siejeweils eine kurze Begrundung (1 Satz) oder ein Gegenbeispiel.
Losung von Aufgabe 40.
• Nicht injektiv da z.B.f(∅) = f({1}).
• Nicht surjektiv, da es keine Menge a gibt so dass f(a) = ∅.
24
Aufgabe 41. Gegeben sind die Mengen
A = {1, 2, 3}B = {1, 2}
und die Funktionen
f =(A,B, {(1, 2), (2, 1), (3, 1)}
)g =
(B,A, {(1, 3), (2, 1)}
)• Entscheiden Sie von beiden Funktionen, ob sie injektiv bzw. surjektiv
sind. (Jeweils ein Satz Begrundung.)
• Untersuchen Sie, ob die Kompositionen f ◦ g bzw. g ◦ f existierenund falls ja stellen Sie sie als Tripel bestehend aus zwei Mengen undeiner Relation dar.
Losung von Aufgabe 41.
• f ist surjektiv, da zu jedem b ∈ B ein a ∈ A existiert mit f(a) = b.f ist nicht injektiv, da f(2) = f(3).g ist nicht surjektiv, da zu a = 3 kein b ∈ A existiert mit g(b) = a.g ist injektiv, da zu jedem a ∈ A hochstens ein b ∈ B existiert mitg(b) = a.
• Beide Kompositionen existieren.
f ◦ g =(B,B, {(1, 1), (2, 2)}
)g ◦ f =
(A,A, {(1, 1), (2, 3), (3, 3)}
)Aufgabe 42. Ist die Komposition f ◦g zweier surjektiver Funktionen f ∈ B →
C und g ∈ A → B wieder surjektiv? Geben Sie einen ausfuhrlichen Beweisoder finden Sie ein Gegenbeispiel.
Losung von Aufgabe 42. f ◦ g ist surjektiv.
• Zu zeigen:
∀A,B, C ∀f ∈ B → C ∀g ∈ A → B
(surjektiv(f) ∧ surjektiv(g)) → surjektiv(f ◦ g).
• Seien A,B, C und f ∈ B → C und g ∈ A → B beliebig aber fest. Zuzeigen:
(surjektiv(f) ∧ surjektiv(g)) → surjektiv(f ◦ g).
• Annahme: f und g sind surjektiv.Zu zeigen: f ◦ g ist surjektiv.
25
• Einsetzen der Definition von surjektiv. Zu zeigen:
∀c ∈ C ∃a ∈ A (f ◦ g)(a) = c.
• Sei c ∈ C beliebig aber fest. Zu zeigen:
∃a ∈ A (f ◦ g)(a) = c.
• Surjektivitat von f bedeutet
∀c′ ∈ C ∃b ∈ B f(b) = c′.
Mit der Spezialisierung c′ = c folgt
∃b ∈ B f(b) = c.
Sei b ∈ B so dass f(b) = c.• Surjektivitat von g bedeutet
∀b′ ∈ B ∃a′ ∈ A g(a′) = b′.
Mit der Spezialisierung b′ = b folgt
∃a′ ∈ A g(a′) = b.
Sei a′ ∈ A so dass g(a′) = b.• Da f(b) = c folgt f(g(a′)) = c bzw. (f ◦ g)(a′) = c. Damit ist bewie-
sen, dass∃a ∈ A (f ◦ g)(a) = c.
Aufgabe 43. Sei f ∈ N2 → Z3 und g ∈ Z3 → Z definiert durch
f(x, y) = (x− 1, 1− y, x + y), g(x, y, z) = xy − z.
• Berechnen Sie einen Funktionsterm fur g ◦ f .• Berechnen Sie bild(g ◦ f).• Zeigen Sie durch Angabe eines Gegenbeispiels dass g◦f nicht injektiv
ist.
Losung von Aufgabe 43.
(g ◦ f)(x, y) = g(f(x, y))= g(x− 1, 1− y, x + y)= (x− 1)(1− y)− (x + y)= x− xy − 1 + y − x− y
= −xy − 1.
bild(g ◦ f) = {−2,−3,−4, . . .}.
Nicht injektiv, da z.B. (g ◦ f)(1, 2) = (g ◦ f)(2, 1).
26
