Grupper och delgrupper

Referenser

[F] Edition 7: Del I: avsnitt 2, 3, 4, 5, 6, 7.

1. Kontrollfrågor om brev 1

1.	Kan du visa att om A och B är delmängder till en mängd C, så är A B och A B delmängder till C?
2.	Låt R vara en relation på Z, mängden av heltal, som definieras av a R b om 6 | (a - b). Kan du visa att R är en ekvivalensrelation och ange ekvivalensklasserna?
3.	Kan du definiera mängden Zn och ange hur man adderar och multiplicerar kongruensklasser?
4.	Kan du ange komplexa talet 3+2i i-7 på formen a + bi?

2. Läsanvisningar till Del I i [F]

Avsnitt 2

Avsnittet börjar med definitionen av en binär operation, som är en generalisering av addition och multiplikation. Försök att ge ett exempel på en operation * som är inte väldefinierad, ett exempel där mängden är inte sluten under *, och ett exempel på en binär operation.

För att kontrollera att * på en mängd S är en binär operation måste följande villkor uppfyllas:

* är väldefinierad	-	högst ett värde för varje ordnat par (a, b) i S × S
	-	minst ett värde för varje ordnat par (a, b) i S × S
S är sluten under *	-	a * b S för alla a,b S

Du vet att för heltal a, b, c gäller ab = ba (kommutativitet) och (ab)c = a(bc) (associativitet) men för n × n matriser A, B, C är AB ofta ej lika med BA men (AB)C=A(BC). Varken associativitet eller kommutativitet behövs för en binär operation t ex vektorprodukt × är ej associativ.

Låt S vara en mängd och * en binär operation på S som är associativ och kommutativ. Kan vi lösa ekvationen a * b = c med bara denna information eller behöver vi mer? Låt S vara mängden av heltal och * vara den kommutativa, associativa binära operationen addition. Kan du lösa 7 + c = 14 om du bara använder definition av binär operation, associativ och kommutativ? Vad mer behövs? Tänk steg för steg hur du skulle lösa det.

OBS! En binär operation kan definieras explicit av en tabell. Hur får tabellen se ut? Kan man se om en binär operation är associativ eller kommutativ genom att titta på tabellen?

Avsnitt 3

"Isomorphic" - vad betyder det? Har du sett ordet förut? Kommer du ihåg från grafteori att två grafer H(V,E) och H'(V',E') är isomorfa om det existerar en bijektion f:V->V' så att uv H <=> f(u)f(v) H'. Vad betyder det? Det betyder att man parar ihop hörn i H och H' så att kanterna också par ihop, dvs att strukturen hos de två graferna är samma, med kanske olika namn på hörnen. Det är samma sak med binära strukturer; samma struktur, olika namn på element.
För att visa att två grafer är isomorfa måste man ge en bijektion som uppfyller något villkor. Det är samma sak med grupper; hitta en bijektion f: < G,* > -> < G',*' > så att (x*y) = (x)*' (y) för alla x,y S (Definition 3.7, och How to Show That Binary Structures Are Isomorphic sidan 30-31). För att visa att två grafer inte är isomorfa måste man hitta en olikhet i deras struktur, t ex olika antal hörn med ej att hörnen med gradtal 4 heter A i en graf och a i den andra. Det är samma sak med binära strukturer. (How to Show That Binary Structures Are Not Isomorphic sidan 31-32)
Du bör kunna definitionen och kunna visa om två strukturer är isomorfa eller inte.

Identity element (identitetselement) - jämför med 1 i multiplication av heltal, 0 i addition av heltal och identitetsmatris I i matrismultiplikationen. Hur kan man visa att identitetselement är entydigt? Använd ett motsägelsebevis. Kom ihåg att om man vill visa att "p=>q" så kan man anta att "p" och "inte q" är sanna och hitta en motsägelse. I Theorem 3.13, vad är "p" och "q"? Låt "p" vara "det existerar ett identitetselement" och "q" vara "det är entydigt". Vi antar att det existerar ett identitetselement men att det inte är entydigt, dvs det existerar minst två identitetselement (se bevis av Theorem 3.13). Detta är det vanliga sättet att visa att någonting är entydigt.

Avsnitt 4

Nu generaliserar vi strukturen för ekvationslösning. Vår grundläggande struktur är en grupp (se defintion 4.1).

Definitionen av en grupp < G, * >
Jag tycker att det är lättare att komma ihåg  fyra villkor för en grupp:
- G är sluten under *
- * är associativ
- G innehåller ett identitetselement
- Varje element i G har en invers.

Betrakta definitionen. Kommer du på några frågor? Vi sa att vi vill har en struktur för ekvationslösning. En grupp är en, men vilka ekvationer kan man lösa inom en grupp? När existerar det en lösning till, t ex a*x=b där a,b är element i en grupp < G, * >? Om det existerar en lösning, är den entydig? (se Theorem 4.16)

