Inhaltsverzeichnis

1 Grundlagen 1 2 Gruppen, Ringe, Körper 43 3 Folgen und Reihen 61 4 Vektorräume 73 5 Normierte Räume, Kompaktheit, Stetigkeit 85 6 Lineare Abbildungen, Koordinatensysteme 111 7 Differentiation in normierten Räumen 121 8 Das Riemannsche Integral 137 9 Lineare Gleichungssysteme 155 10 Formen auf Vektorräumen 167 11 Eigenwerte, Normalformen von Matrizen 179

Kapitel 2

Gruppen, Ringe, Körper

Wir haben mit den Bijektionen einer Menge M mathematische Objekte kennengelernt, die sich mittels Komposition ”∘“ so verknüpfen lassen, dass das Resultat wieder eine Bijektion ist. Ferner genügt diese Verknüpfung dem Assoziativgesetz, es existieren eine neutrale Abbildung id sowie zu jeder Bijektion f eine Umkehrabbildung (Inverse) f^{−1}. Die gleichen Eigenschaften weist auch die Multiplikation der rationalen, von Null verschiedenen Zahlen auf, und es lassen sich viele weitere Beispiele finden (siehe später in diesem Kapitel).

Daher ist es ökonomisch, solchermaßen gleichgeartete Beispiele unter einem neuen Begriff mittels Abstrahierung zu erfassen, hier dem Begriff der Gruppe. Die Bezeichnung Gruppe (franz. groupe) stammt von dem genialen Evariste Galois (1811–1832), der mit seiner Lösung des Problems, notwendige und hinreichende Bedingungen für die Auflösung algebraischer Gleichungen durch Radikale anzugeben,

1

E. Galois

1Galois’ Lösung war so revolutionär, dass sie von den zeitgenössischen Mathematikern nicht verstanden wurde. Galois hatte 1829 ein Manuskript mit der Darstellung seiner Methode bei der Akademie eingereicht. Obwohl der für die Prüfung zuständige A. Cauchy sich selbst mit Permutationen beschäftigt hatte, hat er die Galoissche Arbeit nicht verstanden. Denn aus einem in den Archiven der Akademie befindlichen Brief geht hervor, dass Cauchy am 18.01.1830 in der Akademie über Galois’ Arbeit vortragen wollte. Er entschuldigte sich jedoch wegen Krankheit, kündigte dabei den Vortrag für die folgende Woche an, sprach dort jedoch über eigene Arbeiten und erwähnte Galois niemals (?) wieder. Cauchy hatte sich wohl überhoben. Galois reichte seine Arbeit im Februar 1830 erneut bei der Akademie ein. Diesmal ging sie jedoch wundersamerweise unter der Federführung von J. Fourier verloren. Am weitesten kam noch das dritte 1831 bei der Akademie eingereichte Papier:

44 D. Garbe: Mathematik I für Naturwissenschaftliche Informatik

bahnbrechend für die Auffassung von Mathematik als einer Theorie der Strukturen wurde.^{2}

Je n’ai pas le temps

Letzteres wurde auf Empfehlung von Poisson zurückgewiesen. An eine kritische Randbemerkung schrieb Galois (wahrscheinlich in der Nacht vor dem Duell) die legendären Worte ”On jugera“ (Die Nachwelt wird darüber richten), an eine andere Stelle ”Je n’ai pas le temps“ (Ich habe nicht die Zeit …). Die mathematische Fachwelt brauchte fast 40 Jahre, ehe die Galoissche Theorie verstanden wurde. Das widerlegt auch die bisweilen leichtfertig geäußerte These, dass gute Mathematik eo ipso gute Didaktik bedeute.

2”Seit Beginn des (19.) Jahrhunderts hat der Kalkül einen solchen Grad an Kompliziertheit erreicht, dass jeder Fortschritt durch dieses Mittel unmöglich geworden ist … In dieser Abhandlung werden die weitestgehenden der bisher verwendeten kalkulatorischen Methoden als Spezialfälle (einer allgemeineren Betrachtungsweise) aufgefasst … “ E. Galois, manuscripts, ed. J. Tannery, Paris 1918, p. 25, 26.

Es werden also, sobald man genügend verschiedene Beispiele dafür hat, neue, abstrakte Strukturen axiomatisch durch Angabe ihrer Eigenschaften definiert. Objektorientierten Programmierern ist Ähnliches von dem Entwurf von Klassen, Templates usw. her bekannt.

2.1 Definitionen : (Binäre) Verknüpfung ∘ auf einer Menge M wird eine Abbildung M × M → M mit (a, b) ↦ a ∘ b für alle a, b ∈ M genannt.

(i) Wenn stets a ∘ b = b ∘ a ist, so heißt die Verknüpfung kommutativ.

(ii) Eine Menge A mit einer bzw. mehreren Verknüpfungen heißt eine algebraische Struktur.

(iii) Eine Menge H mit einer assoziativen (siehe 1.12(ii)) Verknüpfung ∘ heißt eine Halbgruppe.

(iv) Ein Element e ∈ H heißt neutrales Element oder Einselement, wenn e ∘ x = x ∘ e = x für alle x ∈ H gilt.

(v) Eine Halbgruppe mit neutralem Element wird ein Monoid genannt.

(vi) Ein Element b eines Monoids M heißt ein Inverses von a ∈ M, wenn b ∘ a = a ∘ b = e gilt. Das Inverse b wird dann mit a^{−1} bezeichnet.

(vii) Ein Monoid G heißt eine Gruppe, wenn jedes Element von G ein Inverses besitzt. ∘ wird dann die Gruppenmultiplikation genannt und von nun an auch so geschrieben, also ”ab“ statt ”a ∘ b“.

(viii) Wenn die Gruppenmultiplikation kommutativ ist, so heißt G kommutative oder abelsche Gruppe.

N. H. Abel (1802-1829)

(ix) Die Kardinalzahl |G| von G – d.i. im endlichen Fall die Anzahl der Elemente von G – heißt die Ordnung von G.

(x) G heißt endliche Gruppe, wenn |G| < ∞ ist.

2.2 Bemerkungen :

(i) In einem Monoid ist das neutrale Element eindeutig bestimmt, eine Halbgruppe kann also höchstens ein neutrales Element enthalten. Denn: Wenn e, e′ neutrale Elemente sind, so gilt e ∘ e′ = e′, aber auch = e. Mithin ist e = e′.

(ii) Zu jedem Gruppenelement ist das Inverse eindeutig bestimmt. Denn: Wenn a^{−1}, α^{−1} Inverse zu a sind, so gilt a^{−1} = a^{−1}e = a^{−1}aα^{−1} = eα^{−1} = α^{−1}.

(iii) Sei G eine Gruppe. Dann gilt

∀(a, b) ∈ G × G ∃_{1}(x, y) ∈ G × G : xa = b ∧ ay = b .

Denn: x := ba^{−1} löst xa = b, und x_{1}a = x_{2}a impliziert x_{1} = x_{2}. Analog für y.

(iv) Es seien G Gruppe und a, a_{1}, a_{2}, …, a_{n} ∈ G. Dann gilt (a^{−1})^{−1} = a und (a_{1}a_{2} … a_{n})^{−1} = a_{n}^{−1} … a_{2}^{−1}a_{1}^{−1}.

(v) In der Gruppe G vermitteln die Abbildungen x ↦ xa, x ↦ ax und x ↦ x^{−1} Bijektionen von G auf sich. Denn: x ↦ xa ist surjektiv wegen der Existenz der Lösung von xa = b und injektiv wegen der Eindeutigkeit der Lösung. Schließe analog für x ↦ ax. Schließlich ist x ↦ x^{−1} eine Abbildung α mit α ∘ α = id_{G}, also ist α nach 1.13 bijektiv.

2.3 Beispiele :

(i) ℕ ist bezüglich der Multiplikation ein kommutatives Monoid (1 ist das neutrale Element).

