Musterlösung zur 1.Übung  Seite 1

Universität des Saarlandes

Fachbereich 9, Mathematik Prof. Dr. R. Berger

�

Musterlösung zur 1. Übung der Linearen Algebra I, WS 1998/99

Lösung zur Aufgabe 5:

a) Sei n die Anzahl der Elemente von X und Y. Sei f surjektiv. Angenommen, f sei nicht injektiv. Dann gibt es x_{1} ≠ x_{2} ∈ X mit f(x_{1}) = f(x_{2}). Dann ist die Anzahl der Elemente von f(X) kleiner als n und f nicht surjektiv, was ein Widerspruch ist. Sei f injektiv. Jedes Element von X hat unter f ein anderes Bild in Y, d.h. |Y | ≥ |f(X)| ≥ n. Also hat f(X) genau n Elemente und f ist surjektiv.

b) Aus Teil a) sieht man, daß X unendlich viele Elemente enthalten muß.

(i) f : ℕ → ℕ : n↦2n (ii)f : ℕ → ℕ : n↦ \{ \begin{matrix}\frac{n}{2}, & n gerade \\ \frac{n−1}{2}, & n ungerade \end{matrix}

Lösung zur Aufgabe 6:

a) Sei V := ⋂_{U∈𝔐}U. Wegen ∀ U ∈ 𝔐 : e ∈ U ist e ∈ V, d.h. V ≠ ∅. Seien x, y ∈ V beliebig. Dann

gilt ∀ U ∈ 𝔐 : x, y ∈ U, also ∀ U ∈ 𝔐 : x ∘ y^{−1} ∈ U, und da alle U Untergruppen von G sind, gilt x ∘ y^{−1} ∈ V. Also erfüllt V das Untergruppenkriterium (1.5.4), ist also Gruppe.

b) Was ist der leere Schnitt?? Wie kann man das sinnvoll definieren? Eine Möglichkeit ist V := ⋂_{U∈∅} U = ∅ ist keine Gruppe, da V kein Einselement enthält. Also ist die kleinste Gruppe

überhaupt G = {e}. Man kann jedoch, was meistens gemacht wird, auch den leeren Schnitt als die gesamte Gruppe definieren ⋂_{U∈∅} U := G, um diesem Problem zu entkommen.

c) 𝔐 kann überabzählbar unendlich viele Elemente enthalten.

d) Wegen M ⊂ G ist G sicherlich eine Gruppe, welche die Menge M umfaßt, d.h. der Schnitt ist nicht leer und nach (a) eine Gruppe.

Lösung zur Aufgabe 7:

In 1.6.2 der Vorlesung wurde a^{n+1} := a^{n} ∘ a für alle n ∈ ℕ_{0} und a^{0} := e definiert.

a) Der Beweis erfolgt in mehreren Schritten:

(i) Beh.: Sei n ∈ ℕ_{0}. Dann gilt a ∘ a^{n} = a^{n+1} = a^{n} ∘ a (”Kommutativität”) Beweis durch vollständige Induktion: n = 0 n = 0 n = 0: a ∘ e = a^{1} = e ∘ a klar!

n → n + 1 n → n + 1 n → n + 1: a^{(n+1)+1} =^{Def.} (a^{n+1}) ∘ a =^{IV} (a ∘ a^{n}) ∘ a = a ∘ (a^{n} ∘ a) = a ∘ a^{n+1}

(ii)\underline{Fall n, m ≥ 0:} Vollständige Induktion nach n n = 0 n = 0 n = 0: a^{0+m} = a^{m} = e ∘ a^{m} = a^{0} ∘ a^{m}.

n → n + 1 n → n + 1 n → n + 1: a^{(n+1)+m} = a^{n+(1+m)} =^{IV} a^{n} ∘ a^{m+1} =^{(i)} a^{n} ∘ (a ∘ a^{m}) = (a^{n} ∘ a) ∘ a^{m} = a^{n+1} ∘ a^{m}

(iii) \underline{Fall n, m < 0:} a^{n} ∘ a^{m} = \underbrace{(a^{−1})^{−n}}_{a^{−n} =^{Teil b)}(a^{−1})^{n}} ∘(a^{−1})^{−m} =^{(ii)} (a^{−1})^{−n−m} = a^{n+m}

(iv) \underline{Fall n ≥ 0, m < 0:}Vollständige Induktion nach n n = 0 n = 0 n = 0: a^{0} ∘ a^{m} = a^{0+m} klar!

n → n + 1 n → n + 1 n → n + 1: a^{n+1} ∘ a^{m} =^{(i)} a ∘ a^{n} ∘ a^{m} =^{IV} a ∘ a^{n+m}

= \{ \begin{matrix}a^{n+m+1}, & falls n + m ≥ 0 \\ a ∘ (a^{−1})^{−(n+m)} = a ∘ a^{−1} ∘ (a^{−1})^{−(n+m)−1} = (a^{−1})^{−(n+m+1)}, & falls n + m < 0 \end{matrix} \} = a^{n+m+1}

