 \(\begingroup\)
Gruppenzwang XIII Da sind wir wieder mit dem nächsten Teil der unendlichen Geschichte Gruppenzwang-Reihe.
Wir haben im letzten Artikel die freien Gruppen kennen gelernt. Diesen Artikel möchte ich nutzen, um ein wichtiges Resultat über freie Gruppen zu beweisen: Den Satz von Schreier-Nielsen, der besagt, dass jede Untergruppe einer freien Gruppe selbst frei ist. Dafür werden wir einige Hilfsmittel aus der Graphentheorie kennenlernen und benutzen.
Inhalt - Graphen
- Gerichtete und ungerichtete Graphen
- Kreise, Wege, Bäume
- Quotientengraphen
- Cayley-Graphen
- Der Satz von Schreier-Nielsen
- Abschluss
Graphen
Ich kann hier keinen vollständigen Überblick über die Graphentheorie liefern. Nicht einmal eine angemessene Einführung. Ich empfehle daher allen Interessenten etwa den Artikel von jannna Warum wohnt der Nikolaus nicht im Bungalow?. Die Arbeitsgruppe Alexandria hat auch einige andere Graphentheorie-Artikel in ihrem Verzeichnis.
In diesem Artikel kann ich nur einen Crashkurs durch die allernotwendigsten Definitionen geben und ein Mindestmaß an Anschauung geben, mehr aber auch nicht.
Ein \darkblue array(\(gerichteter\) Graph)__\black ist ein Tupel \G=(V,E) aus Mengen V und E\subseteq\ V\times\ V.
Wir bezeichnen die Elemente von V auch als \darkblue\ Knoten__\black oder \darkblue\ Ecken__\black des Graphen \(daher auch das V vom englischen Wort "vertices"\).
Die Elemente von E bezeichnen wir als \darkblue\ Kanten\black__ des Graphen \(englisch "edges", daher das E\). Für v,w\in\ V sagen wir, v sei \darkblue\ adjazent__\black zu w, falls (v,w)\in\ E oder (w,v)\in\ E gilt.
Die Anschauung ist die, dass V eine Menge von Punkten ist und E eine Menge von gerichteten Verbindungen zwischen diesen Punkten. Dabei verwenden wir die Konvention, dass wir e\in\ E als gerichtete Kante von v nach w auffassen, falls e=(v,w). Die erste Komponente gibt den Start\-, die zweite den Endpunkt der Kante an.
Oft ist es unübersichtlich, zu jedem in einem Beweis vorkommenden Graphen eine eigene Bezeichnung für die Ecken\- und Kantenmenge suchen zu müssen. Die Eckenmenge eines Graphen \G werden wir daher auch einfach als V(\G), die Kantenmenge als E(\G) bezeichnen.
Es sei nochmal explizit darauf hingewiesen: Wir machen hier keine der sonst in der Graphentheorie üblichen Einschränkungen! Wir fordern weder, dass V und E endlich sind, noch dass jeder Knoten nur endlich viele Nachbarn hat o.Ä., noch verbieten wir beispielsweise, dass ein Knoten mit sich selbst verbunden ist (das ist eine so genannte "Schlinge").
\geo
x(-3,3)
y(-0.5,2)
ebene(480,200)
noaxis()
nolabel()
punktform(of)
color(blue)
# Knoten des Graphen
p(-2,0,Am2) p(-1,0,Am1) p(0,0,A0) p(1,0,A1) p(2,0,A2)
p(0,1,D) p(0,2,E) p(2,2,F)
#Hilfspunkte
p(-2.3,0,B,hide) p(2.3,0,C,hide)
p(-0.05,1.05,D1,hide) p(0.05,1.05,D2,hide)
p(-0.05,1.95,E1,hide) p(0.05,1.95,E2,hide)
p(-2.25,0.25,B1,hide) p(2.25,0.25,C1,hide)
p(2.25,2,F1,hide) p(2,1.75,F2,hide) p(2.25,1.75,FM,hide)
color(black)
pfeil(Am2,Am1) pfeil(Am1,A0) pfeil(A0,A1) pfeil(A1,A2)
pfeil(B,Am2) s(A2,C)
print(...,-2.7,0.1) print(...,+2.5,0.1)
s(D,B1) pfeil(D,Am2) pfeil(D,Am1) pfeil(D,A0) pfeil(D,A1) pfeil(D,A2) s(D,C1)
pfeil(D1,E1) pfeil(E2,D2)
pfeil(D,F) pfeil(F,E)
bogen(FM,F2,F1) s(F,F1) pfeil(F2,F)
\geooff
Beispiel für einen Graphen:
geoprint(,Graph 1)
Dass wir diese Einschränkungen nicht treffen, hat auch seine Gründe, denn die Graphen, die wir betrachten werden, werden i.A. unendlich sein, Schlingen haben und auch nicht lokal endlich sein.
Es kann natürlich vorkommen, dass in einem Graphen \G=(V,E) zu jeder Kante (v,w)\in\ E auch (w,v) eine Kante ist, d.h. dass je zwei Punkte entweder gar nicht oder in beide Richtungen verbunden sind.
Ist das der Fall, so nennen wir \G \darkblue\ ungerichtet__\black und unterscheiden ggf. nicht mehr zwischen den Kanten (v,w) und (w,v).
Zu beinahe jeder Struktur in der Mathematik gehört ein geeigneter Begriff von Morphismen. So auch hier.
Sind \G_1=(V_1, E_1) und \G_2=(V_2, E_2) Graphen, so ist ein \darkblue\ Graphenmorphismus__\black \G_1\to\G_2 ist eine Abbildung g:V_1\to V_2, sodass
\forall\ v,v'\in\ V_1: (v,v')\in\ E_1 => (g(v),g(v'))\in\ E_2.
Sind zwei Ecken in \G_1 adjazent, so sollen die Bildknoten auch in \G_2 \(in derselben Richtung\) adjazent sein.
Hat man erstmal den Begriff des Graphenmorphismus kann man wie üblich Monomorphismen, Epimorphismen und Isomorphismen definieren. Das sind genau die injektiven, die surjektiven bzw. die bijektiven Morphismen, deren Umkehrabbildung ebenfalls ein Graphenmorphismus ist.
Für später sei die Bedingung für einen Graphenmorphismus nochmal explizit aufgeschrieben: Ein \darkblue\ Graphisomorphismus__\black zwischen (V_1, E_1) und (V_2, E_2) ist eine Bijektion f: V_1\to\ V_2 ist, die
\forall\ v,v'\in\ V_1: (v,v')\in\ E_1<=>(f(v),f(v'))\in\ E_2
erfüllt.
Sind \G=(V,E) und \G||'=(V',E') zwei Graphen, so schreiben wir \G<=\G||' und nennen \G einen \darkblue\ Teilgraphen__\black von \G||', falls V\subseteq\ V' und E\subseteq\ E' gilt.
Anschaulich ist das der Fall, wenn wir aus \G||' einfach einen Teil der Ecken und der sie verbindenden Kanten auswählen und diesen Ausschnitt als eigenständigen Graphen betrachten.
Jede Teilmenge U\subseteq\ V können wir als Teilgraphen auffassen, indem wir Ecken in U durch alle die Kanten verbinden, durch die sie auch in \G verbunden sind. Man spricht hier auch vom \darkblue\ induzierten__\black Graphen oder \darkblue\ Untergraphen__\black auf U und schreibt \G[U]. Es gilt also \G[U]=(U,(U\times\ U)\cut\ E).
Kreise, Wege, Bäume
Ein endlicher \(!\) Graph \G heißt \darkblue\ Kreis__\black, falls V(\G)=menge(v_1, ..., v_n)!=\0 und E(\G) zu jedem i genau eines der beiden Paare (v_i, v_(i+1)) oder (v_(i+1), v_i) enthält und sonst keine Elemente, wobei die Indizies mod n zu lesen sind.
n heißt \darkblue\ Länge__\black des Kreises.
\geo
xy(-1.1,1.1)
ebene(200,200)
noaxis()
nolabel()
punktform(of)
p(0,0,M,hide) k(M,1,k,hide)
color(blue)
p(k,0,A) p(k,60,B) p(k,120,C) p(k,180,D) p(k,-120,E) p(k,-60,F)
color(black)
pfeil(A,B) pfeil(C,B) pfeil(C,D) pfeil(D,E) pfeil(E,F) pfeil(A,F)
\geooff
array(Ein Beispiel für einen Kreis:,geoprint(,Graph 2))
\geo
x(-2.5,2.5)
y(-0.5,0.5)
ebene(500,100)
noaxis()
nolabel()
punktform(of)
color(blue)
p(-2,0,Am2) p(-1,0,Am1) p(0,0,A0) p(1,0,A1) p(2,0,A2)
p(-2.3,0,B,hide) p(2.3,0,C,hide)
color(black)
pfeil(Am2,Am1) pfeil(Am1,A0) pfeil(A0,A1) pfeil(A1,A2)
pfeil(B,Am2) s(A2,C)
print(...,-2.5,0.1) print(...,+2.3,0.1)
\geooff
Ein Grund, weshalb wir Endlichkeit fordern, ist, dass wir z.B. folgenden Graphen nicht als Kreis bezeichnen wollen:
geoprint(,Graph 3)
Wir halten noch ein paar Konsequenzen der Definition des Kreises fest:
\ll(*)V ist endlich
\ll(*)Der leere Graph (\0,\0) ist kein Kreis. Ein Kreis der Länge 1 ist ein einzelner Knoten mit Schlinge, ein Kreis der Länge zwei ist ein Paar von Knoten, die durch zwei Kanten mit gegengerichteter Orientierung verbunden sind. \(Unsere Definition von Graphen verbietet, dass zwei verschiedene Kanten zwischen denselben Ecken in derselben Richtung verlaufen\).
Ein endlicher \(!\) Teilgraph \G_0<=\G heißt \darkblue array(gerichteter Weg)__\black, falls V(\G_0)=menge(v_0, v_1, ..., v_n) und E(\G_0)=menge((v_0, v_1), (v_1, v_2), ..., (v_(n-1), v_n)) ist.
\G_0 heißt \darkblue array(\(ungerichteter\) Weg)__\black, falls auch V(\G_0)=menge(v_0, v_1, ..., v_n) gilt, aber E(\G_0) zu jedem i=1...n genau eines der beiden Paare (v_(i-1), v_i) und (v_i, v_(i-1)) enthält und sonst keine Kanten. \(diesmal nicht mod n\)
In beiden Fällen heißt n die \darkblue\ Länge__\black des Weges.
Auch hier möchte ich ein paar Offensichtlichkeiten festhalten:
\ll(*)Ein gerichteter Weg ist auch ein ungerichteter Weg. Wir werden im Weiteren Verlauf nur von "Wegen" sprechen und explizit daraufhinweisen, falls ein Weg unbedingt gerichtet zu sein hat.
\ll(*)Ist v_0\in\ V(\G) eine Ecke von V, so ist \G_0=(menge(v_0),\0)<=\G ein Weg der Länge 0. Ein Weg der Länge 1 besteht einfach aus zwei Knoten mit genau einer Kante dazwischen.
Wege und Kreise haben bei mir nach Definition immer endliche Länge. Einige Resultate in der Theorie unendlicher Graphen gelten auch für (geeignet definierte) unendliche Wege und Kreise. Diese werden für uns aber keine Rolle spielen. Im Gegenteil: Kreise und Wege müssen endlich sein, sonst funktioniert Vieles von dem, was wir vorhaben, nicht mehr.
Und weil die entsprechenden Definitionen auch ausarten würden, lasse ich sie hier weg.
Ein Graph heißt \darkblue\ zusammenhängend__\black, falls es zu je zwei Ecken v,w einen Weg zwischen v und w gibt. \(Wenn es sogar jeweils gerichtete Wege von v nach w gibt, so spricht man auch von "stark" zusammenhängenden Graphen.\)
Da Wege stets endliche Länge haben, ist etwa \stress\ Graph 3\normal als Ganzes kein Weg. Er ist jedoch ein zusammenhängender Graph, da zwischen je zwei Punkten ein endlicher Weg existiert.
Ein Graph \G heißt \darkblue\ kreisfrei__\black oder auch \darkblue\ Wald__\black, falls keiner seiner Teilgraphen ein Kreis ist. Ist \G zusammenhängend und kreisfrei, heißt \G \darkblue\ Baum__\black.
Der \stress\ Graph 3\normal ist ein Beispiel für einen Baum.
Für eine Ecke v\in\ V heißt der größte \(bzgl. der Teilgraphrelation\) zusammenhängende Teilgraph \G_v von \G, der die Ecke v enthält, \darkblue\ array(Zusammenhangskomponente von v)__\black in \G.
Natürlich muss man sich davon überzeugen, dass es so etwas überhaupt gibt, aber das ist einfach, denn man kann die Zusammenhangskomponente \G_v von v explizit beschreiben: Die Eckenmenge ist
V_v:=menge(w\in\ V | \exists Weg zwischen v und w)
und die Kanten sind einfach alle, die schon in \G zwischen diesen Ecken vorhanden sind, d.h. die Zusammenhangskomponente ist \G_v:=\G\[||array(V_v)\].
Ein zusammenhängender Teilgraph, der v enthält, ist nach Definition bereits ein Teilgraph von \G_v.
Sind umgekehrt w,w'\in\ V_v, so gibt es Wege P,P'<=\G, die w bzw. w' mit v verbinden. Seien w=u_0, u_1, ..., u_n=v die Knoten von P und w'=u'_0, u'_1, ..., u'_m=v die von P'.
Wähle dann j als ersten Index, bei dem u_j\in V(P') ist und k der Index, für den u_j=u'_k ist. Die Ecken u_0, u_1, ..., u_j=u'_k, u'_(k-1), ..., u'_0 bilden in dieser Reihenfolge zusammen mit den Kanten von P bzw. P', die zwischen ihnen verlaufen, ein Weg von w=u_0 nach u'_0=w'. Das heißt, \G_v ist zusammenhängend. Also ist \G_v der größte zusammenhängende Teilgraph, der v enthält.
Man sieht nun sofort, dass die \G_v den Graph partitionieren: Jedes v\in\ V(\G) ist in \G_v. Ist u\in\ V(\G_v)\cut\ V(\G_w), so ist \G_v<=\G_u, da beides zusammenhängende Teilgraphen sind, die u enthalten, und \G_u der größte solche ist. Damit enthält \G_u auch v, d.h. das gleiche Argument mit vertauschten Rollen liefert \G_u<=\G_v => \G_u=\G_v. Ebenso ist \G_u=\G_w, also \G_v=\G_w.
Der erste Satz aus der Graphentheorie, den wir brauchen werden, ist folgender:
\darkred\ll(0.1)Jeder zusammenhängende Graph \G=(V,E) hat einen aufspannenden Baum, d.h. einen kreisfreien, zusammenhängenden Teilgraphen \G_0<=\G, sodass V(\G_0)=V(\G).
Das eigentlich Interessante an diesem Satz ist, dass wir \G_0 als zusammenhängend wählen könen, denn natürlich könnten wir stets den Teilgraphen (V,\0)<=(V,E) betrachten. Da er überhaupt keine Kanten hat, ist er insbesondere kreisfrei.
\blue\ Beweis:
Falls abs(V(G))<=abs(\IN) ist, könnte man das halbwegs algorithmisch machen und eine rekursive Konstruktionsvorschrift für den Baum angeben. Die Idee ist sogar recht simpel, man findet sie in jedem Graphentheorie\-Buch oder \-Skript.
Falls abs(V)>abs(\IN), wird das allerdings schwieriger. Es gibt nun zwei Alternativen, wie man etwas vom Abzählbaren ins Beliebig\-Unendliche rettet: Transfinite Induktion oder Zorns Lemma. Ich entscheide mich für Zweiteres und definiere:
\calB:=menge(B<=\G | B ist ein Baum)
Jeder einpunktige Teilgraph ohne Kanten (menge(v),\0) ist ein Baum, d.h. insbesondere, dass \calB!=\0 \(Der Graph (\0,\0) erfüllt natürlich trivialerweise die Behauptung, da wäre also nichts zu zeigen\). Die Teilgraph\-Relation ist eine partielle Ordnung auf \calB, für die wir nun Zorns Lemma anwenden werden.
Sei dafür \calK\subseteq\calB eine Kette. Wir setzen V_\inf:=union(V(B),B\in\calK) und E_\inf:=union(E(B),B\in\calK). Dann ist offenbar E_\inf\subseteq\ V_\inf\times\ V_\inf, d.h. B_\inf:=(V_\inf, E_\inf) definiert einen Teilgraphen von \G mit B<=B_\inf für alle B\in\calK.
Angenommen, es gäbe einen Kreis C<=B_\inf. Da ein Kreis nur endlich viele Ecken und Kanten hat und \calK total geordnet ist, gibt es ein B\in\calK mit C<=B. Das ist ein Widerspruch zur Kreisfreiheit von B. Also ist B_\inf kreisfrei.
Seien v,v'\in V_\inf zwei Ecken. Da \calK total geordnet ist, gibt es ein B\in\calK, sodass v,v' beide in V(B) liegen. Dann gibt es einen Weg P<=B<=B_\inf zwischen v und v'. Damit ist B_\inf zusammenhängend, also ein Baum und damit eine obere Schranke in \calB für die Kette \calK.
Die Voraussetzungen für das Lemma von Zorn sind damit gegeben. Wir erhalten einen maximalen Baum B_max=(V_max, E_max)<=\G.
Dieser muss bereits aufspannend sein: Da wie oben festgestellt, die Einpunktgraphen auch Bäume sind, enthält B_max mindestens eine Ecke v_0. Gäbe es eine Ecke v_n\in\ V\\V_max, so könnten wir einen Weg P=(menge(v_0, v_1, ..., v_n), ...) <=\G finden, da \G zusammenhängend ist. oBdA nehmen wir an, dass v_n von v_0 aus der erste Knoten in diesem Weg ist, der außerhalb von V_max liegt, d.h. v_i\in\ V_max für i Quotientengraphen
Wir schauen uns jetzt eine Konstruktion analog zu Quotientenstrukturen in anderen Kategorien an und wie man sie auf Graphen übertragen kann.
Ganz allgemein sei dazu ~ eine Äquivalenzrelation auf V. Dann betrachten wir \G^-=(V^-, E^-) mit V^-:=V\/~ und E^-:=menge((v^-, w^-) | \exists v'~v, w'~w: (v',w')\in\ E), d.h. wir definieren eine Kante von der Äquivalenzklasse v^- zu w^-, wenn es mindestens zwischen zwei Vertretern der Klassen eine Kante in dieser Richtung gibt.
Wir nennen \G^- den \darkblue\ Quotientengraphen__\black von \G nach ~.
Mit dieser Definition induziert die Projektionsabbildung V\to V^- einen Graphenmorphismus \G\to\G^-. Es ist eine sehr nützliche Konvention Bilder unter diesem Morphismus stets durch einen Querstrich zu kennzeichnen. So ist eine Kante in \G^- etwa stets von der Form e^- für ein geeignetes e\in\ E(\G).
Es gibt nun verschiedene Methoden, sich diese Äquivalenzrelation zu beschaffen. Eine für uns wesentliche Möglichkeit ist, eine Gruppenoperation zu betrachten:
Eine Operation der Gruppe G auf der Menge V ist eine \darkblue array(Operation auf dem Graphen)__\black \G=(V,E), falls (v,w)\in\ E <=> (\void^g\.v,\void^g\.w)\in\ E für alle g\in\ G, v,w\in\ V gilt, d.h. falls die Bijektion, die das Element g\in\ G auf V(\G) induziert, ein Automorphismus von \G ist.
Ist eine solche Operation gegeben, so ist auf V natürlich die Bahnenzerlegung definiert, d.h. v~w <=> \exists g\in\ G: \void^g\.v=w.
Den so definierten Quotientengraphen werden wir mit \G\/G bezeichnen.
Eine andere Methode ist es, gezielt irgendwelche vorgegebenen Eckenmengen zu je einem Punkt zu identifizieren, d.h. wir nehmen uns paarweise disjunkte Teilmengen V_i\subseteq\ V und definieren die Relation so, dass jedes V_i eine Klasse wird und die restlichen Klassen einelementig sind:
v~w :<=> v=w \or \exists i\in\ I: menge(v,w)\subseteq\ V_i
Anschaulich bedeutet das Bilden eines solchen Quotientengraphen, dass jedes V_i auf einen Punkt zusammengezogen wird. Entstehen dabei Mehrfachkanten, so werden diese durch eine einzelne Kante pro Richtung ersetzt. Zwischen Punkten außerhalb der V_i verändert sich jedoch nichts, sie sind in \G^- genau dann verbunden, wenn sie es in \G sind.
Hier ein Beispiel, in dem die hellblauen Punkte zu einem kontrahiert werden:
\geo
x(0,5)
y(0,2)
ebene(500,200)
noaxis()
nolabel()
punktform(of)
replace()
color(0099ff)
p(0,0,A) p(0,1,B) p(0,2,C)
color(blue)
p(1,1,D) p(2,1,E) p(2,2,F)
color(black)
pfeil(A,D) pfeil(D,B) pfeil(D,C)
pfeil(D,E) pfeil(E,F) pfeil(F,D)
print(\big Vorher,1,2)
color(0099ff)
p(3,1,ABC)
p(3.1,1.05,ABC1,hide) p(3.1,0.95,ABC2,hide)
p(3.9,1.05,D1,hide) p(3.9,0.95,D2,hide)
color(blue)
p(4,1,D) p(5,1,E) p(5,2,F)
color(black)
pfeil(ABC1,D1) pfeil(D2,ABC2)
pfeil(D,E) pfeil(E,F) pfeil(F,D)
print(\big Nachher,4,2)
\geooff
geoprint()
In ziemlich ähnlicher Weise wie \ref(0.1) beweisen wir jetzt dieses Resultat, welches uns ebenfalls noch zu Gute kommen wird:
\darkred\ll(0.3)Sei \G=(V,E) ein Graph und G eine Gruppe, die auf diesem Graphen operiert. Setze \G^-:=\G\/G und bezeichne mit \pi: \G\to\G^- die kanonische Abbildung v\mapsto v^-. Sei weiter B^~<=\G^- ein Wald. Dann existiert ein Wald B<=\G, sodass \pi_\|B ein Graphenisomorphimus B\to B^~ ist. Ist B^~ zusammenhängend, so kann auch B zusammenhängend gewählt werden.
Dieser Satz sagt uns also, dass wir Bäume und Wälder in \(speziellen\) Quotientengraphen \G^- zu Bäumen bzw. Wäldern von \G liften können.
\blue\ Beweis:
Wir beschränken uns sofort auf den Fall, dass B^~ zusammenhängend ist. Ansonsten betrachten wir jede Zusammenhangskomponente einzeln, finden jeweils einen Lift des Baumes und kriegen durch Vereinigung einen Lift des ganzen Waldes.
Auch hier werden wir von einem konstruktiven Beweis, wie er im endlichen und abzählbaren Falle durchaus denkbar wäre, absehen zu Gunsten eines zwar zornigen, aber dafür allgemeinen Beweises. Wir setzen:
\calB:=menge(B<=\G | array(B ist Baum \and B^-<=B^~ \and \pi ist injektiv auf V(B) \and;\forall\ v\,v'\in\ V(B): (v,v')\in\ E(B)<=>(v^-, v'^-)\in\ E(B^~)))
Für jede Ecke v^-\in\ V(B^~) ist jeder einpunktige Graph (menge(v),\0) ein Baum, also auch ein Element von \calB. \(vom Trivialfall des leeren Graphen sehen wir auch hier ab\). Also ist \calB!=\0.
Ist \calK\subseteq\calB eine Kette, so ist B_\inf:=union(B,B\in\calK) ein Baum, wie wir im Beweis von \ref(0.1) gesehen haben.
Sind v,v'\in V(B_\inf) mit \pi(v)=\pi(v'), so gibt es ein B\in\calK, sodass v,v'\in\ V(B) sind. Dann folgt aus B\in\calB und der Injektivität von \pi_\|B sofort v=v', d.h. \pi_\|B_\inf ist ebenfalls injektiv.
Da alle V(B) und E(B) durch \pi in V(B^~) bzw. E(B^~) abgebildet werden, trifft das auch auf union(V(B),B\in\calK)=V(B_\inf) und union(E(B),B\in\calK)=E(B_\inf) zu, also gelten \pi(B_\inf)<=B^~ und (v,v')\in\ E(B_\inf) => (v^-, v'^-)\in\ E(B^~) bereits.
Sind umgekehrt v,v'\in\ V(B_\inf) zwei Ecken mit (v^-, v'^-)\in\ E(B^~), so gibt es wieder ein B\in\calK mit v,v'\in\ V(B), d.h. es gilt auch (v,v')\in\ E(B)\subseteq\ E(B_\inf) nach Vorausetzung an B.
=> B_\inf\in\calB => Zorns Lemma ist anwendbar.
Wir erhalten somit ein maximales Element B_max in \calB. Es bleibt nun zu zeigen, dass B_max der Baum ist, dessen Existenz wir behaupten.
Dazu stellen wir fest, dass B_max nichtleer ist, da wie gesagt auch die einpunktigen Graphen in \calB enthalten sind. D.h. wir können eine Ecke v\in\ V(B_max) wählen.
Angenommen, es gäbe eine Ecke w^-\in\ V(B^~)\\V((B_max)^-). Da B^~ ein Baum also zusammenhängend ist, können wir wie schon in \ref(0.1) oBdA annnehmen, dass v^- und w^- durch eine Kante e^~ verbunden sind.
Wir brauchen eine Kante in \G, die e^~ entspricht, um den Widerspruch von \ref(0.1) zu wiederholen. Dafür verwenden wir nun endlich, dass \G der Quotientengraph nach einer Gruppenwirkung ist.
Dass e^~ eine Kante in \G zwischen v^- und w^- ist, heißt, dass es Ecken v' und w' gibt, sodass v'~v, w'~w und v',w' adjazent in \G.
Das heißt, dass es Elemente g,h\in\ G gibt, sodass v'=\void^g\.v und w'=\void^h\.w. => \void^g\.v und \void^h\.w sind adjazent => v und \void^(g^(-1)\.h)\.w sind adjanzent.
w'':=\void^(g^(-1)\.h)\.w ist ein Element der Klasse w^-. Wir können unseren Baum B_max also durch die Ecke w und die Kante zwischen v und w'' vergrößern.
Das ergibt den gewünschten Widerspruch zur Maximalität von B_max in \calB. Also wissen wir, dass \pi_\|B_max surjektiv als Abbildung V(B_max)\to\ V(B^~) ist.
Die Bedingungen, mit denen wir \calB definiert haben, sichern uns, dass \pi_\|B_max tatsächlich ein Graphisomorphismus B_max\to\ B^~ ist.
\blue\ q.e.d.
Auch auf die zweite Methode, Quotientengraphen zu erhalten, gehen wir noch genauer ein und zeigen Folgendes:
\darkred\ll(0.4)Sei \G=(V,E) ein Graph. Sei menge(V_i | i\in\ I) eine Partition der Eckenmenge V, ~ die zugehörige Äquivalenzrelation und bezeichne \G^- den Quotientengraphen \G\/~. Ist \G kreisfrei und sind die Untergraphen \G[V_i]<=\G zusammenhängend, so hat jeder Kreis in \G^- die Länge 1.
Wir werden dieses Lemma brauchen, um zu zeigen, dass ein Quotientengraphen eines Baumes unter den gegebenen Bedingungen selbst ein Baum wird, wenn man alle Schlingen entfernt.
\blue\ Beweis:
Sei C^~<=\G^- ein Kreis mit n>=2 Ecken (v_1)^-, ..., (v_n)^-, wobei (v_i)^- mit (v_(i+1))^- in \G^- adjazent ist \(Indizes wieder mod n gelesen\).
Die Klassen (v_i)^- sind dann jeweils solche V_j aus der Partition.
Nach Definition der Quotientengraphen gibt es Elemente u_i und w_i für i=1...n, die in (v_i)^- liegen, sodass w_1 mit u_2, w_2 mit u_3, ..., w_(n-1) mit u_n und w_n mit u_1 verbunden ist.
Da der Teilgraph \G[||(v_i)^-] zusammenhängend ist, gibt es Wege P_i, die u_i mit w_i verbinden und nur Ecken aus (v_1)^- benutzen. Diese Wege könnten Länge 0 haben, nämlich wenn u_i=w_i für ein i gilt.
Diese Wege zusammen mit den Kanten zwischen w_i und u_(i+1) bilden einen Kreis C in \G. Das ist anschaulich klar und eigentlich nicht schwer zu beweisen. Es erfordert trotzdem ein paar Fallunterscheidungen und ist insgesamt einfach weder hübsch aufzuschreiben noch gewinnbringend für uns. Daher lasse ich das einfach weg, wer mag, betrachte dies als Übung.
Auf jeden Fall liefert uns dieses C einen Widerspruch zur Kreisfreiheit von G.
\blue\ q.e.d.
Cayley-Graphen
Nachdem wir nun im Höchsttempo die für uns wichtigen Begriffe der Graphentheorie eingeführt haben, möchte ich die Graphen definieren, welche für den Gruppentheoretiker den besonderen Reiz ausmachen: Die Cayley-Graphen.
Sei dafür G eine Gruppe und S\subseteq\ G eine beliebige Teilmenge. Wir definieren den \darkblue\ Cayley\-Graphen__\black \G_array(G\,S) als Graph mit V(\G_array(G\,S)):=G und E(\G_array(G\,S)):=menge((g,h)\in\ G\times\ G | g^(-1)\.h\in\ S)=menge((g,gs) | g\in\ G, s\in\ S).
Der Cayley\-Graph \G_array(\IZ_n\,\{1\}) ist so zum Beispiel ein Kreis der Länge n, \G_array(\IZ\,\{1\}) ist der \stress Graph 3\normal. Auch andere bekannte Graphen treten wieder auf:
\geo
x(-0.1,4.1)
y(-0.1,1.6)
ebene(250,125)
noaxis()
punktform(of) nolabel()
color(blue)
p(0,1.5,v3) p(2,1.5,v1) p(4,1.5,v5)
p(0,0.0,v0) p(2,0.0,v4) p(4,0.0,v2)
color(black)
s(v0,v3) s(v0,v1) s(v0,v5)
s(v4,v3) s(v4,v1) s(v4,v5)
s(v2,v3) s(v2,v1) s(v2,v5)
print(0,0.1,0)
print(4,2.1,0)
print(2,4.1,0)
print(3,0.1,1.7)
print(1,2.1,1.7)
print(5,4.1,1.7)
\geooff
\G_array(\IZ_6\,\{1\,3\,5\}) ist etwa der \(ungerichtete!\) vollständige, bipartite Graph K^array(3\,3):
geoprint()
\geo
xy(-3.6,3.4)
ebene(300,300)
noaxis()
nolabel()
makro(vert, \
punkt(%1,%2,v_%1%2) \
)
punktform(of) color(blue)
for(i,-4,4,1,\
for(j,-4,4,1,\
vert(i,j) \
)\
)
makro(edges, \
replace() \
konstante(x1,%1+0.1) konstante(y1,%2) p(x1,y1,A,hide) \
konstante(x2,%1+0.9) konstante(y2,%2) p(x2,y2,B,hide) \
pfeil(A,B) \
konstante(x1,%1) konstante(y1,%2+0.1) p(x1,y1,A,hide) \
konstante(x2,%1) konstante(y2,%2+0.9) p(x2,y2,B,hide) \
pfeil(A,B) \
konstante(x1,%1-0.1) konstante(y1,%2) p(x1,y1,B,hide) \
konstante(x2,%1-0.9) konstante(y2,%2) p(x2,y2,A,hide) \
pfeil(A,B) \
konstante(x1,%1) konstante(y1,%2-0.1) p(x1,y1,B,hide) \
konstante(x2,%1) konstante(y2,%2-0.9) p(x2,y2,A,hide) \
pfeil(A,B) \
replace() \
)
color(black)
for(i,-3,3,1,\
for(j,-3,3,1,\
edges(i,j) \
)\
)
\geooff
Der Cayley\-Graph von \IZ^2 mit S=menge((1,0),(0,1)) ist ein unendliches, zweidimensionales, gerichtetes Gitter:
geoprint()
\geo
xy(-4,4)
ebene(500,500)
noaxis()
konst(s,2)
makro(xcoord, \
konst(x,0) konst(i,0) \
konst(a,s) konst(b,0) \
konst(u,-a) konst(v,-b) \
iterate(c,%1,none, konst(x,x+power(2,-i)*c) konst(i,i+1)) \
)
makro(ycoord, \
konst(y,0) konst(i,0) \
konst(a,0) konst(b,s) \
konst(u,-a) konst(v,-b) \
iterate(c,%1,none, konst(y,y+power(2,-i)*c) konst(i,i+1)) \
)
makro(vert,\
xcoord(%1) ycoord(%1) \
punkt(x,y,v_%1) \
)
nolabel()
punktform(of) color(blue)
punkt(0,0,v_)
vert(a) vert(u) vert(b) vert(v)
vert(aa) vert(ab) vert(av)
vert(uu) vert(ub) vert(uv)
vert(ba) vert(bu) vert(bb)
vert(va) vert(vu) vert(vv)
vert(aaa) vert(aab) vert(aav)
vert(aba) vert(abu) vert(abb)
vert(ava) vert(avu) vert(avv)
vert(uuu) vert(uub) vert(uuv)
vert(uba) vert(ubu) vert(ubb)
vert(uva) vert(uvu) vert(uvv)
vert(baa) vert(bab) vert(bav)
vert(buu) vert(bub) vert(buv)
vert(bba) vert(bbu) vert(bbb)
vert(vaa) vert(vab) vert(vav)
vert(vuu) vert(vub) vert(vuv)
vert(vva) vert(vvu) vert(vvv)
color(black)
#pfeil(v_x,v_xa) pfeil(v_x,v_xb)
pfeil(v_,v_a) pfeil(v_,v_b)
pfeil(v_a,v_aa) pfeil(v_a,v_ab)
pfeil(v_u,v_) pfeil(v_u,v_ub)
pfeil(v_b,v_ba) pfeil(v_b,v_bb)
pfeil(v_v,v_va) pfeil(v_v,v_)
pfeil(v_aa,v_aaa) pfeil(v_aa,v_aab)
pfeil(v_ab,v_aba) pfeil(v_ab,v_abb)
pfeil(v_av,v_ava) pfeil(v_av,v_a)
pfeil(v_uu,v_u) pfeil(v_uu,v_uub)
pfeil(v_ub,v_uba) pfeil(v_ub,v_ubb)
pfeil(v_uv,v_uva) pfeil(v_uv,v_u)
pfeil(v_ba,v_baa) pfeil(v_ba,v_bab)
pfeil(v_bu,v_b) pfeil(v_bu,v_bub)
pfeil(v_bb,v_bba) pfeil(v_bb,v_bbb)
pfeil(v_va,v_vaa) pfeil(v_va,v_vab)
pfeil(v_vu,v_v) pfeil(v_vu,v_vub)
pfeil(v_vv,v_vva) pfeil(v_vv,v_v)
pfeil(v_aav,v_aa)
pfeil(v_abu,v_ab)
pfeil(v_bav,v_ba)
pfeil(v_bbu,v_bb)
pfeil(v_buu,v_bu)
pfeil(v_buv,v_bu)
pfeil(v_ubu,v_ub)
pfeil(v_uuu,v_uu)
pfeil(v_uuv,v_uu)
pfeil(v_uvv,v_uv)
pfeil(v_uvu,v_uv)
pfeil(v_vuu,v_vu)
pfeil(v_vuv,v_vu)
pfeil(v_vvu,v_vv)
pfeil(v_vvv,v_vv)
pfeil(v_vav,v_va)
pfeil(v_avu,v_av)
pfeil(v_avv,v_av)
\geooff
Der Cayley\-Graph der freien Gruppe über 2 Erzeugern ist ein unendlicher Graph, der sich am besten als "Fraktal" beschreiben lässt, da der selbstähnlich ist. Wenn man Wörter der Länge <=3 zeichnet, bekommt man beispielsweise:
geoprint()
Wir halten ein paar mehr oder minder offensichtliche Fakten über Cayley\-Graphen fest:
\ll(*)\G_array(G\,G) hat alle, \G_array(G\,\0) gar keine Kanten.
\ll(*)Jeder Knoten in \G_array(G\,S) hat genau abs(S) eingehende und genau abs(S) ausgehende Kanten.
\ll(*)Es gibt genau dann Schlingen in \G_array(G\,S), wenn 1\in\ S ist.
\ll(*)\G_array(G\,S) ist ungerichtet genau dann, wenn S=S^(-1).
Wichtig ist auch folgende Feststellung: G operiert durch Linksmultiplikation auf \G_array(G\,S). Dies ist mit der Graphenstruktur verträglich, denn (xg)^(-1)\.(xh)=g^(-1)\.h, d.h. g\mapsto\ xg ist ein Graphenautomorphismus für jedes x.
Diese Operation auf V(\G_array(G\,S)) ist regulär, d.h. zu je zwei Ecken gibt es genau ein Gruppenelement, welches diese ineinander überführt. Anders formuliert: Die Operation auf den Ecken ist transitiv und frei \(eine Operation von G auf \Omega heißt frei, falls \forall\omega\forall\ g:(\void^g\.\omega=\omega=>g=1) gilt\).
Beides sind wichtige Feststellungen.
Die Operation auf den Kanten ist i.A. nicht transitiv. Es gilt für zwei Kanten
\exists\ x\in\ G: (g,h)=\void^x\.(g',h')<=> g^(-1)\.h=g'^(-1)\.h'
d.h. die Bahnen von G auf der Kantenmenge sind genau die Mengen menge((g,gs) | g\in\ G), sie stehen also in einer recht natürlichen Bijektion zu S.
Etwas weniger trivial, dafür aber wichtig, ist der folgende Satz:
\darkred\ll(1.1)Sei G eine Gruppe, S\subseteq\ G. Dann sind die Zusammenhangskomponenten von \G_array(G\,S) genau die Linksnebenklassen von braket(S). Insbesondere ist \G_array(G\,S) genau dann zusammenhängend, wenn S ein Erzeugendsystem von G ist.
\blue\ Beweis:
Die Translation mit x ist ein Graphenautomorphismus, d.h. g und h sind genau dann durch einen Weg verbunden, wenn es xg und xh sind. OBdA können wir uns daher darauf beschränken, zu zeigen, dass braket(S) die Zusammenhangskomponente von 1 ist.
Sei P=(menge(g_1, ..., g_n),...)<=\G_array(G\,S) ein Weg von g_1:=1 nach g_n:=g. Wir wählen die Nummerierung so, dass für i=1...n-1 stets
(g_i, g_(i+1))\in\ E \or (g_(i+1), g_i)\in\ E
<=> g_i^(-1)\.g_(i+1)\in\ S \or g_(i+1)^(-1)\.g_i\in\ S
<=> \exists\ s_i\in\ S: g_(i+1)=g_i*s_i \or g_(i+1)=g_i*s_i^(-1)
D.h.
\align\ g=g_n><=g_(n-1)*s_(n-1)^(+-1)
><=...
><=g_1*s_1^(+-1)*s_2^(+-1)*...*s_n^(+-1)
><=1*s_1^(+-1)*...*s_n^(+-1)\in\ braket(S).
\stopalign
Ist umgekehrt g\in\ braket(S), so existiert eine Darstellung g=t_1*...*t_n wobei t_i=s_i oder t_i=s_i^(-1) für ein geeignetes s_i\in\ S. oBdA nehmen wir an, n sei die kleinste natürliche Zahl, für die es so eine Darstellung gibt. Dann setze für i=0...n
g_i:=t_1*t_2*...*t_i
Diese Elemente von G sind alle verschieden, denn wäre g_i=g_j für j>i, so wäre 1=g_i^(-1)*g_j=t_(i+1)*...*t_j => Die Darstellung von g war nicht von minimaler Länge, da man ein Zwischenstück entfernen kann.
Es außerdem gilt g_(i-1)^(-1)\.g_i=t_i\in\ S\union\ S^(-1) für alle i=1,...,n, d.h. g_(i-1) und g_i sind adjazent. Die Ecken 1=g_0, g_1, ..., g_n=g zusammen mit eben diesen Kanten bilden also einen Weg von 1 nach g, damit liegt g auch in der Zusammenhangskomponente von 1.
\blue\ q.e.d.
Wo kommen nun die freien Gruppen ins Spiel? Jetzt kommen sie:
\darkred\ll(1.2)Sei G eine Gruppe, S\subseteq\ G. G ist genau dann frei über S, wenn \G_array(G\,S) ein Baum ist.
\blue\ Beweis:
Ist G frei über S, so wird G von S erzeugt, wie wir im letzten Artikel festgestellt haben \(das war dort \ref(1.1)\). Also ist \G_array(G\,S) wie eben gesehen schonmal zusammenhängend.
Es bleibt zu prüfen, ob \G_array(G\,S) kreisfrei ist. Angenommen, es gäbe einen Kreis der Länge n in \G_array(G\,S) dessen Ecken genau g_1, ..., g_n seien \(d.h. insbesondere nehmen wir an, dass es sich um paarweise verschiedene Elemente handelt\). Dann gibt es t_i\in S\union\ S^(-1), sodass g_(i+1)=g_i*t_i für alle i gilt \(Indizes wieder mod n gelesen\).
=> g_1=g_n*t_n=...||=g_1*t_1*t_2*...*t_n => 1=t_1*...*t_n.
t_1*...*t_n ist ein reduziertes Wort, denn wäre t_i=t||array(\small-1;i\+1\normal) für ein i=1,...,n-1, so wäre g_(i+2)=g_(i+1)*t_(i+1)=g_i*t_i*t_(i+1)=g_i, das ist ein Widerspruch, das Wort muss reduziert sein.
Ein reduziertes Wort ungleich dem leeren Wort ist in einer freien Gruppe jedoch nie gleich 1, d.h. es kann keine Kreise geben. Also \G_array(G\,S) ein Baum.
Ist umgekehrt \G_array(G\,S) ein Baum, so ist der Graph insbesondere zusammenhängend, d.h. G=braket(S). Das sagt uns, dass der von id_S: S\to G induzierte Homomorphismus F(S)\to G surjektiv ist.
Wir drehen die Argumentation von oben einfach um, um zu zeigen, dass er auch injektiv ist. Sei ein \(oBdA reduziertes\) Wort t_1*...*t_n mit t_i\in\ S\union\ S^(-1) im Kern von F(S)\to G. oBdA nehmen wir auch an, n sei die kleinste Länge, für die es solch ein Wort gibt.
Ist n>0, das Wort also nicht das leere Wort, so sind die Ecken 1,t_1, t_1*t_2, ..., t_1*t_2*...*t_(n-1) paarweise verschieden, denn ansonsten wäre t_1*...*t_i=t_1*...*t_j für ein Paar j>i => 1=t_(i+1)*...*t_j, d.h. n wäre nicht minimal.
Diese Ecken bilden einen Kreis in \G_array(G\,S), da jeweils t_i\in\ S oder t_i^(-1)\in\ S gilt. Das ist ein Widerspruch, also ist n=0, d.h. das Element des Kerns von F(S)\to G, von welchem wir ausgingen, ist das neutrale Element.
Also ist F(S)\to G injektiv und damit ein Isomorphismus. Da dabei S auf sich abgebildet wird, ist S also eine freie Basis von G, denn S ist eine freie Basis von F(S).
\blue\ q.e.d.
Der Satz von Schreier-Nielsen
Kommen wir nun endlich zum Beweis des Satzes von Schreier-Nielsen.
Dazu erinnere ich nochmal daran, was es heißt, dass eine Gruppe G \darkblue\ frei__\black \(auch "semiregulär" genannt\) auf einer Menge \Omega operiert: Das heißt, dass für alle \omega\in\Omega, g\in\ G aus \void^g\.\omega=\omega stets g=1 folgt.
Eine freie Operation haben wir eben kennengelernt: Jede Gruppe operiert frei auf der Eckenmenge von \G_array(G\,S) \(Welche Teilmenge S\subseteq\ G ist, ist dabei egal\).
Offensichtlich ist auch, die Feststellung, dass mit G auch jede Untergruppe H<=G frei auf \Omega operiert.
Was bringt uns das jetzt? Der Schlüssel zum Beweis des Satzes von Schreier-Nielsen wird folgender Satz sein:
\darkred\ll(2.1)Sei \G ein Baum, auf dem die Gruppe G operiert. Ist die Operation von G auf V(\G) frei, so ist G eine freie Gruppe.
\blue\ Beweis:
Zuerst betrachten wir den Quotientengraphen \G^-:=\G\/G. Da \G zusammenhängend ist und \G\to\G^- ein surjektiver Graphenmorphismus ist, ist nach \ref(0.2) auch \G^- zusammenhängend. Nach \ref(0.1) gibt es deshalb einen aufspannenden Baum T^~<=\G^-. Nach \ref(0.3) hat dieser Baum einen isomorphen Lift in \G, d.h. einen Baum T<=\G, sodass T^-=T^~ gilt und v\mapsto\ v^- ein Isomorphismus T\to\ T^~ ist.
Da V(T)^-=V(T^-)=V(\G^-) ist, enthält T also aus jeder Bahn von G auf V(\G) eine Ecke. Es ist sogar jeweils genau eine Ecke, da T\to\ T^- injektiv ist.
Die Ecken der Bäume \void^g\.T (g\in\ G) überdecken also die komplette Eckenmenge V(\G). Diese Bäume sind alle disjunkt, denn sei etwa V(\void^g\.T)\cut\ V(\void^h\.T)!=\0, so gibt es u,v\in\ V(T) mit \void^g\.u=\void^h\.v => u und v liegen alle in derselben Bahn => u^-=v^-. Da T\to T^- wie gesagt injektiv ist, folgt u=v. => \void^g\.u=\void^h\.v => g=h, da G frei auf V(\G) operiert.
Wir betrachten nun einen zweiten Quotientengraphen \G^\*, der durch Kontraktion aller Bäume \void^g\.T zu je einem Punkt entsteht.
Da die Bäume \void^g\.T ganz \G überdecken, ist V(\G^\*)=menge(\void^g\.T | g\in\ G). Das heißt \phi: G\to\ V(\G^\*), g\mapsto\void^g\.T ist surjektiv. Da wie eben gesehen \void^g\.T\cut\void^h\.T!=\0 => g=h gilt, ist \phi sogar bijektiv.
Wir schauen uns an, wie die Kanten in \G^\* verlaufen. Nach Definition des Quotientengraphen ist
\align\ (\void^g\.T, \void^h\.T)\in\ E(\G^\*) ><<=> \exists\ v\in\ V(\void^g\.T), v'\in\ V(\void^h\.T): (v,v')\in\ E(\G)
><<=> \exists\ u,u'\in\ V(T): (\void^g\.u, \void^h\.u')\in\ E(\G)
><<=> \exists\ u,u'\in\ V(T): (u, \void^array(g^(-1)\.h)\.u')\in\ E(\G)
><<=> (T, \void^array(g^(-1)\.h)\.T)\in\ E(\G^\*)
\stopalign
Da T \- von Trivialfällen einmal abgesehen \- üblicherweise mehr als eine Ecke enthält, wird i.A. jeder Knoten in \G^\* mit sich selbst verbunden sein. Entfernen wir alle Schlingen, so erhalten wir einen Teilgraphen \G||'<=\G^\*.
Wir setzen nun S:=menge(s\in\ G | (T,\void^s\.T)\in\ E(\G^\*))\\{1}. Dann gilt also:
\align\breakalign\ (\void^g\.T,\void^h\.T)\in\ E(\G||') ><<=> (\void^g\.T, \void^h\.T)\in\ E(\G^\*) \and \void^g\.T!=\void^h\.T
><<=> (T,\void^array(g^(-1)\.h)\.T)\in\ E(\G^\*) \and g!=h
><<=> g^(-1)\.h\in\ S
><<=> (g,h)\in\ E(\G_array(G\,S))
\stopalign
Die Abbildung \phi: G\to\ V(\G||') ist somit ein Graphenisomorphismus \G_array(G\,S)\to\G||'.
Was für ein Graph ist \G||' nun? \G^\* ist als Quotientengraph von \G zusammenhängend wieder nach \ref(0.2). Eine Schlinge ist niemals Teil eines Weges, d.h. \G||' ist immer noch zusammenhängend.
Aus \ref(0.4) folgt, dass die einzigen Kreise in \G^\* die Schlingen sind, d.h. \G||' ist kreisfrei und damit ein Baum.
Und jetzt sind wir am Ziel: \G_array(G\,S)~=\G||' ist ein Baum, also ist G frei über S.
\blue\ q.e.d.
Der eben bewiesene Satz riecht natürlich schon verdächtig nach dem Satz von Schreier-Nielsen. In der Tat ist dieser Beweis nun einfach, ja beinahe trivial:
\darkred\ll(Schreier-Nielsen)Jede Untergruppe einer freien Gruppe ist frei.
\blue\ Beweis:
Sei G frei über S. Dann ist \G_array(G\,S) nach \ref(1.2) ein Baum, auf dem G frei operiert. Ist H<=G, so operiert auch H frei auf diesem Baum, ist also nach \ref(2.1) selbst eine freie Gruppe.
\blue\ q.e.d.
Der Satz von Schreier\-Nielsen sagt erstmal nur, dass es eine freie Basis für H gibt. Über die Größe einer solchen Basis lässt sich erstmal nichts ableiten. Da wir die Größen von F(S) Bescheid wissen, falls abs(S)>=abs(\IN) ist, können wir für G~=F(S), H~=F(T) und unendliche S auch sagen, dass abs(T)<=abs(F(T))=abs(H)<=abs(G)=abs(S) sein muss.
Für endliche S ist das jedoch nicht mehr richtig. So hat beispielsweise die freie Gruppe über zwei Erzeugern {x,y} eine Untergruppe, die frei über abzählbar vielen Erzeugern ist, etwa H=braket(x^n*y*x^(-n), n\in\IZ), wie wir im vorherigen Artikel bewiesen hatten.
Abschluss
Ich persönlich finde diesen Beweis sehr interessant. Zum einen, weil er wiedermal demonstriert, wie unglaublich nützlich Gruppenoperationen für das Studium von Gruppen sind, und zum anderen, weil er eine schöne Verbindung zwischen Graphentheorie und Gruppentheorie aufzeigt, die ebenfalls sehr fruchtbar sein kann.
\geo
x(0,2.2)
y(0,1)
ebene(220,100)
noaxis()
print(\big\blue mfg,0,0.6)
print(\big\blue\G_array(G\,ockel),0.85,0.6)
nolabel() punktform(of) color(black)
p(0.35,0.55,A1,hide) p(0.8,0.55,B1,hide) pfeil(A1,B1)
p(0.35,0.45,A2,hide) p(0.8,0.45,B2,hide) pfeil(B2,A2)
p(1.9,0.5,M,hide) k(M,0.25,k1,hide)
p(k1,135,C,hide) p(k1,-135,E,hide)
bogen(M,E,C)
tangente(k1,C,h1,hide) tangente(k1,E,h2,hide)
schnittpunkt(h1,h2,D,hide)
s(E,D) pfeil(C,D)
\geooff
geoprint()
Die Gruppenzwang-Reihe
Teil 1: Wir rechnen mit allem
Teil 2: Anonyme Mathematiker bieten Gruppentherapie an
Teil 3: Sensation: Homo Morphismus ist ein Gruppentier
Teil 4: Gruppencamper brauchen Iso(morphie)matten
Teil 5: Dr.Cauchy und Dr.Sylow bitte zur GruppenOP
Teil 6: Randale: Gruppendemo musste aufgelöst werden
Teil 7: Gruppen sind immer noch top!
Teil 8: Konvois auf der A20: Autos nur noch in Gruppen unterwegs
Teil 9: Unfall im Genlabor: (Per)mutationen in der Bevölkerung
Teil 10: Jäger der verlorenen Gruppe - Special Xtended Version
Teil 11: Der Gruppentheorie-Adventskranz
Teil 12: Wegen guter Führung entlassen: Gruppen sind frei
Teil 13: Amnestie: Auch Untergruppen frei
\(\endgroup\)
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