(ii) 2ℕ := {2, 4, 6, … } ist bezüglich der Multiplikation eine Halbgruppe, aber kein Monoid. Informatiker betrachten bisweilen Halbgruppen, z.B. stetige Matrixhalbgruppen mit stetiger Zeit bei Markoffprozessen.^{3} (iii) ℤ ist bezüglich der Addition eine abelsche Grup-

3Siehe G. Pflug: Stochastische Modelle in der Informatik, p. 29ff.

pe.

(iv) ℚ^{∗} := ℚ \ {0} ist eine (abelsche) Gruppe bezüglich der Multiplikation.

Nebenstehend Abels Denkmal in Oslo. Der Genius tritt die Ignoranten in den Staub

(v) Die Menge aller Bijektionen von M, sogenannter Permutationen oder auch Transformationen der Menge M, ist eine i.a. nichtabelsche Gruppe bezüglich der Komposition, oft als S_{M} bezeichnet. Wenn |M| endlich ist, etwa = n, nimmt man als Bezeichnung für die n Elemente von M gern 1, 2, …, n, spricht von ihnen als den Ziffern der Permutationsgruppe und nennt letztere die symmetrische Gruppe S_{n} vom Grad n. Nach 1.21 hat die Gruppe die Ordnung n!.

(vi) Rechnen wir doch einmal in der symmetrischen Gruppe S_{3}: Eine Schreibweise für Permutationen besteht im Untereinandersetzen von Urbild

und Bild: g_{1} = ( \begin{matrix}1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix} ), g_{2} = ( \begin{matrix}1 & 2 & 3 \\ 1 & 3 & 2 \end{matrix} ), g_{3} = ( \begin{matrix}1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix} ),

g_{4} = ( \begin{matrix}1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix} ), g_{5} = ( \begin{matrix}1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix} ), g_{6} = ( \begin{matrix}1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix} ) sind also die

Elemente von S_{3}. g_{1} ist das neutrale Element, g_{4} ist das Inverse von g_{5}. g_{2}g_{3} ≠ g_{3}g_{2} zeigt, daß S_{3} nicht abelsch ist. Wir lesen das Produkt von Permutationen von links nach rechts!

(vii) Die Menge T aller Drehungen, die ein reguläres Tetraeder mit sich zur Deckung bringen, ist bzgl. der Komposition eine Gruppe der Ordnung 12, die sog. Tetraedergruppe. (Sie tritt z.B. als Drehgruppe des Methan-Moleküls auf). In den Anwendungen (z.B. Kristallographie) treten oft auch die Oktaedergruppe O mit |O| = 24 und die Ikosaedergruppe I mit |I| = 60 auf.

Für den Umgang mit Permutationen ist oft die sogenannte Zyklenschreibweise zweckmäßig: Es seien G eine Permutationsgruppe, g ∈ G und i eine der Ziffern. Statt gg ⋯ g (n Faktoren) schreiben wir g^{n}. Die Ziffern i, ig, ig^{2}, … bilden die sogenannte Bahn oder das Orbit von i unter g. Bei endlich vielen Ziffern ist notwendig ig^{k} = ig^{j} für gewisse k, j ∈ ℕ. Sei etwa k ≥ j und es sei die erste Situation beim Durchlaufen der Ziffern von j nach k, wo eine solche Gleichheit auftritt. Dann ist ig^{k−j} = i, und i, ig, ig^{2}, …, ig^{k−j−1} sind paarweise verschieden. Wir schreiben für den Teil der Permutation, der diese Ziffern betrifft:

( \begin{matrix}i & ig & ig^{2} & … & ig^{k−j−1} \\ ig & ig^{2} & ig^{3} & … & i \end{matrix} ) := ( i ig ig^{2} … ig^{k−j−1} ) .

Letzteres Gebilde heißt ein Zyklus, da das Orbit zyklisch durchlaufen wird. Wie eine Schlange, die sich in den Schwanz beißt!

Die Ziffernmenge eines Zyklus von g ist also die Bahn einer Ziffer. Zur gleichen Bahn unter g zu gehören definiert eine Äquivalenzrelation auf der Menge der Ziffern. Daher gilt:

2.4 Satz : Jede Permutation von endlich vielen Ziffern lässt sich bis auf Reihenfolge eindeutig als Produkt elementfremder Zyklen schreiben.

2.5 Gruppentafeln :

Eine m × n-Matrix (g_{ij}) meint ein Rechteckschema:[ \begin{matrix}g_{11} & g_{12} & ⋯ & g_{1n} \\ g_{21} & g_{22} & ⋯ & g_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ g_{m1} & g_{m2} & ⋯ & g_{mn} \end{matrix} ]

Wenn |G| = n ist, so lässt sich die Gruppe G durch eine n × n-Matrix (g_{ij}) folgendermaßen beschreiben: Wir rändern die Matrix mit einer oberen Zeile g_{1}, g_{2}, …, g_{n} sowie einer entsprechenden ersten Spalte und verabreden g_{ij} := g_{i}g_{j} ∈ G. Die geränderte Matrix heißt dann die Gruppentafel von G. Zum Beispiel für n = 2: Sei etwa g_{1} das neutrale Element. Dann ist notwendig g_{21} = g_{2} und somit g_{22} = g_{1} (wegen der Bijektivität von x ↦ xg_{2}). Die Bijektivität der Abbildungen x ↦ g_{i}x und x ↦ xg_{j} (2.2 (v)) begründet den

Slogan: In jeder Zeile (bzw. Spalte) der Gruppentafel tritt jedes Gruppenelement genau einmal auf.

Für n = 3 hat die Gruppentafel folgendes Aussehen: \begin{matrix}* & g_{1} & g_{2} & g_{3} \\ g_{1} & g_{1} & g_{2} & g_{3} \\ g_{2} & g_{2} & g_{3} & g_{1} \\ g_{3} & g_{3} & g_{1} & g_{2} \end{matrix}

Überlege, dass sich für n = 4 kombinatorisch zwei essentiell verschiedene Möglichkeiten ergeben!

Um zu zeigen, dass die konstruierten Tafeln auch Gruppen darstellen, müssen wir jeweils nur noch das Assoziativgesetz nachweisen. Denn es gilt:

2.6 Satz : Sei G eine Menge mit einer Verknüpfung ∗ so, dass

(i) das Assoziativgesetz gilt und

(ii) zu jedem a, b ∈ G x, y ∈ G existieren mit a ∗ x = b und y ∗ a = b.

Dann ist G eine Gruppe. Beweis: Wegen (ii) existiert zu jedem a ∈ G eine ”individuelle Linkseins“ e_{1}(a), d.h. e_{1}(a) ∗ a = a. Dann ist e_{1}(a) aber sogar ”universelle Linkseins“, d.h. es gilt e_{1}(a) ∗ g = g für alle g ∈ G; denn wegen der Lösbarkeit von a ∗ x = g gilt: e_{1}(a) ∗ g = e_{1}(a) ∗ a ∗ x = a ∗ x = g. Ebenso existiert eine universelle Rechtseins e_{2}. Linkseins ist gleich Rechtseins, denn es gilt e_{1} = e_{1} ∗ e_{2} = e_{2}. Also existiert eindeutig (2.2 (i)) das neutrale Element e. Die Voraussetzung (ii) impliziert ebenso die Existenz des Inversen: Denn zu a existiert ein Linksinverses l(a) und ein Rechtsinverses r(a): l(a) ∗ a = e = a ∗ r(a). Nun ist aber l(a) = l(a) ∗ e = l(a) ∗ a ∗ r(a) = e ∗ r(a) = r(a), also existiert das Inverse zu a. □

2.7 Definition : Es seien G eine Gruppe und U eine Teilmenge von G. U heißt Untergruppe von G, geschrieben U < G, wenn U bezüglich der in G erklärten Gruppenmultiplikation wieder eine Gruppe ist.

2.8 Bemerkungen :