Är t ex identitetselement entydigt? (se Theorem 4.17) Är inversen till ett element a entydigt? (se Theorem 4.17) Den binära operationen måste vara associativ men måste den vara kommutativ? (se defintion 4.3) Är det någon egenskap som följer direkt från definitionen?

Du har säkert träffat på begreppet invers förut, t ex invers till en matris. Hur kan man använda en invers? Om ab = ac, när gäller b = c? (se Theorem 4.15)

Finite Groups and Group tables

Har du sett en liknande tabell förut?

Hur många grupper finns det med exakt fyra element? Skriv ner alla icke-isomorfa grupptabeller på mängden {a,b,c,d}.

Avsnitt 5

OBS! Vi brukar skriva a + b eller ab istället för a * b, där a + b används endast om * är kommutativ.

Vad är en delgrupp? Det är en delmängd som själv är en grupp (se definition 5.4). Vilka villkor måste uppfyllas?

Det är viktigt att du kan kontrollera om en mängd är en delgrupp till en given grupp. För att göra detta måste du kunna både sats 5.14 och definitionen av en delgrupp. Varför måste du kunna definitionen? Om du måste bevisa att en mängd är en ring (del IV) måste du första bevisa att den är en grupp. Om man kan visa att den är en delgrupp till någon känd grupp så har man visat att den själv är en grupp med hjälp av definitionen. Detta är ofta lättare än att visa att de fyra villkor för grupper, t ex associativitet, håller på delmängden.

De två grupperna på fyra element som kallas för Kleins 4-grupp V och Z₄ är viktiga.

Vad är en cyklisk grupp? Det är en grupp där alla element kan genereras av ett element a genom att använda den binära operationen på a med sin själv, dvs alla element kan skrivas som a^k där k är ett heltal, t ex Z₄ är cyklisk och generas av 3: 3, 3+3=2, 2+3=1, 1+3=0, och 2Z generas av 2: ..., -2, 0, 2, 4, 6, 8, ... .

Hur många icke-isomorfa cykliska grupper av ordning n existerar det? Fundera lite över: Hur många oändligt cykliska grupper existerar det? Är någon cycklisk grupp abelsk? Har en cyklisk grupp någon cyklisk undergrupp?

Avsnitt 6

Cykliska grupper är ett enkelt exempel på abelska grupper (se Theorem 6.1). Är varje abelsk grupp också cyklisk? Är Kleins 4-grupp abelsk? Är Kleins 4-grupp cyklisk? Varje delgrupp till en cyklisk grupp är cyklisk (se Theorem 6.6). Om varje äkta delgrupp till en grupp G är cyklisk, är även G cyklisk? (Ledning: Kleins 4-grupp är inte cyklisk!)

Du vet väl att det går att dividera ett heltal med ett annat (utom 0) (se Theorem 6.3) men kan du generalisera detta till polynom? Kan du generalisera Euklides algoritm, största gemensamma delare och primtal till polynom? I Del IV, V och IX förklarar boken hur man kan göra detta så det är viktigt att förstå och vara van vid primtal, största gemensamma delare och Euklides algoritm.

The Structure of Cyclic Groups

Nu ser vi att alla oändliga cykliska grupper är isomorfa med Z. Det finns cykliska grupper av alla ändliga ordningar n och alla grupper av ordning n är isomorfa med Z_n.

Subgroups of Finite Cyclic Groups

Varje element i en grupp genererar en delgrupp men hur stor blir delgruppen? Theorem 6.14 besvarar frågan för cykliska grupper. Lagranges sats (Theorem 10.10) ger ett bredare svar på frågan. Theorem 6.14 är grundläggande för Lagranges sats.
Theorem 6.14 ger en enkel följdsats. Vilka slutsats kan du dra om vilka element av en cyklisk grupp som är generatorer till den? Hur många är de? (Se Corollary 6.16)

Avsnitt 7 (ej Cayley Digraphs)

Generators of a Group

Vi har set att ett element generarar en grupp, men alla grupper kan inte genereras av ett element. Nu diskuterar vi mängder av element som genererar en grupp.

Varför får vi inte alltid skriva aba = a²b, men varför gäller aba = a²b om en grupp G är cyklisk?

3. Övningar Del I

Nu är det viktigt att göra några övningar. Jag förslår att du försoker göra alla övningar markerad med * först. Kontakta mig om du går bet på någon övning.

Avsnitt	Problem
2	7, 9, 11, 12*, 13, 17, 18, 23*, 24, 27, 28
3	1, 2, 4*, 19, 21, 28, 32, 34*
4	1, 4 (jmf med 1), 5, 7, 19*, 20* 23, 25, 31, 32
5	1-7, 20*, 36, 39, 44, 45*, 46
6	14, 18, 23, 27, 32, 33-37, 45*, 46, 49*, 51*
7	1, 2

4. Inlämningsuppgift (tisdag v. 39)

[F] Avsnitt 5: 36

[F] Avsnitt 6: 51