(v) \underline{Fall n < 0, m ≥ 0:} Analog zu (iv) (vi) Beh.: ∀ m ∈ ℕ_{0} : (a^{n})^{m} = a^{nm}. Der Beweis geht durch Induktion nach m … (vii) Beh.: ∀ m < 0 : (a^{n})^{m} = a^{nm}. Bew.: Vorüberlegung: Wegen a^{n} ∘ (a^{−1})^{n} = a^{n} ∘ a^{−n} = a^{n−n} = e und der Eindeutigkeit des Inversen ist (a^{n})^{−1} = (a^{−1})^{n}. Deswegen gilt (a^{n})^{m} = ((a^{n})^{−1})^{−m} = ((a^{−1})^{n})^{−m} = (a^{−1})^{−nm} = a^{nm}.

b) Es ist (a ∘ b) ∘ (b^{−1} ∘ a^{−1}) = a ∘ (b ∘ b^{−1}) ∘ a^{−1} = a ∘ a^{−1} = e und da das Inverse in einer Gruppe eindeutig definiert ist, muß (b^{−1} ∘ a^{−1}) = (a ∘ b)^{−1} gelten.

c) Beh.: (a ∘ b)^{n} = a^{n} ∘ b^{n} Bew.: n = 0 n = 0 n = 0: klar!

n → n + 1 n → n + 1 n → n + 1 : (a ∘ b)^{n+1} =^{Def} (a ∘ b)^{n} ∘ (a ∘ b) =^{IV} a^{n} ∘ b^{n} ∘ a ∘ b =^{komm.} a^{n} ∘ a ∘ b^{n} ∘ b = a^{n+1} ∘ b^{n+1}

n < 0 n < 0 n < 0: (a ∘ b)^{n} = ((a ∘ b)^{−1})^{−n} = (a^{−1} ∘ b^{−1})^{−n} = (a^{−1})^{−n} ∘ (b^{−1})^{−n} = a^{n} ∘ b^{n}

Lösung zur Aufgabe 8:

a) Die Anzahl der Bijektionen ist |�_{3}| = 3! = 6.

b) Die Elemente von �_{3} sind

\begin{aligned}& 123 \\ e & 123 \\ τ_{1} & 132 \\ τ_{2} & 321 \\ τ_{3} & 213 \\ σ_{1} & 312 \\ σ_{2} & 231 \end{aligned} Die τ_{i} sind Transpositionen, d.h. Permutationen, die genau zwei Elemente vertauschen. Um die Gruppentafel zu berechnen ist es nicht nötig, alle Elemente miteinander zu multiplizieren. Bei endlichen Gruppen stehen in jeder Zeile und jeder Spalte immer alle Elemente genau einmal, d.h. es reicht hier fünf pro Spalte und Zeile zu berechnen. Aber durch Ergänzen kann man die Arbeit noch mehr vereinfachen - wie man gleich sehen wird.

Die erste Spalte und Zeile ist klar, da es sich dabei nur um Multiplikation mit dem Neutralelement handelt. Auch die σ_{i}∘τ_{j} sind sofort klar, da τ_{j} einfach zwei Elemente vertauscht. Ebenfalls klar ist, daß doppelte Vertauschung nichts vertausch, d.h. τ_{j}^{2} = e gilt. Somit sind die folgenden Einträge klar:

\begin{matrix}∘ & e & τ_{1} & τ_{2} & τ_{3} & σ_{1} & σ_{2} \\ e & e & τ_{1} & τ_{2} & τ_{3} & σ_{1} & σ_{2} \\ τ_{1} & τ_{1} & e \\ τ_{2} & τ_{2} & & e \\ τ_{3} & τ_{3} & & & e \\ σ_{1} & σ_{1} & τ_{2} & τ_{3} & τ_{1} \\ σ_{2} & σ_{2} & τ_{3} & τ_{1} & τ_{2} \end{matrix}

Rechnen wir weiter: σ_{1}^{2} = σ_{2}. Also kann in der fünften Zeile sofort das letzte fehlende Element σ_{1} ∘ σ_{2} = e eingetragen werden. Da das Inverse eindeutig ist, gilt auch σ_{2} ∘ σ_{1} = e und damit ist auch der Eintrag rechts unten in der Tabelle klar. Der Rest geht schnell:

• τ_{2} ∘ τ_{1} = σ_{1} ⇒ τ_{3} ∘ τ_{1} = σ_{2}

• τ_{3} ∘ τ_{2} = σ_{1} ⇒ τ_{1} ∘ τ_{2} = σ_{2}

• τ_{1} ∘ τ_{3} = σ_{1} ⇒ τ_{2} ∘ τ_{3} = σ_{2}

• τ_{1} ∘ σ_{1} = τ_{3} ⇒ τ_{1} ∘ σ_{2} = τ_{2}

