<<

. 2
( 60 .)



>>

¨
explizit andeutet, dass die Mengen auch gleich sein k¨nnen. Wir werden diese
o
Notation jedoch nicht verwenden.
Teilmengen einer Menge werden auch sehr oft durch Eigenschaften beschrie-
ben. Ist M eine Menge und E eine Eigenschaft, so ist
A = {x ∈ M : x hat Eigenschaft E}
einfach die Menge derjenigen Elemente von M, die die Eigenschaft E besitzen.
Die Menge {’1, 1} liesse sich dann auch durch
A = x ∈ R : x2 = 1
beschreiben.
Aus der Schule sind wahrscheinlich Durchschnitt, Vereinigung und Kom-
plement bekannt: Es seien A und B zwei Mengen. Dann sind diese neuen
Mengen wie folgt de¬niert:
A © B := {x : x ∈ A und x ∈ B} ,
A ∪ B := {x : x ∈ A oder x ∈ B} ,
A\B := {x : x ∈ A und x ∈ B} .
/
Wir werden oft Teilmengen einer festen Menge, nennen wir sie M, betrachten,
die dann fur eine l¨ngere Betrachtung nicht mehr wechselt. Dann schreibt man
a
¨
c
einfach A fur M \A. Das ist das Komplement von A in M. Naturlich musste
¨ ¨ ¨
man eigentlich M in der Notation mit ausdrucken. Das wird jedoch stets aus
¨
dem Kontext ersichtlich sein. Fur die obigen Mengenoperationen gelten einige
¨
Rechenregeln, die wir hier als bekannt voraussetzen, z.B.
A © (B ∪ C) = (A © B) ∪ (A © C) , (1.4)
(A ∪ B)c = Ac © B c .

7
Den Beweis, dass zwei Mengen, nennen wir sie F und G, gleich sind, fuhrt
¨
man oft in zwei Schritten. Man zeigt zuerst, dass F ‚ G gilt, und dann, dass
G ‚ F gilt. Wir exempli¬zieren das mit einem Beweis von (1.4):

Beweis von (1.4). Sei x ∈ A © (B ∪ C) . Dann ist x Element von A und von
B∪C. Ist x ∈ B∪C, so ist x in B oder in C. Gilt Ersteres, so ist x ∈ A©B und gilt
Letzteres, so gilt x ∈ A©C. In jedem Fall folgt dann x ∈ (A © B)∪(A © C) . Damit
haben wir gezeigt, dass jedes Element von A © (B ∪ C) auch in (A © B) ∪ (A © C)
ist. Damit haben wir nachgewiesen, dass

A © (B ∪ C) ‚ (A © B) ∪ (A © C) (1.5)

gilt.
Nun kommen wir zum zweiten Teil des Beweises. Sei x ∈ (A © B) ∪ (A © C) .
Dann ist x ∈ A © B oder x ∈ A © C. x liegt also in A und B, oder in A und C.
In jedem Fall liegt also x in A und dann in B oder C. Das bedeutet aber nichts
anderes, dass x ∈ A © (B ∪ C) gilt. Wir haben also

(A © B) ∪ (A © C) ‚ A © (B ∪ C) (1.6)

nachgewiesen.
(1.5) und (1.6) implizieren (1.4).

Wir betrachten nun die Vereinigung oder den Durchschnitt von mehr als zwei
Mengen, unter Umst¨nden von unendlich vielen. In solchen F¨llen sind die Men-
a a
gen dann oft mit Hilfe von Indizes beschrieben: Ai , wobei i eine Indexmenge
durchl¨uft, z.B. die naturlichen Zahlen: Sind A1 , A2 , A3 , . . . Mengen so schreiben
a ¨
wir i=1 Ai fur die Vereinigung und ∞ Ai fur den Durchschnitt dieser Mengen.

¨ ¨
i=1
Die Indexmenge, aus der i ist, braucht jedoch nicht die Menge der naturlichen ¨
Zahlen zu sein, sondern kann eine ganz beliebige Menge I sein (z.B. die Menge
der reellen Zahlen). Wir schreiben dann i∈I Ai bzw. i∈I Ai . Es gibt eine formal
etwas abstraktere Schreibweise, die manchmal bequem ist. Die Darstellung einer
Kollektion von Mengen mit Hilfe eines Indexes ist mathematisch n¨mlich meist
a
uber¬‚ussig. Wir k¨nnen statt dessen einfach Mengen betrachten, deren Elemen-
o
¨ ¨
te selbst Mengen sind. Ausgehend von der Folge A1 , A2 , A3 , . . . betrachten wir
def
die Menge A = {A1 , A2 , A3 , . . .} . Deren Elemente sind nun gerade die Ai . Wir
schreiben dann einfach A fur ∞ Ai . Also: Ist A eine Menge deren Elemente
¨ i=1
selbst Mengen sind (oft sagt man dann auch eine “Familie von Mengen”), so ist
A die Vereinigung dieser Elemente. Entsprechend fur den Durchschnitt. Hier
¨
noch die ganz formale De¬nition:

