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.
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).
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.
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.