12 svar
125 visningar
Jocke011 257
Postad: 14 nov 2017

Antalet möjliga homomorfismer

Hej

jag vill bara kolla om jag har tänkt rätt eller om jag bara fick rätt ändå:

Bestäm antalet möjliga homomorfismer från:

a) 8 till 21

b) 8 till 24

Svaret blir 1 i a men 8 i b, är det eftersom den största gemensamma delaren till (8,21)=1 och (8,24)=8

Stokastisk 2797
Postad: 14 nov 2017

Om vi säger så här, jag ser inte riktigt att du givit ett resonemang för varför det just skulle vara (8, 21) och (8, 24) som är det du ska räkna ut.  Om jag skulle säga att jag inte tror på dig, skulle du kunna bevisa att det faktiskt är så? (Om du kan ge mig ett sånt resonemang så har du nog tänkt rätt, om inte så har du nog inte riktigt tänkt efter).

Jocke011 257
Postad: 15 nov 2017

Det enda som jag tänkte på var att använda största gemensamma delaren av storleken på grupperna men det måste finnas något bättre sätt som jag inte riktigt förstår.

oggih 132 – F.d. Moderator
Postad: 16 nov 2017 Redigerad: 16 nov 2017

Du har rätt svar, men rätt svar räcker inte; man måste motivera! Halva poängen med att läsa matematik är att lära sig skriva riktigt bra logiska argument.

När jag själv skriver ner en lösning till ett matematiskt problem brukar jag försöka tänka mig att jag förklarar för en förvirrad klasskompis som dels fattar lite mindre än jag själv gör och dels misstänksamt ifrågasätter allt jag säger. Varför då? Hur kan du veta det? Vad exakt betyder det när du säger så? är några av hennes favoritfrågor.

Skulle hon se den här tråden hade hon direkt rynkat pannan och upprört frågat varför i hela fridens namn det skulle finnas en koppling mellan delbarhet och grupphomomorfismer? 😐 

oggih 132 – F.d. Moderator
Postad: 16 nov 2017 Redigerad: 16 nov 2017

En ledtråd (Spoilervarning! Notera även att det säkert finns flera andra approacher till problemet än denna):

Z8 genereras av elementet [1] (vad menar jag med det?), så varje grupphomomorfi f: Z8 -> Z21 bestäms av vilket element i Z21 som [1] avbildas på (vad menar jag med det; varför är det sant?).

Det finns maximalt 21 möjliga val för detta (nämligen f([1])=[0], f([1])=[1], f([1])=[2], ..., och f([1])=[20]), men endast (8,21)=1 av dessa val gör f till en fungerande grupphomomorfi; övriga leder till en motsägelse. Varför? 

oggih 132 – F.d. Moderator
Postad: 16 nov 2017 Redigerad: 16 nov 2017

En till ledtråd (Ännu mer spoilervarning!): Vad kan man säga om ordningen av f([1])? Vilka begränsningar sätter Lagrange på vad ordningen av ett element i Z21 kan vara?

Jocke011 257
Postad: 16 nov 2017
oggih skrev :

En ledtråd (Spoilervarning! Notera även att det säkert finns flera andra approacher till problemet än denna):

Z8 genereras av elementet [1] (vad menar jag med det?), så varje grupphomomorfi f: Z8 -> Z21 bestäms av vilket element i Z21 som [1] avbildas på (vad menar jag med det; varför är det sant?).

Det finns maximalt 21 möjliga val för detta (nämligen f([1])=[0], f([1])=[1], f([1])=[2], ..., och f([1])=[20]), men endast (8,21)=1 av dessa val gör f till en fungerande grupphomomorfi; övriga leder till en motsägelse. Varför? 

Att Z8 genereras av elementet 1 betyder väl att vi får samtliga element representerade av elementet 1 i cayleytabellen och därmed är den också cyklisk och då en generator till Z8

På samma sätt får vi samtliga element representerade av 1 i cayleytabellen för Z21

Däremot har jag fortfarande lite problem med att förstå hur endast (8,21)=1 av dessa val för f till en fungerande grupphomomorfi och övriga leder till en motsägelse. Hur ska man bevisa eller motbevisa det? 

oggih 132 – F.d. Moderator
Postad: 16 nov 2017

Se min andra ledtråd!

Jocke011 257
Postad: 16 nov 2017

okej vi har alltså att ordningen för undergruppen H  är en delare till ordningen för gruppen G

Alltså ska ordningen av Z8 dela ordningen av Z21 och då får man leta efter tal som är delbara båda med 8 och 21, vilket är 1 medans om man tar det andra fallet då vi har Z8och Z24får vi att 1,2,4,8 delar både 8 och 24