(i) Wenn U eine nichtleere, bezüglich der Multiplikation abgeschlossene Teilmenge einer Gruppe G ist, für die mit jedem u ∈ U auch u^{−1} ∈ U gilt, so ist U < G. Denn: Die Assoziativität ist für U erfüllt, da die Assoziativität in G gilt. Inverse existieren nach Voraussetzung. Es ist aber auch e = uu^{−1} ∈ U.

(ii) Wenn U eine endliche nichtleere, bezüglich der Multiplikation abgeschlossene Teilmenge einer Gruppe G ist, so ist U < G. Denn: Für a ∈ U ist x ↦ xa nach 2.2 (v) eine Injektion U → U, wegen der Endlichkeit von U sogar eine Bijektion. Also ist xa = a in U lösbar und somit e ∈ U. Aber auch xa = e ist in U lösbar und somit a^{−1} ∈ U.

(iii) Jede Gruppe besitzt zwei triviale Untergruppen , nämlich {e} und G.

2.9 Definitionen : Sei G eine Gruppe und seien A, B ⊂ G. AB := {ab : a ∈ A ∧ b ∈ B} heißt das Komplexprodukt von A und B. Ist speziell A = {a}, so schreiben wir aB statt {a}B (analog Ab). Wir verwenden auch die Bezeichnung A^{−1} := {a^{−1} : a ∈ A}. Wenn U < G und g ∈ G ist, so heißt Ug eine Rechtsnebenklasse von U in G.

2.10 Beispiel : Sei G = (ℤ, +) die additive Gruppe von ℤ, und sei U := 5ℤ := {0, ±5, ±10, … }. Die Rechtsnebenklassen von U in G sind die Kongruenzklassen mod 5: U = U + 0, U + 1 = {…, −9, −4, 1, 6, 11, … }, U + 2, U + 3, U + 4.

2.11 Bemerkungen : Sei G eine Gruppe. Dann gilt:

(i) U < G ↔ UU = U ∧ U = U^{−1}

(ii) Wenn U < G und g, h ∈ G sind, so gilt: h ∈ Ug ↔ Ug = Uh. Denn: Wenn h ∈ Ug, etwa h = ug, ist, so gilt Uh = Uug = Ug. Wenn Ug = Uh ist, so ist h = eh ∈ Uh = Ug.

(iii) Für U < G und alle g ∈ G gilt |Ug| = |U| = |gU|.

(iv) Sei U < G. Wir definieren eine Relation ρ auf G: Es gelte aρb, wenn a und b in derselben Rechtsnebenklasse von U sind. ρ ist eine Äquivalenzrelation. Wir erhalten also eine Partition von G in Rechtsnebenklassen: G = ⋃_{g∈S} ; . Ug, wobei S ein sogenannter Schnitt oder ein

Rechts-Repräsentantensystem ist, nämlich eine Menge, die aus jeder Äquivalenzklasse genau ein Element enthält.

Es gilt auch G = ⋃_{g∈S} ; . g^{−1}U. Also: Die Kardinalität der Menge der

Rechtsnebenklassen ist gleich der Kardinalität der Menge der Linksnebenklassen, der sogenannte Index von U in G, geschrieben |G : U|. Denn: Ug = Uh ↔ h ∈ Ug ↔ h = ug für ein u ∈ U ↔ h^{−1} = g^{−1}u für ein u ∈ U ↔ h^{−1}U = g^{−1}U.

Damit ist der folgende Satz bewiesen: 2.12 Satz von Lagrange : Sei G eine Gruppe mit U < G.

Dann ist |G| = |U| · |G : U|.

Slogan: Die Ordnung der Untergruppe ist ein Teiler der Gruppenordnung.

Übung (zu 2.9 bis 2.11): Nachfolgend sind alle nichttrivialen Untergruppen von S_{3} aufgeführt: C_{3} = {( 1 2 3 ) , ( 1 )}, C_{2}^{(1)} = {( 1 2 ) , ( 1 )}, C_{2}^{(2)} = {( 2 3 ) , ( 1 )}, C_{2}^{(3)} = {( 1 3 ) , ( 1 )}.

Schreibe für jede der vier nichttrivialen Untergruppen die Partition von S_{3} in Linksnebenklassen bzw. in Rechtsnebenklassen auf. Nebenstehend der Graph des Untergruppenverbandes von S_{3}. (|_{B}^{A}n bedeutet B < A mit Index |A : B| = n).

2.13 Definitionen : G_{1}, G_{2} seien Gruppen.

(i) Eine Abbildung φ : G_{1} → G_{2} heißt ein Gruppenmorphismus (früher auch: Gruppenhomomorphismus) , wenn für φ die sogenannte Relationstreue gilt, d.h. wenn φ(gh) = φ(g)φ(h) für alle g, h ∈ G gilt.

Die Bedingung der Relationstreue kann auch geometrisch durch die sog. Kommutativität des nebenstehenden Diagramms dargestellt werden.

[figure: G_{1} × G_{1}; φ; ∘; G_{1}; φ; G_{2} × G_{2}; ∘; G_{2}]

(ii) Ist G_{1} = G_{2}, so heißt der Morphismus auch Endomorphismus.

(iii) Ein injektiver Morphismus heißt Monomorphismus.

(iv) Ein surjektiver Morphismus heißt Epimorphismus.

(v) Ein bijektiver Morphismus heißt Isomorphismus , geschrieben G_{1} ≃ G_{2}. Wir sagen auch: es besteht Isomorphie zwischen G_{1} und G_{2}. Oder: G_{1} ist isomorph zu G_{2}.

(vi) Wenn G_{1} = G_{2} ist, so heißt ein Isomorphismus auch Automorphismus.

(vii) Wir definieren schließlich noch: Kern φ := {x : x ∈ G_{1} ∧ φ(x) = e_{G_{2}}}.

Slogan (für Relationstreue): Das Bild des Produktes ist gleich dem Produkt der Bilder.

Morphismen sind die an die algebraische Struktur des Urbildes angepaßten Abbildungen (Denke an die Relationstreue!). Sie ”vergröbern“ u.U. die algebraische Struktur, ohne sie jedoch ”in ihrem Wesen“ zu zerstören. Ein Maß für die ”Vergröberung“ ist die Größe des Kerns. Bei einem Homomorphismus φ werden jeweils genau die Elemente einer Nebenklasse des Kerns auf dasselbe Bildelement abgebildet:

2.14 Bemerkungen : Sei φ : G → H ein Gruppenmorphismus. Dann gelten:

(i) φ(e_{G}) = e_{H} (denn e_{G}x = x impliziert φ(e_{G})φ(x) = φ(x)),

(ii) φ(x^{−1}) = φ(x)^{−1} (Wende φ auf xx^{−1} = e an),

(iii) wenn U < G, so ist φ(U) < φ(G) (wegen (i), (ii). Die Abgeschlossenheit bzgl. der Multiplikation ist klar),

(iv) wenn U′ < H, so ist φ^{−1}(U′) < G ,

(v) Kern φ < G.

2.15 Beispiele :

Die Gruppe D_{3} der Drehungen eines gleichseitigen Dreiecks (im 3-dimensionalen Raum) heißt Diedergruppe (der Ordnung 6). Die Gruppe S_{3} aller Permutationen von 3 Ziffern heißt symmetrische Gruppe vom Grad 3. Es besteht eine Isomorphie S_{3} ≃ D_{3}: e ↔ (1)(2)(3), c_{2} ↔ (1 2), d_{2} ↔ (2 3), f_{2} ↔ (1 3), c_{3} ↔ (1 2 3), c_{3}^{2} ↔ (1 3 2).

Die Abbildung, die e, c_{3}, c_{3}^{2} auf (1) und c_{2}, d_{2}, f_{2} auf (1 2) abbildet, ist ein Morphismus D_{3} → S_{2}, der kein Isomorphismus ist.

Wir gehen jetzt zu algebraischen Strukturen mit zwei Verknüpfungen über. Als Modell haben wir zunächst den Bereich ℤ der ganzrationalen Zahlen vor Augen mit seinen beiden Verknüpfungen Addition und Multiplikation.