• τ_{2} ∘ σ_{1} = τ_{1} und nun folgt der ganze Rest: τ_{2}∘σ_{2} = τ_{3}, τ_{3}∘σ_{1} = τ_{2}, τ_{3}∘σ_{2} = τ_{1}

\begin{matrix}∘ & e & τ_{1} & τ_{2} & τ_{3} & σ_{1} & σ_{2} \\ e & e & τ_{1} & τ_{2} & τ_{3} & σ_{1} & σ_{2} \\ τ_{1} & τ_{1} & e & σ_{2} & σ_{1} & τ_{3} & τ_{2} \\ τ_{2} & τ_{2} & σ_{1} & e & σ_{2} & τ_{1} & τ_{3} \\ τ_{3} & τ_{3} & σ_{2} & σ_{1} & e & τ_{2} & τ_{1} \\ σ_{1} & σ_{1} & τ_{2} & τ_{3} & τ_{1} & σ_{2} & e \\ σ_{2} & σ_{2} & τ_{3} & τ_{1} & τ_{2} & e & σ_{1} \end{matrix}

c) Die sechs Untergruppen sind U_{0} = {e}, U_{1} = {e, τ_{1}}, U_{2} = {e, τ_{2}}, U_{3} = {e, τ_{3}}, U_{4} = {e, σ_{1}, σ_{2}} und U_{5} = �_{3}. U_{0} und U_{5} sind trivialerweise Untergruppen. Aus b) wissen wir τ_{i}^{2} = e, d.h. nach 1.5.4 sind U_{1,2,3} Untergruppen. Das einzige Problem ist U_{4}: Bei endlichen Gruppen reicht es (i) e ∈ U und (ii) ∀ a, b ∈ U : a∘b ∈ U nachzuweisen: Bedingung (i) gilt trivialerweise. Ferner gilt σ_{1}^{2} = σ_{2} ∈ U_{4}, σ_{2}^{2} = σ_{1} ∈ U_{4}, σ_{1} ∘ σ_{2} = e = σ_{2} ∘ σ_{1} ∈ U_{4}. Damit sind alle Produkte in U_{4} und wir sind fertig. Wer das Untergruppenkriterium 1.5.4 anwenden möchte, kann in der Gruppentafel jeweils das Inverse nachschlagen und sämtliche Produkte a ∘ b^{−1} ausrechnen.

Lösung zur Aufgabe 9:

Da ℕ keine Gruppe ist, gibt es keine Gruppenhomomorphismen; jedoch ist ℕ ein Monoid, so daß es Monoidhomomorphismen gibt. Die folgenden vier Homomorphismen zwischen den Monoiden sind leicht zu sehen:

(i) f : ℕ → G : n↦ \{ \begin{matrix}n, & n gerade \\ n − 1, & n ungerade \end{matrix} \} surjektiv mit ker f = \{0, 1\} und Bild f = G.
(ii) f : ℕ → ℤ : n ↪ n injektiv mit ker f = {0} und Bild f = ℕ.
(iii) f : ℕ → ℚ : n ↪ n injektiv mit ker f = {0} und Bild f = ℕ.
(iv) f : ℕ → ℝ : n ↪ n injektiv mit ker f = {0} und Bild f = ℕ.

Man beachte daß die letzten drei Funktionen verschieden sind, da sie verschiedene Wertebereiche haben. In den Fällen (i)-(iii) gibt es aber sogar bijektive Abbildungen:

(i) f : ℕ → G : n↦2n
(ii) f : ℕ → ℤ : n↦ \{ \begin{matrix}−\frac{n}{2}, & n gerade \\ \frac{n+1}{2}, & n ungerade \end{matrix}

Bis hierher läßt es sich leicht nachrechnen, aber nun wird es schwer und ich verweise auf die Literatur (Forster, Analysis I §9). Kurz angedeutet gehen die Beweise folgendermaßen:

(iii)

Zuerst werden alle Brüche zwischen 0 und 1 nach Größe sortiert aufgeschrieben. Hierdurch läßt sich jedem solchen Bruch eineindeutig eine natürliche Zahl zuordnen, d.h. es gibt eine Bijektion zwischen ℕ und {b ∈ ℚ|0 ≤ b < 1}. Dies kann man für alle Intervalle machen, von denen es ℕ viele gibt. Insgesamt haben wir also abzählbar unendlich viele abzählbar unendliche Mengen und wie man leicht zeigt, sind das wieder abzählbar viele Elemente.

(iv)  Man benutze Cantors Diagonalverfahren.

Quintessenz: Es gibt mindestens zwei verschiedene Arten von Unendlichkeit, nämlich abzählbar (bijektiv zu ℕ) und überabzählbar unendlich (nicht bijektiv zu ℕ). Die Aufgabe 4 (b) ist also ungenau formuliert. Man benötigt eine Fallunterscheidung: Ob ein Bus mit abzählbar oder überabzählbar unendlich vielen Gästen kommt. Nur im ersten Fall kann man alle Gäste unterbringen!