1.1 Mengen Und Abbildungen

Transcript

Lineare Algebra I – WS 2015/16 1.1 c Rudolf Scharlau 3 Mengen und Abbildungen In diesem Abschnitt stellen wir die grundlegende mathematische Sprache und Notation zusammen, die f¨ ur jede Art von heutiger Mathematik unverzichtbar ist. Wir kn¨ upfen an u ¨bliches (schul-)mathematisches Vorwissen u ¨ber Zahlen und Funktionen an, auch setzen wir ein Grundverst¨andnis von analytischer Geometrie voraus (Beschreibung von Punkten durch Koordinaten). Der Rahmen unserer Ausf¨ uhrungen ist allerdings viel weiter gesteckt und dementsprechend die Darstellung abstrakt“ im Sinne ” der axiomatischen Vorgehensweise der modernen Mathematik. (Im folgenden Abschnitt 1.3 wird dieser Aspekt noch deutlicher werden.) Im ersten Teil dieses Abschnittes geht es um Mengen: Darstellung von Mengen, Standard-Bezeichnungen f¨ ur gewisse Mengen, Teilmengen, Vereinigung, Durchschnitt, Differenzmenge, kartesisches Produkt, M¨achtigkeit. Im zweiten Teil geht es um das Konzept einer Abbildung (Funktion); hierzu geh¨ oren die Begriffe Definitionsbereich, Zielbereich, Bild und Urbild (von Elementen und von Teilmengen). Besonders wichtig sind die Begriffe injektiv, surjektiv, bijektiv und Umkehrabbildung (inverse Abbildung). Nicht jede Abbildung besitzt eine Umkehrabbildung, vielmehr trifft dieses genau f¨ ur die bijektiven Abbildungen zu. Zum Schluss des Abschnittes stellen wir den Zusammenhang zwischen Abbildungen und M¨ achtigkeit von Mengen her und f¨ uhren den Begriff einer abz¨ahlbaren Menge ein. Erkl¨ arung 1.1.1 (G. Cantor1 ) Eine Menge ist eine Zusammenfassung bestimmter wohlunterschiedener Objekte unserer Anschauung oder unseres Denkens – welche die Elemente der Menge genannt werden – zu einem Ganzen. Schreibweise: x∈M x 6∈ M x ist ein Element von M x ist nicht ein Element von M Definition 1.1.2 (Standard-Bezeichnungen f¨ ur Mengen) N = {1, 2, 3, 4, . . .} die nat¨ urlichen Zahlen N0 = {0, 1, 2, 3, 4, . . .} die nat¨ urliche Zahlen mit Null Z = {. . . , −2, −1, 0, 1, 2, . . .} die ganzen Zahlen Q = {m n | m ∈ Z, n ∈ N} die Bruchzahlen, rationalen Zahlen R die reellen Zahlen ∅ die leere Menge Neben den nat¨ urlichen, ganzen und rationalen Zahlen (Bruchzahlen) setzen wir auch die reellen Zahlen (dargestellt zum Beispiel durch endliche oder unendliche Dezimalbr¨ uche) grunds¨atzlich als bekannt voraus. Beispiele: 3 ∈ N, 3 ∈ R, 1, 5 6∈ Z, −1 ∈ Z, −1 6∈ N, 1, 2121 · · · ∈ R Definition 1.1.3 Eine Menge M heißt endlich, wenn sie aus nur endlich vielen Elementen besteht. In diesem Fall heißt die Anzahl der Elemente die M¨ achtigkeit oder auch Kardinalit¨ at von M , in Zeichen: |M | oder #M . Wir kommen unten auf diesen Begriff zur¨ uck und gehen dann auch auf unendliche Mengen ein. 1 Georg Cantor, 1845 - 1918, deutscher Mathematiker, Professor in Halle (Saale) 4 c Rudolf Scharlau Lineare Algebra I – WS 2015/16 Erkl¨ arung 1.1.4 (Beschreibung von Mengen) 1. Durch Aufz¨ ahlung der Elemente, z.B. M = {1, 3, 5, 6}, A = {a, b, c, d, e, f } ; dieses ist prinzipiell bei endlichen Mengen m¨oglich, u.U. auch bei unendlichen Mengen, wenn keine Missverst¨andnisse zu bef¨ urchten sind: N0 = {0, 1, 2, 3, 4 . . .} G = {2, 4, 6, 8, . . .} die Menge der geraden Zahlen. 2. In beschreibender Form, d.h. durch Angabe der Eigenschaften der Elemente, z.B. G = {x | x ∈ N und x ist gerade} . Die allgemeine Form ist: M = {x | A(x)} , dabei steht A f¨ ur eine Eigenschaft, die potentielle Elemente haben k¨ onnen; A(x) heißt: die Eigenschaft A trifft f¨ ur das Objekt x zu. Man kann auch schreiben: G = {x ∈ N | x ist gerade}, d.h. die gr¨oßere Menge, in der sich die Elemente der zu definierenden Menge befinden, hier die Menge N, wird nicht unter den Eigenschaften, sondern bereits vor dem Trennstrich in der Mengenklammer genannt. 3. In abgek¨ urzter beschreibender Form, z.B. G = {2 · m | m ∈ N} . Man verzichtet hier auf einen speziellen Namen f¨ ur die Elemente und gibt sofort ein Bildungsgesetz, z.B. einen Term oder algebraischen Ausdruck, an. Ein anderes Beispiel hierzu: K = = {1 + 3z | z ∈ Z} {. . . , −5, −2, 1, 4, 7, 10, . . . } . Beispiel: die Menge der Quadratzahlen in allen drei Beschreibungsformen: Q = {1, 4, 9, 16, 25, . . .} = {y | y ∈ N und es existiert ein x ∈ N so dass x2 = y} = {x2 | x ∈ N} Definition 1.1.5 (Teilmenge) a) Eine Menge A heißt Teilmenge einer Menge M , falls jedes Element von A auch Element von M ist. Die entsprechende Beziehung zwischen A und M heißt auch Inklusion (von A in M ). Bezeichnung: A⊆M . c Rudolf Scharlau Lineare Algebra I – WS 2015/16 5 b) Eine Menge A heißt echte Teilmenge einer Menge M , falls A Teilmenge von M und A 6= M ist. Die entsprechende Beziehung zwischen A und M heißt auch echte Inklusion (von A in M ). Bezeichnung: A(M oder A&M . Wir weisen ausdr¨ ucklich darauf hin, dass bei der Inklusion die Gleichheit der beiden Mengen erlaubt ist: es gilt M ⊆ M . F¨ ur die Inklusion wird oft auch die Schreibweise A ⊂ M benutzt; die von uns gew¨ahlte Konvention hat den Vorteil, dass sie zu den u ur den ¨blichen Zeichen ≤ bzw. < f¨ Gr¨ oßenvergleich von Zahlen passt. Definition 1.1.6 (Operationen mit Mengen) A∩B A∪B ArB = {x | x ∈ A und x ∈ B} = {x | x ∈ A oder x ∈ B} = {x | x ∈ A und x ∈ 6 B} Durchschnitt Vereinigung Differenz(menge) Beachte, dass bei der Bildung der Differenzmenge B nicht in A enthalten sein muss. Man kann sich allerdings immer auf diesen Fall zur¨ uckziehen, denn es gilt offensichtlich A r B = A r (A ∩ B) . Mengen und Mengenoperationen k¨ onnen durch sog. Venn-Diagramme veranschaulicht werden; hier ist die Veranschaulichung der Differenzmenge: A A B A\B B A\B Abb. 1.1: Differenzmenge Falls alle betrachteten Mengen Teilmengen einer festen Menge M sind (in einer solchen Situation wird M auch als Grundmenge bezeichnet), wird die Differenzmenge M r A auch als das Komplement von A in M bezeichnet. Oft schreibt man f¨ ur diese Menge {A oder A; wir werden diese Bezeichnungen nicht verwenden, weil sie den Bezug auf die Grundmenge M nicht mehr ausdr¨ ucken. Definition und Bemerkung 1.1.7 Zwei Teilmengen A und B einer Menge M heißen disjunkt, falls A ∩ B = ∅ ist. Eine Menge M heißt disjunkte Vereinigung von zwei Teilmengen A und B, falls A ∩ B = ∅ und A ∪ B = M ist. Man schreibt dann M = A ∪˙ B. In diesem Fall gilt f¨ ur die M¨ achtigkeiten |A ∪˙ B| = |A| + |B|. Definition 1.1.8 (Kartesisches Produkt, Produktmenge) a) Das kartesische Produkt zweier Mengen A und B ist definiert als A × B := {(a, b) | a ∈ A und b ∈ B}. Ein Element (a, b) ∈ A × B heißt geordnetes Paar. Nach Definition gilt f¨ ur beliebige a, a0 ∈ A, b, b0 ∈ B: (a, b) = (a0 , b0 ) genau dann, wenn a = a0 und b = b0 6 Lineare Algebra I – WS 2015/16 c Rudolf Scharlau b) Allgemeiner ist das kartesische Produkt von n Mengen A1 , A2 , . . . , An definiert als A1 × A2 × · · · × An = {(a1 , a2 , . . . , an ) | ai ∈ Ai f¨ ur i = 1, . . . , n} . Ein Element (a1 , a2 , . . . , an ) ∈ A1 × A2 × · · · × An heißt n-Tupel. Nach Definition gilt f¨ ur beliebige ai , bi ∈ Ai , i = 1, . . . , n: (a1 , a2 , . . . , an ) = (b1 , b2 , . . . , bn ) genau dann, wenn ai = bi f¨ ur i = 1, . . . , n . Das kartesische Produkt wird auch einfach als Produktmenge bezeichnet. Zwei n-Tupel sind also nur dann gleich, wenn an entsprechenden Stellen dasselbe Element der jeweiligen Menge Ai steht. Insbesondere kommt es in geordneten Paaren auf die Reihenfolge der beiden Elemente an: Es gilt (a, b) 6= (b, a), falls a 6= b. (Es m¨ ussen a und b beide in A und B liegen, damit die fraglichen Paare in A × B liegen. Wir denken bei dieser Bemerkung insbesondere an den wichtigen Fall A = B.) Bez¨ uglich Reihenfolge verh¨alt sich also (a, b) anders als die Menge {a, b}, f¨ ur die ¨ offenbar {a, b} = {b, a} gilt. Ubrigens sollte man die Notation {a, b} nur benutzen, wenn a 6= b ist (sonst notiert man die einelementige Menge nat¨ urlich als {a}), w¨ahrend ein geordnetes Paar (a, a) durchaus Sinn macht. Bei n-Tupeln (wir nehmen hier der Einfachheit halber den Fall A1 = A2 = · · · = An =: A an) kommt es erst recht auf die Reihenfolge an: wenn etwa a, b, c drei verschiedene Elemente aus A sind, dann k¨onnen wir hieraus 6 verschiedene Tripel in A × A × A bilden, n¨amlich (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a). Als Spezialfall eines kartesischen Produktes ist vor allem die Menge R × R =: R2 bekannt. Hier handelt es sich um reelle Zahlenpaare, die nach Einf¨ uhrung eines Koordinatensystems mit den Punkten der Ebene identifiziert werden. Wenn M ⊆ R und N ⊆ R Intervalle sind, kann man sich entsprechend M × N als Rechteck vorstellen. Von dieser geometrischen Interpretation kommt auch die Wortwahl kartesisch“ beim ” kartesischen Produkt her: Descartes 2 f¨ uhrte als erster ein solches kar” tesisches“ Koordinatensystem ein. Die Bezeichnung eines kartesischen Produktes als Produkt“ wird auch ” durch den folgenden Satz unterst¨ utzt. Satz 1.1.9 Es seien M und N zwei endliche Mengen. Dann ist auch ihr kartesiches Produkt endlich und seine M¨ achtigkeit gleich dem Produkt der M¨ achtigkeiten von M und N : |M × N | = |M | · |N | . Beweis: Sei |M | = m, |N | = n, M = {x1 , x2 , . . . , xm }. Dann ist M × N die disjunkte Vereinigung der m Mengen {xi } × N, i = 1, . . . , m. Jede dieser Mengen hat n Elemente (sie ist gleichm¨achtig zur Menge N , siehe unten 1.1.22 a)). Die M¨achtigkeit von M × N ergibt sich also als die m-fache Summe der Zahl n, also als m · n, wie behauptet.  Wir behandeln noch eine andere Abz¨ahlfrage im Zusammenhang mit endlichen Mengen. 2 Ren´ e Descartes, 1596 – 1650, franz¨ osischer Philosoph und Mathematiker Lineare Algebra I – WS 2015/16 c Rudolf Scharlau 7 Definition und Satz 1.1.10 Die Menge aller Teilmengen einer Menge M heißt Potenzmenge von M und wird mit P(M ) bezeichnet: P(M ) := {X | X ⊆ M } . Wenn M endlich mit n Elementen ist, dann besteht P(M ) aus 2n Elementen: |P(M )| = 2|M | . Beweis durch vollst¨ andige Induktion nach n:3 Induktionsanfang: F¨ ur n = 0, also M = ∅ ist die Behauptung richtig, denn P(∅) = {∅}. Induktionsschritt: Die Behauptung sei f¨ ur Mengen der M¨achtigkeit n bewiesen. Sei M eine Menge mit |M | = n+1. W¨ahle ein Element a ∈ M , setze M 0 := M r {a}. Es gilt also |M 0 | = n. Wir teilen die Teilmengen X ⊆ M in zwei Klassen ein: Mengen mit a ∈ / X, das sind genau die Teilmengen von M 0 , und Mengen mit a ∈ X. Auf diese Art haben wir eine Darstellung P(M ) = P(M 0 ) ∪ P 0 als disjunkte Vereinigung, wobei P 0 = {X ⊆ M | a ∈ X}. Die Mengen in P 0 sind alle von der Form X = X 0 ∪ {a}, wobei X 0 eine (durch X eindeutig bestimmte) Teilmenge von M 0 ist. Von diesen Mengen gibt es also genau so viele wie Teilmengen von M 0 , m.a.W. |P 0 | = |P(M 0 )|. Nach Induktionsannahme gilt |P(M 0 )| = 2n . Insgesamt folgt also |P(M )| = |P(M 0 )|+|P 0 | = |P(M 0 )|+|P(M 0 )| = 2|P(M 0 )| = 2·2n = 2n+1 , wie gew¨ unscht. Es sei n = 3, M = {a, b, c}. Dann ist P(M ) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} = {∅, {c}, {b}, {b, c}, {a}, {a, c}, {a, b}, {a, b, c}} . (Die zweite Zeile zeigt die Anordnung der Teilmengen, die sich aus dem Beweis ergibt.) Wir f¨ uhren zwischendurch einige gr¨ oßtenteils aus der Aussagenlogik stammende Symbole ein, die f¨ ur das strukturierte und etwas abgek¨ urzte Aufschreiben von S¨ atzen und Definitionen sehr praktisch sind. Bezeichnungen 1.1.11 (einige Symbole der Logik) ∃ ∀ =⇒ ⇐⇒ :⇐⇒ ∧ ∨ heißt heißt heißt heißt heißt heißt heißt es gibt ein“ ” f¨ ur alle“ ” impliziert“, aus . . . folgt“ ” ” genau dann, wenn“ ” genau dann, wenn“(Definition der linken Seite) ” und” ” oder” ” Wir kommen zum zweiten Teil dieses Paragraphen, n¨amlich dem mathematischen Begriff einer Abbildung. Definition 1.1.12 Es seien X und Y zwei Mengen. Eine Abbildung von X in Y ist gegeben durch eine Vorschrift f , die jedem Element x ∈ X genau ein Element y ∈ Y zuordnet. Man schreibt y = f (x) (lies: f von ” x“). F¨ ur die gesamte Abbildung schreibt man 3 F¨ ur das Prinzip der vollst¨ andigen Induktion siehe den Punkt 1.2.1 im folgenden Unterkapitel 1.2. 8 Lineare Algebra I – WS 2015/16 c Rudolf Scharlau f : X → Y (lies: f von X nach Y “ oder . . . in Y “). ” ” F¨ ur ein Element x ∈ X benutzt man die Notation x 7→ f (x) (lies: x wird abgebildet auf f (x)“). ” f (x) heißt das Bild von x unter f . X heißt Definitionsbereich. Y heißt Zielbereich oder die Zielmenge. Die Elemente von X heißen auch die Argumente der Abbildung Wichtig: Zwei Abbildungen sind nur dann gleich, wenn die Vorschriften und auch die Definitions- und Zielbereiche u ¨bereinstimmen. Die Abbildungen unter (1) des folgenden Beispiels sind alle verschieden, auch wenn die Vorschrift immer die gleiche, n¨amlich das Quadrieren einer Zahl ist. Beispiele 1.1.13 (Abbildungen) (1a) X = N, Y = N, f (x) = x2 (1b) X = Z, Y = N0 , f (x) = x2 (1c) X = Z, Y = Z, f (x) = x2 (2) X = Y = R, f (x) = ex , cos x, sin x reelle Funktionen“, wie man sie in der Analysis studiert, sind ” ebenfalls Abbildungen. (3) X = P({1, 2, . . . , n}), Y = N0 , f (x) = |x| die M¨achtigkeit von x. (4) X wie eben, Y = X, f (x) = x := {1, 2, . . . , n} r x das Komplement von x. (5) X sei endlich. Dann kann die Vorschrift“ als eine (endliche) Ta” belle aufgefasst werden. Zum Beispiel: X = {1, 2, 3, 4, 5}, Y = {u, v, w, x, y, z}, 1 2 3 4 5 x f (x) y v w x w Abbildungen zwischen endlichen Mengen (mit wenigen Elementen) kann man auch durch ein Pfeildiagramm veranschaulichen: die Mengen X und Y werden in geeigneter Weise skizziert, und jedes Element des Definitionsbereiches wird mit seinem Bild durch einen Pfeil verbunden: 1 u 2 v 3 w 4 x 5 y z Abb. 1.2 Pfeildiagramm einer Abbildung Das Pfeildiagramm einer Abbildung kann nicht beliebig aussehen, vielmehr hat es folgende charakteristische Eigenschaft: Bei jedem Element des Definitionsbereichs X beginnt genau ein Pfeil. Ist eine Abbildung f mit Definitionsbereich X gegeben, kann man den Begriff des Bildes unter f“ von den Elementen von X auf Teilmengen ” von X ausdehnen; wir erg¨anzen ihn nun um den Begriff des Urbildes: Lineare Algebra I – WS 2015/16 c Rudolf Scharlau 9 Definition 1.1.14 (Bilder und Urbilder von Teilmengen) Es sei f : X → Y eine Abbildung. a) F¨ ur A ⊆ X definiere f (A) := {y ∈ Y | es gibt ein a ∈ A mit f (a) = y} = {f (a) | a ∈ A} das Bild von A unter f . b) F¨ ur B ⊆ Y definiere f −1 (B) := {x ∈ X | f (x) ∈ B} das Urbild von B unter f . Zur Illustration dieser Begriffe benutzen wir die obigen Beispiele 1.1.13. Beispiele 1.1.15 (1a) X = N, Y = N, f (x) = x2 f ({1, 2, 3}) = {1, 4, 9} f ({5, 7, 12}) = {25, 49, 144} f −1 ({25, 36, 49}) = {5, 6, 7} f −1 ({10, 11, 12, . . . , 20}) = {4} f −1 ({100, 101, . . . , 200}) = {10, 11, 12, 13, 14} (1c) X = Z, Y = Z, f (x) = x2 f −1 ({25}) = {5, −5} f −1 ({25, 36, 49}) = {±5, ±6, ±7} (6 Elemente) f −1 ({−1, −2, −3, . . .}) = ∅ (leere Menge) (5) (siehe 1.1.13 (5)): X = {1, 2, 3, 4, 5}, Y = {u, v, w, x, y, z} f −1 ({u, v}) = {2} f −1 ({z}) = ∅ f −1 ({v, w}) = {2, 3, 5} Man mache sich auch klar, wie man Bilder und Urbilder sieht“, wenn ” eine Abbildung durch ein Pfeildiagramm gegeben ist. Definition 1.1.16 Eine Abbildung f : X → Y heißt injektiv :⇐⇒ f¨ ur alle x, x0 ∈ X gilt: x 6= x0 =⇒ f (x) 6= f (x0 ), (Verschiedene Elemente in X haben auch verschiedene Bilder unter f .) surjektiv :⇐⇒ f¨ ur alle y ∈ Y gibt es ein x ∈ X mit f (x) = y, (Jedes Element in Y kommt als Bild unter f vor.) bijektiv :⇐⇒ f ist injektiv und surjektiv. Bemerkung a) Die Injektivit¨ at kann man auch wie folgt formulieren: ∀ x, x0 ∈ X : f (x) = f (x0 ) =⇒ x = x0 . Wenn zwei Elemente das gleiche Bild haben, so sind sie gleich. b) Die Menge f (X) (also das Bild von ganz X unter f ) heißt auch die Bildmenge oder einfach das Bild von f . Eine Abbildung f : X → Y ist surjektiv genau dann, wenn f (X) = Y ist, d.h. ihr Bild gleich ganz Y ist. 10 Lineare Algebra I – WS 2015/16 c Rudolf Scharlau Im Pfeildiagramm bedeuten diese Eigenschaften: injektiv surjektiv : : es laufen keine zwei Pfeile zusammen bei jedem y in Y endet ein Pfeil Aus einer beliebigen Abbildung f : X → Y kann man leicht eine surjektive Abbildung machen: Man ersetze n¨amlich Y durch die Bildmenge f (X). Definition 1.1.17 Es sei f : X → Y eine Abbildung. Der Graph von f ist definiert als Γf := {(x, f (x) | x ∈ X} ⊆ X × Y . Definition 1.1.18 Es seien f : X → Y und g : Y 0 → Z, dabei Y ⊆ Y 0 zwei Abbildungen, wobei der Zielbereich der ersten im Definitionsbereich der zweiten enthalten ist. Die Komposition, Verkettung oder Hintereinanderausf¨ uhrung g◦f :X →Z (lies: g nach f“) ist definiert durch ” (g ◦ f )(x) = g(f (x)) f¨ ur alle x ∈ X . Bemerkung 1.1.19 Die Komposition ist assoziativ, d.h. wenn f : X → Y , g : Y 0 → Z, h : Z 0 → W drei Abbildungen sind mit Y ⊆ Y 0 und Z ⊆ Z 0 , so ist h ◦ (g ◦ f ) = (h ◦ g) ◦ f : X → W . Definition und Bemerkung 1.1.20 Es sei X irgendeine Menge. Die identische Abbildung idX : X → X ist definiert durch idX (x) = x f¨ ur alle x ∈ X. Wenn f : X → Y eine beliebige Abbildung ist, so gilt f ◦ idX = f = idY ◦f . Satz und Definition 1.1.21 (Umkehrabbildung) Es sei f : X → Y eine Abbildung. a) Die folgenden beiden Eigenschaften sind ¨aquivalent: i) f ist bijektiv. ii) Es gibt eine Abbildung g : Y → X so, dass g(f (x)) = x f¨ ur alle x ∈ X, d.h. g ◦ f = idX und f (g(y)) = y f¨ ur alle y ∈ Y , d.h. f ◦ g = idY . b) Falls f bijektiv ist, so gibt es nur eine Abbildung g, die ii) erf¨ ullt. Schreibe g =: f −1 . Diese Abbildung heißt die zu f inverse Abbildung, oder Umkehrabbildung von f . c) Wenn f : X → Y bijektiv ist, so ist auch f −1 : Y → X bijektiv, und es gilt (f −1 )−1 = f . Beweis: zu a): Es sind zwei Implikationen zu zeigen: i) =⇒ ii)“: Zu jedem y ∈ Y gibt es genau ein x ∈ X mit f (x) = y, ” denn f ist surjektiv und injektiv. Setze nun g(y) := x. Dann gilt nach Konstruktion g(f (x)) = x f¨ ur alle x ∈ X , Lineare Algebra I – WS 2015/16 c Rudolf Scharlau 11 wie unter ii) als erstes behauptet. Wir zeigen nun die zweite Behauptung unter ii). Sei y ∈ Y beliebig. Weil f surjektiv ist, existiert ein x ∈ X mit f (x) = y. Es folgt f (g(y)) = f (g(f (x))) = f (x) = y, wie gew¨ unscht. ii) =⇒ i)“: ” 1) f ist injektiv: Es seien x, x0 ∈ X mit f (x) = f (x0 ). Dann ist x = g(f (x)) = g(f (x0 )) = x0 , wie gew¨ unscht. 2) f ist surjektiv: Sei y ∈ Y gegeben. Setze x := g(y). Dann ist f (x) = f (g(y)) = (f ◦ g)(y) = y, wie gew¨ unscht. zu b): (Eindeutigkeit von g): Angenommen, h : Y → X hat die gleichen Eigenschaften wie g. Dann gilt h = h ◦ idY = h ◦ (f ◦ g) = (h ◦ f ) ◦ g = idX ◦g = g. zu c): Dieses folgt sofort aus der in a) gegebenen Kennzeichnung bijektiver Abbildungen.  Wir kehren noch einmal zum Begriff der M¨achtigkeit einer Menge zur¨ uck, den wir jetzt mit Hilfe des Abbildungsbegriffs vertiefen k¨onnen. Definition 1.1.22 a) Eine Menge M heißt gleichm¨ achtig zu einer Menge N , falls eine bijektive Abbildung f : M → N existiert. b) Eine Menge heißt abz¨ ahlbar, falls sie gleichm¨achtig zur Menge der nat¨ urlichen Zahlen ist. Bemerkung: Wenn M gleichm¨ achtig zu N ist, so k¨onnen wir statt der Abbildung f : M → N aus der Definition auch die (ebenfalls bijektive) Umkehrabbildung f −1 : N → M betrachten. Es folgt, dass N gleichm¨ achtig zu M ist. Etwas l¨ assiger k¨onnen wir also auch sagen Die ” Mengen M und N sind gleichm¨ achtig“, wobei es dann auf die Reihenfolge, in der M und N genannt werden, nicht ankommt. (Sp¨ater werden wir sagen: Die Relation gleichm¨ achtig“ ist symmetrisch.) ” Wir u ur ¨berlegen uns, dass die Definition der Beziehung gleichm¨achtig“ f¨ ” endliche Mengen zur urspr¨ unglichen Definition der M¨achtigkeit passt: Eine Menge M hat n Elemente“, wenn ihre Elemente in der Form ” x1 , x2 , . . . , xn aufgez¨ ahlt werden k¨ onnen (wobei nat¨ urlich alle xi voneinander verschieden sind). Eine solche Aufz¨ ahlung (oder Abz¨ ahlung) ist aber nichts anderes als eine bijektive Abbildung {1, 2, . . . , n} → M , i 7→ xi . D.h. jede n-elementige Menge M ist gleichm¨achtig zur Menge {1, 2, . . . , n}, die also die Rolle einer Art Standardmenge“ der M¨achtigkeit n hat. Wir ” ¨ halten diese Uberlegung in etwas vervollst¨andigter und zitierbarer Form fest: Bemerkung 1.1.23 Es sei n ∈ N. Eine Menge M hat die M¨achtigkeit n genau dann, wenn sie gleichm¨ achtig zur Menge {1, 2, . . . , n} ist. Wer mag, kann dieses auch als Definition einer Menge der M¨achtigkeit n ansehen, womit dann die endlichen und abz¨ahlbaren Mengen einheitlich behandelt werden. Um allerdings jeder endlichen Menge eine eindeutige 12 Lineare Algebra I – WS 2015/16 c Rudolf Scharlau M¨ achtikeit zuordnen zu k¨onnen, muss man wissen, dass f¨ ur m 6= n die Mengen {1, 2, . . . , m} und {1, 2, . . . , n} nicht gleichm¨achtig sind, dass also keine bijektive Abbildung zwischen ihnen exstiert. Hier sind wir dann doch wieder auf unser intuitives Verst¨andnis endlicher Mengen angewiesen, das bereits der obigen Definition 1.1.3 zugrundegelegt wurde. Zum Schluss dieses Abschnitts kommen wir noch einmal auf die Begriffe injektiv“ und surjektiv“ zur¨ uck: ” ” Satz 1.1.24 Es seien f : X → Y und g : Y → Z zwei injektive (surjektive, bijektive) Abbildungen. Dann ist auch die Verkettung g ◦ f injektiv (bzw. surjektiv, bijektiv). ¨ Den Beweis u wir haben oben beim ¨berlassen wir als Ubungsaufgabe; Beweis von Satz 1.1.21 vorgef¨ uhrt, wie solch ein im Prinzip einfacher, jedoch abstrakter“ Beweis aussieht. Folgender Hinweis ist noch n¨ utzlich: ” Wenn man den Satz f¨ ur injektive und surjektive Abbildungen bewiesen hat, so ist f¨ ur bijektive Abbildungen kein Beweis mehr n¨otig (denn definitionsgem¨aß sind bijektive Abbildungen diejenigen, die gleichzeitig injektiv und surjektiv sind). Einen von den anderen F¨allen unabh¨angigen direkten Beweis im bijektiven Fall kann man in wenigen Zeilen geben, wenn man die Kennzeichnung bijektiver Abbildungen aus Satz 1.1.21, Teil a) benutzt: Man pr¨ uft n¨amlich nach, dass die Abbildung f −1 ◦ g −1 die Eigenschaften der Inversen zu g ◦ f erf¨ ullt. Dieser Beweis erspart das Rechnen“ mit Elementen der beteiligten Mengen, man rechnet“ mit ” ” den Abbildungen selbst und benutzt nur das Assoziativgesetz sowie die Eigenschaft der identischen Abbildung aus Bemerkung 1.1.20.