2.16 Definitionen : Eine algebraische Struktur R mit R ≠ Ø und den beiden Verknüpfungen + und ·, genannt Addition und Multiplikation, heißt ein Ring, wenn folgende Eigenschaften gelten:

(i) (R, +) ist eine abelsche Gruppe , (ii) die Multiplikation ist assoziativ ,

(iii) ∀a, b, c ∈ R : a(b + c) = ab + ac ∧ (a + b)c = ac + bc .

Wenn 1 ∈ R existiert mit 1x = x1 = x für alle x ∈ R, so heißt R ein Ring mit Eins.

Ein Element u eines Ringes mit Eins heißt eine Einheit, wenn u sowohl ein multiplikatives Rechtsinverses wie auch ein multiplikatives Linksinverses besitzt, d.h. es existieren a, b ∈ R mit au = 1 und ub = 1.

Wenn die Multiplikation im Ring R kommutativ ist, so heißt R kommutativer Ring. Eine bezüglich beider Verknüpfungen relationstreue Abbildung von Ringen heißt ein Ringhomomorphismus oder -morphismus . Analog werden Ringisomorphismus, -epimorphismus , … definiert.

2.17 Beispiele :

(i) (ℤ, +, ·) und (ℚ, +, ·) sind kommutative Ringe mit 1. {+1, −1} und ℚ \ {0} =: ℚ^{∗} sind die Einheitenmengen von ℤ bzw. ℚ.

(ii) nℤ := {nz : n ∈ ℕ ∧ z ∈ ℤ} ist für n ∈ ℕ \ {1} ein kommutativer Ring ohne 1.

(iii) ℤ_{n} := \{ˆ0, ˆ1, …, { \atop n − 1}\} ist ein kommutativer Ring mit 1, wobei î die Kongruenzklasse nℤ + i modulo n ist, der sog. Restklassenring modulo n. Dabei wird mit den Restklassen î so gerechnet wie mit den kleinsten positiven Resten i mod n. Also z.B. in ℤ_{6}: 4 · 3 = 12 ≡ 0 mod 6, daher ist ˆ4 · ˆ3 = ˆ0. Die Einheitenmenge von ℤ_{6} ist {ˆ1, ˆ5}.

(iv) Sei R ein kommutativer Ring mit Eins (letztere als 1 geschrieben). Wir definieren: R[x] := {(a_{0}, a_{1}, a_{2}, …) : a_{i} ∈ R, i ∈ ℕ ∪ {0}, nur endlich viele a_{i} ≠ 0}, (a_{0}, a_{1}, …) = (b_{0}, b_{1}, …) :↔ a_{i} = b_{i} für alle i ∈ ℕ ∪ {0}, (a_{0}, a_{1}, …) + (b_{0}, b_{1}, …) :↔ (a_{0} + b_{0}, a_{1} + b_{1}, …), (a_{0}, a_{1}, …) · (b_{0}, b_{1}, …) :↔ (a_{0}b_{0}, a_{0}b_{1} + a_{1}b_{0}, …, a_{0}b_{k} + a_{1}b_{k−1} + … + a_{k}b_{0}, …) (an der k-ten Stelle, kurz ∑_{m+n=k}a_{m}b_{n}).

Es ist leicht nachzuprüfen, dass R[x] mit den solchermaßen definierten Verknüpfungen ein kommutativer Ring mit Eins ist. Zum Beispiel rechnen wir ein Distributivgesetz nach:

(…, a_{i}, …)[(…, b_{i}, …) + (…, c_{i}, …)]

= (…, a_{i}, …)(…, b_{i} + c_{i}, …)

= (…, ∑_{m+n=i}a_{m}(b_{n} + c_{n}), …)

= (…, ∑_{m+n=i}a_{m}b_{n} + ∑_{m+n=i}a_{m}c_{n}, …)

= (…, ∑_{m+n=i}a_{m}b_{n}, …) + (…, ∑_{m+n=i}a_{m}c_{n}, …)

= (…, a_{i}, …)(…, b_{i}, …) + (…, a_{i}, …)(…, c_{i}, …) .

Wir betrachten eine Abbildung α, die durch α((a_{0}, a_{1}, a_{2}, …)) := a_{0} + a_{1}x + a_{2}x^{2} + … definiert sei. R[x] wird wegen der Abbildung α der Polynomring über R in der Unbestimmten x genannt. Wenn wir nämlich im Bildbereich von α rechnen, wie wir das Rechnen mit Polynomen auf der Schule gelernt haben, so ist α ein Ringisomorphismus. x

erfüllt keine algebraische Gleichung ∑_{j=0}^{n}a_{i}x^{i} = 0, heißt auch nichtalge-

braisch oder transzendent über R. So ist z.B. π transzendent über ℚ. Aber \sqrt{2} ist algebraisch über ℚ, da es Lösung der algebraischen Gleichung x^{2} − 2 = 0 ist. Die Einheiten von R[x] sind genau die Einheiten von R.

(v) Eine n × n-Matrix ist ein Gebilde der Gestalt [ \begin{matrix}a_{11} & a_{12} & ⋯ & a_{1n} \\ a_{21} & a_{22} & ⋯ & a_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{n1} & a_{n2} & ⋯ & a_{nn} \end{matrix} ],

kurz (a_{ij}) geschrieben. Die a_{ij} heißen Einträge oder Koeffizienten der Matrix. Sei M_{n,n}(R) die Menge aller n × n-Matrizen mit Koeffizienten aus dem Ring R. M_{n,n}(R) wird ein Ring, wenn Addition und Multiplikation folgendermaßen definiert werden: (a_{ij}) + (b_{ij}) := (a_{ij} + b_{ij}),

(a_{ij})(b_{ij}) := (∑_{ν=1}^{n}a_{iν}b_{νj}).

Slogan: Die Matrizenaddition erfolgt komponentenweise. Die Matrizenmultiplikation erfolgt nach dem Motto ”Zeile mal Spalte“.

2.18 Bemerkungen : Sei R ein Ring. Dann gelten:

(i) 0r = r0 = 0 für alle r ∈ R. Denn: 0r = (0 + 0)r = 0r + 0r, also 0r = 0 wegen der Eindeutigkeit des neutralen Elements der additiven Gruppe.

(ii) (−a)b = a(−b) = −ab für alle a, b ∈ R. Denn: wegen 0 = 0b = (a + (−a))b = ab + (−a)b ist (−a)b = −ab.

(iii) (−a)(−b) = ab für alle a, b ∈ R. Denn: Es ist (−a)(−b) = −(a(−b)) = −(−ab), also = ab (2.2 (vi)).

(iv) Wenn φ : R → R′ ein Ringhomomorphismus ist, so ist φ(R) ein Ring.

(v) Wenn φ : R → R′ ein Ringhomomorphismus und R ein Ring mit Eins ist, so ist φ(1)y = yφ(1) = y für alle y ∈ φ(R).

Achtung: φ(1) ist damit noch nicht notwendig Eins in R′! Betrachte zum Beispiel die natürliche Injektion φ(a) := (a, 0) von ℤ in ℤ × ℤ, wobei letztere Menge vermöge komponentenweise definierter Addition und Multiplikation ein Ring ist (vgl. auch Übungsaufgabe 14 ). Dann ist φ(1) := (1, 0) nicht Eins in ℤ × ℤ.

(vi) In Ringen besitzt jede Einheit genau ein multiplikatives Inverses, das sowohl Links- als auch Rechtsinverses ist. Denn: Nach der Definition der Einheit u existieren a, b ∈ R mit au = 1 und ub = 1, also gilt b = (au)b = a(ub) = a. Mithin ist in R jedes Linksinverse von u gleich jedem Rechtsinversen. Also existiert genau ein multiplikatives Inverses von u.

2.19 Definitionen : Ein kommutativer Ring R heißt euklidisch, wenn

