Gruppteori och abstrakt algebra¶
Detta är kursens mest abstrakta sträcka, och abstraktion är där poäng läcker ut — inte för att idéerna är svåra, utan för att vag skrift bedöms med högst två poäng. Den goda nyheten: nästan varje fråga besvaras av något av tre ting — axiomen, Lagranges sats, eller cykelnotation. Kan du känna igen vilket av de tre ett problem vill ha, är du större delen av vägen dit.
En snabb orientering före formaliteterna: en grupp är den matematiska destillationen av "en mängd drag du kan ångra och kombinera" — rotationer av en form, blandningar av en kortlek, additioner på en klocka. Axiomen nedan är bara de minsta regler som får "kombinera och ångra" att uppföra sig förnuftigt.
Gruppaxiomen¶
En grupp \((G, *)\) är en mängd \(G\) med en operation \(*\) som uppfyller fyra regler:
| Axiom | Utsaga | I ord |
|---|---|---|
| Slutenhet | \(x * y \in G\) | att kombinera två medlemmar stannar inom mängden |
| Associativitet | \((x * y) * z = x * (y * z)\) | gruppering spelar ingen roll |
| Identitet | något \(e\) har \(e * x = x * e = x\) | det finns ett "gör ingenting"-element |
| Inverser | varje \(x\) har \(x^{-1}\) med \(x * x^{-1} = e\) | varje drag kan ångras |
Om, utöver dessa, ordningen aldrig spelar roll (\(x * y = y * x\) för alla \(x, y\)), är gruppen abelsk (kommutativ). Många välbekanta grupper är abelska; de symmetriska grupperna nedan är de viktiga som inte är det.
Två ting som kallas "ordning" — förväxla dem inte:
- Gruppens ordning \(\lvert G \rvert\) är hur många element den har.
- Ordningen av ett element \(g\) är det minsta \(k > 0\) med \(g^k = e\) — hur många gånger du tillämpar \(g\) innan du återvänder till starten.
Samma ord, olika betydelser; problem utnyttjar förväxlingen.
Du behöver inte alla fyra axiom för att kontrollera en delgrupp
En delgrupp är en delmängd som är en grupp i egen rätt. För att verifiera att \(H \subseteq G\) är en delgrupp behöver du bara: \(H\) är icke-tom, sluten under \(*\), och sluten under inverser. Associativitet ärvs från \(G\) gratis, och identiteten tvingas fram av de andra två. För en ändlig \(H\) är det ännu lättare — icke-tom och sluten under \(*\) räcker redan (inverserna följer med automatiskt).
Lagranges sats¶
Områdets enskilt mest användbara sats, och den som mest sannolikt spräcker upp en tentauppgift på en rad.
Lagranges sats
Om \(H\) är en delgrupp till en ändlig grupp \(G\), så är
— storleken på en delgrupp delar alltid storleken på gruppen.
Varför den är sann (och var du sett detta förr). Delgruppen \(H\) hackar \(G\) i sidoklasser, som var och en har exakt \(\lvert H \rvert\) element, och dessa sidoklasser partitionerar \(G\) — inga överlapp, täcker allt. Så \(G\) är bara något helt antal likstora block av storlek \(\lvert H \rvert\), vilket tvingar \(\lvert H \rvert\) att dela \(\lvert G \rvert\). Det är exakt samma "ekvivalensrelation → partition"-idé från logikkapitlet, i gruppteorikläder.
Följdsatserna du faktiskt kommer att använda:
- Ordningen av vilket element som helst delar \(\lvert G \rvert\) (tillämpa Lagrange på delgruppen \(\langle g \rangle\) det genererar).
- \(g^{\lvert G \rvert} = e\) för varje \(g\). (Fermats lilla sats är precis detta, för gruppen \(\mathbb{Z}_p^{\times}\) — de två satserna är samma utsaga!)
- Varje grupp av primtalsordning är cyklisk, genererad av vilket element som helst utom identiteten.
Lagrange går bara åt ett håll — omvändningen är falsk
Lagrange säger att en delgrupps storlek måste dela \(\lvert G \rvert\). Den lovar inte en delgrupp för varje delare. Så använd den för att utesluta delgrupper, aldrig för att frammana en. För att visa att en delgrupp av en viss storlek finns måste du faktiskt uppvisa en.
Tentamen (maj 2024, uppgift 6a): har \(S_6\) en delgrupp av storlek 7?
Gruppen \(S_6\) har \(\lvert S_6 \rvert = 6! = 720\) element. En delgrupp av storlek \(7\) skulle kräva \(7 \mid 720\) — men \(720 = 7 \cdot 102 + 6\), så \(7 \nmid 720\). Enligt Lagrange finns ingen sådan delgrupp.
Det är hela svaret: en delbarhetskontroll. Denna "utesluta"-riktning är precis vad Lagrange är till för.
Sidoklasser, konkret¶
Beviset för Lagrange vilar på sidoklasser, och det är värt att se dem röra sig. Given en delgrupp \(H \le G\) är (vänster)sidoklassen för ett element \(g\) mängden \(gH = \{\, g * h : h \in H \,\}\) — hela delgruppen "förskjuten" med \(g\). Två egenskaper gör allt arbete:
- Varje sidoklass har samma storlek \(\lvert H \rvert\) (förskjutning är en bijektion).
- Sidoklasser är antingen identiska eller disjunkta — de partitionerar \(G\) i lika stora block. Antalet block är indexet \([G : H] = \lvert G\rvert / \lvert H\rvert\).
Löst: sidoklasserna för \(H = \{0, 3\}\) i \(\mathbb{Z}_6\)
Här är \(G = \mathbb{Z}_6\) (addition mod \(6\)) och \(H = \{0, 3\}\), storlek \(2\). Bygg sidoklasser \(g + H\):
och \(3+H = \{3,0\} = 0+H\), \(4+H = 1+H\), \(5+H = 2+H\) — inga nya. Så de tre sidoklasserna \(\{0,3\}, \{1,4\}, \{2,5\}\) täcker \(\mathbb{Z}_6\) i lika stora par. Det är Lagrange synliggjort: \(\lvert H\rvert = 2\) delar \(\lvert G\rvert = 6\) eftersom \(G\) är exakt \([G:H] = 3\) kopior av \(H\). (Dessa sidoklasser är också elementen i kvotgruppen \(\mathbb{Z}_6 / H \cong \mathbb{Z}_3\) — att addera sidoklasser beter sig som att addera mod \(3\).)
Cykliska grupper¶
En grupp är cyklisk om ett enda element \(g\) genererar allt genom att ta potenser: \(G = \langle g \rangle = \{\dots, g^{-1}, e, g, g^2, \dots\}\). Cykliska grupper är den enklaste sorten — en generator driver hela saken.
Två fakta gör det mesta av arbetet:
- Varje cyklisk grupp är abelsk (potenser av samma \(g\) kommuterar uppenbart).
- Därför, inte abelsk ⟹ inte cyklisk. Denna kontraposition är det snabbaste icke-cyklicitetsbeviset som finns: visa två element som inte kommuterar, så är du klar.
- \(\mathbb{Z}_n\) under addition är cyklisk, genererad av \(1\) (addera \(1\) upprepade gånger och du når allt).
Strukturen inuti en cyklisk grupp¶
Ta modellen för en cyklisk grupp, \(\mathbb{Z}_n\) (under addition). Allt om dess element och delgrupper styrs av ett enda tal — en gcd:
Ordningen av ett element i \(\mathbb{Z}_n\)
Elementet \(k\) har ordning
I synnerhet genererar \(k\) hela gruppen (har ordning \(n\)) precis när \(\gcd(n, k) = 1\). Så antalet generatorer för \(\mathbb{Z}_n\) är \(\varphi(n)\), totienten.
Varför gcd:n. Att upprepat addera \(k\) landar på multiplerna \(0, k, 2k, \dots\); du återvänder till \(0\) vid den första multipeln av \(k\) som också är en multipel av \(n\) — det är \(\operatorname{lcm}(n,k)\). Antalet steg är \(\operatorname{lcm}(n,k)/k = n/\gcd(n,k)\).
Två fakta till fullbordar bilden, och båda är ren delarbokföring:
- Delgrupper till en cyklisk grupp är cykliska, och en cyklisk grupp av ordning \(n\) har exakt en delgrupp av ordning \(d\) för varje delare \(d \mid n\) — varken fler eller färre. (Jämför Lagrange, som bara förbjuder icke-delare; för cykliska grupper gäller omvändningen faktiskt.)
- Varje delgrupp till \(\mathbb{Z}_n\) har formen \(\langle n/d \rangle\) och består av multiplerna av \(n/d\).
Löst: ordningar och generatorer i \(\mathbb{Z}_{12}\)
Med \(\operatorname{ord}(k) = 12/\gcd(12,k)\):
| \(k\) | \(\gcd(12,k)\) | ordning |
|---|---|---|
| \(1,5,7,11\) | \(1\) | \(12\) — dessa är generatorerna |
| \(2,10\) | \(2\) | \(6\) |
| \(3,9\) | \(3\) | \(4\) |
| \(4,8\) | \(4\) | \(3\) |
| \(6\) | \(6\) | \(2\) |
| \(0\) | \(12\) | \(1\) |
Det finns \(\varphi(12) = 4\) generatorer, vilket matchar översta raden. Och delgruppsordningarna som förekommer — \(1,2,3,4,6,12\) — är exakt delarna till \(12\), en delgrupp var, som utlovat.
Tentamen (maj 2024, uppgift 6b–d): delgrupper till \(S_6\)
(b) En cyklisk delgrupp av ordning 4. Ta en enda 4-cykel, t.ex. \(g = (1\,2\,3\,4)\). Då har \(\langle g \rangle = \{\mathrm{id}, g, g^2, g^3\}\) \(4\) element och är cyklisk per konstruktion (en generator). ✓
(c) En delgrupp av ordning 4 som inte är cyklisk. Ta två disjunkta transpositioner \(h_1 = (1\,2)\) och \(h_2 = (3\,4)\). Eftersom de flyttar olika punkter är \(h_1^2 = h_2^2 = \mathrm{id}\) och \(h_1 h_2 = h_2 h_1\), så
är sluten och alltså en delgrupp av ordning \(4\). Den är inte cyklisk: varje element kvadreras till identiteten, så inget har ordning \(4\) — och en cyklisk grupp av ordning \(4\) behöver ett element av ordning \(4\). (Denna lilla grupp är berömd: Kleins fyrgrupp.)
(d) Är \(S_6\) cyklisk? Nej — och det finns två rena sätt att säga det:
- Via elementordningar. Om \(S_6 = \langle g \rangle\), så skulle \(g\) behöva ordning \(6! = 720\). Men i cykelform är ett elements ordning lcm av dess cykellängder, och de längderna summerar till högst \(6\) — så ordningen är högst \(6\) (långt under \(720\)). Motsägelse.
- Via kommutativitet. Cyklisk ⟹ abelsk, men \(S_6\) är inte abelsk: \((1\,2)(1\,3) \neq (1\,3)(1\,2)\). Klart på en rad.
Det andra argumentet är kortare och generaliserar: \(S_n\) är icke-abelsk för varje \(n \geq 3\), alltså aldrig cyklisk.
Direkta produkter¶
Du kan bygga en större grupp av två mindre genom att köra dem sida vid sida. Den direkta produkten \(G \times H\) har som element paren \((g, h)\), kombinerade koordinatvis: \((g_1, h_1) * (g_2, h_2) = (g_1 g_2,\ h_1 h_2)\). Dess ordning är helt enkelt \(\lvert G\rvert \cdot \lvert H\rvert\), och ordningen av ett element är lcm av de två koordinatordningarna.
Den enda examinerbara satsen knyter direkt tillbaka till kinesiska restsatsen:
När är en produkt av cykliska grupper cyklisk?
Varför gcd-villkoret. Elementet \((1, 1)\) har ordning \(\operatorname{lcm}(m, n)\). För att produkten ska vara cyklisk behöver den ett element av ordning \(mn\) — och \(\operatorname{lcm}(m,n) = mn\) inträffar precis när \(\gcd(m,n) = 1\). När de delar en faktor delar varje elements ordning \(\operatorname{lcm}(m,n) < mn\), så ingen generator finns.
Löst: \(\mathbb{Z}_2 \times \mathbb{Z}_3\) kontra \(\mathbb{Z}_2 \times \mathbb{Z}_2\)
- \(\mathbb{Z}_2 \times \mathbb{Z}_3\): \(\gcd(2,3)=1\), så den är cyklisk, \(\cong \mathbb{Z}_6\). Elementet \((1,1)\) har ordning \(\operatorname{lcm}(2,3) = 6\) och genererar allt — det här är CRT i gruppteoretiska kläder (\(x \equiv 1 \bmod 2\), \(x \equiv 1 \bmod 3\) fastställer \(x\) mod \(6\)).
- \(\mathbb{Z}_2 \times \mathbb{Z}_2\): \(\gcd(2,2)=2 \neq 1\), så inte cyklisk. Varje icke-identitetselement har ordning \(2\) (inget element av ordning \(4\)), och detta är just Kleins fyrgrupp igen — samma grupp som dök upp som en icke-cyklisk delgrupp till \(S_6\).
Isomorfier och homomorfier¶
En homomorfi är en avbildning mellan grupper som respekterar operationen — det spelar ingen roll om du kombinerar först och avbildar sedan, eller avbildar först och kombinerar sedan:
En isomorfi är en homomorfi som också är en bijektion. Om en sådan finns skriver vi \(G_1 \cong G_2\) och säger att grupperna är desamma sånär som på omdöpning — strukturellt identiska, bara med olika etiketter på elementen.
- För att bevisa isomorfi: producera avbildningen \(\varphi\), kontrollera att den respekterar operationen, och kontrollera att den är en bijektion.
- För att bevisa icke-isomorfi: hitta en strukturell egenskap som bevaras av varje isomorfi som den ena gruppen har och den andra saknar — olik storlek, en abelsk och den andra inte, olikt antal element av ordning \(2\), en cyklisk och den andra inte, och så vidare. Vilken sådan diskrepans som helst avgör saken.
En homomorfi är fastnaglad av vad den gör med generatorer
Om \(G = \langle g \rangle\), så bestämmer vetskapen om \(\varphi(g)\) hela \(\varphi\) (eftersom varje element är en potens av \(g\)). Mer allmänt fixerar det att fixera \(\varphi\) på en genererande mängd den fullständigt. Det är precis varför tentamens problem \(S_n \to \mathbb{Z}_2\) reduceras till en enda fråga: vad gör \(\varphi\) med en transposition?
Tentamen (maj 2024, uppgift 9): homomorfier \(S_n \to \mathbb{Z}_2\)
Påstående att bevisa: varje homomorfi \(\varphi: S_n \to \mathbb{Z}_2\) är antingen identiskt \(0\), eller så är den exakt teckenavbildningen (\(\varphi(g) = 1\) omm \(g\) är en udda permutation).
Strategin: varje permutation är en produkt av transpositioner, så \(\varphi\) är fullständigt bestämd av sina värden på transpositioner. Så vi behöver bara förstå dem.
Fall 1. Om \(\varphi(\tau) = 0\) för varje transposition \(\tau\), så skickar \(\varphi\) varje produkt av transpositioner till \(0\) — alltså \(\varphi = 0\). Det är det första alternativet.
Fall 2. Annars har någon transposition \(\varphi(\tau) = 1\), säg \(\tau = (i\,j)\). Nyckelfaktumet är att alla transpositioner är konjugerade — vilken som helst kan förvandlas till vilken annan som helst genom ommärkning. Gjort konkret, för vilken annan transposition \(\tau' = (k\,l)\) som helst:
Tillämpa \(\varphi\) (och kom ihåg att \(\mathbb{Z}_2\) adderar, med \(2x = 0\)):
eftersom varje upprepad term förekommer två gånger och tar ut sig. Så varje transposition avbildas på \(1\), vilket betyder att en produkt av \(k\) transpositioner avbildas på \(k \bmod 2\) — precis \(\operatorname{sign}(g)\). Det är det andra alternativet. \(\square\)
Notera argumentets form: "bestämd av generatorer" reducerade hela problemet till transpositioner, och "alla transpositioner är konjugerade" tvingade dem att uppföra sig likformigt.
Permutationer¶
En permutation är en bijektion av \(\{1, \dots, n\}\) till sig själv — en omarrangering. Den symmetriska gruppen \(S_n\) är alla sådana under sammansättning.
Cykelnotation¶
Varje permutation bryts entydigt i disjunkta cykler: \((1\,2\,3)\) betyder "1→2, 2→3, 3→1", och disjunkta cykler rör olika element. Eftersom de rör olika element kommuterar disjunkta cykler — vilket är det som får ordningsformeln att fungera.
Ordningen av en permutation
Ordningen av en permutation är minsta gemensamma multipeln av dess disjunkta cykellängder.
Varför lcm. En cykel av längd \(\ell\) återvänder till start var \(\ell\):te tillämpning. Hela permutationen är tillbaka vid identiteten först när alla dess cykler samtidigt är hemma — vilket först händer vid lcm av deras längder. Så \((1\,2\,3)(4\,5)\) har ordning \(\operatorname{lcm}(3, 2) = 6\). (Att hitta den största möjliga ordningen i \(S_n\) är därför en gåta om att dela \(n\) för att maximera en lcm.)
Tecken: udda och jämn¶
Varje permutation kan också skrivas som en produkt av transpositioner (2-cykler — enkla byten). Antalet transpositioner är inte entydigt, men dess paritet (jämn/udda) är alltid det, och den pariteten är permutationens tecken:
- Jämnt antal transpositioner ⟹ jämn permutation, \(\operatorname{sign} = +1\).
- Udda antal ⟹ udda permutation, \(\operatorname{sign} = -1\).
En användbar genväg: en \(k\)-cykel delas i \(k - 1\) transpositioner, så den är jämn precis när \(k\) är udda. För att hitta en permutations tecken, addera \((k_i - 1)\) över dess cykler: \(\operatorname{sign} = (-1)^{\sum (k_i - 1)}\).
Tecken är multiplikativt — \(\operatorname{sign}(gh) = \operatorname{sign}(g)\operatorname{sign}(h)\) — vilket bara är utsagan att tecken är en homomorfi \(S_n \to \{\pm 1\} \cong \mathbb{Z}_2\). Och enligt uppgift 9 ovan är det i grunden den enda icke-triviala homomorfin ut från \(S_n\) till \(\mathbb{Z}_2\). Trådarna knyts ihop.