oggih 132 – F.d. Moderator
Postad: 16 nov 2017 Redigerad: 16 nov 2017

Nu hade den där skeptiska klasskompisen rynkat pannan igen! Z8 är inte alls en undergrupp av Z21, utan det är f(Z8) som är en undergrupp av Z21, så om du vill prata om ordning av delgupper så är det |f(Z8)| som i så fall ska dela |Z21|. Detta är typ på rätt väg, men jag har svårt att se hur man skulle nå hela vägen (speciellt i fallet när vi har bytt ut 21 mot 24) utan att prata om generatorer.

 

Det jag menade med ordet ordning var inte ordningen av delgrupper utan ordningen av element. Har ni pratat om det finns två olika betydelser av begreppet ordning?

 

Kort utläggning om ordning:

Om (G,*) är en grupp med identitet e, och x € G, så ges ordningen av elementet x av

   ord(x) = min{ k positivt heltal : x^k=e },

där x^k = x*x*...*x (k gånger).

Om operationen är + och identiteten är 0 kan detta även skrivas som

   ord(x) = min { k positivt heltal : kx=0 },

där kx=x+x+...+x (k gånger).

Notera att jag här använder konventionen att minØ tolkas som oändligheten, så om det inte finns något positivt heltal k sådant att x^k=e (eller kx=0), så säger vi att ord(a)=oändligheten.

Det kan tyckas förvirrande att det finns två olika ordningsbegrepp i gruppteorin, men lyckligtvis är de inte så värst olika som man kan tro. Det finns det en stark koppling mellan dem som motiverar att de har samma namn. Det är nämligen enkelt att visa att ordningen av elementet x är lika med ordningen av den delgrupp som x genererar, dvs.

   ord(x) = |<x>|.

Du kan säkert läsa mycket mer om detta i din kursbok. Slut på utläggning.

 

Testa nu att gå tillbaka till min sista ledtråd och se om den makear mer sense nu.

Jocke011 257
Postad: 16 nov 2017

ja det jag hittade är att om vi har g som är ett element i G och e är enhetselementet i G, så är ordningen för g lika med det minsta positiva heltalet n sådant att gn=e, då delar ordningen för g alltid G

Så det är ju som du skrivit ovan bara att dom har g och n istället för x och k.

Om man då ska använda det på uppgifterna i frågan, ska vi alltså hitta det minsta positiva heltalet n sådant att ord(g)=min(n:gn=0) 

Ska man då titta på vad som genererar 0 i 8respektive 21 i respektive cayleytabell?

oggih 132 – F.d. Moderator
Postad: 16 nov 2017 Redigerad: 17 nov 2017

Jag tänker så här:

Uppgiften: Beräkna antalet möjliga homomorfier f: Z8 -> Z24.

Bakgrund: Vi vet att vart och ett av de 24 tänkbara valen för vad [1] i Z8 skulle kunna mappas till för något i Z24 (dvs. f([1])=[0], f([1])=[1], f([1])=[2], ..., f([1])=[23]) motsvarar en tänkbar homomorfism f: Z8 -> Z24.

Varför är det så? Jo, det är för att iom att alla element  i Z8 genereras av [1] och f är en homomorfism, så räcker det att veta vad f([1]) är, för att kunna klura ut vad f([x]) är, för vilket [x] i Z8 som helst. Exempelvis gäller

   f([3])=f([1]+[1]+[1])=f([1])+f([1])+f([1]),

och generellt: 

   f([x])=x f([1])      (*)

där x är ett heltal och x f([1])=f([1])+...+f([1]) (x stycken gånger). 

Det vi vill göra nu, är att bestämma vilka av dessa 24 stycken tänkbara val som ger upphov till en fungerande homomorfism f: Z8 -> Z24.

* * * * * * * *

Fortsättning: Det enda som krävs för att en funktion ska vara en fungerande grupphomomorfi är att  respektera gruppoperationen och vara väldefinierad. Respekten för gruppoperationen får vi mer eller mindre automatiskt av (*). Det som kan gå snett är att det kan bli kaos med väldefinierbarheten.

Generellt är f i det här fallet väldefinierad detsamma som att [n]=[m] medför att f([n])=f([m]) för [n] och [m] i Z8. Men i stället för att kontrollera detta direkt för generella [n] och [m] kollar vi på ett speciellt fall. Vi vet ju nämligen att [8]=[0] i Z8, vilket betyder att vi vill att f([8])=f([0]) ska gälla i Z24 om f är väldefinierad. Enligt vårt sätt (*) att definera f i termer av f([1]), betyder detta att

   8 f([1])=0 f([1])

eller ekvivalent:

   8 f([1])=[0]