(i) R nullteilerfrei ist, d.h. wenn (ab = 0 → a = 0 ∨ b = 0) gilt, und es eine Abbildung N : R \ {0} → ℕ ∪ {0} gibt so, daß

(ii) a|b ∧ b ≠ 0 → N(a) ≤ N(b) und

(iii) ⋀_{a,b∈R,b≠0} ⋁_{q,r∈R}(a = bq + r ∧ (r = 0 ∨ N(r) < N(b)))

( Divisionsalgorithmus)

gilt. Ein Element a eines kommutativen, nullteilerfreien Ringes mit 1 heißt ein Teiler von b, geschrieben a|b, wenn ∃c ∈ R : b = ac. Sei q ∈ R, q ≠ 0, q sei keine Einheit. Dann heißt q ein irreduzibles Element , wenn q nur die trivialen Teiler besitzt (d.h. die Einheiten und die Produkte aus einer Einheit und q).

2.20 Bemerkungen :

(i) Die Eigenschaft (iii) von 2.19 formuliert die schon aus der Elementarschule für ganzrationale Zahlen bekannte Division mit Rest. Hierbei ist N(z) := |z|. Euklidische Ringe sind also im wesentlichen solche Ringe, in denen sich die Division mit Rest sinnvoll erklären läßt. Ein weiteres, auch aus der Schule bekanntes Beispiel (Polynomdivision) ist ℚ[x] (später auch ℝ[x], ℂ[x]). ℚ[x] ist bezüglich N(P) := Grad P ein euklidischer Ring, wobei der Grad eines Polynoms a_{n}x^{n} + a_{n−1}x^{n−1} + … + a_{0} mit a_{n} ≠ 0 zu n definiert ist.

(ii) Die Irreduzibilität verallgemeinert die Eigenschaft, die Primzahlen kennzeichnet. Also sind die irreduziblen Elemente von ℤ die Elemente ±p, wobei p eine Primzahl ist. Die irreduziblen Elemente von ℚ[x] sind die linearen Polynome und gewisse quadratische Polynome, z.B. x^{2} + 1.

(iii) Euklidische Ringe sind Gaußsche Ringe, d.h. es gilt die (bis auf Reihenfolge und Einheitenfaktoren) eindeutige Zerlegung in irreduzible Elemente. Z.B. z = ± ∏_{i=1,... ,n}p_{i}^{e_{i}} in ℤ (p_{i} Primzahlen, e_{i} ∈ ℕ),

f(x) = r ∏(x + c_{i}) ∏(x^{2} + a_{j}x + b_{j}) in R[x]. (Beweis bei Th.W. Hungerford, Algebra, Ch. III, Theorem 3.9)

2.21 Definitionen : Sei R ein kommutativer, nullteilerfreier Ring mit 1, ein sogenannter Integritätsbereich. d ∈ R heißt ein größter gemeinsamer Teiler von a_{1}, a_{2}, …, a_{n} ∈ R, geschrieben (a_{1}, a_{2}, …, a_{n}), wenn (d|a_{i} für alle i = 1, …, n ∧ {t|a_{i} für alle i = 1, …, n → t|d}) gilt.

2.22 Satz : In euklidischen Ringen gilt der Hauptsatz vom ggT, nämlich

(i) Zu a_{1}, a_{2}, …, a_{n} ∈ R existiert stets ein bis auf Einheitenfaktoren eindeutig bestimmter ggT (a_{1}, a_{2}, …, a_{n}).

(ii) Es ist (a_{1}, a_{2}, …, a_{n}) als ∑_{i=1}^{n}c_{i}a_{i} mit c_{i} ∈ R darstellbar.

Beweis: Der Beweis erfolgt mittels des sog. euklidischen Algorithmus (aus dem 7. Buch der Elemente des griechischen Mathematikers Euklid, der um 300 v.u.Z. in Alexandria lebte). Heute ist die Implementierung dieses Algorithmus meist eine der ersten Übungen beim Programmieren.

Wir zeigen die Aussage für n = 2: Wiederholte Anwendung von 2.19 (iii) ergibt: a_{1} = q_{1}a_{2} + r_{1} mit N(r_{1}) < N(a_{2}) a_{2} = q_{2}r_{1} + r_{2} mit N(r_{2}) < N(r_{1}) r_{1} = q_{3}r_{2} + r_{3} mit N(r_{3}) < N(r_{2}) … r_{m−1} = q_{m+1}r_{m} + r_{m+1} mit N(r_{m+1}) < N(r_{m}) r_{m} = q_{m+2}r_{m+1}

Euklid Aus Elements,ed. A. Tacquet, 1765

Das Verfahren muß irgendwann mit r_{m+2} = 0 abbrechen, da wir eine absteigende Kette N(a_{2}) > N(r_{1}) > N(r_{2}) > … in ℕ vorliegen haben (wegen der sog. Wohlordnungseigenschaft von ℕ). Verfolgen wir das Gleichungssystem von unten nach oben, so erhalten wir: r_{m+1} ist ein Teiler von r_{m} und wegen der zweitletzten Gleichung auch von r_{m−1} usf. aufwärts, bis wir oben folgern: r_{m}|a_{1} ∧ r_{m}|a_{2}. Gehen wir von oben nach unten, so überzeugen wir uns davon, daß jeder gemeinsame Teiler von a_{1} und a_{2} auch ein Teiler von r_{m+1} ist. Also ist r_{m+1} ein größter gemeinsamer Teiler von a_{1} und a_{2}.

Durch schrittweises Einsetzen – von unten nach oben gehend – ergibt sich auch der Beweis von (ii). Die Eindeutigkeit des ggT (bis auf Einheitenfaktoren): Seien d_{1}, d_{2} zwei ggT von a_{1}, a_{2}. Dann gilt: d_{1}|d_{2} ∧ d_{2}|d_{1}, und somit d_{1} = d′_{2}d_{2} ∧ d_{2} = d′_{1}d_{1}. Also d_{1} = d′_{2}d′_{1}d_{1}. Mithin gilt d′_{2}d′_{1} = 1. Daher ist d′_{1} eine Einheit und es ist d_{2} = d′_{1}d_{1}.

2.23 Definitionen : ℤ_{n}^{∗} := {a : a ∈ ℤ_{n} ∧ (a, n) = 1} heißt Gruppe der primen Restklassen modulo n; denn für (a, b) = 1 sagen wir: a ist prim (oder teilerfremd) zu b. φ(n) := |ℤ_{n}^{∗}| definiert die sogenannte Eulersche φ-Funktion , eine Abbildung ℕ → ℕ.

2.24 Bemerkungen :

(i) (ℤ_{n}^{∗}, ·) ist eine Gruppe. Denn: Wenn (a, n) = 1 ist, so existieren r, s ∈ ℤ mit ra + sn = 1 (2.22 (ii)). Also ist ra ≡ 1 mod n, mithin hat â ein Inverses, nämlich r̂ ∈ ℤ_{n}. Die übrigen Gruppenaxiome sind ebenfalls erfüllt.

(ii) Sei p eine Primzahl. Es gilt: φ(p^{n}) = p^{n} − p^{n−1} für n ∈ ℕ. Denn: Zu p^{n} nicht teilerfremd sind genau die folgenden natürlichen Zahlen ≤ p^{n}: 0, p, 2p, 3p, …, (p^{n−1} − 1)p, also p^{n−1} Stück.

(iii) (a, b) = 1, (a, b ∈ ℕ) → φ(ab) = φ(a)φ(b).

2.25 Kleiner Fermatscher Satz : (a, n) = 1, (a, n ∈ ℕ) → a^{φ(n)} ≡ 1 mod n. Beweis: Wir betrachten die Menge ⟨â⟩ := {â, ââ =: â^{2}, â^{3}, … } in ℤ_{n}^{∗}. Die Folge der â-Potenzen in dieser Menge endet mit â^{m} = e (Begründung analog zu Zeile 1 von S. 38). Es ist ⟨â⟩ eine Untergruppe von ℤ_{n}^{∗} der Ordnung m, eine sog. zyklische, von â erzeugte Gruppe, also nach 2.12 gilt m|φ(n). Daher ist â^{φ(n)} = e, und mithin gilt die Behauptung. □