A = {x : ∃A ∈ A mit x ∈ A} ,

wobei wir hier das Symbol ∃ verwenden, was einfach eine Abkurzung fur “exi-
¨ ¨
stiert” ist, und

8
A = {x : x ∈ A f¨r ∀A ∈ A} .
u
Wenn Sie im Moment noch etwas Schwierigkeiten mit diesen abstrakten Formu-
lierungen haben, so ist das nicht allzu schlimm; Sie werden sich mit der Zeit
daran gew¨hnen.
o
Eine spezielle Familie von Mengen ist die sogenannte Potenzmenge einer
Menge. Ist A eine Menge, so ist die Potenzmenge P (A) die Menge aller Teilmen-
gen von A :
P (A) := {B : B ‚ A} .
Z.B. hat fur A = {1, 2} die Potenzmenge die vier Elemente …, {1}, {2}, {1, 2},
¨
also
P ({1, 2}) = {…, {1} , {2} , {1, 2}} .

1.2 Abbildungen
A und B seien zwei Mengen. Eine Abbildung f : A ’ B ist eine Vorschrift,
die jedem x ∈ A genau ein Element f (x) ∈ B zuordnet. f (x) heisst dann das
Bildelement von x.
Wir schreiben auch oft A x ’’ f (x) ∈ B.

Beispiel 1.1 a) Wir betrachten die Abbildung f : R ’ R, die jedem Element x
sein Quadrat zuordnet. f (x) := x2 .
b) f sei die Abbildung N ’ N, die jeder Zahl das Doppelte zuordnet: f (x) :=
2x.

Die beiden Beispiele oben waren sogenannte Selbstabbildungen, wo die Ziel-
menge B die gleiche wie die Ursprungsmenge A ist. Das braucht jedoch nicht so
zu sein. Wir werden noch sehr viele Beispiele kennenlernen, wo das anders ist.
Eine Selbstabbildung einer Menge A spielt eine besondere Rolle, die identische
Abbildung idA : A ’ A :
idA (x) := x
fur alle x ∈ A.
¨
Wir ben¨tigen noch ein paar weitere Begri¬sbildungen.
o

De¬nition 1.1 Eine Abbildung f : A ’ B heisst surjektiv, wenn jedes Ele-
ment von B als Bildelement eines Elementes in A vorkommt, d.h. fur jedes y ∈ B
¨
existiert (mindestens) ein x ∈ A mit f (x) = y. In formaler “Stenographenschreib-
weise”:
f surjektiv ⇐’ ∀y ∈ B ∃x ∈ A (f (x) = y) .




9
x ’ x2 ∈ R ist o¬enbar nicht surjektiv, denn es gibt
Die Abbildung R
Elemente von R, die nicht also Bildelemente vorkommen, namlich die negativen
¨
reellen Zahlen. Auch die Abbildung N x ’ 2x ∈ N ist nicht surjektiv, denn
die ungeraden naturlichen Zahlen kommen nicht als Bildelemente vor.
¨

De¬nition 1.2 Eine Abbildung f : A ’ B heisst injektiv, wenn zwei verschie-
dene Elemente in A auch auf verschiedene Elemente in B abbgebildet werden:
Falls x, x ∈ A und x = x gelten, so ist f (x) = f (x ). Eine Abbildung, die sowohl
injektiv wie surjektiv ist, heisst bijektiv.

Die Abbildung N x ’ 2x ∈ N ist o¬enbar injektiv, nicht aber R x ’ x2 ∈
R, denn unter letzterer werden z.B. ’1 und 1 auf dasselbe Element abgebildet.

De¬nition 1.3 Sind f : A ’ B und g : B ’ C zwei Abbildungen, so ist die
Zusammensetzung oder Komposition dieser Abbildungen g —¦ f : A ’ C wie
folgt de¬niert:
(g —¦ f ) (x) := g (f (x)) .

