Vorlesungsskript

Skript zu der Vorlesung
Lineare Algebra 1
Prof. Dr. Mark Groves
WS2016/17
3. Dezember 2016
Inhaltsverzeichnis
1 Mengen, Funktionen und Relationen
1.1 Mengenlehre . . . . . . . . . . . .
1.2 Funktionen . . . . . . . . . . . . .
1.3 Geordnete Paare und Relationen
1.4 Wohlordnung und Induktion . .
1.5 Abzählbarkeit . . . . . . . . . . .
.
.
.
.
.
3
3
9
18
29
33
2 Algebraische Strukturen
2.1 Verknüpfungen, Gruppen und Körper . . . . . . . . . . . . . . . . .
2.2 Komplexe Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
39
50
3 Vektorräume
3.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Elementare Vektorraumtheorie . . . . . . . . . . . . . . . . . . . . .
67
67
74
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1 Mengen, Funktionen und Relationen
1 Mengen, Funktionen und Relationen
1.1 Mengenlehre
Definition (Cantor, 1895)
“Unter einer Menge verstehen wir jede Zusammenfassung von bestimmten wohl
unterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem
Ganzen.”
Die Objekte, die zu einer Menge zusammengefasst sind, heißen Elemente dieser
Menge. Eine Menge enthält ihre Elemente.
Wir können eine Menge festlegen, indem wir ihre Elemente explizit zwischen
geschweiften Klammern angeben.
Beispiele
1. Die Menge aller Vokale im englischen Alphabet ist {a,e,i,o,u}.
2. Die Menge aller ungeraden positiven ganzen Zahlen, die kleiner als 10 sind,
ist {1,3,5,7,9}.
Wir können eine Menge auch festlegen, indem wir die charakteristische Eigenschaft ihrer Elemente angeben.
Beispiel
Die Menge
{ x : x ist eine gerade, positive ganze Zahl, die kleiner als 10 ist}
ist
{2,4,6,8}.
Wir benutzen besondere Symbole für gewisse Mengen:
3
1.1 Mengenlehre
N = {1,2,3, . . . }
(die Menge der natürlichen Zahlen)
N0 = {0,1,2,3, . . .}
(die Menge der nichtnegativen
ganzen Zahlen)
Z = {. . . , −2, − 1,0,1,2, . . .}
nm
o
Q=
: m ∈ Z, n ∈ N
n
R ist die Menge aller reellen Zahlen.
(die Menge der ganzen Zahlen)
(die Menge der rationalen Zahlen)
C ist die Menge aller komplexen Zahlen.
∅ = {} ist die leere Menge.
Bemerkung
Eine Menge ist eine nicht geordnete Sammlung von Objekten, so dass
{2,4,6,8} = {4,8,6,2}.
Wir schreiben
x∈A
für die Tatsache, dass x Element von A ist, und
x∈
/A
für die Tatsache, dass x kein Element von A ist.
Definition
Eine Menge A heißt Teilmenge einer Menge B, wenn jedes Element von A auch
Element von B ist. In diesem Fall schreiben wir “A ⊆ B”.
Beispiele
1. {1,3,5} ⊆ {1,3,5,7}
2. ∅ ⊆ N ⊆ N0 ⊆ Z ⊆ Q ⊆ R ⊆ C
3. {1,3,5} 6⊆ {1,2,3,4}
4
1.1 Mengenlehre
Definitionen
1. Zwei Mengen sind gleich, wenn A ⊆ B und B ⊆ A. In diesem Fall schreiben
wir “A = B”.
2. Eine Menge A heißt echte Teilmenge von B, falls A ⊆ B und A 6= ∅, A 6= B.
Wir können Mengen kombinieren, um weitere Mengen zu bilden.
Definitionen
A und B seien Mengen.
1. Die Vereinigungsmenge oder Vereinigung von A und B ist die Menge
A ∪ B = { x : x ∈ A oder x ∈ B}.
↑
“A vereinigt mit B”
2. Die Schnittmenge oder der Durchschnitt von A und B ist die Menge
A ∩ B = { x : x ∈ A und x ∈ B}.
↑
“A durchschnitten B”
3. Die Differenz von A und B ist die Menge
A \ B = { x : x ∈ A und x ∈
/ B }.
↑
“A ohne B”
Bemerkungen
1. In der Mathematik benutzen wir das Wort “oder” immer im nicht ausschließenden Sinne. “x ∈ A oder x ∈ B” bedeutet also “x ∈ A” oder “x ∈ B”
oder beides.
2. Falls A ∩ B = ∅ (d.h. A und B haben keine gemeinsamen Elemente), sagen
wir: A und B sind disjunkt.
5
1.1 Mengenlehre
Beispiel
S1 = {( x,y) : ( x − 1)2 + (y − 1)2 < 1}, S2 = {( x,y) : |y| < 1}
seien Teilmengen der Ebene
P = {( x,y) : x,y ∈ R }.
Zeichnen Sie die Mengen S1 ,S2 ,S1 ∩ S2 und S1 ∪ S2 .
Lösung
y
S1
y
S1 ∩ S2
1
1
1
x
y
S2
y
S1 ∪ S2
1
x
1
1
x
-1
1
x
-1
Zeichenerklärung
— “Rand” gehört zur Menge
- - “Rand” gehört nicht zur Menge
• “Eckpunkt” gehört zur Menge
◦ “Eckpunkt” gehört nicht zur Menge
6
1.1 Mengenlehre
Im letzten Beispiel betrachteten wir S1 und S2 als Teilmengen einer Universalmenge P.
Definition
A sei Teilmenge einer Universalmenge U. Die Menge
A := U \ A
↑
definitionsgemäß gleich
heißt Komplement von A in U.
Gesetze der Mengenoperationen
X, Y und Z seien Teilmengen der Universalmenge U.
X∪∅=X
X∩U = X
Identitätsgesetze
X∪X=U
X∩X=∅
Dominationsgesetze
(X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z)
(X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z)
X∪Y =Y∪X
X∩Y =Y∩X
Assoziativgesetze
Kommutativgesetze
X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z)
X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z)
Distributivgesetze
Wir betrachten diese Grundgesetze der Mengenoperationen als Axiome (gegebene, nicht beweisbare Gesetze) und leiten weitere Ergebnisse von ihnen her.
7
1.1 Mengenlehre
Lemma
A und B seien Teilmengen der Universalmenge U. Es gelten:
A∪A= A
A∩A= A
Idempotenzgesetz
A = A (Involutionsgesetz)
A∪B= A∩B
de Morgansche Gesetze
A∩B= A∪B
Beweis
Es gilt:
A ∪ A = ( A ∪ A) ∩ U
(Identitätsgesetz)
= ( A ∪ A) ∩ ( A ∪ A) (Dominationsgesetz)
= A ∪ ( A ∩ A)
(Distributivgesetz)
=A
(Identitätsgesetz)
=A∪∅
(Dominationsgesetz)
Die anderen Aussagen werden in ähnlicher Weise bewiesen.
Bemerkung
Unsere Definition von einer Menge als “Sammlung von Objekten” ist etwas naiv
und kann zu Problemen führen.
(i) Als Elemente können Mengen andere Mengen haben.
Beispiel
A sei eine Menge. Die Menge aller Teilmengen von A heißt die Potenzmenge
von A und wird mit P( A) bezeichnet.
Für A = {1,2} ist z. B.
P( A) = {∅, {1},{2},{1,2}}.
8
1.2 Funktionen
(ii) Eine Menge kann sich selbst als Element haben. L sei die Liste aller Dinge in
Prof. Groves’ Uni-Tasche. Diese Liste L stellt eine Menge durch Aufzählung
dar:
L = {Lehrbuch, Stift, Vorlesungsnotizen, Hammer}.
(Der Hammer ist zum Kaputtschlagen von Handys, die während der Vorlesung klingeln.) Oft legt Prof. Groves auch die Liste in seine Tasche. Wir
müssen also L in
L = {Lehrbuch, Stift, Vorlesungsnotizen, Hammer, L}
abändern. Damit enthält die Menge L sich selbst.
(iii) Die Russelsche Antimonie
M sei die Menge aller Mengen, die sich selbst nicht enthalten. Frage: Enthält
M sich selbst, d. h. ist M ∈ M?
– Falls M ∈ M, gilt definitionsgemäß M 6∈ M.
– Falls M 6∈ M, gilt definitionsgemäß M ∈ M.
Damit führt die Existenz von M zu einem logischen Widerspruch.
Um solche Probleme zu vermeiden, brauchen wir eine subtilere Definition des
Begriffs “Menge”. Es handelt sich hier um die axiomatische Mengenlehre, die in
dieser Vorlesung nicht behandelt wird.
1.2 Funktionen
Definition
A und B seien Mengen. Eine Funktion oder Abbildung f : A → B (“ f von A
nach B”) ist eine Vorschrift, die jedem Element a ∈ A genau ein Element f (a) ∈ B
zuordnet.
9
1.2 Funktionen
A
B
a1
a2
f(a1)
f
f(a2)
f(a3)
a3
Die Menge A ist die
Urmenge von f
Die Menge B ist die
Zielmenge von f
Beispiele
1. Wir sind daran gewöhnt, Funktionen durch explizite Formeln zu definieren,
z. B.
f : R → R,
f ( x ) = sin x.
2. Wir brauchen jedoch nur die maßgebende Zuordnung anzugeben, z. B.
f : {1,3,5} → N,
f (1 ) = 3
f (3) = 4,
f (5) = 7.
Definitionen
f : A → B sei eine Funktion.
Das Element f (a) ∈ B heißt Bild oder (Funktions)wert von a ∈ A unter f .
Die Menge aller Funktionswerte von f , d. h.
R( f ) := { f (a) : a ∈ A},
heißt Bildmenge oder Wertebereich von f ; sie ist Teilmenge von B.
A
B
a1
a2
a3
f(a1)
f
f(a2)
f(a3)
R(f)
10
1.2 Funktionen
Beispiele
1. f : R → R, f ( x ) = sin x.
Es gilt:
R( f ) = {sin x : x ∈ R }
= [−1,1].
2. f : {1,3,5} → N,
f (1 ) = 3
f (3) = 4,
f (5) = 7.
Es gilt:
R( f ) = { f (1), f (3), f (5)}
= {3, 4, 7}.
Definition
f : A → B sei eine Funktion und C sei Teilmenge von A. Die Menge aller Funktionswerte von f , die aus Elementen von C stammen, d. h.
f [C ] := { f ( a) : a ∈ C }
heißt das Bild von C unter der Funktion f .
A
B
C
a1
a2
f(a1)
f
f[C]
f(a2)
11
1.2 Funktionen
Beispiele
1. f : R → R, f ( x ) = sin x.
Es gilt:
f ([0,π ]) = {sin x : x ∈ [0,π ]}
= [0,1].
2. f : {1,3,5} → N,
f (1 ) = 3
f (3) = 4,
f (5) = 7.
Es gilt:
f ({1,3}) = { f (1), f (3)}
= {3, 4}.
Definition
f : A → B sei eine Funktion und D sei Teilmenge von B. Die Menge aller Elemente
von A, deren Bilder unter f in D liegen, d. h.
f −1 [ D ] : = { a ∈ A : f ( a) ∈ D }
heißt das Urbild von D unter der Funktion f .
A
B
a1
a2
f(a1)
f
f -1[D]
D
f(a2)
Beispiele
1. f : R → R, f ( x ) = sin x.
Es gilt:
f −1 ([0,1]) = {[
x : sin x ∈ [0,1]}
=
[2nπ,(2n + 1)π ]
n ∈Z
12
1.2 Funktionen
2. f : {1,3,5} → N,
f (1 ) = 3
f (3) = 4,
f (5) = 7.
Es gilt:
f −1 ({77}) = ∅
Definitionen
Eine Funktion f : A → B heißt
(i) injektiv, falls
a1 6 = a2 ⇒ f ( a1 ) 6 = f ( a2 );
“a1 6= a2 impliziert f (a1 ) 6= f (a2 )”
(ii) surjektiv, falls
R( f ) = B;
(iii) bijektiv, falls sie injektiv und surjektiv ist.
Beispiele
1.
A
B
f
Diese Funktion ist weder injektiv noch surjektiv.
2.
A
B
f
Diese Funktion ist injektiv, aber nicht surjektiv.
13
1.2 Funktionen
3.
A
B
f
Diese Funktion ist injektiv und surjektiv, also bijektiv.
4. f 1 : R → R, f 1 ( x ) = sin x
Zielmenge (R)
Manche Elemente der Zielmenge werden mehr als
einmal erfasst. f 1 ist also
nicht injektiv.
Urmenge (R)
Nicht alle Elemente der Zielmenge werden
erfasst. f 1 ist also nicht surjektiv.
5. f 2 : R → [−1,1], f 2 ( x ) = sin x
Zielmenge ([−1,1])
. . . aber nicht injektiv.
Urmenge (R)
Jetzt werden alle Elemente der Zielmenge
erfasst. f 2 ist also surjektiv . . .
14
1.2 Funktionen
6. f 3 : [− π2 , π2 ] → [−1,1], f 3 ( x ) = sin x
Zielmenge ([−1,1])
Urmenge ([− π2 , π2 ])
Alle Elemente der Zielmenge werden genau einmal erfasst. f 3 ist also surjektiv und injektiv, also
bijektiv.
Beispiele 4–6 verdeutlichen, dass die Wahl der Mengen A und B ein wesentlicher
Teil der Definition einer Funktion f : A → B ist.
Bemerkung
Betrachten Sie eine bijektive Funktion f : A → B. Weil f injektiv ist, existiert zu
jedem Element b in der Bildmenge von f genau ein Element a in der Urmenge
von f , das auf b abgebildet wird. Weil f surjektiv ist, ist die Bildmenge von f
gleich B. Somit haben wir eine neue Funktion definiert:
Definition
f : A → B sei eine bijektive Funktion. Die Funktion f −1 : B → A,
f −1 (b) := a,
wobei a das eindeutige Element aus A mit
der Eigenschaft b = f (a) ist,
heißt Umkehrfunktion von f .
f
A
B
f -1
15
1.2 Funktionen
Bemerkung
f −1 : B → A ist ebenfalls bijektiv, und es gilt
f −1 ( f (a)) = a,
f ( f −1 (b)) = b,
a ∈ A,
b ∈ B.
Beispiel
Die Umkehrfunktion der bijektiven Funktion
f : R → R,
f ( x ) = 2x − 3
ist
f −1 : R → R,
f −1 (y ) =
weil
y = 2x − 3 ⇔ x =
y 3
+ ,
2 2
y 3
+ .
2 2
x=f -1(y)
y=f(x)
3/2
3/2
x
-3
y
-3
Geometrisch gesehen tauschen wir die Rollen der horizontalen und vertikalen
Achsen. Die Graphen von f und f −1 sind also durch eine Spiegelung an der Geraden y = x miteinander verwandt.
16
1.2 Funktionen
Definition
g : A → B und f : B → C seien Funktionen.
Die Funktion
f ◦ g : A → C,
↑
“ f nach g”
( f ◦ g)(a) = f ( g(a))
heißt Komposition von f und g.
A
C
B
g
f
f◦g
Proposition
Es seien g : A → B und f : B → C Funktionen.
1. Ist f ◦ g : A → C injektiv, so ist g : A → B injektiv.
2. Ist f ◦ g : A → C surjektiv, so ist f : B → C surjektiv.
Beweis
1. Wir wissen:
Aus ( f ◦ g)(a1 ) = ( f ◦ g)(a2 ) folgt a1 = a2 .
Wir müssen zeigen:
Aus g(a1 ) = g(a2 ) folgt a1 = a2 .
17
1.3 Geordnete Paare und Relationen
Es sei also g(a1 ) = g(a2 ). Dann ist f ( g(a1 )) = f ( g(a2 )), d.h. ( f ◦ g)(a1 ) =
( f ◦ g)(a2 ). Folglich gilt a1 = a2 .
2. Wir wissen:
Zu jedem c ∈ C existiert a ∈ A mit ( f ◦ g)(a) = c.
Wir müssen zeigen:
Zu jedem c ∈ C existiert b ∈ B mit f (b) = c.
Es sei also c ∈ C. Dann gibt es a ∈ A mit ( f ◦ g)(a) = c, d.h. f ( g(a)) = c.
Folglich hat b = g(a) die Eigenschaft f (b) = c.
1.3 Geordnete Paare und Relationen
Definition
A und B seien beliebige Mengen.
Ein Paar (a,b) mit a ∈ A und b ∈ B heißt geordnetes Paar mit a als erster
Komponente und b als zweiter Komponente.
Die Menge aller solchen geordneten Paare
A × B := {(a,b) : a ∈ A, b ∈ B}
↑
“A kreuz B”
heißt Produktmenge oder kartesisches Produkt von A und B.
Beispiel
Die Lage eines Punktes P der Ebene läßt sich durch ein geordnetes Paar reeller
Zahlen beschreiben:
18
1.3 Geordnete Paare und Relationen
P
y
P( x,y)
ր տ
horizontale
vertikale
Koordinate Koordinate
x
Damit ist die Ebene die Menge aller geordneten Paare reeller Zahlen, d.h. die
Menge R × R. Statt R × R schreibt man meist R2 .
Bemerkung
Diese Konstruktion läßt sich verallgemeinern.
A1 , . . . ,An seien n beliebige Mengen. Die Menge
A1 × A2 × . . . × An = {(a1 , . . . ,an ) : a1 ∈ A1 , . . . ,an ∈ An }
aller geordneten n-Tupel (a1 , . . . ,an ) mit ai ∈ Ai , i = 1, . . . ,n heißt Produktmenge
oder kartesisches Produkt von A1 , . . . , An .
Definition
Es sei f : A → B eine Abbildung. Der Graph von f ist die Teilmenge
G f := {(a, f (a)) : a ∈ A}
von A × B.
19
1.3 Geordnete Paare und Relationen
Beispiele
1. f : R → R, f ( x ) = sin x.
G f = {( x, sin x ) : x ∈ R } können wir als Teilmenge von R2 gut visualisieren:
f(x)
Dies ist der Graph von f .
x
2. f : {1,3,5} → N,
f (1 ) = 3
f (3) = 4,
f (5) = 7.
Der Graph von f ist die Teilmenge {(1,3),(3,4),(5,7)} von
{1,3,5} × N = {(1,1),(1,2),(1,3), . . . ,(3,1),(3,2),(3,3), . . . ,(5,1),(5,2),(5,3), . . . }.
Bemerkung
Wir definierten eine Funktion f : A → B als Vorschrift, die jedem Element a ∈ A
genau ein Element f (a) ∈ B zuordnet. Der Graph von f ist lediglich die Menge
dieser Zuordnungen:
(a,b) ∈ G f
bedeutet
b ist das Element von B, das a zugordnet wird,
d.h. b = f (a)
f wird also vollständig von G f wiedergegeben, und somit können wir f durch
seinen Graphen definieren.
20
1.3 Geordnete Paare und Relationen
Definitionen
A und B seien Mengen.
1. Eine Relation R zwischen A und B ist eine Teilmenge der Produktmenge
A × B.
Oft schreiben wir aRb statt (a,b) ∈ R und sagen: ‘a steht in Relation zu b’.
2. Die Menge A wird als Quellmenge oder Vorbereich der Relation bezeichnet. Die Menge B ist die Zielmenge oder der Nachbereich der Relation.
Beispiel
Es seien M und F die Mengen aller Männer bzw. aller Frauen. Die Teilmenge
{(m, f ) ∈ R : m ist der Ehemann von f }
von M × F ist eine Relation zwischen M und F.
Es gilt z.B.
(Prince Charles, Camilla Parker-Bowles) ∈ R,
(Donald Trump, Hillary Clinton) 6∈ R.
Definitionen
Eine Relation R zwischen zweier Mengen A und B heißt
1. linkstotal, falls es zu jedem a ∈ A ein b ∈ B mit aRb gibt,
2. rechtstotal, falls es zu jedem b ∈ B ein a ∈ A mit aRb gibt,
3. linkseindeutig, falls aus a1 Rb und a2 Rb die Gleichheit a1 = a2 folgt,
4. rechtseindeutig, falls aus aRb1 und aRb2 die Gleichheit b1 = b2 folgt,
21
1.3 Geordnete Paare und Relationen
Beispiele
Es seien A = { a1 ,a2 ,a3 }, B = {b1 ,b2 ,b3 ,b4 }.
1.
A
B
b1
a1
a2
b4
a3
b3
b2
Die Relation R = {(a1 ,b1 ),(a2 ,b3 ),(a3 ,b4 )} ist linkstotal und links- und rechtseindeutig, aber nicht rechtstotal.
2.
A
B
a1
a2
a3
b1
b4
b3
b2
Die Relation R = {(a1 ,b1 ),(a1 ,b2 ),(a3 ,b2 )} ist weder linkstotal, rechtstotal,
linkseindeutig noch rechtseindeutig.
Bemerkungen
Es seien A und B Mengen.
Eine Funktion f : A → B ist eine linkstotale, rechtseindeutige Relation zwischen A
und B. f ist genau dann injektiv, wenn die Relation linkseindeutig ist, und genau
dann surjektiv, wenn die Relation rechtstotal ist.
Definitionen
Eine Relation zwischen einer Menge A und sich selbst heißt homogen. Wir sprechen in diesem Fall von ‘einer Relation auf einer Menge M’. Homogene Relationen werden häufig mit dem Symbol ∼ bezeichnet und heißen
22
1.3 Geordnete Paare und Relationen
1. reflexiv, falls a ∼ a für alle a ∈ A,
2. konnex, falls für alle a,b ∈ A mit a 6= b entweder a ∼ b oder b ∼ a gilt,
3. symmetrisch, falls a ∼ b ⇒ b ∼ a,
4. asymmetrisch, falls a ∼ b ⇒ b 6∼ a,
5. antisymmetrisch, falls a ∼ b und b ∼ a ⇒ a = b,
6. transitiv, falls a ∼ b und b ∼ c ⇒ a ∼ c.
Beispiele
Die Tabelle zeigt einige homogene Relationen auf N.
x ∼ y, falls
reflexiv?
symmetrisch?
transitiv?
x≤y
ja (x ≤ x)
nein (3 ≤ 4, 4 6≤ 3)
ja (x ≤ y, y ≤ z ⇒ x ≤ z)
x |y
ja (x | x)
nein (3|6, 66 |3)
ja (x |y, y|z ⇒ x |z)
x+y=7
nein (2x 6= 7
für alle x ∈ N)
ja
nein (3 + 4 = 7 und 4 + 3 = 7,
3 + 3 = 6)
x ∼ y, falls
konnex?
asymmetrisch?
antisymmetrisch?
x≤y
ja
nein (reflexiv)
ja (x ≤ y, y ≤ x ⇒ x = y)
x |y
nein (36 |5, 56 |3)
ja
ja (x |y, y| x ⇒ x |y)
x+y=7
nein (3 + 2 6= 7,
2 + 3 6= 7)
nein (symmetrisch)
nein (3 + 4 = 7, 4 + 3 = 7)
Definition
Eine Relation ∼ auf einer Menge M heißt Äquivalenzrelation, falls sie reflexiv,
symmetrisch und transitiv ist.
23
1.3 Geordnete Paare und Relationen
Beispiel
Es sei M die Menge aller Bücher in der Bibliothek. Die Relation
a∼b
⇔
a und b haben dieselbe ISBN
ist eine Äquivalenzrelation auf M:
Definition
Es sei n ∈ N. Zwei Zahlen a, b ∈ Z heißen kongruent modulo n, falls n|(a − b).
In diesem Fall schreiben wir
a ≡ b (mod n).
Proposition
Es sei n ∈ N. Die Formel
a∼b
⇔
a ≡ b (mod n)
definiert eine Äquivalenzrelation auf Z.
Beweis
∼ ist reflexiv: a ∼ a für alle a ∈ Z, denn a − a = 0 und n|0.
24
1.3 Geordnete Paare und Relationen
∼ ist symmetrisch: Es gelte a ∼ b, so dass n|(a − b). Folglich gilt auch
n|(b − a), d.h. b ∼ a.
∼ ist transitiv: Es gelten a ∼ b und b ∼ c, so dass n|(a − b) und n|(b − c).
Folglich gilt es ganze Zahlen q1 und q2 derart, dass a − b = q1 n und b − c =
q2 n. Es ist also a − c = (a − b) + (b − c) = (q1 + q2 )n und n|(a − c), d.h. a ∼ c.
Definition
Es seien ∼ eine Äquivalenzrelation auf einer Menge M und m ∈ M.
Die Teilmenge
[m] := { x ∈ M : x ∼ m}
heißt die Äquivalenzklasse von m in M.
Lemma
Es sei ∼ eine Äquivalenzrelation auf eine Menge M. Dann bilden die Äquivalenzklassen von ∼ eine Partition von M, d.h.
1. für alle x, y ∈ M gilt entweder [ x ] ∩ [y] = ∅ oder [ x ] = [y],
2.
S
[ x ] = M.
x∈ M
Beweis
1. Es sei [ x ] ∩ [y] 6= ∅. Wähle z ∈ [ x ] ∩ [y].
Es gilt nun
a ∈ [ x] ⇒ a ∼ x
⇒a∼z
⇒a∼y
⇒ a ∈ [ y ],
(denn a ∼ x und x ∼ z)
(denn a ∼ z und z ∼ y)
so dass [ x ] ⊆ [y]. Dasgleiche Argument ergibt [y] ⊆ [ x ], so dass [ x ] = [y] ist.
25
1.3 Geordnete Paare und Relationen
2. Wähle m ∈ M. Aus m ∼ m folgt m ∈ [m] und daher
m ∈ [m] ⊆
so dass M ⊆
S
[
[ x ]. Definitionsgemäß gilt
x∈ M
[ x ],
x∈ M
S
x∈ M
[ x ] ⊆ M.
Bemerkung
Insbesondere folgt [ x ] = [y] aus x ∼ y.
Beispiele
1. Es sei M die Menge aller Bücher in der Bibliothek. Die Äquivalenzklassen
der Äquivalenzrelation
a∼b
⇔
a und b haben dieselbe ISBN
bilden eine Partition von M:
2. Es seien n ∈ N und ∼ die Äquivalenzrelation
a∼b
⇔
a ≡ b (mod n)
auf Z.
Um die Äquivalenzklassen zu bestimmen, brauchen wir das folgende Ergebnis, das später bewiesen wird:
26
1.3 Geordnete Paare und Relationen
Zu jedem a ∈ Z gibt es eindeutige Zahlen qa ∈ Z (den Quotienten) und
r a ∈ {0, . . . ,n − 1} (den Rest) derart, dass
a = qa n + ra .
Aus
a − x = (q a − q x )n + r a − r x
folgt nun
a∼x
so dass
⇔
ra = rx ,
[ x ] = { a ∈ Z : r a = r x }.
Es gibt also n verschiedene Äquivalenzklassen, nämlich
[0] = {0, n, 2n, . . . } ∪ {−n, − 2n, . . . },
[1] = {1, n + 1, 2n + 1, . . .} ∪ {−n + 1, − 2n + 1, . . .},
[2] = {2,n + 2,2n + 2, . . .} ∪ {−n + 2, − 2n + 2, . . .},
..
.
[n − 1] = {n − 1,2n − 1,4n − 1, . . .} ∪ {−1, − 1 − n, . . . },
und diese bilden eine Partition von Z:
Z=
n[
−1
[i ],
i =0
[i ] ∩ [ j] = ∅ für i 6= j.
Lemma
Es sei { Xi }i ∈ I eine Partition einer Menge X, d.h.
[
Xi = X,
i∈ I
Xi ∩ X j = ∅ für i 6= j.
Dann definiert die Formel
a∼b
⇔
a, b ∈ Xi ⋆ für irgendein i ⋆ ∈ I
eine Äquivalenzrelation auf X, deren Äquivalenzklassen die Mengen Xi , i ∈ I
sind.
Ist ferner ≈ eine weitere Äquivalenzrelation auf X, deren Äquivalenzklassen genau die Mengen Xi , i ∈ I sind, so stimmt ≈ mit ∼ überein.
27
1.3 Geordnete Paare und Relationen
Definition
Eine Relation auf einer Menge M heißt partielle Ordnung, falls sie reflexiv,
antisymmetrisch und transitiv ist. Sie ist eine Totalordnung, falls sie auch konnex
ist.
Bemerkung
Für eine Ordnung schreiben wir oft a ≺ b, falls a b aber a 6= b.
Beispiele
1. Die Relation
ab
⇔
a|b
ist eine partielle Ordnung aber keine Totalordnung auf N.
2. Die Relation
ab
⇔
ist eine Totalordnung auf R.
a≤b
3. Die Relation , wobei
(a1 , . . . ,an ) ≺ (b1 , . . . ,bn ), falls entweder a1 < b1
oder a1 = b1 und a2 < b2
..
.
oder a1 = b1 , . . . , an−1 = bn−1 und an < bn ,
definiert eine Totalordnung auf N n .
Im Falle n = 4 gilt z.B.
(1,2,3,5) ≺ (1,2,4,3), denn 3 < 4,
(1,7,9,11) ≺ (1,7,9,14), denn 11 < 14.
4. Auf der Menge aller Ketten von natürlichen Zahlen wird eine Totalordnung
durch die Regel
a1 a2 . . . am ≺ b1 b2 . . . bn , falls entweder (a1 , . . . ,at ) ≺ (b1 , . . . ,bt )
order (a1 , . . . , at ) = (b1 , . . . , bt ) und m < n
28
1.4
Wohlordnung und Induktion
definiert, wobei t = min(m,n).
Schreiben wir a, . . . , z statt 1, . . . , 26, so erhalten wir die lexikographische
Ordnung: Es gilt z.B.
zumuten ≺ Zumutung
faulen ≺ faulenzen
1.4 Wohlordnung und Induktion
Definition
Es seien (X, ) eine geordnete Menge und Y eine Teilmenge von X.
1. Ein Element M ∈ X heißt obere Schranke für Y, falls y M für alle y ∈ Y.
Liegt M in Y, so heißt sie größtes Element von Y.
2. Ein Element M ∈ Y heißt maximales Element von Y, falls
y ∈ Y mit y M
⇒
y = M.
Es gelten die entsprechenden Definitionen für untere Schranken, kleinste Elemente und minimale Elemente.
Bemerkungen
1. Falls Y eine größtes (kleinstes) Element besitzt, so ist es eindeutig.
Es seien nämlich M1 , M2 größte (kleinste) Elemente von Y. Die Relationen
y M1 , y M2
(y M1 , y M2 )
für alle y ∈ Y gelten insbesondere für y = M1 und y = M2 , so dass M1 M2
und M2 M1 , und folglich M1 = M2 .
2. Ein größtes (kleinstes) Element für Y ist auch ein maximales (minimales)
Element von Y. Ein maximales (minimales) Element von Y ist dagegen nicht
notwendigerweise ein größtes (kleinstes) Element von Y. Die Begriffe stimmen aber miteinander überein, falls eine Totalordnung ist.
29
1.4
Wohlordnung und Induktion
Beispiele
1. Betrachte die geordnete Menge (N, ), wobei
nm
⇔
n|m.
Die Teilmenge {1,2,3,4,6} von N hat
die oberen Schranken 12, 24, 36, . . . .
ein kleinstes Element (1),
kein größtes Element,
die maximale Elemente 4 und 6,
2. Betrachte die total geordnete Menge (R, ≤). Die Teilmenge (0,1] von R hat
die untere Schranke m für alle m ≤ 0,
kein kleinstes Element, denn aus der Existenz eines kleinsten Elements
m ∈ (0,1] folgt der Widerspruch m2 ∈ (0,1] aber m2 < m,
das größte Element 1.
Dieselbe Schlüsse gelten für (0,1) ∩ Q als Teilmenge von (Q, ≤).
Definition
Eine total geordnete Menge (X, ) heißt wohlgeordnet, falls jede nichtleere Teilmenge von X ein kleinstes Element hat.
Beispiele
1. (R, ≤) und (Q, ≤) sind nicht wohlgeordnet (die Teilmenge (0,1) bzw. (0,1) ∩
Q hat kein kleinstes Element).
2. (N, ≤) ist wohlgeordnet. Dies ist das Wohlordnungsaxiom der natürlichen
Zahlen.
30
1.4
Wohlordnung und Induktion
3. (Z, ≤) ist nicht wohlgeordnet (die Teilmenge {. . . , −3, − 2, − 1} hat kein
kleinstes Element). Versehen mit der Totalordnung
0 ≺ 1 ≺ −1 ≺ 2 ≺ −2 ≺ −3 ≺ · · ·
ist sie jedoch wohlgeordnet.
Das dritte Beispiel verdeutlicht, dass die Wahl der Ordnung wichtig ist.
Satz (Wohlordnungssatz)
Zu jeder nichtleeren Menge gibt es eine Totalordnung, bezüglich dessen sie wohlgeordnet ist.
Dieser Satz wird aus dem folgenden Auswahlaxiom der Mengenlehre hergeleitet:
Es sei { Mi }i ∈ I eine Menge nichtleerer Mengen. Dann gibt es eine Menge M,
die aus jeder der Mengen Mi , i ∈ I genau ein Element und sonst keine weiteren Elemente enthält.
Es gibt eine weitere Folgerung aus dem Auswahlaxiom, die für Ordnungen relevant ist.
Satz (Lemma von Zorn)
Es sei X eine nichtleere, geordnete Menge mit der Eigenschaft, dass jede total
geordnete Teilmenge von X eine obere Schranke besitzt. Dann hat X (mindestens)
ein maximales Element.
Bemerkung
Der Wohlordnungssatz, das Auswahlaxiom und das Lemma von Zorn sind logisch äquivalent: Aus je einem lassen sich die anderen beiden folgern.
31
1.4
Wohlordnung und Induktion
Satz (transfinite Induktion)
Es sei ( I, ) eine wohlgeordnete Menge und P(i ), i ∈ I eine Aussageform mit der
folgende Eigenschaft:
Ist P( j) für alle j ≺ k wahr, so ist P(k) wahr.
Dann ist P(i ) wahr für jedes i ∈ I.
Beweis
Es sei P(i ) falsch für irgendein i ∈ I. Da ( I, ) wohlgeordnet ist, gibt ein kleinstes
solches Element i ⋆ .
Nun ist P( j) ist wahr für alle j ≺ i ⋆ . Folglich ist P(i ⋆ ) wahr, und dies ist ein
Widerspruch.
Bemerkung
Im Sonderfall, dass ( I, ) gleich (N, ≤) ist, handelt es sich um das Prinzip der
starken Induktion.
Beispiel
Die durch das Rekursionsschema
f 1 = 1,
f 2 = 1,
f n = f n−1 + f n−2 , n = 3,4, . . .
definierte Folge { f n } heißt Fibonacci-Folge. Zeigen Sie, dass
n−3
3
fn ≥
, n = 1,2, . . . .
2
Lösung
Es sei P(n) die Aussageform
n−3
3
fn ≥
2
für n ∈ N. Wir zeigen, dass P(1), P(2), . . . , P(k − 1) ⇒ P(k) für alle k ∈ N.
32
1.5 Abzählbarkeit
Die Aussagen P(1) und P(1) ⇒ P(2) werden gesondert verifiziert. Dies ist der
Induktionsanfang. Es gilt
1−3
2−3
3
4
2
3
1 = f1 ≥
= ,
= .
1 = f2 ≥
2
9
2
3
(Da P(1) wahr ist, ist P(1) ⇒ P(2) äquivalent zu P(2).)
Nun sei k ≥ 3. Im Induktionsschluss beweisen wir, dass die Induktionsvoraussetzung
j−3
3
P( j) : f j ≥
,
j = 1, . . . , k − 1
(1 )
2
die Induktionsbehauptung
k−3
3
P(k) : f k ≥
2
impliziert.
Es gilt nun
f k = f k−1 + f k−2
k−4 k−5
3
3
+
≥
2
2
k−5 3
3
=
+1
(wegen (1))
2
2
k−5 5
3
=
2
2
k−5 3
9
≥
(denn 25 > 94 )
2
4
k−3
3
.
=
2
1.5 Abzählbarkeit
Definition
Eine nichtleere Menge M heißt endlich, falls es eine natürliche Zahl n und eine
bijektive Funktion f : N n → M gibt, wobei
N n = { m ∈ N : m ≤ n}
ist. In diesem Fall hat M n Elemente.
33
1.5 Abzählbarkeit
Bemerkung
Eine endliche Menge M kann nicht gleichzeitig n1 und n2 Elemente mit n1 6= n2
haben. In diesem Fall gäbe es Bijektionen f 1 : N n1 → M und f 2 : N n2 → M, so dass
g := f 1−1 ◦ f 2 : N n2 → N n1 und g−1 : N n1 → N n2 Bijektionen wären. Die Existenz
solcher Funktionen schließt aber das folgende Lemma aus.
Lemma (Schubfachprinzip)
Es seien m und n natürliche Zahlen mit m < n. Dann gibt es keine Injektion N n →
Nm .
Beweis
Es sei
S = {n ∈ N: Es existieren eine natürliche Zahl
m < n und eine Injektion f : N n → N m }.
Falls S 6= ∅ ist, hat S dem Wohlordnungsaxiom zufolge ein kleinstes Element k.
Es existieren also eine natürliche Zahl ℓ < k und eine Injektion g : N k → N ℓ .
Es ist ℓ 6= 1, denn keine Funktion N k → N1 = {1} ist eine Injektion für k > 1.
Damit ist ℓ > 1, so dass ℓ = q + 1 und daher k = p + 1 für igendwelche natürlichen
Zahlen p, q sind.
Bemerke:
N k = N p ∪ { p + 1},
N ℓ = N q ∪ { q + 1}.
Falls q + 1 nicht in g[N p ] ist, ist die durch die Formel
h ( x ) = g ( x ),
definierte Funktion h : N p → N q injektiv.
x ∈ Np
Falls q + 1 in g[N p ] ist, existiert x1 ∈ N p mit g( x1 ) = q + 1. Folglich ist
g( p + 1) 6= q + 1. Damit ist die durch die Formel
g ( x ),
x 6 = x1 ,
h( x ) =
g ( p + 1 ), x = x 1
definierte Funktion h : N p → N q injektiv.
In beiden Fällen haben wir eine Injektion h : N p → N q mit q < p und p < k konstruiert. Dies widerspricht aber der Definition von k.
34
1.5 Abzählbarkeit
Bemerkung
Das Schubfachprinzip wird oft folgendermaßen formuliert:
Falls man n Objekte in m < n Schubfächer einteilen möchte, gibt es
mindestens ein Schubfach, in dem mehr als ein Objekt landet.
Mit anderen Worten existiert keine Injektion f : M → S, wobei M die Menge der
Objekte und S die Menge der Schubfächer ist. Definitionsgemäß existieren Bijektionen f 1 : N n → M und f 2 : N m → S. Die Existenz einer Injektion f : M → S
impliziert, dass f 2−1 ◦ f ◦ f 1 : N n → N m injektiv ist. Dies widerspricht dem obigen
Lemma.
Definitionen
1. Die leere Menge betrachten wir als endlich mit 0 Elementen.
2. Eine nichtleere Menge M ist unendlich, falls sie nicht endlich ist.
Lemma
Eine nichtleere Menge M ist unendlich, falls es eine Injektion f : N → M gibt.
Beweis
Nehmen wir an, M ist endlich. Dann gibt es eine natürliche Zahl n und eine Bijektion f n : N n → M. Es sei i : N n+1 → N die Inklusion
i ( x ) = x,
x = 1, . . . ,n + 1.
Damit ist h := f n−1 ◦ f ◦ i : N n+1 → N n eine Injektion. Dies widerspricht aber dem
Schubfachprinzip.
.
35
1.5 Abzählbarkeit
Definitionen
1. Eine nichtleere Menge M heißt abzählbar unendlich, falls es eine bijektive
Funktion f : N → M gibt.
2. Eine endliche oder abzählbar unendliche Menge heißt abzählbar.
3. Eine nicht abzählbare Menge heißt überabzählbar.
Beispiele
1. Die Menge Z ist abzählbar unendlich. So zählt man ihre Elemente ab:
Zielmenge (Z )
Urmenge (N )
0 1 −1 2 −2 3 −3 · · ·
↑ ↑ ↑ ↑ ↑ ↑ ↑
1 2 3 4 5 6 7 ···
2. Die Produktmenge
N × N = {(n1 ,n2 ) : n1 ,n2 ∈ N }
ist abzählbar unendlich. So zählt man ihre Elemente ab:
1
(1, 1)
3
2
(1, 2)
5
(2, 1)
(2, 2)
6
9
(3, 1)
4
(1, 3)
7
(1, 4)
···
8
(2, 3)
(2, 4)
(3, 2)
(3, 3)
(3, 4)
(4, 2)
(4, 3)
(4, 4)
10
···
(4, 1)
Zeichenerklärung: durchgezogene Pfeile: N → Z
gestrichelte Pfeile: Abzählungsrichtung
36
1.5 Abzählbarkeit
3. Die Menge aller positiven rationalen Zahlen ist abzählbar unendlich. So zählt
man ihre Elemente ab:
1
1
1
2
1
2
1
3
1
4
1
5
2
3
2
4
2
5
3
2
3
3
3
4
3
5
4
2
4
3
4
4
4
5
5
2
5
3
5
4
5
5
2
2
5
3
1
···
7
3
2
1
10
6
4
8
9
4
1
11
5
1
..
.
Zeichenerklärung: durchgezogene Pfeile: N → Q
gestrichelte Pfeile: Abzählungsrichtung
4. Die Menge R ist nicht abzählbar. Sie ist unendlich, da die Inklusion N → R
offensichtlich injektiv ist. Dass sie nicht abzählbar unendlich ist, beweisen wir
durch Widerspruch.
Nehmen wir an, R ist abzählbar unendlich. Es existiert also eine bijektive Funktion f : N → R. Wir bezeichnen f (n) mit Nn ,d1n d2n d3n . . ., wobei Nn eine ganze Zahl
ist und d1n ,d2n ,d3n , . . . ∈ {0,1, . . . ,9} sind:
Urmenge (N )
1
2
3
..
.
Zielmenge (R )
→
N1 ,d11 d21 d31 . . .
→
N3 ,d13 d23 d33 . . .
..
.
→
N2 , d12 d22 d32 . . .
(Hier benutzen wir die Dezimalschreibweise für reelle Zahlen, die Nichteindeutigkeiten wie 0,999 . . . = 1,000 . . . enthält.)
37
1.5 Abzählbarkeit
j
D j sei eine ganze Zahl zwischen 1 und 8 mit D j 6= d j . Betrachte nun die reelle Zahl
0,D1 D2 D3 . . .
Diese Zahl ist nicht gleich f (1), da D1 6= d11 ist.
Sie ist ebenfalls nicht gleich f (2), da D2 6= d22 ist.
j
Sie ist tatsächlich nicht gleich f ( j) für jedes j ∈ N, da D j 6= d j ist.
Sie ist also nicht Element der Bildmenge von f : Dies widerspricht der Annahme,
dass f surjektiv ist.
38
2 Algebraische Strukturen
2 Algebraische Strukturen
2.1 Verknüpfungen, Gruppen und Körper
Definition
Es sei X eine nichtleere Menge. Eine (binäre) Verknüpfung · auf X ist eine Abbildung X × X → X.
In der Regel verwenden wir die Notation x1 · x2 an Stelle von ·( x1 ,x2 ).
Beispiele
1. Addition und Multiplikation sind Verknüpfungen auf der Menge N: Für
alle n1 , n2 ∈ N sind n1 + n2 und n1 .n2 ebenfalls Elemente in N. Sie sind
auch Verknüpfungen auf den Mengen Z, Q und R.
2. Es sei M eine nichtleere Menge und X die Menge aller Funktionen M → M.
Komposition ist eine Verknüfung auf X: Für alle Funktionen f , g : M → M
ist f ◦ g ebenfalls eine Funktion M → M.
Definitionen
Es sei X eine nichtleere Menge. Eine Verknüpfung · auf X heißt
(i) assoziativ, falls (a · b) · c = a · (b · c) für alle a,b,c ∈ X,
(ii) kommutativ, falls a · b = b · a für alle a, b ∈ X.
Beispiele
1. Addition und Multiplikation sind assoziative, kommutative Verknüpfungen auf N, Z, Q und R.
2. Es sei X die Menge aller Funktion R → R.
39
2.1 Verknüpfungen, Gruppen und Körper
Es seien f , g, h ∈ M. Wegen der Definition ( F1 ◦ F2 )(y) = F1 ( F2 (y)) gilt
(( f ◦ g) ◦ h)( x ) = ( f ◦ g)(h( x )) = f ( g(h( x ))
und
so dass
( f ◦ ( g ◦ h))( x ) = f (( g ◦ h)( x )) = f ( g(h( x )),
(( f ◦ g) ◦ h)( x ) = ( f ◦ ( g ◦ h))( x )
für alle x ∈ X. Folglich gilt (( f ◦ g) ◦ h = f ◦ ( g ◦ h), d.h. ◦ ist assoziativ.
Es sei f ( x ) = sin x und g( x ) = 2x. Dann ist f ( g( π2 )) = sin(π ) = 0 aber
g( f ( π2 )) = 2 sin( π2 ) = 2. Folglich ist f ◦ g 6= g ◦ f , d.h. ◦ ist nicht kommutativ.
Definition
Eine Gruppe ist eine mit einer Verknüpfung · versehene nichtleere Menge X, die
die folgenden Eigenschaften hat.
• Die Verknüpfung · ist assoziativ.
• Es existiert ein Element i ∈ X derart,
dass x · i = i · x = x für alle x ∈ X.
• Zu jedem x ∈ X existiert ein Element
x −1 ∈ X derart, dass x · x −1 = x −1 · x = i.
(Assoziativgesetz)
(Existenz eines
neutralen Elements)
(Existenz von Inversen)
Ist die Verknüpfung · auch kommutativ, so handelt es sich um eine Abelsche
Gruppe.
In der Regel verwenden wir die Schreibweise (X,·) für eine Gruppe.
Beispiele
1. (Z,+) ist eine Abelsche Gruppe, wobei
das neutrale Element 0 ist, denn 0 + x = x + 0 = x für alle x ∈ N,
das inverse Element zu x die Zahl − x ist, denn x + (− x ) = (− x ) + x = 0
für alle x ∈ N.
(Q,+) und (R,+) sind ebenfalls Abelsche Gruppen.
40
2.1 Verknüpfungen, Gruppen und Körper
2. (Q \ {0}, .) ist eine Abelsche Gruppe, wobei
das neutrale Element 1 ist, denn 1.x = x.1 = x für alle x ∈ Q \ {0},
das inverse Element zu x die Zahl
x ∈ Q \ {0}.
1
x
ist, denn x. 1x = x1 .x = 1 für alle
(R \ {0},.) ist ebenfalls eine Abelsche Gruppe.
3. Es sei X eine nichtleere Menge. Die Menge aller Bijektionen X → X bildet
eine Gruppe bezüglich Komposition von Funktionen:
Das neutrale Element ist die Identitätsfunktion I : X → X mit I ( x ) = x
für alle x ∈ X, denn f ◦ I = I ◦ f = f für jede Bijektion f : X → X.
Das Inverse zu f : X → X ist die Umkehrfunktion f −1 : X → X, denn
f ◦ f −1 = f −1 ◦ f = I für jede Bijektion f : X → X.
Ist X eine endliche Menge, so nennen wir diese Gruppe die symmetrische
Gruppe S(X ) von X und bezeichnen ihre Elemente als Permutationen. Für
eine Permutation σ der Menge { x1 ,x2 , . . . ,xn } verwendet man oft die Notation
x1
x2 · · · x n
,
σ ( x1 ) σ ( x2 ) · · · σ ( x n )
so dass z.B.
1 2 3
1 3 2
die Permutation 1 7→ 1, 2 7→ 3, 3 7→ 2 der Menge {1,2,3} bezeichnet. Diese
Permutation können wir auch in der Zykeldarstellung als (1)(23) oder einfach (23) schreiben. Die Notation S({1, . . . ,n}) kurzen wir oft auf Sn ab, so
dass z.B.
S3 = {i,(123),(321),(23),(13),(12)}.
4. Eine Symmetrie einer ebenen geometrischen Figur ist eine winkel- und abstandstreue Bijektion der Ebene auf sich selbst, die diese Figur ebenfalls auf
sich selbst abbildet.
Die Abbildung zeigt die sechs Symmetrien eines gleichseitigen Dreiecks:
Die Identität I, Rotationen R±2π/3 durch ± 2π
3 und Reflektionen T1 , T2 , T3
an den Winkelhalbierenden.
41
2.1 Verknüpfungen, Gruppen und Körper
1
2
I
R2π/3
1
2
T1
3
3
2
2
R−2π/3
3
1
T2
1
3
2
2
3
1
T3 2
3
1
1
3
Die Menge der Symmetrien oder Symmetriemenge des gleichseitigen Dreiecks ist eine Gruppe bezüglich Kompositionen von Funktionen:
Das neutrale Element ist I.
−1
1
−1
−1
Es gilt I −1 = I, R2π/3
= R−2π/3 , R−
−2π/3 = R2π/3 , T1 = T1 , T2 = T2 und
T3−1 = T3 .
Die Gruppe ist jedoch nicht Abelsch, denn T1 R2π/3 = T2 aber R2π/3 T1 = T3 .
Wir können die Symmetrien auch als Permutationen der Menge {1,2,3,}
darstellen:
R2π/3 = (123),
R−2π/3 = (321),
T1 = (23),
T2 = (13),
T3 = (12).
Somit können wir die Symmetriegroupe eines gleichseitigen Dreiecks mit
der symmetrischen Gruppe S3 identifizieren.
42
2.1 Verknüpfungen, Gruppen und Körper
5. Es seien m, n ∈ N. Eine (m × n) (reelle) Matrix ist ein mn-Tupel
A = (aij ) i=1,...,m, reeller Zahlen. Man schreibt
j =1,...,n


a11 a12 · · · a1n 
 a21 a22 · · · a2n  



A = (aij ) =  ..
..  m Zeilen,
..
 .
. 
.


am1 am2 · · · amn 
|
{z
}
n Spalten

d.h. man ordnet das mn-Tupel (aij ) i=1,...,m, in Form eines rechteckigen Schej =1,...,n
mas mit m Zeilen und n Spalten. Der Koeffizient aij steht in der i-ten Zeile
und der j-ten Spalte.
Die Menge R m×n der (m × n) reellen Matrizen ist eine Abelsche Gruppe
bezüglich punktweise Addition der Koeffizienten:
(aij ) + (bij ) := (aij + bij ),
denn
das neutrale Element ist die Nullmatrix (0), deren Koeffizienten alle
Null sind,
das inverse Element zu (aij ) ist die Matrix (− aij ).
Proposition
Es sei (X,·) eine Gruppe.
1. Das neutrale Element i ist eindeutig.
2. Es sei x ∈ X. Das inverse Element zu x ist eindeutig.
Beweis
1. Es seien i1 und i2 neutrale Elemente, so dass insbesondere
x = x · i1 ,
y = i2 · y
für alle x, y ∈ X. Insbesondere gilt dies für x = i2 und y = i1 , sodass
Folglich ist i2 = i1 .
i2 = i2 · i1 ,
i1 = i2 · i1 .
43
2.1 Verknüpfungen, Gruppen und Körper
2. Es seien y und z zwei inverse Elemente zu x, sodass
y · x = x · y = i,
z · x = x · z = i.
Nun gilt
y = i · y = (z · x ) · y = z · ( x · y) = z · i = z.
Von besondere Bedeutung sind Abbildungen zwischen Gruppen, die mit der
Gruppenstruktur verträglich sind.
Definition
Es seien (G,· G ) und ( H, · H ) Gruppen. Eine Funktion f : G → H mit der Eigenschaft
f ( x · G y) = f ( x ) · H f (y)
für alle x,y ∈ G
heißt (Gruppen-)homomorphismus. Ist f zusätzlich eine Bijektion, so heißt sie
(Gruppen-)isomorphismus.
Proposition
Es seien (G,· G ) und ( H, · H ) Gruppen und f : G → H ein Gruppenhomomorphismums. Dann gilt
(i) f (i G ) = i H , wobei i G und i H die neutrale Elemente von G und H sind,
(ii) f ( x −1 ) = f ( x )−1 für alle x ∈ G.
Beweis
Nun schreiben wir · G und · H als ·. Aus dem Kontext wir klar, welcher gemeint
ist.
(i) Es gilt
d.h.
f (i G · i G ) = f (i G ) · f (i G ),
| {z }
= iG
f (i G ) = f (i G ) · f (i G ).
44
2.1 Verknüpfungen, Gruppen und Körper
Da das einzeige Element a einer (beliebigen) Gruppe mit der Eigenschaft
a · a = a das neutrale Element ist, gilt nun
f (i G ) = i H .
(ii) Es gilt
und
i H = f (i G ) = f ( x − 1 · x ) = f ( x − 1 ) · f ( x )
i H = f (i G ) = f ( x · x − 1 ) = f ( x ) · f ( x − 1 ).
Die Gleichheit f ( x )−1 = f ( x −1 ) folgt nun aus der Eindeutigkeit von Inversen.
Beispiele
1. Die Exponentialfunktion exp : (R,·) → (R \ {0},.) ist wegen der Formel
exp( x + y) = exp( x ). exp(y),
x,y ∈ R
ein Gruppenhomomorphismus.
2. In einem früheren Beispiel haben wir die Symmetriegruppe SD des Dreiecks
mit der symmetrischen Gruppe S3 identifiziert. Diese Identifizierung lässt
sich formal durch die Abbildung S : SD → S3 mit
S( I ) = (),
S( R2π/3 ) = (123),
S(T1 ) = (23),
S( R−2π/3 ) = (321),
S(T2 ) = (13),
S(T3 ) = (12)
angeben. Somit ist S : SD → S3 ein Gruppenisomorphismus.
3. Es sei (G,·) eine Gruppe. Ein Automorphismus ist ein Isomorphismus
G → G. Die Menge Aut(G ) aller Automorphismen auf G bildet eine Gruppe
bezüglich Komposition.
Definition
Es seien (G,· G ) und ( H, · H ) Gruppen und f : G → H ein Gruppenhomomorphismums. Der Kern von f ist die Teilmenge
ker f := f −1 (i H ) = { x ∈ G : f ( x ) = i H }
von G.
45
2.1 Verknüpfungen, Gruppen und Körper
Bemerkung
Definitionsgemäß liegt i G in ker f .
Proposition
Es seien (G,· G ) und ( H, · H ) Gruppen und f : G → H ein Gruppenhomomorphismums. Dann ist f genau dann injektiv, wenn ker f = {i G } ist.
Beweis
Es sei f injektiv. Wähle x ∈ ker f , Aus f ( x ) = f (i G ) = i H folgt x = i G . Folglich
ist ker f = {i G }.
Nun sei ker f = {i G }. Wähle x1 , x2 ∈ G mit f ( x1 ) = f ( x2 ). Aus
f ( x1−1 · x2 ) = f ( x1−1 ) · f ( x2 ) = f ( x1 )−1 · f ( x2 ) = f ( x1 )−1 · f ( x1 ) = i H
folgt x1−1 · x2 ∈ ker f . Folglich gilt x1−1 · x2 = i G und daher x2 = x1 . Somit ist f
injektiv.
Definition
Eine Untergruppe (Y,·) einer Gruppe (X, ·) besteht aus einer Teilmenge Y von X,
die bezüglich der Verknüpfung · wieder eine Gruppe ist.
Proposition
Es seien (X,·) eine Gruppe und Y eine nichtleere Teilmenge von X. Es gelte
1. i ∈ Y,
2. Y ist abgeschlossen bezüglich ·, d.h. x1 , x2 ∈ Y ⇒ x1 · x2 ∈ Y,
3. Y ist abgeschlossen bezüglich der Inversen, d.h. x ∈ Y ⇒ x −1 ∈ Y.
Dann ist (Y,·) eine Untergruppe von (X,·).
46
2.1 Verknüpfungen, Gruppen und Körper
Proposition
Es seien (G,· G ) und ( H, · H ) Gruppen und f : G → H ein Gruppenhomomorphismums.
1. Die Bildmenge von f ist eine Untergruppe von H.
2. Der Kern von f ist eine Untergruppe von G.
Beweis
1. Offenbar ist i H = f (i G ) ∈ R( f ), und für jedes f ( x ) ∈ R( f ) ist
f ( x )−1 = f ( x −1 ) ∈ R( f ). Schießlich seien f ( x1 ), f ( x2 ) ∈ R( f ). Dann ist
f ( x1 ) · f ( x2 ) = f ( x1 · x2 ) ∈ R( f ).
1
2. i G ∈ ker f . Aus x ∈ ker f folgt x −1 ∈ ker f , denn f ( x −1 ) = f ( x )−1 = i −
H = iH.
Schließlich seien x1 , x2 ∈ ker f . Dann gilt f ( x1 · x2 ) = f ( x1 ) · f ( x2 ) = i H · i H =
i H , so dass x1 · x2 ∈ ker f .
Wir werden Gruppentheorie in dieser Vorlesung nicht weiter vertiefen.
Definition
Ein Körper ist eine mit zwei Verknüpfungen + (‘Addition’) und . (’Multiplikation’) versehene nichtleere Menge X, die die folgenden Eigenschaften haben.
∀ x,y,z ∈ X (Assoziativgesetz
der Addition)
(A2) x + y = y + x ∀ x,y ∈ X
(Kommutativgesetz der
Addition)
(A3) Es existiert ein Element
(Existenz eines neutralen
0 ∈ X mit der Eigenschaft
Elements der Addition)
x + 0 = 0 + x = x ∀x ∈ X
(A4) Zu jedem x ∈ X existiert
(Existenz additiver
ein Element − x ∈ X derart, dass
inverser Elemente)
x + (− x ) = − x + x = 0
(A1)
x + (y + z) = ( x + y) + z
47
2.1 Verknüpfungen, Gruppen und Körper
(A5)
x.(y.z) = ( x.y).z
(A6)
x.y = y.x
∀ x,y,z ∈ X
∀ x,y ∈ X
(A7) Es existiert ein Element
1 ∈ X \ {0} mit der Eigenschaft
1.x = x.1 = x ∀ x ∈ X
(A8) Zu jedem x ∈ X \{0} existiert
ein Element x −1 ∈ X derart, dass
x.x −1 = x −1 .x = 1
(A9) x.(y + z) = x.y + x.z ∀ x,y,z ∈ X
(Assoziativgesetz der
Multiplikation)
(Kommutativgesetz der
Multiplikation)
(Existenz eines neutralen
Elements der Multiplikation)
(Existenz multiplikativer
inverser Elemente)
(Distributivgesetz)
In der Regel verwenden wir die Schreibweise (X, + ,.) für einen Körper.
Bemerkungen
1. (A1)-(A4) besagen, dass (X,+) eine Abelsche Gruppe ist. (A5)-(A8) besagen
dagegen, dass (X \ {0},.) eine Abelsche Gruppe ist.
2. Insgesamt besagen diese Eigenschaften, dass die ‘üblichen’ Regeln der Arithmetik innerhalb eines Körpers gelten.
Beispiel
Die Menge der reellen Zahlen bildet einen Körper bezüglich Addition und Multiplikation. In der Regel schreiben wir a.b, a.b−1 und a + (−b) als ab, a/b bzw.
a − b.
Definition
Ein Unterkörper oder Teilkörper (Y, + ,.) eines Körpers (X, + ,.) besteht aus einer
Teilmenge Y von X, die bezüglich der Verknüpfungen + und . wieder ein Körper
ist.
48
2.1 Verknüpfungen, Gruppen und Körper
Proposition
Es seien (X, + ,.) ein Körper und Y eine nichtleere Teilmenge von X. Es gelte
1. 0,1 ∈ Y,
2. Y ist abgeschlossen bezüglich + und ., d.h. x1 , x2 ∈ Y ⇒ x1 + x2 , x1 .x2 ∈ Y,
3. Y ist abgeschlossen bezüglich der Inversen, d.h. x ∈ Y ⇒ − x, x −1 ∈ Y.
Dann ist (Y, + ,.) ein Teilkörper von (X, + ,.).
Beispiel
Die Menge
Q=
nm
: m ∈ Z, n ∈ Z \ {0}
o
n
der rationalen Zahlen bildet einen Teilkörper von (R, + ,.):
Für jedes n ∈ Z \{0} ist
0=
0
,
n
1=
n
,
n
so dass 0, 1 Elemente in Q sind.
Q is abgeschlossen bezüglich der Addition und Multiplikation der reellen
Zahlen, denn mit a, c ∈ Z und b, d ∈ Z \ {0} ist
a
c
a.d + b.c
+ =
∈ Q,
b d
b.d
a c
a.c
. =
∈ Q.
b d
b.d
Für m ∈ Z, n ∈ Z \ {0} ist
−
und für m, n ∈ Z \{0} ist
m
n
=
m −1
(−m)
∈Q
n
n
∈ Q.
n
m
Q ist also abgeschlossen bezüglich der Inversen.
=
49
2.2 Komplexe Zahlen
2.2 Komplexe Zahlen
Definitionen
Eine komplexe Zahl ist ein geordnetes Paar (a,b), wobei a und b reelle Zahlen
sind.
Die Menge aller komplexen Zahlen bezeichnen wir mit C.
Lemma
Mit den durch die Formeln
(a,b) + (c,d) := (a + c,b + d),
(a,b).(c,d) := (ac − bd, ad + bc)
(Addition)
(Multiplikation )
definierten Verknüpfungen bildet die Menge C einen Körper. Dabei sind die neutrale Elemente der Addition und Multiplikation (0,0) bzw. (1,0) und
b
a
−1
,− 2
.
−(a,b) = (− a, − b),
(a,b) =
a2 + b2
a + b2
Lemma
1. Die Teilmenge X = {(a,0) : a ∈ R } von C bildet einen Teilörper von (C, + ,.)
2. Die Abbildung ψ : (a,0) 7→ a ist ein Körperisomorphismus X → R, d.h. eine
Bijektion X → R mit
ψ ( x 1 + x 2 ) = ψ ( x 1 ) + ψ ( x 2 ),
ψ( x1 .x2 ) = ψ( x1 )ψ( x2 )
für alle x1 , x2 ∈ X.
Beweis
1. Wir müssen zeigen:
50
2.2 Komplexe Zahlen
(i) Die additive Identität sowie die multiplikative Identität gehören zu X.
Dies ist trivial: (0,0), (1,0) ∈ X.
(ii) X ist abgeschlossen bezüglich + und .. Dies folgt aus
(a,0) + (b,0) = (a + b,0),
(a,0).(b,0) = (ab,0)
(1)
(2)
(iii) X is abgeschlossen bezüglich der Inversen. Dies folgt aus
−(a,0) = (− a,0),
(a,0)−1 = (a−1 ,0),
a 6= 0.
2. Dies folgt aus (1) und (2).
(3)
(4)
Bemerkung
Die obige Notation für komplexe Zahlen ist etwas umständlich und wird üblicherweise vereinfacht wie folgt.
Wir identifizieren die Teilmenge X von C mit R und schreiben (a,0) als a.
Wir definieren i = (0,1) und bemerken, dass
i.i = (0,1).(0,1)
= (−1,0)
= −1.
Damit gilt
(a,b) = (a,0) + (0,b)
= (a,0) + (0,1).(b,0)
= a + ib.
Wir schreiben also (a,b) als a + ib and arbeiten mit den üblichen Rechenregeln
und dem Zusatz i2 = −1.
51
2.2 Komplexe Zahlen
Beispiel
Es seien z1 = ( x1 ,y1 ), z2 = ( x2 ,y2 ). Dann gilt
z1 z2 = ( x1 ,y1 ).( x2 ,y2 )
= ( x1 x2 − y1 y2 ,x1 y2 + x2 y1 ).
Schreibe nun z1 = x1 + iy1 , z2 = x2 + iy2 . Dann gilt
z1 z2 = ( x1 + iy1 )( x2 + iy2 )
= x 1 x 2 + x 1 y 2 i + x 2 y 1 i + y 1 y 2 i2
= x1 x2 − y1 y + ( x1 y2 + x2 y1 )i.
Definitionen
Betrachte die komplexe Zahl z = x + iy.
1. x ist der Realteil von z. Wir schreiben x = Re z.
2. y ist der Imaginärteil von z. Wir schreiben x = Im z.
3. x − iy ist die zu z konjugiert komplexe Zahl. Wir schreiben x − iy = z̄.
4.
p
x2 + y2 ist der Betrag von z. Wir schreiben
p
x 2 + y2 = | z |.
z heißt reell, falls Im z = 0 ist, und imaginär, falls Re z = 0 ist.
Proposition
Für jede komplexe Zahl z gilt
1. z + z̄ = 2Re z,
2. z − z̄ = 2i Im z,
3. zz̄ = |z|2 .
52
2.2 Komplexe Zahlen
Proposition
Für alle komplexen Zahlen z1 , z2 gelten die Regeln
1. z1 + z2 = z̄1 + z̄2 ,
2. z1 z2 = z̄1 z̄2 ,
3.
1
1
= , falls z1 6= 0,
z̄1
z1
4. z̄1 = z1 ,
5. |z̄1 | = |z1 |.
Geometrische Darstellungen komplexer Zahlen
Da eine komplexe Zahl ein geordnetes Paar ( x,y) reeller Zahlen ist, können wir
sie als Punkt in der Koordinatenebene (komplexer Ebene oder Gaußscher Zahlenebene) darstellen:
Im
z = x + iy
y
Im z
Re z
−y
x
Re
z̄ wird von z durch eine
Spiegelung an der reellen
Achse hergeleitet.
z̄ = x − iy
Es ist auch hilfreich, Polarkoordinaten einzuführen:
53
2.2 Komplexe Zahlen
Im
Hier gilt
z = x + iy
y
x = r cos θ,
y = r sin θ,
q
r = x 2 + y2 ,
y
tan θ = .
x
r
θ
Re
x
Bemerke insbesondere, das
r = | z |.
Der Winkel θ heißt Argument der komplexen Zahl z = x + iy. Er ist nicht eindeutig: Er ist nur bis auf ganzzahlige Vielfache von 2π bestimmt. Diese Mehrdeutigkeit wird behoben, indem man sich auf Werte von θ im Intervall (−π,π ]
einschränkt. In diesem Fall ist θ das Haupt- oder Prinzipalargument von z und
wird mit arg z bezeichnet:
Im
Im
z
z
|z|
arg z
|z|
arg z
Re
Re
Im
Im
Re
arg z
Re
|z|
arg z
|z|
z
z
54
2.2 Komplexe Zahlen
Beispiel
Beschreiben Sie die folgenden Mengen geometrisch.
(i) {z ∈ C : |z − (1 + i)| = 3}
(ii) {z ∈ C : 1 < |z| ≤ 3}
(iii) {z ∈ C : |z − i| < |z + i|}
(iv) {z ∈ C : −π/4 < arg z ≤ π/4}
Lösung
(i) {z ∈ C : |z − (1 + i)| = 3} ist die Menge der komplexen Zahlen, deren Distanz
zur komplexen Zahl 1 + i gleich 3 ist. Sie ist daher ein Kreis mit Mittelpunkt
1 + i und Radius 3:
Im
1
1+ i
3
1
Re
(ii) {z ∈ C : 1 < |z| ≤ 3} ist die Menge der komplexen Zahlen, deren Distanz zum
Nullpunkt größer als 1 und kleiner als oder gleich 3 ist. Es handelt sich daher
um einen Annulus mit Mittelpunkt 0 und Radien 1 und 3:
55
2.2 Komplexe Zahlen
Im
1
3
Re
(iii) {z ∈ C : |z − i| < |z + i|} ist die Menge der komplexen Zahlen, die näher an i
als an −i liegen. Sie ist also die obere Halbebene:
Im
1
Re
−1
(iv) {z ∈ C : −π/4 < arg z ≤ π/4} ist die Menge der komplexen Zahlen, deren
Winkel zur reellen Achse zwischen −π/4 und π/4 liegt. Es handelt sich daher um einen Sektor:
56
2.2 Komplexe Zahlen
Im
π
4
π
4
Re
Lemma
Betrachte die komplexen Zahlen
z1 = x1 + iy1 = r1 cos θ1 + ir1 sin θ1 ,
z2 = x2 + iy2 = r2 cos θ2 + ir2 sin θ2 .
Es gelten die Regeln
z1 z2 = r1 r2 cos(θ1 + θ2 ) + ir1 r2 sin(θ1 + θ2 )
(i)
und
z1n = r1n cos nθ1 + ir1n sin nθ1 ,
n = 1,2,3, . . . .
(Satz von de Moivre)
(ii)
Beweis
(i) Es gilt
z1 z2 = (r1 cos θ1 + ir1 sin θ1 )(r2 cos θ2 + ir2 sin θ2 )
= r1 r2 cos θ1 cos θ2 + i2 r1 r2 sin θ1 sin θ2 + ir1 r2 cos θ1 sin θ2 + ir1 r2 sin θ1 cos θ2
= r1 r2 (cos θ1 cos θ2 − sin θ1 sin θ2 ) + ir1 r2 (cos θ1 sin θ2 + sin θ1 cos θ2 )
= r1 r2 cos(θ1 + θ2 ) + ir1 r2 sin(θ1 + θ2 ).
57
2.2 Komplexe Zahlen
(ii) Dieses Ergebnis folgt induktiv aus (i).
Bemerkung
Wir können (i) geometrisch interpretieren: Die Distanz des Punktes z1 z2 zum
Nullpunkt in der komplexen Ebene ist das Produkt der Distanzen der beiden
Punkten z1 und z2 zum Nullpunkt und der Winkel des Punktes z1 z2 zur reellen
Achse ist die Summe der Winkel der beiden Punkten z1 und z2 zur reellen Achse:
Im
z1 z 2
z2
r1 r2
r2
θ1+θ2 r1
θ1
z1
θ2
Re
Funktionen einer komplexen Veränderlichen
Wir beginnen mit den Definitionen der Exponential-, trigonometrischen und hyperbolischen Funktionen.
58
2.2 Komplexe Zahlen
Definitionen
Für z ∈ C definieren wir
ez := ex (cos y + i sin y),
1
sin z := (eiz − e−iz ),
2i
1
cos z := (eiz + e−iz) ,
2
1
sinh z := (ez − e−z ),
2
1 z
cosh z := (e + e−z ).
2
wobei x = Re z, y = Im z,
Weitere spezielle Funktionen wie tan(·), cot(·), usw. werden durch diese Grundfunktionen auf der üblichen Art und Weise definiert.
Proposition
Es gelten
cosh z = cos(iz),
sinh z = −i sin(iz),
eiθ = cos θ + i sin θ,
z ∈ C,
z ∈ C,
θ ∈ R,
(Eulers Formel)
und die Grundidentitäten für die Beziehungen zwischen den Exponential-, trigonometrischen und hyperbolischen Funktionen sind weiterhin gültig.
Bemerkung
Wir können die komplexe Zahl z in Polarkoordinaten als z = r cos θ + ir sin θ
schreiben und durch Eulers Formel als z = reiθ umschreiben.
59
2.2 Komplexe Zahlen
Bemerkungen (Nullstellen)
1. Die Berechnung
|ez | = |ex (cos y + i sin y)|
= |ex || cos y + i sin y|
= ex
für z = x + iy mit x,y ∈ R zeigt, dass
|ez | = eRe z .
Insbesondere hat die Exponentialfunktion keine Nullstellen in der komplexen Ebene.
2. Es gilt
sin z = 0
⇔
cos z = 0
⇔
z = 0, ±π, ±2π, . . . ,
π 3π 5π
z = ± ,± ,± ,...
2
2
2
(siehe unten).
3. Aus den Formeln in der letzten Proposition folgt
sinh z = 0
⇔
cosh z = 0
⇔
z = 0, ±πi, ±2πi, . . . ,
πi 3πi 5πi
z = ± ,±
,±
,....
2
2
2
Beispiel
Finden Sie die Nullstellen der Funktion cos(·) : C → C.
60
2.2 Komplexe Zahlen
Lösung
Es gilt
cos z = 0
1
⇔ (eiz + e−iz ) = 0
2
⇔ eiz = −e−iz
⇔ e2iz = −1.
Schreibe nun z = x + iy und bemerke, dass −1 = 1eiπ :
Im
| − 1| = 1
π
arg(−1) = π
−1
Re
1
Daher gilt
⇔
⇔
⇔
⇔
e2iz = −1
e2i (x+iy) = −1
e−2y e2ix = 1eiπ
2x = π + 2nπ, n = 0, ± 1, ± 2, . . .
e−2y = 1,
π
y = 0,
x = + nπ, n = 0, ± 1, ± 2, . . . .
2
Es ist also
cos z = 0
⇔
π 3π 5π
z = ± ,± ,± ,....
2
2
2
Definition
Es sei n ∈ N0 . Ein Polynom n-ten Grades ist ein Ausdruck der Form
a n z n + a n − 1 z n − 1 + . . . + a1 z + a0 ,
wobei a0 , . . . , an konstante komplexe Zahlen sind und an 6= 0 ist.
61
2.2 Komplexe Zahlen
Satz (Fundamentalsatz der Algebra)
Es sei n ∈ N. Jedes Polynom n-ten Grades hat eine komplexe Nullstelle.
Korollar
Es sei n ∈ N. Jedes Polynom
z n + a n − 1 z n − 1 + . . . + a1 z + a0
n-ten Grades hat n komplexe Nullstellen z1 ,. . . ,zn (die nicht notwendigerweise
verschieden sind), und lässt sich daher als
zn + an−1 zn−1 + . . . + a1 z + a0 = (z − z1 )(z − z2 ) . . . (z − zn )
zerlegen, wobei wir ohne Beschränkung der Allgemeinheit an = 1 gesetzt haben.
Bemerkung
Falls die Koeffizienten a0 , . . . , an reell sind, kommen alle Nullstellen in konjugiert
komplexen Paaren vor (im Sonderfall können sie reell sein). Es sei nämlich z⋆ eine
Nullstelle. Dann gilt
a n ( z ⋆ ) n + a n − 1 ( z ⋆ ) n − 1 + . . . + a1 ( z ⋆ ) + a0 = 0
⇒ a n ( z ⋆ ) n + a n − 1 ( z ⋆ ) n − 1 + . . . + a1 ( z ⋆ ) + a0 = 0
⇒ ān (z̄⋆ )n + ān−1 (z̄⋆ )n−1 + . . . + ā1 z̄⋆ + ā0 = 0
⇒ an (z̄⋆ )n + an−1 (z̄⋆ )n−1 + . . . + a1 z̄⋆ + a0 = 0,
(da a0 , . . . , an reell sind)
so dass z̄⋆ ebenfalls eine Nullstelle ist.
Definition
Eine n-te Wurzel einer komplexen Zahl a ist eine Lösung der Gleichung
zn = a.
62
2.2 Komplexe Zahlen
Beispiel
Finden Sie alle fünften Einheitswurzeln und interpretieren Sie das Ergebnis geometrisch.
Lösung
Wir müssen alle Lösungen der Gleichung
z5 = 1
finden. Schreibe nun z = reiθ und bemerke, dass 1 = 1ei0 :
Im
|1| = 1
arg(1) = 0
1
Re
1
Daher gilt
z5 = 1
⇔ r5 e5iθ = 1ei0
⇔ r5 = 1,
5θ = 0 + 2nπ, n = 0, ± 1, ± 2, . . .
2nπ
, n = 0, ± 1, ± 2, . . . .
⇔ r = 1,
θ=
5
| {z }
Die fünf Werte dieses Ausdrucks in
4π
2π
4π
(−π,π ] sind 0, 2π
5 , 5 ,− 5 ,− 5
Die fünften Einheitswurzel sind also
ei0 ,
|{z}
=1
e
2πi
5
,
e
4πi
5
,
e−
2πi
5
,
e−
4πi
5
.
63
2.2 Komplexe Zahlen
Im
e
e
2πi
5
4πi
5
Die Wurzeln sind fünf gleichmäßig
verteilte Punkte auf einem Kreis mit
Mittelpunkt 0 und Radius 1.
2π
5
1
Re
Sie bilden die Eckpunkte eines
regelmäßigen Fünfecks.
e−
4πi
5
e−
2πi
5
Das folgende Lemma wird durch die Methode im obigen Beispiel bewiesen.
Lemma
Es sei n eine natürliche Zahl und a eine von Null verschiedene komplexe Zahl.
Dann hat a genau n verschiedene n-te Wurzeln.
Falls n ≥ 3 ist, so sind sie n gleichmäßig verteilte Punkte auf einem Kreis mit
Mittelpunkt 0 und Radius | a|1/n . Sie bilden somit ein regelmäßiges n-Eck.
Proposition
Es seien a, b, c konstante komplexe Zahlen mit a 6= 0. Das quadratische Polynom
az2 + bz + c
besitzt
genau die eine Nullstelle −b/(2a), falls b2 − 4ac = 0,
genau die zwei Nullstellen −b/(2a) + z1 , −b/(2a) + z2 wobei z1 , z2 die beiden Wurzeln aus (b2 − 4ac)/(4a2 ) sind, falls b2 − 4ac 6= 0.
64
2.2 Komplexe Zahlen
Beweis
Quadratische Ergänzung ergibt
b
az + bz + c = a z +
2a
2
2
−
b2
−c .
4a
Bemerkung
Da z2 = −z1 ist, missbrauchen wir oft die Notation und fassen die obige Proposition als
r
b
b2 − 4ac
z=− ±
2a
4a2
p
zusammen, wobei (b2 − 4ac)/4a2 entweder für z1 oder für z2 steht.
Beispiel
Finden Sie alle komplexen Nullstellen des Polynoms
z3 − 3z2 + 4z − 2.
Lösung
1 ist offenbar eine Nullstelle, so dass (z − 1) Faktor des Polynoms ist. Aus der
Rechnung
z2 − 2z + 2
z − 1 z3 − 3z2 + 4z − 2
z3 − z2
−2z2 + 4z − 2
−2z2 + 2z
2z − 2
2z − 2
0
65
2.2 Komplexe Zahlen
folgt
z3 − 3z2 + 4z − 2 = (z − 1)(z2 − 2z + 2).
Die Nullstellen des Polynoms
z2 − 2z + 2
finden wir mit Hilfe der Formel aus der letzten Proposition. Sie sind
r
√
2
4 − 4.1.2
±
= 1 ± −1 = 1 ± i.
2
4
Damit ist
z3 − 3z2 + 4z − 2 = (z − 1)(z − 1 − i)(z − 1 + i).
66
3 Vektorräume
3 Vektorräume
3.1 Einführung
Definition
Es sei (V,+ ) eine Abelsche Gruppe mit neutralem Element 0, so dass
(V1)
(u + v) + w = u + (v + w) ∀u, v, w ∈ V,
(V2)
v+w=w+v
∀v, w ∈ V,
(V3)
v + 0 = 0 + +v = v
∀v ∈ V,
(V4) Zu jedem v ∈ V existiert ein eindeutiges
Element − v ∈ V derart, dass
− v) = 0.
− v + v = v + (−
Nun sei (K, + ,·) ein Körper mit neutralen Elementen 0 und 1. Wir nennen V
einen Vektorraum über K, falls es eine Abbildung
mit den Eigenschaften
(S1)
(S2)
V × K → V,
(α, v) 7→ αv
(⋆)
(α + β)v = αv + βv ∀α, β ∈ K, v ∈ V
(α · β)v = α( βv)
∀v ∈ V
∀α, β ∈ K, v ∈ V
(S3)
1v = v
(S4)
α(v + w) = αv + αw
∀α ∈ K, v, w ∈ V.
Die Elemente von V und K heißen Vektoren bzw. Skalare, die Verknüpfung +
heißt Vektoraddition, und die Abbildung (⋆) heißt Skalarmultiplikation.
Ist K = R oder C, so bezeichnen wir V als reellen bzw. komplexen Vektorraum.
Proposition
Es sei V ein Vektorraum über einem Körper K. Dann gilt
0v = 0
und
für alle v ∈ V.
(−1)v = − v
67
3.1 Einführung
Beweis
Es gilt
0v = (0 + 0)v (Definition des additiven neutralen Elements in K)
= 0v + 0v (S1)
und folglich ist 0v = 0, denn das einzige Element x in der Gruppe (V,+ ) mit
x + x = x ist x = 0.
Ferner gilt
v + (−1)v = 1v + (−1)v (S3)
= (1 − 1 ) v
(S1)
= 0v
(Definition des additiven neutralen Elements in K)
= 0,
so dass
− v = (−1)v
(wegen der Eindeutigkeit der inversen Elemente in der Gruppe (V,+ )).
Bemerkung
In der Regel schreibt man + sowie − als + bzw. −, denn aus dem Kontext wird
klar, welche Verknüpfung gemeint ist. In den meisten Beispielen schreibt man die
Vektoren auch nicht fett.
Beispiele
1. Die Menge
R n = {x = ( x1 , . . . ,xn ) : x1 , . . . , xn ∈ R }
ist ein reeller Vektorraum mit punktweiser Vektoraddition
x + y : = ( x1 + y1 , . . . , x n + y n )
und Skalarmultiplikation
αx := (αx1 , . . . , αxn ).
In den Fällen n = 2 oder n = 3 lassen sich solche Vektoren als Pfeile in der
Ebene bzw. Raum veranschaulichen. Der Vektor x = ( x1 ,x2 ,x3 ) stellt dabei
eine Verschiebung um Distanz xi in Richtung i dar.
68
3.1 Einführung
x
x
0
0
y
x+y
Der Vektor x + y stellt eine
Verschiebung um Distanz
xi + yi in Richtung i dar.
y
3
x
2
x
0
0
0
− 32 x
Der Vektor αx stellt eine
Verschiebung um Distanz
αxi in Richtung i dar.
2. Es sei K ein Körper. Die Menge K n ist ein Vektorraum über K mit punktweiser Vektoraddition und Skalarmultiplikation.
3. Die Menge {0} (mit trivialer Vektoraddition und Skalarmultiplikation) ist
ein Vektorraum über jeden Körper.
4. Die Menge R m×n der (m × n) reellen Matrizen ist ein reeller Vektorraum
mit punktweiser Vektoraddition
(aij ) + (bij ) := (aij + bij ),
d.h.

 

a11 a12 · · · a1n
b11 b12 · · · b1n
 a a22 · · · a2n   b b22 · · · b2n 
 21
  21

 ..
..
..  +  ..
..
.. 
 .


.
.
.
.
. 
am1 am2 · · · amn
bm1 bm2 · · · bmn


a11 + b11 a12 + b12 · · · a1n + b1n
 a21 + b21 a22 + b22 · · · a2n + b2n 


:= 

..
..
..


.
.
.
am1 + bm1 am2 + bm2 · · · amn + bmn
und Skalarmultiplikation
α(aij ) = (αaij ),
69
3.1 Einführung
d.h.




a11 a12 · · · a1n
αa11 αa12 · · · αa1n
 a a22 · · · a2n 
 αa αa22 · · · αa2n 
 21

 21

α  ..
:
=
 ..
..
.. 
..
..  .
 .
 .
.
. 
.
. 
am1 am2 · · · amn
αam1 αam2 · · · αamn
5. Die Menge K m×n der (m × n) Matrizen mit Einträgen aus einem Körper K
ist ein Vektorraum über K mit punktweiser Vektoraddition und Skalarmultiplikation.
6. Die Menge aller Funktionen f : R → R ( f : C → C) ist ein reeller (komplexer)
Vektorraum mit punktweiser Vektoraddition
( f + g)( x ) := f ( x ) + g( x ),
x ∈ R (C )
und Skalarmultiplikation
(α f )( x ) := α f ( x ),
x ∈ R (C ).
Definition
Es sei V ein Vektorraum über einem Körper K. Eine Teilmenge W von V heißt
Unterraum von V, falls W ein Vektorraum über demselben Körper K ist.
Bemerkung
W 6= ∅ ist ein Unterraum von V genau dann, wenn
(i) W abgeschlossen bezüglich Skalarmultiplikation ist, d.h. αw ∈ W für alle w ∈
W und α ∈ K.
(ii) W abgeschlossen bezüglich Vektoraddition ist, d.h. w1 + w2 ∈ W für alle w1 ,
w2 ∈ W,
((i) impliziert 0 ∈ W und −w ∈ W für alle w ∈ W, so dass aus (i), (ii) folgt, dass
(W,+) eine Abelsche Gruppe ist.)
70
3.1 Einführung
Beispiele
1. Es seien K ein Körper, n eine natürliche Zahl und λ1 , . . . , λn feste Zahlen in
K, die nicht alle verschwinden. Die Hyperebene
E = {k = (k1 , . . . ,kn ) : λ1 k1 + · · · + λn k1 = 0},
die offentsichlich 0 enthält, ist ein Unterraum von K n :
Es seien k = (k1 , . . . ,kn ) ∈ E, so dass λ1 k1 + · · · + λn kn = 0, und α ∈ K.
Dann erfüllt αk = (αk1 , . . . , αkn ) die Gleichung
λ1 (αk1 ) + · · · + λn (αkn ) = 0,
so dass αk ∈ E.
Es seien k = (k1 , . . . ,kn ), ℓ = (ℓ1 , . . . ,ℓn ) ∈ E, so dass λ1 k1 + · · · + λn k1 = 0
und λ1 ℓ1 + · · · + λn ℓn = 0. Dann erfüllt k + ℓ = (k1 + ℓ1 , . . . , kn + ℓn ) die
Gleichung
λ1 (k1 + ℓ1 ) + · · · + λn (kn + ℓn ) = 0,
so dass k + ℓ ∈ E.
Nun sei K = R.
y
Im Falle n = 2 ist
E
x
E = {( x,y) ∈ R2 : λ1 x + λ2 y = 0}
eine Gerade durch den Nullpunkt.
z
Im Falle n = 3 ist
E
y
E = {( x,y,z) ∈ R3 : λ1 x + λ2 y + λ3 z = 0}
eine Ebene durch den Nullpunkt.
x
71
3.1 Einführung
2. Es sei F (R ) der reelle Vektorraum aller Funktionen R → R. Die Menge
P(R ) = {αn x n + αn−1 x n−1 + · · · + α1 x + α0 : n ∈ N0 , α0 , . . . ,αn ∈ R }
aller reellen Polynome ist ein Unterraum vom F (R ).
3. Es sei n ∈ N0 . Die Menge
Pn (R ) = {αn x n + αn−1 x n−1 + · · · + α1 x + α0 : α0 , . . . ,αn ∈ R }
aller reellen Polynome mit Grad kleiner gleich n ist ein Unterraum von
P(R ).
Proposition
Es seien V ein Vektorraum über einem Körper K und {Wi }i ∈ I eine Familie von
T
Unterräumen von V. Dann ist W := Wi ein Unterraum von V.
i∈ I
Beweis
Da 0 ∈ Wi für alle i ∈ I ist, ist 0 ∈
T
i∈ I
Wi = W.
Es seien w ∈ W und α ∈ K. Aus w ∈
T
i∈ I
Wi folgt w ∈ Wi für alle i ∈ I. Da Wi ein
Unterraum von V ist, gilt αw ∈ Wi für alle i ∈ I und daher w ∈
Es seien w1 , w2 ∈ W. Aus w1 , w2 ∈
ein Unterraum von V ist, gilt
T
Wi = W.
i∈ I
T
T
i∈ I
Wi = W.
Wi folgt w1 , w2 ∈ Wi für alle i ∈ I. Da Wi
i∈ I
w1 + w2
∈ Wi für alle i ∈ I und daher w1 + w2 ∈
Bemerkung
Im Allgemeinen ist die Vereinigungsmenge zweier Unterräume eines Vektorraums
selbst kein Unterraum.
72
3.2 Elementare Vektorraumtheorie
y
E2
Die Mengen E1 = {( x,0) : x ∈ R }
und E2 = {(0,y) : y ∈ R } sind Unterräume von R2 .
(1,1)
E1 x
Es gilt (1,0) ∈ E1 , (0,1) ∈ E2 aber
(1,1) = (1,0) + (0,1) 6∈ E1 ∪ E2 .
Bemerkung
In der linearen Algebra ist es üblich, die n-Tupel (k1 , . . . , kn ) der Vektorräume K n
eher als Spaltenvektoren
 
k1
 .. 
.
kn
zu schreiben, und wir werden nun in diese Praxis übergehen.
3.2 Elementare Vektorraumtheorie
Definition
Es seien V ein Vektorrraum über einem Körper K und v1 , v2 , . . . , vn Vektoren aus
V. Eine lineare Kombination von v1 , v2 , . . . , vn ist ein Vektor der Form
k 1 v1 + k 2 v2 + . . . k n v n ,
wobei k1 , k2 , . . . , kn Skalare sind.
Beispiele
R2
1
1
und
eine lineare Kombination der Vektoren
ist der Vektor
0
1
1. In
0
in R2 , denn
1
0
1
1
.
+1
=1
1
0
1
73
3.2 Elementare Vektorraumtheorie
2. In P(R ) ist das Polynom x4 + x2 + 2 eine lineare Kombination der Polynome x4 + 21 x2 , x2 + 1 und 1, denn
x4 + x2 + 2 = 1( x4 + 21 x2 ) + 12 ( x2 + 1) + 21 (1).
Definition
Es seien V ein Vektorrraum über einem Körper K und v1 , v2 , . . . , vn Vektoren aus
V. Das Erzeugnis dieser Vektoren ist die Menge
h v1 , . . . , v n i = { k 1 v1 + k 2 v2 + · · · k n v n : k 1 , k 2 , . . . , k n ∈ K }
aller möglichen liearen Kombinationen von v1 , v2 , . . . , vn .
Beispiel
1. In P(R ) ist
h1, x, x2 i = {α0 + α1 x + α2 x2 : α0 , α1 , α2 ∈ R } = P2 (R ).
2. Es seien v1 , v2 6= 0 zwei nichtparallelen Vektoren in R3 (d.h. es gibt kein
λ ∈ R derart, dass v2 = λv1 ). Dann ist
h v1 , v2 i = { x ∈ R 3 = α 1 v2 + α 2 v2 : α 1 , α 2 ∈ R }
eine Ebene durch den Nullpunkt:
v2
v1
0
Proposition
Es seien V ein Vektorrraum über einem Körper K und v1 , v2 , . . . , vn Vektoren aus
V. Das Ergeuznis von v1 , . . . , vn ist ein Unterraum von V.
74
3.2 Elementare Vektorraumtheorie
Beweis
Offensichtlich ist 0 ∈ hv1 , . . . , vn i.
Es seien α ∈ K und v ∈ hv1 , . . . , vn i, so dass es k1 , . . . , kn ∈ K mit
gibt. Dann ist aber
v = k 1 v1 + · · · + k n v n
αv = αk1 v1 + · · · + αkn vn ∈ hv1 , . . . , vn i.
Es seien v, w ∈ hv1 , . . . , vn i, so dass es k1 , . . . , kn , ℓ1 , . . . , ℓn ∈ K mit
v = k 1 v1 + · · · + k n v n ,
gibt. Dann ist aber
w = ℓ1 v 1 + · · · + ℓ n v n
v + w = ( k 1 + ℓ1 ) v 1 + · · · + ( k n + ℓ n ) v n ∈ h v 1 , . . . , v n i.
Definition
Ein Vektorraum V heißt endlichdimensional, falls es eine nichtleere endliche
Teilmenge S von V gibt, so dass hSi = V. Ansonsten ist er unendlichdimensional.
Beispiele
1. Der Vektorraum R2 ist endlichdimensional, denn
α1
2
R =
: α1 , α2 ∈ R
α2
0
1
: α1 , α2 ∈ R
+ α2
= α1
1
0
1
0
=
,
.
0
1
2. Der Vektorraum P(R ) ist unendlichdimensional. Es sei nämlich S eine nichtleere endliche Teilmenge von P(R ). Setze m = max{deg p : p ∈ S}. Dann ist
x m+1 6∈ hSi, so dass P(R ) 6= hSi.
3. Der Vektorraum {0} (über einen beliebigen Körper) ist endlichdimensional,
denn {0} = h0i.
75
3.2 Elementare Vektorraumtheorie
Definition
Es seien V ein Vektorrraum über einem Körper K. Die Vektoren v1 , v2 , . . . , vn aus
V heißt linear unabhängig, falls
α1 v1 + · · · + α n v n = 0
Ansonsten ist sie linear abhängig.
⇒
α1 = 0, . . . , αn = 0.
Bemerkung
Betrachten wir
α1 v1 + · · · + α n v n = 0
als Gleichung für α1 , . . . , αn , so ist α1 = 0, . . . , αn = 0 immer eine Lösung. Dass v1 ,
. . . , vn linear unabhängig sind, ist die Aussage, dass dies die einzige Lösung ist.
Beispiele
     
1
0
0
3





1. In R sind die Vektoren 0 , 1 , 1 linear unabhängig, denn aus
0
0
0
 
 
   
1
0
0
0







α1 0 + α2 1 + α3 1 = 0
0
0
0
0
{z
}
|
 
α1

= α2 
α3
folgt α1 = 0, α2 = 0, α3 = 0.
   
1
1
3



2. In R sind die Vektoren 1 , −1, ebenfalls linear unabhängig, denn
0
0
aus
   
 
1
0
1





α 1 1 + α 2 − 1 = 0
0
0
0
|
 {z
 }
α1 + α2

= α1 − α2 
0
folgt α1 + α2 = 0, α1 − α2 = 0 und daher α1 = 0, α2 = 0.
76
3.2 Elementare Vektorraumtheorie
3. In F (R ) sind die Funktionen sin(·) und cos(·) linear unabhängig, denn aus
α1 sin x + α2 cos x = 0,
für alle x ∈ R
folgt mit x = π2 , dass α1 = 0 und mit x = 0, dass α2 = 0.
4. In
R2
0
1
1
in R2 linear abhängig, denn
,
,
sind die Vektoren
1
0
1
1
1
0
0
1
−1
−1
=
.
1
0
1
0
5. In P(R ) sind die Polynome x4 + x2 + 2, x4 + 12 x2 , x2 + 1, 1 linear abhängig,
denn
1( x4 + x2 + 2) − 1( x4 + 12 x2 ) − 21 ( x2 + 1) − 12 (1) = 0.
6. In einem beliebigen Vektorraum ist {0} immer eine linear abhängige Menge, denn
α0 = 0
für alle Skalare α, insbesondere für α = 1.
77

Download Report