Zyklische Drehgruppen der Ordnung 4 bzw. 3 bei thrakischen Wirbelmotiven. Schmuckplatten aus dem 4. Jh. v. u. Z., Craiova, Rumänien.

Der kleine Fermatsche Satz findet mannigfache, für Informatiker interessante Antwendungen, z.B. beim probabilistischen Primzahltest nach Miller-Rabin, besonders aber beim RSA-Verfahren in der Kryptographie. Letzteres ist von den heute bekannten Verschlüsselungsverfahren das sicherste. Die Einführung von Falltür-Krypto-Systemen mit öffentlichen Schlüsseln wurde 1976 von Whitfield Diffie und Martin Hellmann vorgeschlagen (New Directions in Cryptography, IEEE Trans. Inform. Theory 22, 644). Ausgenutzt wird die Tatsache, dass es keine hinreichend schnellen Verfahren für das Ziehen von Wurzeln in ℤ_{n} gibt.

Wenn wir mit T den ASCII-Wert des zu verschlüsselnden Buchstaben und mit C den des verschlüsselten Buchstaben bezeichnen, so erfolgt die Verschlüsselung durch C ≡ T^{e} mod n, wobei e und n öffentlich gemacht und so gewählt werden, dass (e, φ(n)) = 1 gilt. Dann lässt sich nämlich ed ≡ 1 mod φ(n) lösen, und das d ist der Entschlüsselungsexponent: C^{d} ≡ T^{ed} = T^{kφ(n)+1} = T (T^{φ(n)})^{k} mod n. Wenn (n, T) = 1 ist, so gilt nach 2.25 T^{φ(n)} ≡ 1 mod n und somit C^{d} ≡ T mod n.^{4}

Diese Idee wurde von Rivest, Shamir und Adleman weiterentwickelt zu dem Verfahren, das heute RSA-Verschlüsselungsmethode genannt wird (Comm. ACM 21 (1978), 120 ff.): Wenn nämlich n speziell als n = pq mit Primzahlen p, q, p ≠ q, gewählt wird, so gilt C^{d} ≡ T mod n für jedes T. Denn im Falle von (T, n) ≠ 1 ist (T, n) = p oder = q, etwa = p. Dann ist (T, q) = 1 und daher T^{φ(q)} ≡ 1 mod q. Da p|T, ist n = pq|T (T^{kφ(q)φ(p)} − 1) für alle k und mithin wieder T^{kφ(n)+1} ≡ T mod n für alle k.

Ohne Kenntnis der Faktorisierung von n läßt sich φ(n) und damit der geheim gehaltene Schlüssel d nicht hinreichend schnell ermitteln. Darin liegt die Sicherheit des Verfahrens. Der Bedarf an leicht zu handhabenden, einbruchsicheren Codes ist in den heutigen Zeiten der globalen Vernetzung enorm: z.B. für Online-Bank- oder Kauf-Geschäfte, für sichere Übermittlung von internen Betriebsdaten etc. Nach jetzigem Stand der Technik gelten Primzahlen mit 200 Dezimalstellen als sicher. Wenn stärkere Prozessoren entwickelt werden, kann man diese Marge unschwer erhöhen.

P. de Fermat

Bevor wir das Thema Ringe verlassen, wollen wir noch eine leichte, aber praktisch bedeutsame Anwendung des Rechnens im Restklassenring ℤ_{n} behandeln, nämlich das Prüfziffernverfahren bei der ISBN (Internationale-Standard-Buch-Nummer). Eine solche besteht aus 10 Ziffern, die in 4 Abschnitte gegliedert sind: Der erste Abschnitt kennzeichnet das Land (USA 0, Deutschland 3, …), der zweite den Verlag, der dritte das Buch, und der

vierte besteht aus der Prüfziffer z_{10} ≡ ∑_{i=1}^{9}iz_{i} mod 11 (für den Rest 10 wird

X geschrieben). Zum Beispiel hat das bekannte Buch von Donald E. Knuth: The Art of Computer Programming, vol. 3, Sorting and Searching, die ISBN 0-201-03803-X. Das Prüfverfahren erkennt alle Einzelfehler und Doppelfehler bis auf einen Teil der Zwillingsvertauschungen und phonetischen Fehler.

4Bei konkreten Implementationen des Verfahrens werden nicht die ASCII-Werte einzelner Textbuchstaben sondern Blöcke aus solchen potenziert. Die Blocklänge wird z. B.

einheitlich so gewählt, dass die Zahlenwerte der Blöcke gering unterhalb des Schlüssels n liegen.

Noch besser ist die Prüfbedingung ∑_{i=1}^{n}2^{i−1}z_{i} ≡ 0 mod 11. Damit arbeitet

angeblich die Dresdner Bank.

Zum Abschluß empfehlen wir noch den

Slogan: Der Kongruenz mod n in ℤ entspricht die Gleichheit in ℤ_{n}.

2.26 Definitionen : Ein kommutativer Ring K mit 1 ≠ 0 heißt ein Körper, wenn K^{∗} := K \ {0} aus Einheiten besteht. Ein endlicher Körper wird auch Galoisfeld genannt.

2.27 Beispiele :

(i) Die Menge ℚ der rationalen Zahlen ist bezüglich der Addition und Multiplikation ein Körper. Das Gleiche stellen wir im Vorgriff von der Menge ℝ der reellen Zahlen fest .^{5}

(ii) Wenn p eine Primzahl ist, so ist ℤ_{p} ein Galoisfeld der Ordnung p. Denn: Nach 2.24 (ii) ist |ℤ_{p}^{∗}| = p − 1 und daher ℤ_{p}^{∗} = ℤ_{p} \ {0}. Wegen 2.24 (i) besteht also ℤ_{p} \ {0} aus lauter Einheiten.

(iii) Auf der Menge ℝ^{2} definieren wir folgendermaßen eine Addition und eine Multiplikation: (a, b) + (c, d) := (a + c, b + d), (a, b) · (c, d) := (ac − bd, ad + bc).

Es ist leicht nachzuprüfen, dass (ℝ^{2}, +, ·) ein Körper ist, der sogenannte Körper ℂ der komplexen Zahlen.

Statt mit Zahlenpaaren (a, b) wird gewöhnlich mit Ausdrücken der Form a + ib gearbeitet, also in dem durch den Körperisomorphismus (a, b) ↦ a + ib, (a, 0) ↦ a, (0, 1) ↦ i = 1 · i festgelegten Bild, das ebenfalls mit ℂ bezeichnet wird.

Es ist (0, 1)·(0, 1) = (−1, 0), also i^{2} = −1. Sei z := a+ib ∈ ℂ. \overline{z} := a−ib heißt die zu z konjugiert-komplexe Zahl (oder die Konjugierte von z). Re z := a heißt der Realteil von z, Im z := b der Imaginärteil von z.

5Während sich der Körper ℚ als Menge der Brüche aus dem Ring ℤ leicht konstruieren lässt, werden zur Konstruktion von ℝ über die algebraischen Methoden hinaus zusätzlich analytisch-topologische Hilfsmittel benötigt, die von unserer Systematik her in das dritte Kapitel gehören. Es sei uns aber gestattet, ℝ bereits hier (wie auch im Beispiel zu 1.10)

in naiver Weise für Beispiele zu gebrauchen.

Wenn die Elemente von ℂ gemäß dem Beispiel von Seite 24 unten als Punkte in einem rechtwinkligen, rechtshändigen Cartesischen Koordinatensystem dargestellt werden – man spricht dann auch von der Darstellung in der Gaußschen Ebene, die horizontal verlaufende Achse wird reelle, die vertikale imaginäre Achse genannt –, so ergibt sich eine anschauliche Darstellung der Addition komplexer Zahlen, wie in nebenstehender Figur gezeigt.