gäller i Z24. Med andra ord är 8 ett heltal k sådant att kf([1])=[0]. Talet 8 är alltså en kandidat till ordnignen av f([1]) i Z24! Men det är inte säkert att 8 är den faktiska ordningen; däremot kan vi enligt en viktig sats om ordningar säga att ord(f([1])) | 8, dvs. ord(f([1])) är antingen 1, 2, 4 eller 8. 

Samtidigt säger en annan sats att om man lägger ihop ett element i en grupp med sig självt lika många gånger som ordningen av gruppen så får man alltid identiteten (ibland kallas detta Fermats lilla sats). Det betyder att 24f([1])=[0], så 24 är också en kandidat för ordningen av f([1]). Det betyder, enligt satsen jag nysss nämnde, att ord(f([1]))|24, dvs. ord(f([1])) är antingen 1, 2, 4, 6, 8 eller 24.

Med andra ord: om f är väldefinerad måste ord(f([1])) vara lika med något av talen 1, 2, 4 eller 8. Vilka element i Z24 uppfyller detta?

[0] har ordningen 1    :-)

[1] har ordningen 24     :-(

[2] har ordningen 12    :-(

[3] har ordningen 8    :-)

[4] har ordningen 6    :-(

[5] har ordningen 24    :-(

[6] har ordningen 4    :-)

[7] har ordningen 24   :-(

[8] har ordningen 3    :-(

osv.

Det går att övertyga sig (övertyga dig själv!) om att mönstret kommer upprepa sig, så att var tredje element i Z24 har en ordning som överensstämmer med vad vi vill ha. Totalt kommer alltså totalt 8 stycken element i Z24 vara okej.

Det betyder att vi kan utesluta alla möjliga val av vad f ska mappa [1] till för något i Z24 utom dessa 8 stycken element.

* * * * * 

Dessa kvarvarande 8 val av f([1]) ger en funktion f sådan att f([8])=f([0]). Men för att f ska vara helt väldefinerad måste f([x])=f([y]) gälla för alla [x] och [y] i Z8 sådana att [x]=[y]. Kan vi vara säkra på att alla dessa 8 kvarvarande val verkligen uppfyller detta?

Det kan vi faktiskt! För om [x]=[y] i Z8, så måste y=x+8n för något heltal n, och om vi har sett till så att f([8])=f([0]), så gäller följande:

  f([y])=f([x+8n])=/f är homo/=

  =f([x])+nf([8])=/vi såg till att f([8])=f([0])/=

  =f([x])+nf([0])=/f([0])=0f([1]) enligt (*) och 0f([0])=[0]/

  =f([x])+n[0]=/[0]+...+[0] (n gånger) är lika med [0]/=

  =f([x])+[0]=f([x]).

Tada! Vi har nu kommit fram till att det finns åtta stycken olika homomorfier f: Z8 -> Z24; en för varje val av f([1]) som vi kunde bekräfta verkligen leder till att f uppfyller kraven på att vara en homomorfi: att respektera gruppoperationen och vara väldefinerad.

* * * * * * * *

Hängde du med? Testa att upprepa samma resonemang med Z21 i stället för Z24, från början till slut. (Vissa steg av resonemanget går att göra mycket snabbare i just det fallet, eftersom alla val av f([1]) utom ett val går att utesluta.) Om du tycker det är för svårt kan du börja med något enklare fall, t.ex. Z4 -> Z5 eller fZ3->Z6. Ställ gärna frågor om du är förvirrad, så försöker jag eller någon annan förklara bättre.

Slutligen: Nej, det är ingen slump att vi får just svaret åtta ovan och att (8,24)=8. Generellt kan man visa att antalet grupphomomorfismer f: Zn -> Zm alltid är (n,m). Ett väldigt snyggt resultat! Men det är inte superlätt att se vad kopplingen mellan det vi gjorde ovan och "största gemensamma delare" är, så mitt tips är att du skiter i detta så länge, och bara satsar på att att förstå hur man med brute force-metoden ovan räknar ut antalet homomorfismer i det specifika fallet. Senare i kursen kan du komma tillbaka till detta och se om du kan göra ett generellt bevis :)

Jocke011 257
Postad: 17 nov 2017

då får jag att i Z8 får jag o(0)=1,o(1)=8,o(2)=4,o(3)=8,o(4)=2,o(5)=8,o(6)=4,o(7)=8 och den enda som stämmer överens med ordningen för elementen i Z21är för o(0)=1 för både Z8 och Z21

Sedan ska man alltså se vilka element i Z24 som har någon av ordningen 1,2,4,8 vilket alltså var 8 olika element som har någon av ordningen 1,2,4 eller 8.

Därmed kan man alltså se att antalet möjliga homomorfismer blir 1 från Z8 till Z21 och 8 från Z8 till Z24

Svara Avbryt
Close