Matematik
Endelig gruppe
11. marts 2006 af
Sabrina (Slettet)
Jeg har brug for et eksempel på en endelig gruppe.
Jeg overvejer at bruge:
(x,y) --> (x+y) mod n
Men jeg har svært ved at se, hvad det neutrale element kan være. Har tænkt på 0, men det duer vel kun, hvis x
Hvis det neutrale element er 0, passer det ellers med, at det inverse element bliver -x.
Hvad angår den associative lov er jeg helt tabt. Jeg ved, at der er regnereglen:
(a+b) mod n = (a mod n + b mod n) mod n
men problemet er, at jeg skriver et projekt om n^2-1-puslespillet, så jeg kan ikke begynde at gå i dybden med modulo-regneregler.
Hvis I skulle have et andet simpelt eksempel på en endelig gruppe, som jeg i stedet kan bruge, er I mere end velkomne til at skrive :)
Jeg overvejer at bruge:
(x,y) --> (x+y) mod n
Men jeg har svært ved at se, hvad det neutrale element kan være. Har tænkt på 0, men det duer vel kun, hvis x
Hvis det neutrale element er 0, passer det ellers med, at det inverse element bliver -x.
Hvad angår den associative lov er jeg helt tabt. Jeg ved, at der er regnereglen:
(a+b) mod n = (a mod n + b mod n) mod n
men problemet er, at jeg skriver et projekt om n^2-1-puslespillet, så jeg kan ikke begynde at gå i dybden med modulo-regneregler.
Hvis I skulle have et andet simpelt eksempel på en endelig gruppe, som jeg i stedet kan bruge, er I mere end velkomne til at skrive :)
Svar #1
11. marts 2006 af Sabrina (Slettet)
Jeg glemte at tilføje, at x,y er indeholdt i {1, 2, ... , 10}
Svar #2
11. marts 2006 af Esmil (Slettet)
Du er ellers inden på noget af det rigtige. Den gruppe, du er ved at konstruere kalder man Z_n
Den simpleste (ikke-trivielle) af disse er Z_2 = {0, 1}, hvor
0 + 0 = 1 + 1 = 0 og
0 + 1 = 1 + 0 = 1.
Hvad med en symmetrisk gruppe?
Lad fx. X = {1, 2, 3}, og G være mængden af alle bijektive funktioner f: X -> X.
Nu udgør (G, o), hvor o her skal betyde funktionssammensætning, en gruppe på 6 elementer.
Funktionssammensætning er altid associativt, så det klarer første aksiom.
Det neutrale element er blot identitetsfunktionen id på X ( id(x) = x ).
Da alle funktioner i G er bijektive har de alle en invers funktion f^-1, som minsandten også er det inverse element i gruppen. f o f^-1 = f^-1 o f = id.
Den simpleste (ikke-trivielle) af disse er Z_2 = {0, 1}, hvor
0 + 0 = 1 + 1 = 0 og
0 + 1 = 1 + 0 = 1.
Hvad med en symmetrisk gruppe?
Lad fx. X = {1, 2, 3}, og G være mængden af alle bijektive funktioner f: X -> X.
Nu udgør (G, o), hvor o her skal betyde funktionssammensætning, en gruppe på 6 elementer.
Funktionssammensætning er altid associativt, så det klarer første aksiom.
Det neutrale element er blot identitetsfunktionen id på X ( id(x) = x ).
Da alle funktioner i G er bijektive har de alle en invers funktion f^-1, som minsandten også er det inverse element i gruppen. f o f^-1 = f^-1 o f = id.
Svar #3
11. marts 2006 af Esmil (Slettet)
Hov forresten. Den symmetriske gruppe jeg beskrev ovenfor kaldes S_3. Den er sjov, for i modsætning til alle Z_n er den ikke abelsk. Dvs. f o g ikke altid er det samme som g o f for f og g i S_3.
På samme måde kan man konstruere S_n, hvis man blot lader X = {1, 2, ..., n}.
Se evt.:
http://da.wikipedia.org/wiki/Gruppe_%28matematik%29
På samme måde kan man konstruere S_n, hvis man blot lader X = {1, 2, ..., n}.
Se evt.:
http://da.wikipedia.org/wiki/Gruppe_%28matematik%29
Svar #4
11. marts 2006 af Sabrina (Slettet)
Mange tak for dit svar!
Jeg tror dog, at jeg er nødt til at se på Z_10 frem for S_3, eftersom jeg først behandler permutationer i afsnittet efter.
Hvad vil det neutrale element være i Z_2? Og hvordan med associativitet og et inverst element?
Hvordan skriver man egentlig denne gruppe op - her tænker jeg på formen (mængde, komposition)?
Men hvordan beviser man egentlig, at funktionssammensætning altid er associativ? Har du evt. et link, hvis det er et længere bevis?
Jeg tror dog, at jeg er nødt til at se på Z_10 frem for S_3, eftersom jeg først behandler permutationer i afsnittet efter.
Hvad vil det neutrale element være i Z_2? Og hvordan med associativitet og et inverst element?
Hvordan skriver man egentlig denne gruppe op - her tænker jeg på formen (mængde, komposition)?
Men hvordan beviser man egentlig, at funktionssammensætning altid er associativ? Har du evt. et link, hvis det er et længere bevis?
Svar #5
11. marts 2006 af Esmil (Slettet)
I Z_2 er det neutrale element 0, da
0 + 0 = 0 og
0 + 1 = 1 + 0 = 1,
og dermed er 0 + x = x + 0 = x for alle x i Z_2.
Det inverse element til 0 er 0, da
0 + 0 = 0,
og det inverse element til 1 er 1, da
1 + 1 = 0.
På samme måde kan du give til at tjecke associativitet, ved at bruge regnereglerne ovenfor, det er dog en smule omstændigt.
Den måde, man normalt konstruerer Z_n er dog en smule kompliceret også. Det, man gør, er at dele Z ind i n ækvivalensklasser.
Først definerer man en ækvivalensrelation ~ ved
x ~ y <=> x = y (mod n) <=> n | x - y
Nu er en ækvivalens klasse så givet ved
[x] = { y i Z | x ~ y }.
Nu kan man så vise, at
[x] = [y] <=> x ~ y,
og at man på den måde får delt hele Z op i n disjunkte mængder. Disse mængder bruger man så som "tal", og definerer
[x] + [y] = [x + y].
Her skal man så bevise, at det er veldefineret. Dvs. at det ikke afhænger af repræsentanterne for ækvivalensklassen. Altså
[x] = [x'] og [y] = [y'] => [x + y] = [x' + y'].
Nu kan man så gå igang med at vise, at det rent faktisk udgør en gruppe med neutralt element [0], og hvor [x]^-1 = [-x].
0 + 0 = 0 og
0 + 1 = 1 + 0 = 1,
og dermed er 0 + x = x + 0 = x for alle x i Z_2.
Det inverse element til 0 er 0, da
0 + 0 = 0,
og det inverse element til 1 er 1, da
1 + 1 = 0.
På samme måde kan du give til at tjecke associativitet, ved at bruge regnereglerne ovenfor, det er dog en smule omstændigt.
Den måde, man normalt konstruerer Z_n er dog en smule kompliceret også. Det, man gør, er at dele Z ind i n ækvivalensklasser.
Først definerer man en ækvivalensrelation ~ ved
x ~ y <=> x = y (mod n) <=> n | x - y
Nu er en ækvivalens klasse så givet ved
[x] = { y i Z | x ~ y }.
Nu kan man så vise, at
[x] = [y] <=> x ~ y,
og at man på den måde får delt hele Z op i n disjunkte mængder. Disse mængder bruger man så som "tal", og definerer
[x] + [y] = [x + y].
Her skal man så bevise, at det er veldefineret. Dvs. at det ikke afhænger af repræsentanterne for ækvivalensklassen. Altså
[x] = [x'] og [y] = [y'] => [x + y] = [x' + y'].
Nu kan man så gå igang med at vise, at det rent faktisk udgør en gruppe med neutralt element [0], og hvor [x]^-1 = [-x].
Svar #6
12. marts 2006 af Sabrina (Slettet)
Mange tak for dit svar!
Ved du, hvordan man beviser, at funktionssammensætning (dvs. o) altid er associativ? Har du evt. et link, hvis det er et længere bevis?
Ved du, hvordan man beviser, at funktionssammensætning (dvs. o) altid er associativ? Har du evt. et link, hvis det er et længere bevis?
Svar #7
12. marts 2006 af Esmil (Slettet)
Jamen prøv at se her:
Lad f, g, h være permutationer af X. Nu gælder for alle x i X, at
((f o g) o h)(x) = (f o g)(h(x)) = f(g(h(x)))
og
(f o (g o h))(x) = f((g o h)(x)) = f(g(h(x))).
Altså er funktionerner (f o g) o h og f o (g o h) ens på hele X, og dermed er det samme funktion.
QED ;-)
Lad f, g, h være permutationer af X. Nu gælder for alle x i X, at
((f o g) o h)(x) = (f o g)(h(x)) = f(g(h(x)))
og
(f o (g o h))(x) = f((g o h)(x)) = f(g(h(x))).
Altså er funktionerner (f o g) o h og f o (g o h) ens på hele X, og dermed er det samme funktion.
QED ;-)
Svar #8
12. marts 2006 af Sabrina (Slettet)
Hehe! Tak :)
Jeg har stadig lidt svært ved at forstå Z_10
Det inverse element vil altid være det samme som elementet selv?
Det neutrale element er 0?
Men vil valget af disse ikke afhænge af værdien af n?
Hvordan skrives gruppen Z_10 på formen (mængde, komposition)?
Håber du orker at svare :)
Jeg har stadig lidt svært ved at forstå Z_10
Det inverse element vil altid være det samme som elementet selv?
Det neutrale element er 0?
Men vil valget af disse ikke afhænge af værdien af n?
Hvordan skrives gruppen Z_10 på formen (mængde, komposition)?
Håber du orker at svare :)
Svar #9
12. marts 2006 af fixer (Slettet)
Undskyld jeg blander mig i jeres tråd, men jeg synes det er betimeligt, for de oprindelige spørgsmål er stadigt ubesvarede.
Du har valgt konstruere en gruppe med heltalsaddition modulo n som komposition. Som bekendt (?) er relationen 'kongruens modulo n' en ækvivalensrelation med ækvivalensklasserne
[0]_n, [1]_n,...,[n-1]_n
Mængden af disse ækvivalensklasser kaldes Z_n. I denne mængde indføres nu kompositionen 'addition modulo n'. Vi kan betegne kompositionen med +' for at adskille den fra den sædvanlige heltalsaddition +.
Det er så en kendt sag, at herved bliver (Z_n,+') en abelsk gruppe som kaldes den additive restklassegruppe modulo n.
Der er ingen grund til at du beviser, at det er en gruppe - f.eks. at kompositionen er associativ. Det følger naturligvis af modulær aritmetik, men det er tilstrækkeligt at referere til det kendte faktum, at (Z_n,+') er en gruppe.
I (Z_n,+') er [0]_n det neutrale element. Det inverse element til [a]_n er [n-a]_n. Man kalder også Z_n for cykliske grupper, men lad os springe det over indtil videre.
Det er i almindelighed _ikke_ muligt at danne en multiplikationsgruppe over Z_n, idet der ikke er noget multiplikativt invers i Z_n, for n > 1. Den eneste multiplikative restklassegruppe er (Z_1,*').
Derimod kan man ved at indføre multiplikation og addition modulo n på Z_n danne en kommutativ ring, som man skrive Z/nZ, men det er en anden sag.
For nu at tage det konkrete tilfælde, så betragtes relationen 'kongruens modulo 10' som giver anledning til en klassedeling af Z i klasserne
[0]_10,[1]_10,...[9]_10
Mængden af disse 10 ækvivalensklasser er Z_10 og indføres heri kompositionen 'addition modulo 10' fremkommer den additive restklassegruppe (Z_10,+').
Det neutrale element er [0]_10. Det inverse element til f.eks [3]_10 er [10-3]_10 = [7]_10. Du kan lege lidt med restklasser for at få fornemmelse for dem. Til eksempel kan vi betragte de to heltal a=13 og b=17. Da gælder at a E [3]_10 og b E [7]_10. Endvidere er a+b = 30 E [0]_10. I addition modulo 10 har man derfor
[3]_10 + [7]_10 = [0]_10
og da summen således er det neutrale element, er [3]_10 og [7]_10 hinandens inverse.
Du har valgt konstruere en gruppe med heltalsaddition modulo n som komposition. Som bekendt (?) er relationen 'kongruens modulo n' en ækvivalensrelation med ækvivalensklasserne
[0]_n, [1]_n,...,[n-1]_n
Mængden af disse ækvivalensklasser kaldes Z_n. I denne mængde indføres nu kompositionen 'addition modulo n'. Vi kan betegne kompositionen med +' for at adskille den fra den sædvanlige heltalsaddition +.
Det er så en kendt sag, at herved bliver (Z_n,+') en abelsk gruppe som kaldes den additive restklassegruppe modulo n.
Der er ingen grund til at du beviser, at det er en gruppe - f.eks. at kompositionen er associativ. Det følger naturligvis af modulær aritmetik, men det er tilstrækkeligt at referere til det kendte faktum, at (Z_n,+') er en gruppe.
I (Z_n,+') er [0]_n det neutrale element. Det inverse element til [a]_n er [n-a]_n. Man kalder også Z_n for cykliske grupper, men lad os springe det over indtil videre.
Det er i almindelighed _ikke_ muligt at danne en multiplikationsgruppe over Z_n, idet der ikke er noget multiplikativt invers i Z_n, for n > 1. Den eneste multiplikative restklassegruppe er (Z_1,*').
Derimod kan man ved at indføre multiplikation og addition modulo n på Z_n danne en kommutativ ring, som man skrive Z/nZ, men det er en anden sag.
For nu at tage det konkrete tilfælde, så betragtes relationen 'kongruens modulo 10' som giver anledning til en klassedeling af Z i klasserne
[0]_10,[1]_10,...[9]_10
Mængden af disse 10 ækvivalensklasser er Z_10 og indføres heri kompositionen 'addition modulo 10' fremkommer den additive restklassegruppe (Z_10,+').
Det neutrale element er [0]_10. Det inverse element til f.eks [3]_10 er [10-3]_10 = [7]_10. Du kan lege lidt med restklasser for at få fornemmelse for dem. Til eksempel kan vi betragte de to heltal a=13 og b=17. Da gælder at a E [3]_10 og b E [7]_10. Endvidere er a+b = 30 E [0]_10. I addition modulo 10 har man derfor
[3]_10 + [7]_10 = [0]_10
og da summen således er det neutrale element, er [3]_10 og [7]_10 hinandens inverse.
Svar #10
12. marts 2006 af fixer (Slettet)
#1
Jeg ser lige denne bemærkning, og bliver derfor nødt til at uddybe bemærkningen i #9 ang. cykliske grupper.
En cyklisk gruppe er en gruppe, der kan genereres af et enkelt element. En gruppe G er defor cyklisk hvis der findes et element h E G sådan at G = gp({x}). Notationen gp({x}) angiver den mængde, der genereres af elementet {x}. Cykliske grupper, C_n, er abelske og har elementer på formen {1,x,x²,...,x^(n-1)}, hvor x er det genererende element. Her menes med x² naturligvis x*x hvor '*' er gruppekompositionen. Tilsvarende for de øvrige elementer.
Eksempel: (Z,+) er en uendelig cyklisk gruppe, idet Z = gp({1}) under addition.
Den cykliske gruppe C_n er isomorf med den additive restklassegruppe modulo n.
Jeg ser lige denne bemærkning, og bliver derfor nødt til at uddybe bemærkningen i #9 ang. cykliske grupper.
En cyklisk gruppe er en gruppe, der kan genereres af et enkelt element. En gruppe G er defor cyklisk hvis der findes et element h E G sådan at G = gp({x}). Notationen gp({x}) angiver den mængde, der genereres af elementet {x}. Cykliske grupper, C_n, er abelske og har elementer på formen {1,x,x²,...,x^(n-1)}, hvor x er det genererende element. Her menes med x² naturligvis x*x hvor '*' er gruppekompositionen. Tilsvarende for de øvrige elementer.
Eksempel: (Z,+) er en uendelig cyklisk gruppe, idet Z = gp({1}) under addition.
Den cykliske gruppe C_n er isomorf med den additive restklassegruppe modulo n.
Svar #12
12. marts 2006 af Esmil (Slettet)
#8 Nej for søren. Z_2 er den eneste af de cykliske grupper, hvor alle elementer er deres egen invers. Hvis [x] er et element i Z_n, så er dets inverse netop den ækvivalensklasse, der indeholder -x, altså [-x]. Nu er
[x] + [-x] = [x + (-x)] = [0],
og [0] er nemlig altid det neutrale element i Z_n. Som fixer også skriver er
[-x] = [n-x].
Jeg kom forresten i tanke om noget, du måske kan bruge, hvis du har haft matrixregning. Der findes nemlig en grupper af matricer (GL_n(F), bestående af invertible n x n matricer over legemet F) med kompositionen gange, der har massere af endelige undergrupper. En af dem (en undergruppe af fx. GL_3(R)) består af disse 6 matricer, og er isomorf til S_3:
(Lad være med at bekymre om det i paranteser, det er der kun for at forvirre dig;-)
[100]
[010] ~ 1,
[001]
[010]
[001] ~ (1 2 3),
[100]
[100]
[001] ~ (1 3 2),
[010]
[010]
[100] ~ (1 2),
[001]
[100]
[001] ~ (2 3),
[010]
[001]
[010] ~ (1 3)
[100]
Du kunne også nøjes med de 3 første matricer. De udgør nemlig en gruppe i sig selv, stadig mht. til matrixmultiplikation, og er isomorf til Z_3.
[x] + [-x] = [x + (-x)] = [0],
og [0] er nemlig altid det neutrale element i Z_n. Som fixer også skriver er
[-x] = [n-x].
Jeg kom forresten i tanke om noget, du måske kan bruge, hvis du har haft matrixregning. Der findes nemlig en grupper af matricer (GL_n(F), bestående af invertible n x n matricer over legemet F) med kompositionen gange, der har massere af endelige undergrupper. En af dem (en undergruppe af fx. GL_3(R)) består af disse 6 matricer, og er isomorf til S_3:
(Lad være med at bekymre om det i paranteser, det er der kun for at forvirre dig;-)
[100]
[010] ~ 1,
[001]
[010]
[001] ~ (1 2 3),
[100]
[100]
[001] ~ (1 3 2),
[010]
[010]
[100] ~ (1 2),
[001]
[100]
[001] ~ (2 3),
[010]
[001]
[010] ~ (1 3)
[100]
Du kunne også nøjes med de 3 første matricer. De udgør nemlig en gruppe i sig selv, stadig mht. til matrixmultiplikation, og er isomorf til Z_3.
Svar #13
12. marts 2006 af Esmil (Slettet)
Ups.. matrix nr. 3 burde have været
[001]
[100]
[010]
og ikke det samme som matrix nr. 5
[001]
[100]
[010]
og ikke det samme som matrix nr. 5
Svar #14
12. marts 2006 af Sabrina (Slettet)
Mange tak til jer begge for de fine svar! :)
Jeg må indrømme, at noget af det er rimelig svært at forstå, da jeg ikke har haft ret meget om grupper. Dog har jeg haft de første fem forelæsninger i et kursus om lineær algebra, så kender da lidt til matricer.
Ang. den associative lov for Z_10, så er jeg nødt til at vise, at den gælder, da det er et krav fra min vejleders side. Dog skal det ske på et lidt "overfladisk niveau", da jeg ikke skal gå i dybden med ækvivalensklasser, moduloregneregler mv.
For at give jer en idé om, hvorledes det gerne skal skrives, kan I prøve at se følgende uddrag af mit eksempel. Der har jeg brugt jeres svar og så skrevet det på en mindre formel måde - og væsentligt mere overfladisk (desværre).
"Vi vil i dette eksempel vise, at (Z_10,+') er en gruppe, hvor kompositionen +' betegner addition modulo 10, og Z_10 = {0, 1, ... , 9}. Modulo 10 angiver resten ved division af et elementer i Z_10 med 10.
I gruppen Z_10,+') er det neutrale element 0, hvilket fremgår af følgende ligning, hvor x indeholdt i Z_10:
(x+0) mod 10 = x mod 10 = x
Lighedstegnet længst mod højre gælder, idet x
Det inverse element x^{-1} i Z_10 til x i Z_10 er 10-x, eftersom
(x+x^-1) mod 10 = (x+(10-x)) mod 10 = 10 mod 10 = 0
Det sidste lighedstegn skyldes, at resten ved division af 10 med 10 bliver 0."
Mængden {1,...,10} lavede jeg om til {0,...,9} for at få det til at passe med det, som I har fortalt mig.
Jeg må indrømme, at noget af det er rimelig svært at forstå, da jeg ikke har haft ret meget om grupper. Dog har jeg haft de første fem forelæsninger i et kursus om lineær algebra, så kender da lidt til matricer.
Ang. den associative lov for Z_10, så er jeg nødt til at vise, at den gælder, da det er et krav fra min vejleders side. Dog skal det ske på et lidt "overfladisk niveau", da jeg ikke skal gå i dybden med ækvivalensklasser, moduloregneregler mv.
For at give jer en idé om, hvorledes det gerne skal skrives, kan I prøve at se følgende uddrag af mit eksempel. Der har jeg brugt jeres svar og så skrevet det på en mindre formel måde - og væsentligt mere overfladisk (desværre).
"Vi vil i dette eksempel vise, at (Z_10,+') er en gruppe, hvor kompositionen +' betegner addition modulo 10, og Z_10 = {0, 1, ... , 9}. Modulo 10 angiver resten ved division af et elementer i Z_10 med 10.
I gruppen Z_10,+') er det neutrale element 0, hvilket fremgår af følgende ligning, hvor x indeholdt i Z_10:
(x+0) mod 10 = x mod 10 = x
Lighedstegnet længst mod højre gælder, idet x
Det inverse element x^{-1} i Z_10 til x i Z_10 er 10-x, eftersom
(x+x^-1) mod 10 = (x+(10-x)) mod 10 = 10 mod 10 = 0
Det sidste lighedstegn skyldes, at resten ved division af 10 med 10 bliver 0."
Mængden {1,...,10} lavede jeg om til {0,...,9} for at få det til at passe med det, som I har fortalt mig.
Svar #15
12. marts 2006 af fixer (Slettet)
Her kommer så argumentationen, så må du selv gøre den så uformel du vil.
For n E N og a,b E Z siger vi at a er kongruent b modulo n hvis der findes et q E Z så a-b = qn.
Dernæst defineres for ethvert n E N relation 'ækvivalens modulo n' og det vises at dette er en ækvivalensrelation (for ethvert n). Det behøver du ikke gøre, det er kendt.
Det følger umiddelbart af definitionen på kongruens modulo n, at ækvivalensklassen for a er mængden
{b E Z | b == a (mod) n} = {a+qn : q E Z}
hvor jeg med symbolet "==" har prøvet at angive ækvivalenstegnet (LaTeX: \\equiv).
Ækvivalensklassen for a er udskrevet altså
{...,a-qn, a-(q-1)n,...,a-n,a,a+n,...a+(q-1)n,a+qn,...}
som vi vælger at skrive enklere som a+nZ.
Det er nu klart at hvis n E N og a,b E Z så er a+nZ = b+nZ hviss a == b (mod) n. Det følger direkte af definitionen på ækvivalensklassen.
Assiciativiteten af addition af restklasser modulo n følger nu hovedsageligt af at addition er associativ i Z, thi så er
((a+nZ) + (b+nZ)) + (c+nZ) = (a+b+nZ) + (c+nZ) = (a+b+c+nZ)
og
(a+nZ) + ((b+nZ) + (c+nZ)) = (a+nZ) + (b+c+nZ) = (a+b+c+nZ)
så addition modulo n er associativ.
Tilsvarende kan vises for multiplikation.
For n E N og a,b E Z siger vi at a er kongruent b modulo n hvis der findes et q E Z så a-b = qn.
Dernæst defineres for ethvert n E N relation 'ækvivalens modulo n' og det vises at dette er en ækvivalensrelation (for ethvert n). Det behøver du ikke gøre, det er kendt.
Det følger umiddelbart af definitionen på kongruens modulo n, at ækvivalensklassen for a er mængden
{b E Z | b == a (mod) n} = {a+qn : q E Z}
hvor jeg med symbolet "==" har prøvet at angive ækvivalenstegnet (LaTeX: \\equiv).
Ækvivalensklassen for a er udskrevet altså
{...,a-qn, a-(q-1)n,...,a-n,a,a+n,...a+(q-1)n,a+qn,...}
som vi vælger at skrive enklere som a+nZ.
Det er nu klart at hvis n E N og a,b E Z så er a+nZ = b+nZ hviss a == b (mod) n. Det følger direkte af definitionen på ækvivalensklassen.
Assiciativiteten af addition af restklasser modulo n følger nu hovedsageligt af at addition er associativ i Z, thi så er
((a+nZ) + (b+nZ)) + (c+nZ) = (a+b+nZ) + (c+nZ) = (a+b+c+nZ)
og
(a+nZ) + ((b+nZ) + (c+nZ)) = (a+nZ) + (b+c+nZ) = (a+b+c+nZ)
så addition modulo n er associativ.
Tilsvarende kan vises for multiplikation.
Svar #16
12. marts 2006 af Sabrina (Slettet)
Mange tak for dit svar!
Jeg skal nok komme til at ødelægge det helt i min uformelle omskrivning ;)
I må have en fortsat god søndag.
Jeg skal nok komme til at ødelægge det helt i min uformelle omskrivning ;)
I må have en fortsat god søndag.
Svar #17
12. marts 2006 af fixer (Slettet)
Måske kunne du fortælle hvad det puslespil går ud på - vi stødte også på det i tråden om prædikatlogik. Nu er jeg ved at være temmelig nysgerrig :-)
Svar #18
13. marts 2006 af Sabrina (Slettet)
Hehe :)
Det kan du tro, at jeg vil.
Som før nævnt går jeg på AAU, som fokuserer på gruppearbejde.
Jeg går på 2. semester på basisåret, hvor jeg er i samme faggruppe som fysikere, dataloger, sundhedsmatematikere og softwareingeniører. Det giver mulighed for at blande sig på kryds og tværs af de forskellige studieretninger. Derfor har jeg valgt at benytte mig af denne mulighed og er sammen med en anden matematiker gået i gruppe med fire dataloger. Vores projekt er så et datalogiprojekt omhandlende 15-puslespillet.
15-puslespillet består af et kvadrat (4*4), hvorpå der er placeret 15 brikker, som er nummereret fra 1 til 15, mens det sidste felt er tomt. Det giver mulighed for at skubbe brikkerne rundt.
Når man køber puslespillet er brikkerne placeret i en tilfældig orden. For at løse det skal man skubbe rundt på brikkerne, således de kommer til at stå i nummerorden (med det tomme felt nederst i højre hjørne).
Vores projekt går ud på, at vi skal udvikle en algoritme, som kan finde den optimale løsning, dvs. den løsning, som kræver det færeste antal træk.
Der er så det specielle ved puslespillet at kun cirka halvdelen af startkonfigurationerne (den placering, som brikkerne har fra start), der kan løses. Vi skal så gå ind og vise, at det forholder sig sådan. Dette kan gøres ved at se på lige og ulige permutationer. Herefter skal vi bruge algoritmen til at finde den optimale løsning til en startkonfiguration, som rent faktisk er løselig.
Selvom vi skal udvikle en algoritme og formentlig også implementere den i C, så er der utrolig meget matematik involveret. For at kunne redegøre for ovenstående og for at være i stand til at udvikle algoritmen skal vi både inddrage relationer (bruges bl.a. til at definere, hvad et træk vil sige), grafteori og gruppeteori (herunder primært permutationer). Derudover vil vi skulle omkring, hvorledes man laver et korrekthedsbevis af algoritmen.
1. ordensprædikatlogik får vi brug for, eftersom vi ved vores beviser skal godtgøre, hvilken bevisteknik vi benytter.
Den kontekstuelle del af vores projekt kommer til at omhandle, hvorledes datalogi påvirker matematikken. Denne problemstilling vil vi undersøge nærmere gennem et casestudie, hvor vi bl.a. går ind og ser på Costas minimalflade.
Det var en lille introduktion til mit projekt - du er velkommen til at stille spørgsmål! :)
Det kan du tro, at jeg vil.
Som før nævnt går jeg på AAU, som fokuserer på gruppearbejde.
Jeg går på 2. semester på basisåret, hvor jeg er i samme faggruppe som fysikere, dataloger, sundhedsmatematikere og softwareingeniører. Det giver mulighed for at blande sig på kryds og tværs af de forskellige studieretninger. Derfor har jeg valgt at benytte mig af denne mulighed og er sammen med en anden matematiker gået i gruppe med fire dataloger. Vores projekt er så et datalogiprojekt omhandlende 15-puslespillet.
15-puslespillet består af et kvadrat (4*4), hvorpå der er placeret 15 brikker, som er nummereret fra 1 til 15, mens det sidste felt er tomt. Det giver mulighed for at skubbe brikkerne rundt.
Når man køber puslespillet er brikkerne placeret i en tilfældig orden. For at løse det skal man skubbe rundt på brikkerne, således de kommer til at stå i nummerorden (med det tomme felt nederst i højre hjørne).
Vores projekt går ud på, at vi skal udvikle en algoritme, som kan finde den optimale løsning, dvs. den løsning, som kræver det færeste antal træk.
Der er så det specielle ved puslespillet at kun cirka halvdelen af startkonfigurationerne (den placering, som brikkerne har fra start), der kan løses. Vi skal så gå ind og vise, at det forholder sig sådan. Dette kan gøres ved at se på lige og ulige permutationer. Herefter skal vi bruge algoritmen til at finde den optimale løsning til en startkonfiguration, som rent faktisk er løselig.
Selvom vi skal udvikle en algoritme og formentlig også implementere den i C, så er der utrolig meget matematik involveret. For at kunne redegøre for ovenstående og for at være i stand til at udvikle algoritmen skal vi både inddrage relationer (bruges bl.a. til at definere, hvad et træk vil sige), grafteori og gruppeteori (herunder primært permutationer). Derudover vil vi skulle omkring, hvorledes man laver et korrekthedsbevis af algoritmen.
1. ordensprædikatlogik får vi brug for, eftersom vi ved vores beviser skal godtgøre, hvilken bevisteknik vi benytter.
Den kontekstuelle del af vores projekt kommer til at omhandle, hvorledes datalogi påvirker matematikken. Denne problemstilling vil vi undersøge nærmere gennem et casestudie, hvor vi bl.a. går ind og ser på Costas minimalflade.
Det var en lille introduktion til mit projekt - du er velkommen til at stille spørgsmål! :)
Svar #19
14. marts 2006 af fixer (Slettet)
Som jeg forstår det, skal i danne en sammenhængende, todelt graf hvis nummererede punkter modsvarer hvert af de 16 felter (som kan være dækket af en brik eller ej) og hvis kanter forbinder nabopunkter (=nabofelter).
Så skal i betragte mængden af samtlige kredse startende (og dermed terminerende) i det tomme felt. Numrene på de af enhver kreds besøgte punkter vil være permutationer af N = {1,2,...,15}.
I kan så redegøre for, at mængden af alle disse permutationer (som er mængden af alle entydeige afbildninger af N på N) er en undergruppe af S_15 - den symmetriske gruppe af grad 15, nemlig den alternerende gruppe af grad 15, A_15. Den alternerende gruppe A_n består af alle lige permutationer i S_n.
Det lyder spændende, så jeg håber der dukker flere spørgsmål op :-)
Costas minimalflade er vist iøvrigt et element i S_4, men hæng mig ikke op på det.
Så skal i betragte mængden af samtlige kredse startende (og dermed terminerende) i det tomme felt. Numrene på de af enhver kreds besøgte punkter vil være permutationer af N = {1,2,...,15}.
I kan så redegøre for, at mængden af alle disse permutationer (som er mængden af alle entydeige afbildninger af N på N) er en undergruppe af S_15 - den symmetriske gruppe af grad 15, nemlig den alternerende gruppe af grad 15, A_15. Den alternerende gruppe A_n består af alle lige permutationer i S_n.
Det lyder spændende, så jeg håber der dukker flere spørgsmål op :-)
Costas minimalflade er vist iøvrigt et element i S_4, men hæng mig ikke op på det.
Svar #20
16. marts 2006 af Sabrina (Slettet)
Hvor er jeg glad for dine inputs - og rigtig taknemmelig for, at jeg ved, hvor jeg kan stille spørgsmål (der dukker helt sikkert nogle op) :)
Jeg skal ærligt indrømme, at vi endnu ikke har styr på, hvorledes vores graf skal konstrueres.
Men jeg havde faktisk fået det indtryk, at hver eneste brætkonfiguration skulle tildeles et punkt, og så skulle vi forbinde de punkter, hvor det var muligt at komme fra det ene bræt til det andet ved hjælp af ét træk.
Nu jeg har læst dit indlæg, synes jeg faktisk, at det lyder vældig smart. Havde slet ikke tænkt over, at der ville være andre måder at gøre det på.
Men ville din graf blive todelt? Hvis du skal forbinde nabofelterne, så kan du vel forbinde alle punkter.
Lige nu er planen, at vi fokuserer lidt på den kontekstuelle del af rapporten, hvor mit ansvar bliver computervisualisering. Herunder Costas minimalflade.
Derudover kommer konteksten til at indeholde kryptering (den anlagte synsvinkel bliver kapløbet mellem datalogi og matematik) og grafteoriens udvikling set i forhold til computerens bidrag inden for området.
Jeg skal ærligt indrømme, at vi endnu ikke har styr på, hvorledes vores graf skal konstrueres.
Men jeg havde faktisk fået det indtryk, at hver eneste brætkonfiguration skulle tildeles et punkt, og så skulle vi forbinde de punkter, hvor det var muligt at komme fra det ene bræt til det andet ved hjælp af ét træk.
Nu jeg har læst dit indlæg, synes jeg faktisk, at det lyder vældig smart. Havde slet ikke tænkt over, at der ville være andre måder at gøre det på.
Men ville din graf blive todelt? Hvis du skal forbinde nabofelterne, så kan du vel forbinde alle punkter.
Lige nu er planen, at vi fokuserer lidt på den kontekstuelle del af rapporten, hvor mit ansvar bliver computervisualisering. Herunder Costas minimalflade.
Derudover kommer konteksten til at indeholde kryptering (den anlagte synsvinkel bliver kapløbet mellem datalogi og matematik) og grafteoriens udvikling set i forhold til computerens bidrag inden for området.