Addition in ℂ

Diese Situation müsste aus der Physik von der Addition der Kräfte (im sog. Kräfteparallelogramm) her bekannt sein. Der Übergang zum konjugiert komplexen Wert bedeutet in diesem Kontext eine Spiegelung an der reellen Achse. Die geometrische Veranschaulichung der Multiplikation im Komplexen erfolgt am Ende des fünften Kapitels.

In ℂ gelten die Beziehungen \overline{\overline{z}} = z; z\overline{z} = (a+ib)(a−ib) = a^{2} +b^{2} = |z|^{2}, wobei |z| := \sqrt{(Re z)^{2} + (Im z)^{2}} der sogenannte Betrag von z ist, der der Länge des ”Vektors“ z entspricht; z + \overline{z} = 2 Re z; z − \overline{z} = 2i Im z.

2.28 Satz : Zu jeder Primzahl p und jedem n ∈ ℕ existiert (bis auf Isomorphie) genau ein Galoisfeld von p^{n} Elementen, bezeichnet mit 𝔽_{p^{n}}. Damit sind alle endlichen Körper aufgezählt. Der kleinste Teilkörper (sog. Primkörper) von 𝔽_{p^{n}} ist isomorph zu ℤ_{p}. Ein Beweis dieses Satzes findet sich in jedem Lehrbuch der Algebra. Endliche Körper sind für Informatiker z.B. im Kontext der Codierungstheorie interessant.

2.29 Definitionen : Ein Körper K heißt angeordnet, wenn es P ⊂ K^{∗} so gibt, dass

(i) ⋀_{x∈K^{∗}} x ∈ P ⊔ −x ∈ P und

(ii) ⋀_{a,b∈P}(a + b ∈ P ∧ ab ∈ P) gilt.

Dann heißen P Positivitätsbereich, seine Elemente positiv und die Elemente von −P := {x : −x ∈ P } negativ. Wir schreiben a < b, wenn b − a ∈ P gilt.

2.30 Definitionen : Eine Relation ρ auf einer Menge M heißt eine Ordnung auf M, wenn sie reflexiv, transitiv und antisymmetrisch (d.h. xρy ∧ yρx → x = y) ist. Eine Ordnung heißt linear, wenn ⋀_{x,y∈M}xρy ∨ yρx

gilt. Eine linear geordnete Menge heißt auch Kette.

2.31 Beispiele :

(i) Die natürliche Ordnung ≤ auf der Menge ℕ ist linear. Die Teilbarkeitsrelation auf ℕ ist eine nichtlineare Ordnung.

(ii) Die Inklusion ⊂ ordnet Potenzmengen (i.a. nichtlinear).

(iii) Die Menge ℝ ist bezüglich der natürlichen Ordnung linear geordnet und bezüglich der Menge P := ℝ^{+} := {x ∈ ℝ : x > 0, > ist die natürliche Ordnung} angeordnet.

Achtung: Beachten Sie den Unterschied zwischen den Begriffen Ordnung und Anordnung!^{6}

2.32 Bemerkungen : Sei K angeordnet mit Positivitätsbereich P. Dann gilt:

(i) x ∈ K^{∗} := K \ {0} → x^{2} ∈ P Denn: In Körpern gilt (−1)(−1) = 1, da 0 = (−1) · 0 = (−1)(−1 + 1) = (−1)(−1) + (−1) · 1 = (−1)(−1) + (−1) gilt, (−1)(−1) also das additive Inverse von −1 ist. Mithin gilt auch für −x ∈ P x^{2} = (−x)^{2} ∈ P ist.

(ii) 1 ∈ P, n · 1 ∈ P für alle n ∈ ℕ.

Denn: Da nach 2.26 im Körper 1 ≠ 0 ist, gilt 1 ∈ P ∨ 1 ∈ −P. Die Annahme −1 ∈ P führt nach (i) und nach (−1)(−1) = 1 auf den Widerspruch 1 ∈ P ∩ −P.

(iii) K ist die disjunkte Vereinigung von P, −P und 0

(iv) Durch b − a ∈ P ↔: a < b wird eine lineare Ordnung ≤ der Menge K induziert mit den folgenden Eigenschaften:

x > 0 ∧ xy > 0 → y > 0 ,
x > 0 → x^{−1} > 0 ,

6Jede Menge lässt sich ordnen, nach dem Auswahlaxiom sogar wohlordnen (siehe 2.38).

Aber nicht jeder Körper kann angeordnet werden (siehe 2.32 (v)).

0 < x < y → 0 < y^{−1} < x^{−1} .

Denn: Sei y ≤ 0 angenommen. Wenn y = 0 ist, so ist xy = 0 (Widerspruch). Wenn aber y < 0 ist, so ist −xy ∈ P und (nach Voraussetzung) xy ∈ P (Widerspruch zu (iii)). Die beiden restlichen Implikationen beweisen Sie bitte übungshalber selbst!

(v) ℂ kann nicht angeordnet werden, 𝔽_{p} kann nicht angeordnet werden. Denn: Es müsste sonst in ℂ wegen (i) i^{2} ∈ P gelten. Nun ist aber −1 ∉ P! In 𝔽_{p} gilt p·1 = 0, aber nach (ii) wäre p·1 ∈ P (Widerspruch!).

2.33 Definitionen : Es seien K ein Körper, \overline{K} ein angeordneter Körper mit Positivitätsbereich \overline{P} (z.B. ℝ angeordnet bezüglich der natürlichen Ordnung ≤). Eine Abbildung | | : K → \overline{P} ∪ \{0\} heißt ein Absolutbetrag auf K, wenn

(i) |x| = 0 ↔ x = 0 ,

(ii) |xy| = |x||y| und

(iii) |x + y| ≤ |x| + |y|

für alle x, y ∈ K gelten. Die Beziehung (iii) heißt Dreiecksungleichung.

2.34 Bemerkungen :

(i) Der in 2.27 (iii) für komplexe Zahlen definierte Betrag ist ein Absolutbetrag im Sinne der Definition in 2.33. Denn: Eigenschaft (i) ist klar und es gilt

|(a + ib)(c + id)| = \sqrt{(ac − bd)^{2} + (ad + bc)^{2}}
= \sqrt{(a^{2} + b^{2})(c^{2} + d^{2})}
= |a + ib||c + id| .

Da (ad − bc)^{2} ≥ 0 ist, gilt 2abcd ≤ a^{2}d^{2} + b^{2}c^{2} und mithin a^{2}c^{2} + 2abcd+b^{2}d^{2} ≤ a^{2}c^{2} +a^{2}d^{2} +b^{2}c^{2} +b^{2}d^{2}. Ziehen wir auf beiden Seiten die Quadratwurzel, so erhalten wir ac + bd ≤ \sqrt{(a^{2} + b^{2})(c^{2} + d^{2})}. Daraus folgt \sqrt{(a + c)^{2} + (b + d)^{2}} ≤ \sqrt{a^{2} + b^{2}}+\sqrt{c^{2} + d^{2}}, also Eigenschaft (iii).

(ii) Im Dreieck ist die Summe der Länge zweier Seiten größer gleich der Länge der dritten, daher der Name ”Dreiecksungleichung“ für (iii) (vgl. die Figur S.61).

(iii) |1| = | − 1| = 1. Denn: Wegen 2.33 (ii) gilt |x| = |x · 1| = |x| · |1| und somit |1| = 1. Wenn im Körper x^{2} = 1 gilt, also 0 = (x + 1)(x − 1), so ist wegen der Nullteilerfreiheit x = ±1.

(iv) |x − y| ≤ |x| + |y|.

Denn: Es gilt |x − y| = |x + (−y)| ≤ |x| + | − y| = |x| + |y|.

(v) |x| − |y| ≤ |x ± y|. Denn: Mit u := x + y und v := −y gilt |x| = |u + v| ≤ |u| + |v| = |x + y| + |y|, also |x| − |y| ≤ |x + y|. Mit u := x − y und v := y erhalten wir analog |x| − |y| ≤ |x − y|.