Man beachte, dass diese Komposition nur de¬niert ist, wenn die Zielmenge B
der Abbildung f gleich der Ausgangsmenge der Abbildung g ist.

Bemerkung 1.1 Die Schreibweise g —¦ f fur diese Komposition ist leider etwas
¨
unglucklich, hat sich jedoch aus historischen Grunden o¬enbar unverruckbar ein-
¨ ¨ ¨
geburgert. Es wird n¨mlich f zuerst ausgefuhrt und dann g. Die Schreibweise
a
¨ ¨
ergibt sich aus der Schreibweise f (x) fur das Bildelement von x unter f. Logi-
¨
scher w¨re es an sich, (x)f zu schreiben, denn man “nimmt” x und wendet dann
a
die Abbildung f darauf an. Es hat erfolglose Anl¨ufe gegeben, das in dieser Weise
a
umzustellen.

Beispiel 1.2 Wir betrachten die folgenden zwei Funktionen f, g : R ’ R : f (x)
= x2 , g(x) = ex . Dann ist f —¦ g die Funktion R x ’ (ex )2 = e2x . Andererseits
2
ist g —¦ f die Funktion R x ’ ex . Man sieht also schon an diesem Beispiel,
dass im Allgemeinen f —¦ g = g —¦ f ist, selbst wenn beide Kompositionen de¬niert
sind.

seien A, B, C Mengen und f : A ’ B und g : B ’ C seien
Satz 1.1 Es
Abbildungen.
und g injektiv, so ist auch g —¦ f injektiv.
a) Sind f
und g surjektiv, so ist auch g —¦ f surjektiv.
b) Sind f
und g bijektiv, so ist auch g —¦ f bijektiv.
c) Sind f

Beweis. c) folgt sofort aus a) und b). Wir beweisen nur a). Der Beweis von
b) sei dem Leser uberlassen.
¨


10
Es seien a, a zwei Elemente von A mit g —¦ f (a) = g —¦ f (a ) . Nun ist aber per
De¬nition der Komposition g —¦ f (a) = g (f (a)) . Also folgt g (f (a)) = g (f (a )) .
Wegen der Injektivitat von g folgt f (a) = f (a ). Aus der Injektivitat von f ergibt
¨ ¨
sich daraus a = a . Dies beweist, dass g —¦ f injektiv ist.
Von besonderer Bedeutung sind bijektive Abbildungen einer endlichen Menge,
etwa {1, . . . , n} , auf sich selbst.
Eine bijektive Abbildung σ : {1, . . . , n} ’ {1, . . . , n} heisst Permutation.
¨
Ublicherweise verwendet man kleine griechische Buchstaben wie σ, „, π um Per-
mutationen zu bezeichnen. Wir werden die folgende Schreibweise fur Permuta-
¨
tionen verwenden
n’1
1 2 ... n
σ= .
σ(1) σ(2) . . . σ(n ’ 1) σ(n)

Zum Beispiel ist
12345
σ=
24153
die Permutation σ die 1 nach 2, 2 nach 4, 3 nach 1, 4 nach 5 und 5 nach 3 schickt.
Die Reihenfolge der Spalten in der obigen Anordnung spielt dann keine Rolle. So
ist
35124
13245
dieselbe Permutation. Die Schreibweise ist auch bequem, um Kompositionen von
Permutationen zu berechnen. Wir geben dazu ein Beispiel. Wir nehmen als
zweite Permutation
12345
„ := .
32451
Dann sind
12345 12345
󗦄 = —¦
24153 32451
32451 12345
—¦
=
14532 32451
12345
= ,
14532


12345 12345
„ —¦σ = —¦
32451 24153
12345
= .
25314

Auch hier sieht man, dass σ —¦ „ = „ —¦ σ ist.

11
Zum Schluss dieses Abschnitts diskutieren wir noch die Umkehrabbildun-
gen. f : A ’ B sei eine bijektive Abbildung. Dann gibt es wegen der Surjek-
tivitat zu jedem Element y ∈ B ein Element x ∈ A mit f (x) = y. Wegen der
¨
Injektivitat gibt es zu jedem y nur ein derartiges Element x. Wir erhalten also
¨
eine eindeutig de¬nierte Zuordnung B y ’ x ∈ A. Diese Zuordnung nennen
wir die Umkehrabbildung von f und bezeichnen sie mit f ’1 , also f ’1 (y) = x.
Wir formulieren einige Eigenschaften als Satz:

<<

. 2
( 60 .)



>>