Beweise zum Satz 27

Prof. Dr. W. Conen

15. November 2004

Satz 27: Verkettung zur Identität (a) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist injektiv (ii) Es existiert eine Funktion g:B ! A mit g ± f = idA

(b) Die folgenden Aussagen sind äquivalent: (i) f: A ! B ist surjektiv (ii) Es existiert eine Funktion g:B ! A mit f ± g = idB

Satz 27: Verkettung zur Identität (a) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist injektiv (ii) Es existiert eine Funktion g: B ! A mit g ± f = idA

Diese Aussage wollen wir zeigen, d.h wir müssen ZWEI Richtungen zeigen, (i) ) (ii) und (ii) ) (i)

Wir beginnen mit (i) ) (ii) Also nehmen wir zunächst an, dass wir eine Funktion f von A nach B

haben, die injektiv ist. Eine Funktion f ist injektiv, wenn keines der von f getroffenen Elemente

mehrmals getroffen wird, formal: Es gibt keine y in {y | (x,y) 2 f} mit x1, x2, x1 x2, (x1,y) 2 f und (x2,y) 2 f

Alternativ (unsere Definition!): für alle x1, x2, y gilt: aus (x1,y) 2 f und (x2,y) 2 f folgt x1 = x2

NICHT INJEKTIV!

Satz 27: Verkettung zur Identität (a) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist injektiv (ii) Es existiert eine Funktion g: B ! A mit g ± f = idA

(i) ) (ii), Annahme f: A ! B ist injektiv Nach Def. 24 existiert die Umkehrfunktion zu f, f-1. Achtung: Die

Umkehrfunktion ist selbst injektiv (sonst hätte f keine Funktion sein können, denn dann wären zwei Pfeile von einem x 2 A ausgegangen!)

Sei nun x 2 A beliebig, aber fest gewählt Es gilt: f(x) = y 2 B. Nach Def. 24 ist zu jedem Paar (a,b) 2 f das gespiegelte Paar (b,a) 2 f-1,

also in f-1. (1) Nach Def. 25 gilt für die Verkettung der Funktionen f-1 ± f = {(a,c) | a 2 A,

(f(a),c) 2 f-1}. Wg. (1) gilt c = a, und damit f-1 ± f = idA

Ist also f-1 unser gesuchtes g?

Satz 27: Verkettung zur Identität (a) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist injektiv (ii) Es existiert eine Funktion g: B ! A mit g ± f = idA

(i) ) (ii), Annahme f: A ! B ist injektiv Ist f-1 unser gesuchtes g?

A B

f

f-1

a = f-1(f(a)) f(a)

Satz 27: Verkettung zur Identität (a) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist injektiv (ii) Es existiert eine Funktion g: B ! A mit g ± f = idA

Ist f-1 unser gesuchtes g? NICHT UNBEDINGT

A B

f

f-1

a = f-1(f(a)) f(a)

rng(f)

Satz 27: Verkettung zur Identität f trifft möglicherweise nicht alle Elemente von B! Wähle nun ein beliebiges a auf A und definiere nun g: B ! A wie folgt:

g|rng(f) = f-1

g(b) = a für alle b aus B – rng(f) (der rein-grüne Bereich)

Dann gilt g ± f = idA, denn hierfür wird nur g|rng(f) verwendet!

A B

f

g

a = f-1(f(a)) f(a)

rng(f)

Satz 27: Verkettung zur Identität (a) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist injektiv (ii) Es existiert eine Funktion g: B ! A mit g ± f = idA

(ii) ) (i), Annahme: Es existiert eine Funktion g: B ! A mit g ± f = idA

Zu zeigen ist, dass f injektiv ist. Angenommen, f wäre nicht injektiv. Dann gibt es ein b 2 B und a1,a2 2 A mit a1 a2 und f(a1) = f(a2) = b. Sei nun g(b) = a. Dann gilt (g ± f)(a1) = (g ± f)(a2) = a

... und wg. a1 a2 kann dann nicht g ± f = idA gelten, im Widerspruch zur Voraussetzung.

Das geht auch direkt mit unserer Definition: für alle x1, x2, y gilt: aus (x1,y) 2 f und (x2,y) 2 f folgt x1 = x2

Sei f(a1) = f(a2) = b. Es gilt nach Voraussetzung g(b) = g(f(a1)) = idA(a1) = a1 bzw. g(b) = g(f(a2)) = idA(a2) = a2, also a1 = a2 (sonst wäre g keine Funktion!)

Satz 27: Verkettung zur Identität (b) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist surjektiv (ii) Es existiert eine Funktion g: B ! A mit f ± g = idB

(i) ) (ii): Sei f: A ! B surjektiv. Wir müssen nun wieder ein „konkretes“ g suchen, das die gesuchte Eigenschaft

ergibt: Ziel ist, zu jedem Element b 2 B mit g einen Funktionswert g(b) zu liefern, der von f

wieder auf b abgebildet wird, d.h. f(g(b)) = b. Da f surjektiv ist, wird jedes Element in B getroffen – aber es kann mehrmals

getroffen werden Bei der „Umkehrung“ verwenden wir einfach nur einen der Pfeile, die zu b führen!

A B

bf

Satz 27: Verkettung zur Identität (b) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist surjektiv (ii) Es existiert eine Funktion g: B ! A mit f ± g = idB

(i) ) (ii): Sei f: A ! B surjektiv. Bei der „Umkehrung“ verwenden wir einfach nur einen der Pfeile, die zu b

führen! g: B ! A wird definiert durch g(b) = „ein a 2 A mit f(a) =b“ Ein solches a existiert in jedem Fall, den rng(f) = B Es gilt also f(g(b)) = b für alle b 2 B, also f ± g = idB

A B

bf

Satz 27: Verkettung zur Identität (b) Die folgenden Aussagen sind äquivalent:

(i) f: A ! B ist surjektiv (ii) Es existiert eine Funktion g: B ! A mit f ± g = idB

(ii) ) (i): Es existiert eine Funktion g: B ! A mit f ± g = idB

Sei b 2 B beliebig gewählt. (f ± g)(b) = b nach Voraussetzung ... und (f ± g)(b) = f(g(b)) nach Def. ± ... also b 2 rng(f).

Da b beliebig aus B gewählt war, liegt jedes b im Range von f und damit rng(f) = B, also f surjektiv nach Definition Surjektivität