(vi) Wenn K auch angeordnet ist, so induziert die Anordnung einen Absolutbetrag mittels

| a| := \{ \begin{matrix}a & für a > 0 \\ 0 & für a = 0 \\ −a & für a < 0 \end{matrix}

Denn: Prüfe die Eigenschaften (i), (ii), (iii) von 2.33 nach!

(vii) Für den nach (v) induzierten Absolutbetrag gilt |x| − |y| ≤ ||x| − |y|| ≤ |x ± y|. Denn: Die rechte Ungleichung folgt unmittelbar aus 2.33(iii) und 2.34(iii). Nach 2.34(iv) gilt |x| − |y| ≤ |x ± y|. Wenn wir hierin x und y vertauschen, so erhalten wir −(|x| + |y|) = |y| − |x| ≤ |y ± x| = |x ± y|, also ||x| − |y|| ≤ |x ± y|.

2.35 Definition : Ein angeordneter Körper K heißt archimedisch angeordnet, wenn das Axiom des Archimedes gilt: ⋀_{a,b∈K,a>0} ⋁_{n∈ℕ}na > b.

2.36 Bemerkungen : Die natürliche Anordnung in ℝ ist archimedisch. Daher gelten dort:

(i) ∀x ∈ ℝ^{+} ∪ {0} ∃_{1}n_{x} ∈ ℕ ∪ {0} : n_{x} ≤ x < n_{x} + 1 (Existenz von ⌊x⌋, floor in math.h in C). Denn: Wegen der Archimedizität von ℝ kann x durch n^{∗} · 1 überschritten werden: n^{∗} · 1 > x. Nimm das kleinste solche n^{∗}, setze n_{x} := n^{∗} − 1 und setze fort auf ℝ^{−}.

(ii) ∀ϵ > 0 ∃n ∈ ℕ : \frac{1}{n} < ϵ. Denn: ∃n ∈ ℕ : n · 1 > \frac{1}{ϵ}.

(iii) Für x ≥ −1 und n ∈ ℕ gilt (1 + x)^{n} ≥ 1 + nx (Bernoullische Ungleichung) . Beweis durch vollständige Induktion: Nach Induktionsannahme und nach Voraussetzung ist (1+x)^{n+1} ≥ (1+nx)(1+x) = 1+(n+1)x+x^{2} ≥ 1 + (n + 1)x.

Slogan: Bernoulli ist abgehackter Binomi.

(iv) b > 1 → ∀a ∈ ℝ ∃n ∈ ℕ : b^{n} > a. Denn: Wir setzen x := b−1, und somit ist x > 0, also ∃n ∈ ℕ : nx > a − 1 wegen der Archimedizität von ℝ. Also ist b^{n} = (1 + x)^{n} ≥ 1 + nx > a.

(v) 0 < b < 1 → ∀ϵ > 0 ∃n ∈ ℕ : b^{n} < ϵ. Denn: Wegen 2.32(iv) impliziert die linke Seite b^{−1} > 1, also existiert nach 2.36(iv) n ∈ ℕ mit (b^{−1})^{n} > ϵ^{−1} und somit auch mit b^{n} < ϵ.

Eine reguläre Pflasterung mit Drehgruppe der Ordnung 72 auf einer orientierbaren Fläche vom Geschlecht 4.

Abschließend noch einige Ausführungen zum sogenannten Auswahlaxiom.

2.37 Satz : Sei M eine geordnete Menge. Dann sind äquivalent:

(i) Minimalbedingung, d. h., jede nichtleere Teilmenge L von M besitzt ein (in L) minimales Element. Wir sagen dann auch, dass M wohlgeordnet ist.

(ii) Wenn m_{1} ≥ m_{2} ≥ … ≥ m_{i} ≥ … eine absteigende Kette in M ist, so existiert ein n ∈ ℕ mit m_{n} = m_{n+1} = … (sog. Bedingung des Abbrechens absteigender Ketten.

(iii) Sei E eine Eigenschaft, für die gilt:

(a) E gilt für alle minimalen Elemente aus M.

(b) Wenn E für alle Elemente gilt, die einem Element m ∈ M streng vorangehen, so gilt E auch für m.

Dann gilt E für alle Elemente aus M (Induktionsbedingung).

Beweis: (i) ⟶ (ii): Sei m_{1} ≥ m_{2} ≥ … ≥ m_{i} ≥ … eine absteigende Kette in M. Wir betrachten die aus den Elementen dieser Kette gebildete Menge L := {m_{1}, m_{2}, …, m_{i}, … }. Sie ist nicht leer, also enthält L nach (i) ein minimales Element m_{k}. Wegen des Absteigens der Kette und wegen der Minimalität von m_{k} gilt a_{k} = a_{k+1} = …. (ii) ⟶ (iii): E erfülle (iii)(a) und (b) und es gelte (ii). Sei L die Teilmenge von M aller derjenigen Elemente, für die E nicht gilt. Angenommen, L sei nicht leer, also l_{1} ∈ L. l_{1} kann wegen (iii)(a) in M nicht minimal sein, also existiert wenigstens ein strikter Vorgänger in M. Unter den strikten Vorgängern von l_{1} existiert einer, der in L liegt und l_{2} genannt sei. Andernfalls wäre nämlich wegen (b) l_{1} ∉ L. Argumentiere für l_{2} so wie eben für l_{1} und folgere einen strikten Vorgänger l_{3}. So fortfahrend erhalten wir eine strikt absteigende Kette l_{1} > l_{2} > l_{3} > …, die nicht abbricht. Also ist L leer, und E gilt für alle Elemente von M. (iii) ⟶ (i): Wir wenden das Induktionsprinzip für die Eigenschaft E := “besitzt ein minimales Element “auf die Menge P(M) \ ∅ an. Die minimalen Elemente von (P(M) \ ∅, ⊂) sind genau die einelementigen Teilmengen. Für sie gilt die Eigenschaft E trivialerweise. Sei L ∈ P(M) \ ∅. Wir zeigen : Wenn E für alle echten Teilmengen von L gilt, dann gilt es auch für L. Wählen wir nämlich x ∈ L und setzen wir L \ {x} =: A, so ist x oder ein nach Induktionsannahme existierendes minimales Element von A minimal in L = A ∪ {x}. Also sind (iii)(a) und (b) für E in P(M) \ ∅ gültig, also gilt nach Voraussetzung (iii) E auf P(M) \ ∅, also gilt (i) für M. □

2.38 Satz : Folgende Aussagen sind äquivalent:

(i) (Auswahlaxiom) Sei M eine Menge. Dann existiert auf P(M) \ ∅ eine Funktion f, die jeder nichtleeren Teilmenge L von M ein Element f(L) ∈ L zuordnet.

Slogan: Das Auswahlaxiom stellt die Existenz einer Funktion sicher, welche aus jeder nichtleeren Teilmenge ein Element herausgreift.

(ii) (Satz von Zermelo oder Wohlordnungssatz) Jede Menge lässt sich wohlordnen.

(iii) (Satz von Kuratowski-Zorn oder Zornsches Lemma) Wenn jede Kette einer geordneten Menge M eine obere Schranke hat, so folgt auf jedes Element von M ein maximales Element.

Beweis: In Hewitt-Stromberg: Real and Abstract Analysis, Thm. 3.12.

2.39 Bemerkungen : Standardbeispiel für eine wohlgeordnete Menge ist (ℕ, ≤), für eine nicht wohlgeordnete Menge (ℤ, ≤). Die Verwendung des Auswahlaxioms war lange Zeit umstritten. Jedoch hat Gödel 1940 gezeigt, dass ein Axiomensystem der Mengenlehre mit Auswahlaxiom und Kontinuumshypothese relativ widerspruchsfrei zu dem genannten Axiomensystem ohne die beiden letzteren Axiome ist.

68 D. Garbe: Mathematik I für Naturwissenschaftliche Informatik