Diskret matematikk finnes ikke [Lecture notes] [PDF]

Zitiervorschau

DISKRET MATEMATIKK FINNES IKKE

Dan Laksov KTH, Stockholm matematikk/thorup/dlbook/April 11, 2005

DISKRET MATEMATIKK FINNES IKKE

Diskret matematikk finnes ikke Dan Laksov Notater for “Forum f¨ or Matematikl¨ arare”. Et prosjekt høsten 2004 støttet av: Marianne och Marcus Wallenbergs Stiftelse Versjon II. 10. Oktober

Matematiska Institutionen KTH

DISKRET MATEMATIKK FINNES IKKE

Matematiska Institutionen KTH 100 44 STOCKHOLM ISBN ? c

2001 Matematiska Institutionen

FORORD

Disse notatene er et supplement til forelesningene i “Matematisk Forum F¨ or Matematikl¨ arare” (eller kort “Forum”) det akademiske ˚ aret 2004-2005. Alt materialet til de syv forelesningene i “Forum” finnes i heftet, men inndelingen av notatene i kapittel og seksjoner svarer bare delvis til innholdet av forelesningen. Heftet er ment som hjelp for hukommelsen, eller for ˚ a finne supplerende og utdypende materiale. Notatene forutsetter bare kjennskap til de enkleste begrepene fra mengdelæren. Presentasjonen av matematikken er s˚ a stringent som mulig, og det er bare ˚ a h˚ ape at dette ikke har gjort notatene uleselige.

v

vi

DISKRET MATEMATIKK FINNES IKKE

INNHOLD

1. Klassifikasjon av matematikken 1.2 Diskret matematikk og AMS-klassifikasjonen . . 1.2 Hvorfor dele i “diskret” og “annen” matematikk? 2. “Diskret” eller “kontinuerlig”? 2.1 “Diskret” og “kontinuerlig” matematikk . . . . 2.2 Avstand og metriske rom . . . . . . . . . . . 2.3 Eksempler p˚ a metriske rom . . . . . . . . . . 2.4 Kontinuitet . . . . . . . . . . . . . . . . . 3. Topologiske rom og kontinuitet 3.1 Definisjoner og eksempler . . . . . . 3.2 Kontinuitet . . . . . . . . . . . . 4. Blokk-koder og Hamming metrikken 4.1 Et eksempel p˚ a blokk-koder . . . . . 4.2 Et eksempel p˚ a lineære koder . . . . 4.3 Lineær algebra . . . . . . . . . . 4.4 Lineære koder . . . . . . . . . . .

. . . . . . . .

1 2

. . . .

. . . .

3 4 5 8

. . . . . . . . . . . . . . . . . .

11 14

. . . .

5. Analyse p˚ a de hele tallene 5.2 Er de hele tallene “diskrete”? . . . . . 5.2 p-adisk utvikling . . . . . . . . . . 5.3 Aritmetiske operasjoner . . . . . . . 5.4 Cauch sekvenser og p-adiske tall . . . . 5.5 Komplettering av de hele tallene . . . 5.6 Løsning av ligninger modulo primtall . . 5.7 Komplettering av metriske rom . . . . A. Appendix. AMS-klassifikasjonen A.1 Hovedomr˚ ader . . . . . . . . . . . A.2 Delomr˚ ader av Algebraisk Geometri . . A.3 Spesialomr˚ adene av Algebraisk Geometri B. Bibliografi I. Index

vii

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

17 19 21 26

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

27 28 29 31 34 36 38

. . . . . . . . . . . . . . . . . . . . . . . .

43 45 46

viii

DISKRET MATEMATIKK FINNES IKKE

1. KLASSIFIKASJONEN AV MATEMATIKKEN

1.1. Diskret matematikk og AMS-klassifikasjonen

→ →

De fleste som har har kommet i kontakt med matematikk i en eller annen form har hørt om diskret matematikk og har en vag oppfatning av hva det er. N˚ ar man skal presisere hva det er f˚ ar alle, amatører som profesjonelle, store vanskeligheter. Hensikten med dette heftet er ˚ a vise at den enkle forklaringen til dette er at diskret matematikk ikke finnes, og at det er ufruktbart, og tvert imot de ledende strømningene i dagens matematikk, ˚ a skille mellom “diskret” matematikk og “annen” matematikk. Det hjelper ikke at Skolverket har oppfunnet et emne matematik diskret, som er obligatorisk p˚ a matematikk/datalogi grenen av NV-programmet. Navnet skulle egentlig være diskret matematik, men i byr˚ akratispr˚ aket m˚ a alle matematikkemner begynne med ordet matematik. Formelt sett finnes ikke emnet diskret matematikk av den enkle grunn at den ikke er med i AMS-klassifikasjonen av matematikken. Dette er en liste over matematiske emner som ble sammensatt av American Mathematical Society (AMS) og brukes av alle profesjonelle matematikere n˚ ar de skal skille p˚ a ulike deler av matematikken. Listen oppdateres stadig og omfatter i dag 63 hovedomr˚ ader. Hver av disse er delt opp i en rekke delomr˚ ader, oftest 10-20 stykker, og hvert delomr˚ ade er oppdelt i et stort antall spesialomr˚ ader. Denne findelingen av matematikken viser hvilken enorm bredde matematikken har. En ekspert p˚ a et spesialomr˚ ade kan ofte forst˚ a eksperter p˚ a andre spesialomr˚ ader innen samme delomr˚ ade, men kan ha store vanskeligheter med emner innefor andre delomr˚ ader. I Appendiks (A.1) viser vi hovedomr˚ adene i AMS-klassifikasjonen og i (A.2) viser vi delomr˚ adene til et av disse, omr˚ adet Algebraisk Geometri (AMS 14). I (A.3) har vi tatt med klassifikasjonen av hovedomr˚ adet Algebraisk Geometri for ˚ a vise mangfoldigheten av spesialiteter innenfor et av de mange hovedomr˚ adene. Ettersom diskret matematikk hverken er et hovedomr˚ ade, et delomr˚ ade, eller er med i findelingen, finnes det “formelt sett” ikke som emne i matematikken. Emnet “matematik diskret” som Skolverket har oppfunnet best˚ ar av et lite utvalg av noen enkle begreper hentet fra emner under findelingen av Matematisk logikk (AMS 03), Kombinatorikk (AMS 05), Tallteori (AMS 11) og Datalogi (AMS 05). Den lille delen av kombinatorikk som er med tilhører egentlig Sannsynlighetsteorien (AMS 60).

1

2

DISKRET MATEMATIKK FINNES IKKE

1.2. Hvorfor dele i “diskret” og “annen” matematikk? Vi kan bare spekulere p˚ a hvorfor amatørene p˚ a Skolverket har funnet det p˚ atrengende ˚ a samle en konfetti av matematiske emner under rubrikken matematik diskret. En sannsynlig forklaring er at de har latt seg villede av “eksperter” som kjenner et behov av ˚ a profilere seg mot omr˚ ader som p˚ ast˚ aens være spesielt nyttige for utviklingen av datamaskiner og for anvendelsene av disse. Datamaskinene er tilsynelatende “diskrete av naturen”. De opererer med 0’er og 1’ere og kan bare inneholde og formidle en endelig mengde informasjon. For ˚ a konstruere, operere og programmere datamaskiner kreves det store mengder matematikk. Uten matematikken skulle den raske utviklingen av elektronikk vært umulig og datamaskinene skulle være langsomme monstre som bare kunne administrere sm˚ a mengder data. I datamaskinenes barndom var det ganske lite og enkel matematikk som kom til anvendelse. De miljøene innenfor matematikk og datalogi som arbeidet p˚ a slike omr˚ ader fant det opportunt ˚ a skille den matematikken de drev p˚ a med fra annen matematikk ved ˚ a kalle den “diskret” og spesielt anpasset for datamaskinen. Dette ga dem en ufortjent prestisje. Desverre sluttet det ikke med dette. Etterhvert som datamaskinene fikk anvendelser innefor teknikk, samfunnsfag, humaniora og naturvitenskap hevdet samme grupper av matematikere og dataloger at den p˚ ast˚ atte diskret matematikken var spesielt anvendbar ogs˚ a p˚ a disse omr˚ adene. Ofte besto anvendelsene bare i at man døpte om matematiske begrep, som grafer, mengder eller permutasjoner, til mer fantasieggende ord som veier, ektemenn, eller gener. Dette øker hverken forst˚ aelsen av det praktiske problemet eller sjansene for ˚ a løse det. Iblandt overskrider det grensen til den pinlige og latterlige. Desverre er det mange som blir lokket av denne virksomheten ettersom de tror man kan gjøre store innsatser uten innsikt i hverken matematikk eller anvendelser. I virkeligheten har det vist seg at nesten alle deler av matematikken kan brukes i forbindelse med datamaskiner og deres anvendelser. Noe spesielt “diskret” over matematikken eller anvendelsene som har nytte for datamaskinene er det umulig ˚ a oppdage. Den gamle terminologien henger imidlertid igjen ettersom det er opportunt med dagens forskningspolitikk ˚ a bli forbundet med IT- og dataomr˚ adet. Dette skulle ikke spille noen større rolle om det ikke hadde dradd oppmerksomheten bort fra de fundamentale anvendelsene av matematikken, og fra levende grener av matematikken der det kreves store kunnskaper og dyp innsikt for ˚ a bidra til utviklingen.

2. “DISKRET” ELLER “KONTINUERLIG”?

2.1. “Diskret” og “kontinuerlig” matematikk Det er ikke bare formelt at diskret matematikk ikke finnes. Forsøkene til ˚ a skille “diskret” matematikk fra “annen” matematikk skaper forvirring og uklarhet. Bare ideen ˚ a skille ulike deler av matematikken i slike bokser g˚ ar tvert imot utviklingen av matematikken der hovedlinjene i lang tid har vært ˚ a finne teorier og metoder som er felles for all matematikk. Det har vist seg mye mer fruktbart ˚ a bryte felles grunn enn ˚ a skille mellom de ulike omr˚ adene. Ofte beskrives diskret matematikk som motsetningen til kontinuerlig matematikk. Vi skal her vise at dette er umulig fordi begrepet kontinuitet gjennomsyrer de fleste deler av matematikken. Intuitivt har vi en følelse av at diskret og kontinuerlig er motsatte begreper. Beveger vi oss langs tallinjen møter vi en kontinuerlig strøm av reelle tall. Med jevne mellomrom møter vi et helt tall. Vi kan beskrive dette som at de reelle tallene utgjør et kontinuum, og at de hele tallene ligger diskret p˚ a tallinjen. Mer problematisk er det med de rasjonale tallene. G˚ ar vi fra et rasjonalt tall til et annet møter vi en “jevn” strøm av rasjonale tall, men ogs˚ a uendelig mange reelle tall som ikke er rasjonale. Det finnes alts˚ a uendelig mange “hull” som er reelle, men ikke rasjonale. De rasjonale tallene har derfor b˚ ade diskrete og kontinuerlige egenskaper. Dette er bare en overfladisk del av vanskelighetene med ˚ a skille diskret og kontinuerlig. Vi skal se at selv p˚ a de hele tallene kan vi innføre naturlige og nyttige avstandsbegrep som gjør at vi kan snakke om kontinuitet ogs˚ a for disse. V˚ ar intuisjon sl˚ ar feil fordi vi forbinder skillet mellom diskret og kontinuerlig med avstand. De hele tallene er diskrete fordi de ligger p˚ a endelig avstand fra hverandre, og de reelle er kontinierlige fordi det bare finnes reelle tall nær et gitt tall. P˚ a de reelle, rasjonale, og hele tallene, finnes det imidlertid en stor mengde naturlige og brukbare avstandsbegreper i tillegg til den Eukliske som er den v˚ ar intuisjon er grunnlagt p˚ a. De fleste av disse avstandene kan vi ikke anskueliggjøre. Til og med endelige mengder har, som vi skal se, slike avstander. Derfor blir vi ofte lurt til ˚ a betrakte hele tall og endelige mengder som diskrete skjønt de har, i mange forbindelser, kontinuerlige egenskaper. Oppgaver. Oppgave 1. Vis at mellom to ulike rasjonale tall finnes det uendelig mange rasjonale tall. 3

4

DISKRET MATEMATIKK FINNES IKKE

Oppgave 2. Vis at mellom to rasjonale tall finnes det uendelig mange reelle tall. Oppgave 3. Vis at vi kan nummerere de rasjonale tallene, slik at det finnes “like mange” rasjonale tall som det finnes naturlige tall 0, 1, 2, . . . . (Hint: Bruk Cantor’s diagonaliseringsmetode). Oppgave 4. Vis at de reelle tallene ikke kan nummereres. (Hint: Bruk Cantor’s diagonaliseringsmetode). 2.2. Avstand og metriske rom Begrepene avstand og kontinuitet forekommer i nesten alle deler av matematikken. Det er dette som er hovedgrunnen til at det er umulig ˚ a skille “kontinuerlig matematikk” fra “annen” matematikk. I denne seksjonen skal vi definere avstand og det tilhørende begrepet metrisk rom og gi eksempler der avstandene har overraskende egenskaper, helt forskjellige fra de vi er vant til. P˚ a den reelle linjen R har vi den vanlige absoluttverdien |x − y| som gir avstanden mellom punktene x og y. De egenskapene vi vanligvis bruker for absoluttverdien er: (1) (2) (3) (4)

(Ikke degenererthet) |x| = 0 hvis og bare hvis x = 0. (Symmetri) |x − y| = |y − x|. (Triangelulikhet) |x + y| ≤ |x| + |y|. (Multiplikativitet) |xy| = |x||y|.

I planet R2 har vi at avstanden mellom punktene x = (a1 , a2 ) og y = (b1 , b2 ) er gitt ved p |x − y| = (a1 − b1 )2 + (a2 − b2 )2 .

Mer generelt har vi i det n-dimensjonale Euklidske rommet Rn at avstanden mellom punktene x = (a1 , a2 , . . . , an ) og y = (b1 , b2 , . . . , bn ) er |x − y| =

p (a1 − b1 )2 + (a2 − b2 )2 + · · · + (an − bn )2 .

Denne avstanden tilfredsstiller egenskapene: (1) (Ikke degenererthet) |x| = 0 hvis og bare hvis x = 0. (2) (Symmetri) |x − y| = |y − x|. (3) (Triangelulikhet) |x + y| ≤ |x| + |y|.

Multiplikativiteten for absoluttverdien av reelle tall har ingen mening i det n dimensjonale rommet ettersom vi ikke kan multiplisere to punkter. N˚ ar vi setter dE (x, y) = |x − y| i disse eksemplene vil dE (x, y) være et ikke negativt tall som tilfredsstiller egenskapene: (1) (Ikke degenererthet) dE (x, y) = 0 hvis og bare hvis x = y. (2) (Symmetri) dE (x, y) = dE (y, x). (3) (Triangelulikhet) dE (x, z) ≤ dE (x, y) + dE (y, z).

Det er naturlig ˚ a bruke egenskapen for avstanden i det Euklidske rommet R n som modell for avstand i vilk˚ arlige rom.

2.3. EKSEMPLER P˚ A METRISKE ROM

5

2.2.1 Definisjon. La X være en vilk˚ arlig mengde. En avstand d, eller som vi sier metrikk, p˚ a X tilordner til hvert par av elementer x, y i X et ikke negativt reelt tall d(x, y) slik at (1) (Ikke degenererthet) d(x, y) = 0 hvis og bare hvis x = y. (2) (Symmetri) d(x, y) = d(y, x). (3) (Triangelulikhet) d(x, z) ≤ d(x, y) + d(y, z).

Vi kaller X med en slik avstand d et metrisk rom. Iblandt kaller vi paret (X, d) for et metrisk rom.

→

2.2.2 Bemerkning. Vi skal i mange situasjoner bruke at om (X, dX ) er et metrisk rom og Y er en undermengde av X, og vi skriver dX (x, y) = dY (x, y) n˚ ar x og y begge er i Y , s˚ a vil (Y, dY ) ogs˚ a være et metrisk rom. Dette er helt klart ettersom aksiomene (1), (2), (3) i Definisjon (2.2.3) er de samme for dX og dY . Vi kaller (Y, dY ) det induserte metriske rommet. Det er bemerkelsesverdig at vi med en slik enkel definisjon har f˚ att et begrep som b˚ ade er anvendbart og fleksibelt, og som omfatter interessante eksempler fra store deler av matematiken. Oppgaver.

→

Oppgave 1. Vis at egenskapene (1), (2), (3) fra Seksjon (2.2) holder for absoluttverdien i Rn . (Hint: Bruk Schwartz ulikhet).

→

Oppgave 2.. Vis at egenskapene (1), (2), (3) fra Seksjon (2.2) for absouttverdien p˚ a Rn gir egenskapene (1), (2), (3) for dE definert av dE (x, y) = |x − y|. 2.3. Eksempler p˚ a metriske rom Vi skal her gi de vanligste eksemplene p˚ a metriske rom, samt noen mer eksotiske smakebiter. Eksemplene har interesse i seg selv, men fremfor alt viser de hvor omfattende og brukbare metriske rom er. Vi skal senere komme tilbake til anvendelser p˚ a koder og i tallteorien. 2.3.1 Eksempel. (Reelle linjen) Vi har sett at den reelle linjen X = R med den Euklidske avstanden dE (x, y) = |x − y| er et metrisk rom.

→

2.3.2 Eksempel. (Euklidske rommet) Mer generelt enn i Eksempel (2.3.1) har vi at det n dimensjonale Euklidske rommet X = Rn med avstanden dE (x, y) = |x − y| er et metrisk rom. 2.3.3 Eksempel. (Diskret metrikk) For hver mengde X setter vi dD (x, y) = Da er (X, dD ) et metrisk rom.



0 om 1 om

x=y x 6= y.

6

DISKRET MATEMATIKK FINNES IKKE

2.3.4 Eksempel. (Hamming metrikken) For hver mengde A skriver vi X = An for det n’te Kartesiske produktet av A med seg selv n ganger. Det vil si, X = A n best˚ ar av alle n’tupler x = (a1 , a2 , . . . , an ) av elementer a1 , a2 , . . . , an i A. For x = (a1 , a2 , . . . , an ) og y = (b1 , b2 , . . . , bn ) i X definerer vi avstanden dH (x, y) mellom x og y som antallet indekser i slik at ai er forskjellig fra bi . Det vil si, dH (x, y) = {antallet indekser i slik at ai 6= bi }. For eksempel, om A = {0, 1} og X = A3 vil dH ((1, 0, 1), (0, 0, 1)) = 1,

→

→

dH ((1, 0, 1), (1, 1, 0)) = 2,

dH ((1, 0, 1), (0, 1, 0)) = 3.

Da er dH en metrikk p˚ a X. Det er klart at egenskapene (1) og (2) fra Definisjon (2.2.1) holder. For ˚ a vise egenskapen (3) tar vi z = (c1 , c2 , . . . , cn ). Om i er en indeks som bidrar til dH (x, z), det vil si ai 6= ci , s˚ a m˚ a enten ai 6= bi eller ai 6= ci , eller begge. Derfor bidrar indeksen i til dH (x, y) eller til dH (y, z), eller til begge. Dette resonnementet for i = 1, 2, . . . , n viser at triangelulikheten dH (x, z) ≤ dH (x, y) + dH (y, z) holder. Metrikken d kalles Hamming metrikken oppkalt etter Richard Hamming (191598) som brukte den i kodeteorien. Vi kommer tilbake til Hamming metrikken i forbindelser med koder i et kapittel (4). 2.3.5 Eksempel. (Taksimetrikken) P˚ a det Kartesiske produktet X = Rn definerer vi avstanden mellom punktene x = (a1 , a2 , . . . , an ) og y = (b1 , b2 , . . . , bn ) ved dT (x, y) = |a1 − b1 | + |a2 − b2 | + · · · + |an − bn |.

→

Det er klart at egenskapene (1) og (2) i for en metrikk i Definisjon (2.3.3) holder for dT , og egenskapen (3) følger av triangelulikhetene |ai − ci | ≤ |ai − bi | + |bi − ci | for i = 1, 2, . . . , n. Derfor er (X, dT ) et metrisk rom. Vi kaller dT for Taksimetrikken ettersom avstanden mellom motsatte hjørner (a1 , a2 ) og (b1 , b2 ) i et rektangel er summen av avstanden mellom hjørnene (a1 , a2 ) og (b1 , a2 ), og avstanden mellom hjørnene (b1 , a2 ) og (b1 , b2 ). Det vil si den avstanden en taksi m˚ a kjøre for ˚ a komme fra hørnet (a1 , a2 ) til det diagonalt motsatte hjørnet (b1 , b2 ) om rektangelet var basen for et hus. Det bemerkelsesverdige ved Taksimetrikken p˚ a Rn er at den p˚ a mange m˚ ater er ekvivalent med den Euklidske metrikken, det vil si, to punkter er nære hverandre i en metrikk n˚ ar de er nære i den andre. Mer bestemt. La dE være den Euklidske metrikken og dT Taksimetrikken. Da finnes det positive konstanter C1 og C2 slik at for alle x og y i X = Rn vil C1 dE (x, y) ≤ dT (x, y) ≤ C2 dE (x, y). Mye av “den vanlige” geometrien kan man gjøre√ i Taksimetrikken. Dette gir mange overraskende resultater, som at “taksi π” er lik 4 2. Se Dukels artikkel i [S] for en underholdende fremstilling.

2.3. EKSEMPLER P˚ A METRISKE ROM

7

2.3.6 Eksempel. (Den p-adiske metrikken p˚ a Z) La X = Z være de hele tallene og velg et primtall p. Hvert heltall n forskjellig fra null kan skrives entydig som n = pk m der k er et ikke negativt heltall og m er et heltall som ikke er delbart med p. Definer en norm p˚ a Z ved |n|p = 1/pk . Tallet 0 er spesielt ettersom pk deler 0 for alle k. Vi setter derfor |0|p = 0. For eksempel, om p = 2 har vi |2|2 = 1/2, |3|2 = 1, |4|2 = 1/22 , |5|2 = 1, |6|2 = 1/2, |7|2 = 1, |8|2 = 1/23 . . . . Det er en grei, og instruktiv, oppgave ˚ a vise at følgende egenskaper holder: (1) (2) (3) (4)

(Ikke degenererthet) |n|p = 0 hvis og bare hvis n = 0. (Symmetri) |n|p = | − n|p . (Ikke arkimedisk triangelulikhet) |m + n|p ≤ max(|m|p , |n|p ). (Multiplikativitet) |nm|p = |m|p |n|p .

Merk at egenskapen (3) er sterkere enn den vanlige triangelulikheten ettersom vi vanligvis har max(|m|p , |n|p ) < |m|p + |n|p . Setter vi dp (m, n) = |m − n|p f˚ ar vi (1) (Ikke degenererthet) dp (x, y) = 0 hvis og bare hvis x = y. (2) (Symmetri) dp (x, y) = dp (y, x). (3) (Ikke arkimedisk triangelulikhet) dp (x, z) ≤ max(dp (x, y), dp(y, z)).

Vi kaller dp den p-adiske metrikken p˚ a heltallene. I den p-adiske metrikker er ikke Z lenger diskret. For eksempel vil det for hvert heltall n finnes uendelig mange heltall n + pk som ligger s˚ a “nær” n som vi vil fordi dp (n, n + pk ) = |pk |p = 1/pk som vi kan f˚ a s˚ a “liten vi vil” ved ˚ a velge k “tilstrekkelig stor”. Rommet (Z, dp ) skiller seg vesentlig fra de hele tallene med metrikken indusert av den Euklidske metrikken p˚ a R. For eksempel vil d2 (2n − 2n−2 , 2n ) = |2n−1 |2 = 1/2n−1 mens dE (2n − 2n−2 , 2n ) = |2n−1 | = 2n−1 . Det vil si, tallene 2n − 2n−1 og 2n ligger “nære” i den 2-adiske metrikken og “langt fra hverandre” i den Euklidske.

8

→ →

DISKRET MATEMATIKK FINNES IKKE

2.3.7 Eksempel. (Den p-adiske metrikken p˚ a Q) Vi fortsetter Eksempelet (2.3.7). La r = m/n være et rasjonalt tall. Om r = m/n = m1 vil mn1 = nm1 , s˚ a vi f˚ ar av multiplikativiteten i (2.3.4) at |m|p |n1 |p = |n|p |m1 |p . Derfor vil |m|p /|n|p = |m1 |p /|n1 |p . Vi kan derfor definere en norm p˚ a de rasjonale tallene Q ved |r|p = |m/n|p = |m|p /|n|p . Det er klart at for alle rasjonale tall r og s vil vi ha (1) (2) (3) (4)

(Ikke degenererthet) |r|p = 0 hvis og bare hvis n = 0. (Symmetri) |r|p = | − r|p . (Ikke arkimedisk triangelulikhet) |r + s|p ≤ max(|r|p , |s|p ). (Multiplikativitet) |rs|p = |r|p |s|p .

Vi setter

dp (r, s) = |r − s|p →

og f˚ ar som i Eksempel (2.3.7) (1) (Ikke degenererthet) dp (x, y) = 0 hvis og bare hvis x = y. (2) (Symmetri) dp (x, y) = dp (y, x). (3) (Triangelulikheten) dp (x, z) ≤ dp (x, y) + dp (y, z). Vi har alts˚ a at (Q, dp ) er et metrisk rom. Oppgaver.

→

Oppgave 1.. Vis at (X, d) i Eksempel (.3) er et metrisk rom. Oppgave 2.. La A = {0, 1}. Regn ut alle avstandene mellom punktene i X = A3 med Hamming metrikken.

→

Oppgave 3.. Vis at egenskapene (1)-(4) holder i Eksempel (?) Oppgave 4.. Gi eksempler som viser at max(|m|p , |n|p ) < |m|p + |n|p .

→

Oppgave 5.. Vis at egenskapene (1), (2), (3) for ||p gir egenskapene (1), (2), (3) for dp (m, n) i Eksempel (?). Oppgave 6.. Vis at om A = {0, 1} og X = An s˚ a er Taksimetrikken og Hammingmetrikken like. Oppgave 7.. Generaliser taksimetrikken p˚ a X = Rn til en taksimetrikk p˚ aX= n Y for alle metriske rom (Y, d). Oppgave 8.. Finn omkretsen av en “taksisirkel”, definer de “taksitrigonometriske” funksjonen, og gi de vanlige relasjonene, som “taksitrigonometriske ene’rn”. (Hint: Kikk etter i Dunkels artikkel i [S]) 2.4. Kontinuitet Vi har sett at det finnes avstandsbegrep i mange forskjellige situasjoner, og at avstandsbegrepene kan ha helt ulike egenskaper. For eksempel har det Kartesiske produktet Rn av de reelle tallene med seg selv n ganger, den vanlige Euklidske metrikken, men den har ogs˚ a Taksimetrikken, Hamming metrikken og den Diskrete metrikken.

2.4. KONTINUITET

9

Intuitivt henger avstandsbegrepet sammen med kontinuitet, ettersom vi kan snakke om at punkter ligger “nære” hverandre. Vi skal vise at v˚ art avstandsbegrep er som skapt for ˚ a innføre kontinuitet. Igjen bruker vi de reelle tallene som modell. En funksjon f :R→R er kontinuerlig i et punkt x om hvert punkt y som ligger “nær” x avbildes til et punkt f (y) som ligger “nær” f (x). Mer presist uttrykker vi dette ved: For hvert x i X og for hvert tall ε > 0 finnes det et tall δ > 0 slik at om |x − y| < δ s˚ a vil |f (x) − f (y)| < ε. I “metrikkspr˚ aket” betyr dette at om dE (x, y) < δ s˚ a skal dE (x, y) < ε. Dette kan vi overføre direkte til metriske rom: 2.4.1 Definisjon. La (X, dX ) og (Y, dY ) være metriske rom. En avbildning f :X→Y er kontinuerlig i et punkt x i X om det for hvert tall ε > 0 finnes et tall δ > 0 slik at om dX (x, y) < δ s˚ a vil δY (f (x), f (y)) < ε. Vi sier at f er kontinuerlig om den er kontinuerlig i alle punkter x. Igjen skal vi gi noen eksempler. Spesielt instruktive er eksempler der den underliggende mengden for de metriske rommene er den samme, men har ulike metrikker. Da ser man klart hvilken betydning metrikkene har for v˚ ar intuisjon om avstand og kontinuitet. 2.4.2 Konvensjon. N˚ ar vi har en avbildning f : X → Y mellom to metriske rom (X, dX ) og Y, dY ) skriver vi dette iblandt f : (X, kX ) → (Y, dY ) for enkelhets skyld. 2.4.3 Eksempel. Identitetsavbildningen id : (Rn , dE ) → (Rn , dT ) →

er kontinuerlig. Dette er fordi det finnes en positiv konstant C slik at dE (x, y) < CdT (x, y) for alle x og y (se Oppgave (?)). Gir vi et tall ε > 0 velger vi δ = ε/C. Om dT (x, y) < δ vil dE (x, y) < CdT (x, y) < Cδ = ε s˚ a id er kontinuerlig. n n P˚ a samme m˚ ate viser vi at id : (R , dT ) → (R , dE ) er kontinuerlig. 2.4.4 Eksempel. Identitetsavbildningen id : (Rn , dE ) → (Rn , dH ) er ikke kontinuerlig. Dette er fordi, for 1 > ε > 0, vil det for hvert tall δ > 0 finnes et y med dE (x, y) < δ og x 6= y. Men da er dH (x, y) ≥ 1. P˚ a den annen side er omvendt id : (Rn , dH ) → (Rn , dE ) kontinuerlig, fordi for hvert tall ε > 0 kan vi velge δ ≤ 1. Da vil dH (x, y) < δ medføre at x = y s˚ a dE (x, y) = 0 < ε.

10

DISKRET MATEMATIKK FINNES IKKE

2.4.5 Eksempel. (Den konstante avbildningen) La (X, dX ) og (Y, dY ) være metriske rom. Hver konstant avbildning f : (X, dX ) → (Y, dY ), det vil si f (x) = f (y) for alle x og y i X, er kontinuerlig fordi dY (f (x), f (y)) = 0 for alle x og y. Oppgaver. Oppgave 1. Vis at identitetsavbildning id : (R, dT ) → (R, dE ) er kontinuerlig.

3. TOPOLOGISKE ROM OG KONTINUITET

3.1. Definisjon og eksempler Den “naturlige omgivelsen” for kontinuerlige avbildninger er topologiske rom. Slike rom er en av grunnstenene i matematikken. De foreklommer i nesten alle deler av matematikken og tilhører de begrepene som forener mange ulike omr˚ ader. Dette er en av forklaringene til vanskelighetene med ˚ a skille mellom diskret og kontinuerlig matematikk. Vi skal her definere topologiske rom og diskutere sammenhengen med metriske rom. Videre gir vi noen eksempler p˚ a topologiske rom. For ˚ a vise hvor flytende skillet mellom diskret og kontinuerlig er gir vi et topologisk bevis for at det finnes uendelig mange primtall. Igjen tar vi det Euklidske rommet Rn som modell. Med en ε-omegn, eller en sfære med radius ε, om et punkt x i Rn mener vi alle punkter med avstand mindre enn ε fra x, det vil si, mendgen Uε (x) = {y ∈ Rn : |x − y| < ε}. Som for de reelle tallen kaller vi en undermengde U av Rn ˚ apen om det for hvert punkt x i U finnes en ε-omegne som ligger i U . Det er klart at X selv er ˚ apen, og at den tomme mengden ∅ er ˚ apen siden den ikke har noen elementer og den derfor ikke behøver ˚ a tilfredsstille noen betingelse. Videre følger det umiddelbart av definisjonen av ˚ apen at unionen av ˚ apne mengder er ˚ apen. Vi har ogs˚ a at snittet av en endelig mengde ˚ apne mengder er ˚ apen, for la U1 , U2 , . . . , Un være ˚ apne og ta x i snittet U1 ∩ U2 ∩ · · · ∩ Un . Da finnes det for hver i et tall εi > 0 slik at Uεi (x) er inneholdt i Ui . Velger vi tallet ε > 0 mindre enn alle tallene ε1 , ε2 , . . . , εn f˚ ar vi at Uε (x) er inneholdt i snittet av Uε1 , Uε2 , . . . , Uεn , og derfor inneholdt i snittet U1 , ∩U2 ∩· · ·∩Un . Det vil si dette snittet er ˚ apent. De egenskapene som vi nettopp har sett holder for de ˚ apne mengdene i Rn viser set ˚ a være fundamentale i analysen. Det er derfor naturlig ˚ a bruke disse som en “modell” for en mer generell situasjon: 3.1.1 Definisjon. La X være en mengde. En topologi p˚ a X er en familie U av undermengder av X slik at (1) Mengden X selv og den tomme mengden ∅ er med i U . (2) Om vi har en familie {Ui }i∈I av undermengder Ui av X som er med i U s˚ a vil unionen ∪i∈I Ui ogs˚ a ogs˚ a være med i U . 11

12

DISKRET MATEMATIKK FINNES IKKE

(3) Om U1 , U2 , . . . , Un er undermengder av X som er med i U s˚ a vil snittet n ∩i=1 Ui = U1 ∩ U2 ∩ · · · ∪ Un være med i U .

Vi sier at X er et topologisk rom med topologi U , og undermengdene U av X som er med i U kalles ˚ apne. 3.1.2 Eksempel. (Triviell topologi) La X være en mengde og la U best˚ a av den tomme mengden ∅ og X. Da er X et toplogiske rom med topologi U . Vi kaller dette den trivielle topologien og betegner med Xtriv mengden X med denne topologien.

3.1.3 Eksempel. (Diskret topologi) La X være en mengde og la U best˚ a av alle undermengdene av X. Da er X et topologisk rom med topologi U . I denne topologien er alle undermengdene av X ˚ apne. Vi kaller dette den diskrete topologien og betegner med Xdiskr mengden X med denne topologien.

→

3.1.4 Eksempel. (Metriske og topologiske rom) La X være et metrisk rom med metrikk d. Vi lar U være familien av alle mengder U som er slik at: For hver x i U finnes et tall ε > 0 slik at om d(x, y) < ε s˚ a vil y være i U . Da er X et topologisk rom med topologi U . For ˚ a se dette resonnerer vi som for R n ovenfor. Det er klart at ∅ og X er med i U . Videre er det klart at betingelsen (2) i Definisjon (3.1.1) holder. For ˚ a vise at betingelsen (3) holder tar vi U1 , U2 , . . . , Un i U og x in U1 ∩ U2 ∩ · · · ∩ Un . For hver i kan vi finne et tall εi > 0 slik at d(x, y) < εi medfører at y er i Ui . Velger vi et tall ε > 0 som er mindre enn ε1 , ε2 , . . . , εn f˚ ar vi at d(x, y) < ε medfører at y er i U1 ∩ U2 ∩ · · · ∩ Un . Vi sier at U er topologien “gitt” av metrikken d og betegner med Xd mengden X med denne topologien. Merk at i Xd er sfæren Uε (x) = {y ∈ X : d(x, y) < 0} om x med radien ε > 0 ˚ apen, fordi om x0 er i Uε (x) velger vi ε0 = ε−d(x, x0 ) > 0. Om 0 0 d(x , y) < ε f˚ ar vi av triangelulikheten at d(x, y) ≤ d(x, x0 ) + d(x0 , y) < ε − ε0 + ε0 = ε s˚ a y er i Uε (x). Det vil si sfæren Uε0 (x0 ) er inneholdt i Uε (x).

→ →

3.1.5 Eksempel. (Endelig komplement topologien) La X være en mengde og la U best˚ a av den tomme mengden ∅ og alle undermengder U av X slik at komplementet X \ U best˚ ar av et endelig antall elementer. Da er det klart at egenskapen (1) i Definisjon (3.1.1) er oppfylt. Videre holder egenskapen (2) fordi om {Ui }i∈I er en familie av undermengder Ui av X slik at hver X \ Ui er endelig s˚ a vil X \ ∪i∈I Ui være inneholdt i X \ Uj for hver j i I s˚ a ∪i∈I Ui er med i U . Videre, om X \ U1 , X \ U2 , . . . , X \ Un er endelige s˚ a vil unionen av disse mengdene n a ∩ni=1 = U1 ∩ U2 ∩ · · · ∩ Un er være endelig. Men X \ ∩i=1 Ui er lik denne unionen s˚ med i U . Derfor er X et topologisk rom med topologi U . Denne topologien virker “eksotisk”, men er viktig i geometrien. For eksempel f˚ ar vi denne topologien p˚ a den komplekse linjen R om vi lar de ˚ apne mengdene være komplementet til nullpunktene til polynomer. 3.1.6 Eksempel. (Det finnes uendelig mange primtall (se[CG])) Vi kaller en undermengde V av de hele tallene Z periodisk om det finnes et tall v slik at for alle m i V s˚ a vil b˚ ade m + v og m − v være i V . Vi kaller tallet v en periode for V . Det

3.1. DEFINISJON OG EKSEMPLER

13

er klart, ved induksjon etter n, at V er periodisk med en periode v hvis og bare hvis m + nv er i V for alle m i V og alle hele tall n. Vi har: (1) Om V er periodisk med en periode v s˚ a er komplementet Z \ V ogs˚ a periodisk med en periode v. (2) Om V og W er periodiske med perioder v, respektive w, s˚ a er unionen V ∪ W periodisk med periode vw. Egenskapen (1) følger av at om m ikke er i V s˚ a kan heller ikke m + v eller m − v være i V , for om m + v eller m − v er i V s˚ a er ogs˚ a m = m + v − v eller m = m − v + v i V , hvilket er mot forutsetningen at m ikke er i V . At egenskapen (2) holder er opplagt. Vi merker at av egenskapen (2) følger, ved induksjon etter antallet periodiske mengder, at enhver endelig union av periodiske mengder er periodisk. Nu kan vi lett vise at det finnes uendelig mange primtall. Anta motsatsen og at p1 , p2 , . . . , pn er alle primtall. La Vi være mengden av alle tall npi for alle heltall n. Da er Vi periodisk med en periode pi . Ettersom alle tall forskjellige fra −1 og 1 er delbare med et primtall vil V1 ∪ V2 ∪ · · · ∪ Vn best˚ a av alle tall untatt {−1, 1}. Men vi har sett at unionen av et endelig antall periodiske mengder er periodisk, og at komplementet til en periodisk mengde er periodisk. Derfor m˚ a komplementet til V1 ∪ V2 ∪ · · · ∪ Vn være periodisk. Men {−1, 1} er ikke periodisk. Derfor har vi f˚ att en motsigelse til antagelsen om at vi har et endelig antall primtall. →

→ →

→ → → →

3.1.7 Merk. Eksempel (3.1.6) er et kontinuerlig bevis for at det finnes uendelig mange primtall. For ˚ a se sammenhengen med topologiske rom merker vi at om vi har en mengde X og en familie V av undermengder av X slik at X er unionene av alle mengdene i V og snittet av et endelig antall mengder i V vil være i V, s˚ a vil familien U som best˚ ar av alle undermengder av X som er unionen av mengder i V danne en topologi for X. Det er klart at ∅ og X begge er med i U , og at egenskap (2) for topologiske rom holder. For ˚ a vise at egenskapen (3) holder tar vi U1 , U2 , . . . , Un i U og x i snittet U1 ∩ U2 ∩ · · · ∩ Un av disse mengdene. For hver i vil det finnes en Vi som er med i V, som inneholder x, og som er inneholdt i Ui . La U = V1 ∩ V2 ∩ · · · ∩ Vn . Da er U med i V ved antagelsen at snittet av et endelig antall mengder som er med i V er med i V. Videre er det klart at U inneholder x og er inneholdt i U1 ∩ U2 ∩ · · · ∩ Un . Derfor er U1 ∩ U2 ∩ · · · ∩ Un unionen av mengder som er med i V s˚ a U er med i U . La nu V best˚ a av alle periodiske mengder i Z. Det er klart at unionen av periodiske mengder er Z. Vi m˚ a vise at snittet av et endelig antall periodiske mengder er periodisk. Dette følger av (1) og (2) ovenfor fordi, om V1 , V2 , . . . , Vn er periodiske undermengder av Z, s˚ a følger det av (1) at komplementene X \ V1 , X \ V2 , . . . , X \ Vn ogs˚ a være periodiske, og derfor av (2) vil (X \V1 )∪(X \V2 )∪· · ·∪(X \Vn ) = X \∩ni=1 Vi være periodisk. Det følger da, igjen av (1), at snittet ∩ni=1 Vi er periodisk. Som vi s˚ a ovenfor vil derfor familien U som best˚ ar av alle undermengder av Z som er unionen av periodiske undermengder vil danne en topologi. En analyse av beviset viser at denne topologien er essensiell i beviset for at vi har uendelig mange primtall. Det opprinnelige beviset av F¨ urstenberg var ogs˚ a “rent topologisk” (se [R]).

14

DISKRET MATEMATIKK FINNES IKKE

Oppgaver. Oppgave 1. Vis at X med den diskrete topologien er et metrisk rom. →

Oppgave 2. Vis at (X, dT ) og (X, dE ) fra Eksemplene (?) og (?) gir samme topologiske rom. Det er dette vi mener n˚ ar vi sier at metrikkene dT og dE er ekvivalente. Oppgave 3. Vis at X med den trivielle topologien ikke kommer fra en metrikk om X har mer enn 1 element. Oppgave 4. Vis at snittet av uendelig mange ˚ apne mengder i Rn ikke behøver ˚ a være ˚ apen. Oppgave 5. Vi at vi f˚ ar en topologi p˚ a den reelle linjen ved ˚ a la de ˚ apne mengdene være komplementet til nullpunktene til polynomer med reelle koeffisienter. Er dette den endelig komplement topologien? 3.2. Kontinuitet I topologiske rom finner begrepet kontinuitet sin riktige plass med føgende definisjon: 3.2.1 Definisjon. La X og Y være topologiske rom med topologier U , respektive V. En avbildning f :X→Y er kontinuerlig om det inverse bildet f −1 (V ) av hver ˚ apen mengde i Y er ˚ apen i X.

→

For at denne definisjonen skal være brukbar er det viktig at om X og Y ogs˚ a er metriske rom og topologiene er gitt av metrikkene p˚ a de topologiske rommene, som i Eksempel (3.1.4) s˚ a m˚ a kontinuitet for topologiske rom sammenfalle med kontinuitet for metriske rom. Neste setning viser at dette er sant. 3.2.2 Setning. La X og Y være metriske rom med metrikker dX , respektive dY , og la U og V være topologiene gitt av dX , respektive dY . En avbildning f :X→Y er en kontinuerlig avbildning av metriske rom f : (X, dX ) → (Y, dY ) hvis og bare hvis den er kontinuerlig av topologiske rom f : XdX → XdY . Proof. Anta at f : (X, dX ) → (Y, dY ) er en kontinuerlig avbildning av metriske rom og la V være ˚ apen i Y . Vi m˚ a vise at f −1 (V ) er ˚ apen i X. Det vil si, for alle −1 x i f (V ) m˚ a vi finne et tall δ > 0 slik at om dX (x, x0 ) < δ s˚ a vil x0 være i V . Vi har at f (x) er i V , og ettersom V er ˚ apen i Y finnes det et tall ε > 0 slik at om 0 0 dY (f (x), y ) < ε s˚ a vil y være i V . Ettersom f er kontinuerlig av metriske rom ved antagelsen kan vi finne et tall δ > 0 slik at n˚ ar dX (x, x0 ) < δ s˚ a vil dY (f (x), f (x0)) < ε. Men da er f (x0 ) i V , eller ekvivalent, vi har at x0 er i f −1 (V ). Om dX (x, x0 ) < δ er alts˚ a x0 i f −1 (V ) hvilket viser at f −1 (V ) er ˚ apen i X. Anta omvendt at f : X → Y er en kontinuerlig avbildning av topologiske rom. Vi m˚ a vise at for hvert tall ε > 0 kan vi finne et tall δ > 0 slik at om dX (x, x0 ) < δ s˚ a

3.2. KONTINUITET

→

15

vil dY (f (x), f (x0)) < ε. Vi s˚ a i Eksempel (3.1.4) at sfæren Uε (f (x)) med radius ε og sentrum f (x) er ˚ apen i X. Vi har at f (x) er i Uε (f (x)) s˚ a x er i f −1 (Uε (f (x))). Ettersom f er kontinuerlig er f −1 (Uε (f (x))) ˚ apen i X. Det følger derfor av at topologien p˚ a X er gitt av metrikken dX at det finnes et tall δ > 0 slik at om dX (x, x0 ) < δ s˚ a vil x0 være i f −1 (Uε (f (x))). Men da er f (x0 ) i Uε (f (x)), det vil si, vi har dY (f (x), f (x0)) < ε. Vi har alts˚ a vist at om dX (x, x0 ) < δ s˚ a vil 0 dY (f (x), f (x )) < ε, hvilket viser at f er en kontinuerlig avbildning av metriske rom. Oppgaver. Oppgave 1. Vis at alle avbildninger f : Xdisk → Xtriv er kontinuerlige. Oppgave 2. Vis at de eneste kontinuerlige avbildningene f : Xtriv → Xdisk er de konstante avbildningene.

16

DISKRET MATEMATIKK FINNES IKKE

4. BLOKK-KODER OG HAMMING METRIKKEN

4.1. Et eksempel p˚ a blokk-koder

→

Vi skal her gi et viktig eksempel fra kodeteorien p˚ a en endelig mengde med en. Som alle vet kan all informasjon overføres til digital kode, det vil si, til strenger av 0’er og 1’ere. Det vanlige er at all informasjon som skal lagres eller sendes skrives som strenger av 0’er og 1’ere av en fast lengde n. Vi skal bruke en mer fantsieggende terminologi og si at informasjonen er overført til ord av lengde n med bokstaver fra alfabetet 0, 1. For eksempel er byte en vanlig enhet for informasjon, og betyr den informasjonen som rommes i de 28 = 256 ordene av lengde 8 fra alfabetet 0, 1. Avstanden mellom to ord definierer vi som antallet posisjoner der ordene er ulike, det vil si, vi bruker Hamming metrikken som vi stiftet bekjentskap med i Eksempel (2.3.4). For eksempel er avstanden d(x, y) mellom ordene x = 01100111 og y = 10101100 lik 5 fordi de skiller seg i første, andre, femte, syvende og ˚ attende posisjon. Avstanden mellom x = 11110000 og y = 00001111 er 8 ettersom x og y skiller seg i alle de 8 posisjonene. At Hamming metrikken er b˚ ade naturlig og viktig ser vi n˚ ar vi bruker den p˚ a feilrettende koder. Anta at vi vil sende informasjon i form av ord av lengde 8 med bokstaver fra alfabetet 0, 1 over en kanal der det forekommer støy slik at det ordet som blir mottat kan skille seg fra det ordet vi sendte. Hva skal vi gjøre for ˚ a oppdage, eller til og med rette, feil? Den vanligste m˚ aten ˚ a oppdage feil p˚ a er ved ˚ a foreta en paritetskontroll, det vil si, vi lar selve meddelelsen være de første 7 bokstavene og lar den 8’ende bokstaven være 0 om det forekommer et like antall 1’ere blandt de syv første bokstaven, og lar den være 1 om det forekommer et odde antall 1’ere. Vi kaller den 8’ende bokstaven for et kontrollsiffer. For eksempel har ordene 01100110 og 10101111 rett paritet. Sender vi ordet 01100110 og det oppst˚ ar en feil slik at vi mottar 01101110 eller 01100111 s˚ a har ordet vi mottar feil paritet og vi vet at en feil har oppst˚ att. Derimot kan vi ikke oppdage to feil ettersom ordet 00000110 har rett paritet og forekommer fra 01100110 om vi gjør en feil i andre og tredje posisjonen. Vi kan heller ikke rette en feil fordi ordet 01101110 som har feil paritet kan fremkomme fra 01100110 og 01101100, begge med rett paritet, om vi gjør en feil. Prisen for ˚ a oppdage en feil er at vi bare kan sende 27 = 128 meddelelser, ettersom den 8’ende bokstaven er bestemt av de 7 første. Vil vi dessuten rette en feil er prisen mye høyere. For ˚ a se dette bruker vi Hamming metrikken for ˚ a f˚ a et geometrisk bilde av situasjonen. Om vi skal rette en feil m˚ a avstanden mellom to kodeord være minst 3. Dette er fordi, om vi sender et kodeord x og mottar ordet x0 med 1 feil, vil 17

18

DISKRET MATEMATIKK FINNES IKKE

d(x, x0 ) = 1. Om y er et annet kodeord og d(x, y) ≥ 3 f˚ ar vi av triangelulikheten at 3 ≤ d(x, y) ≤ d(x, x0 ) + d(x0 , y) = 1 + d(x0 , y),

→

det vil si, vi har d(x0 , y) ≥ 2. Med andre ord m˚ a det har forekommet minst 2 feil 0 om vi sendte y og mottok x . Derfor m˚ a vi ha sendt x om det bare har forekommet en feil. Vi kan formulere kravet at avstanden mellom to kodeord skal være minst 3 geometrisk ved ˚ a si at for ˚ a rette en feil m˚ a hver sfære med radius 1 omkring et kodeord ikke inneholde noe annet kodeord. Vi kan h˚ ape at det rekker ˚ a bruke to kontrollsifre for ˚ a rette en feil. Faktum er at det ikke engang rekker med tre kontrollsifre. For ˚ a se dette merker vi at en sfære med radius 1 omkring et ord x inneholder nøyaktig 9 ord, nemlig x og de 8 ordene vi f˚ ar av x ved ˚ a endre p˚ a en bokstav. Om vi skal rette en feil s˚ a vi at sfærene av radius 1 om kodeordene m˚ a være disjunkte. Bruker vi 3 kontrollsifre kan vi velge de fem første sifrene fritt s˚ a vi har 25 kodeord og de 25 sfærene om disse med radius 1 m˚ a være disjunkte. Dette gir 25 (23 + 1) = 28 + 25 kodeord, som er mer enn det totale antallet 28 kodeord av lengde 8 med bokstaver fra alfabetet 0, 1. Dette er umulig, s˚ a vi har vist at vi m˚ a bruke minst 4 kontrollsifre for ˚ a rette en feil. I sannhet en høy pris. Dette forklarer hvorfor det er s˚ a viktig ˚ a finne gode koder med f˚ a kontrollsifre i forhold til antallet kodeord. Mer generelt best˚ ar en blokk-kode av lengde n fra et alfabet A av en undermengde C av mengden B av alle ord av lengde n med bokstaver fra alfabetet A. Elementene i C kalles kodeord. Avstanden d(x, y) mellom ordene x og y er antallet posisjoner der ordene x og y er forskjellige, det vil si, vi bruker Hamming metrikken fra Eksempel (2.3.4). Hamming distansen dC for en kode C er den minste avstanden mellom to kodeord, det vil si dC = min{d(x, y) : for alle ulike punkter x og y i C}. En kode med Hamming distanse dC kan rette b(dC − 1)/2c feil. Dette sees som ovenfor. Om ordet x i C er et kodeord og x0 et ord vi f˚ ar fra x om vi gjør høyst b(dC − 1)/2c feil s˚ a gir triangelulikheten at for hvert kodeord y s˚ a vil dC ≤ d(x, y) ≤ d(x, x0 ) + d(x0 , y) ≤ b(dC − 1)/2c + d(x0 , y) < dC /2 + d(x0 , y). Det vil si at (dC − 1)/2 < dC /2 < d(x0 , y) s˚ a x er det eneste kodeordet som kan gi 0 opphav til x om vi gjør høyst b(dC − 1)/2c feil. Oppgaver. Oppgave 1. Med alfabetet {0, 1} og ordlengde 8, konstruer en kode med 24 kodeord som kan rette en feil.

4.2. ET EKSEMPEL P˚ A LINEÆRE KODER

19

4.2. Et eksempel p˚ a lineære koder Det er lett ˚ a forst˚ a at det er vanskelig ˚ a konstruere koder med mange kodeord i forhold til kontrollsifre. Kodene skal ogs˚ a være lette ˚ a bruke, s˚ a det m˚ a finnes enkle regler for kodning og avkodning. Vi skal se at oppgaven blir mye lettere om vi har de vanlige aritmetiske operasjonen, addisjon, subtraksjon, multiplikasjon og divisjon i v˚ art alfabet. Dette har vi i alfabetet {0, 1} som har addisjontabell og multiplikasjonstabell +

0

1

0

0

1

1

1

0

og

·

0

1

0

0

0

1

0

1

Det samme gjelder for alfabetet {0, 1, 2} der de aritmetiske operasjonene er gitt av addisjonstabellen og multiplikasjonstabellen +

0

1

2

0

0

1

2

1

1

2

0

2

2

0

1

·

og

0

1

2

0

0

0

0

1

0

1

2

2

0

2

1

Vi kaller slike alfabeter, der vi kan addere, subtrahere, multiplisere og dividere, og de vanlige renereglene gjelder for kropper. For hver potens q = pk av et primtall p finnes det “essensielt” en eneste kropp med q elementer, som betegnes med Fq . Disse er de eneste kroppene med et endelig antall elementer. Kropper med et endelig antall elementer kalles Galois kropper. Det finnes selvsagt et stort utvalg av kropper med uendelig mange elementer, som de rasjonale tallene Q, de reelle tallene R og de komplekse tallene C. Vi illustrer de store vinningene vi f˚ ar ved ˚ a benytte de artimetiske operasjonene med et eksempel der alfabetet er F2 = {0, 1} har to elementer, og kodeordene lengde 7. N˚ ar alfabetet er en kropp er det vanlig ˚ a skrive kodeordene p˚ a vektor form, slik at om x = 0110011 og y = 1010110 s˚ a skriver vi x = (0, 1, 1, 0, 0, 1, 1) og y = (1, 0, 1, 0, 1, 1, 0). vi kan nu addere ord, ved ˚ a addere dem komponentvis, som vi gjør med vektorer. For eksempel har vi x + y = (0 + 1, 1 + 0, 1 + 1, 0 + 0, 0 + 1, 1 + 1, 1 + 0) = (1, 1, 0, 0, 1, 0, 1). Vi vil kode de 23 ordene av lengde 3 fra alfabetet {0, 1}, og skriver x0 = (0, 0, 0),

x1 = (1, 0, 0),

x2 = (0, 1, 0),

x3 = (0, 0, 1)

x4 = (1, 1, 0),

x5 = (1, 0, 1),

x6 = (0, 1, 1),

x7 = (1, 1, 1).

For ˚ a gjøre en enkel paritetskontroll, som vi gjorde ovenfor, rekker det ˚ a multiplisere vektorene x0 , x1 , . . . , x7 med matrisen 1 0 0 1 P = 0101 . 0 011

20

DISKRET MATEMATIKK FINNES IKKE

Matrisemultiplikasjon gir x0 P = (0, 0, 0, 0),

x1 P = (1, 0, 0, 1),

x2 P = (0, 1, 0, 1) x3 P = (0, 0, 1, 1)

x4 P = (1, 1, 0, 0),

x5 P = (1, 0, 1, 0),

x6 P = (0, 1, 1, 0),

x7 P = (1, 1, 1, 1)),

det vil si, matrisemultiplikasjonen legger til en fjerde koordinat som gir pariteten av antallet 1’ere i de første 3 koordinatene. Vi kan utvide paritetskontrollen til mer kompliserte kontrollsifre ved ˚ a multiplisere med større matriser. Multipliserer vi for eksempel alle ordene av lengde 3 med 3 × 6matrisen 1 0 0 1 1 0 P = 010101 00 10 11

f˚ ar vi x0 P = (0, 0, 0, 0, 0, 0),

x1 P = (1, 0, 0, 1, 1, 0),

x2 P = (0, 1, 0, 1, 0, 1)

x3 P = (0, 0, 1, 0, 1, 1),

x4 P = (1, 1, 0, 0, 1, 1),

x5 P = (1, 0, 1, 1, 0, 1)

x6 P = (0, 1, 1, 1, 1, 0),

x7 P = (1, 1, 1, 0, 0, 0)).

Ettersom ordene x0 , x1 , . . . , x7 i den opprinnelige meddelsen kan legges sammen og multipliseres med elementer K kan vi legge sammen ord i blokk-koden og multiplisere dem med elementer i K, og f˚ a nye ord i blokk-koden fordi regnereglene for matrisemultiplikasjon gir xi P + xj P = (xi + xj )P

og a(xi P ) = (axi )P.

Vi kaller derfor koden for en lineær kode. Som vi nettopp s˚ a kan vi med matrisemultiplikasjon enkelt kode meddelelsene slik at vi f˚ ar en lineær kode. Det er ogs˚ a mye enklere ˚ a regne ut Hamming distansen til lineære koder, fordi vi lett viser at dH (x, y) = dH (0, x − y) for alle ord x og y. Istedenfor ˚ a regne ut avstanden dH (x, y) for alle de 23 23 = 64 parene x, y rekker det ˚ a regne ut de syv tallene dH (0, xi P ) for 0, 1, . . . , 7. Vi ser umiddelbart at Hamming distansen er 3, s˚ a koden kan rette 1 feil. For lange ord f˚ ar vi en veldig besparing n˚ ar vi skal regne ut Hamming distansen. N˚ ar vi har aritmetiske operasjoner i alfabetet og betrakter lineære koder er det ogs˚ a mye enklere ˚ a avkode kodeordene. For eksempel kan vi danne 6 × 3 matrisen 1 1 0 101

0 1 1  H= 1 0 0. 010 001

Vi kontrollerer lett at

PH =

1 0 0 1 1 0 0 10 101 0 01 011

1 1 0 1 01

0 1 1   1 0 0 = 0 10 0 01

0 0 0 0 00 0 00

.

4.3. LINEÆR ALGEBRA

21

Det betyr at (xi P )H = 0 for alle kodeord xi P . Det er ogs˚ a lett ˚ a kontrollere at det omvendte gjelder, det vil si, om yH = 0 for et ord y s˚ a vil y = xi P være et kodeord for noe i. Dette kan ogs˚ a vises teoretisk ved ˚ a merke at søylene i H danner et vektorrom av dimensjon 3. Derfor gir yH = 0 tre uavhengige ligninger i seks ukjente. Løsningene danner derfor et 6 − 3 = 3 dimensjonalt vektorrom. Dette rommet inneholder x0 P, x1 P, . . . , x7 P , der x1 P, x2 P, x3 P er lineært uavhengige. Derfor vil x0 P, x1 P, . . . , x7 P være alle løsningene. Sender vi en vektor xi P og det ved overføringen oppst˚ ar en feil i j’te posisjonene mottar vi vektoren y = xi P + ej , der ej er 6 vektoren med 1 i j’te posisjon og 0’er ellers. Vi f˚ ar yH = (xi P + ej )H = xi P H + ej H = ej H, det vil si, vi f˚ ar j’te raden i H. For eksempel, om vi sender x1 P = (1, 0, 0, 1, 1, 0) og mottar y = (1, 1, 0, 1, 1, 0) f˚ ar vi yH = (1, 0, 1) som er andre radene i H. Mottar vi y = (1, 0, 0, 1, 1, 1) f˚ ar vi yH = (0, 0, 1) som er 6’te raden i H. Vi kan nu rette en feil ved ˚ a regne ut yH. Om yH = 0 vil y = xi P for noe i og vi avkoder y som xi . Om yH er j’te rekke i H har vi at (y − ej )H = yH − ej H = 0 s˚ a y − ej = xi P for noe i, og vi avkoder y til xi . P˚ a denne m˚ aten retter vi 1 feil. Merk at vi ikke kan oppdage to feil, for om vi mottar y = (1, 1, 0, 1, 1, 1) som er x1 P med feil i andre og sjette posisjon f˚ ar vi yH = (1, 0, 0) som vi ogs˚ a f˚ ar om vi mottar (1, 1, 1, 1, 0, 0) som er x7 P med 1 feil i 4’de posisjon. Oppgaver. Oppgave 1. Vis at addisjonstabellen og multiplikasjonstabellen i alfabetet med tre elementer {0, 1, 2} gjør at vi ogs˚ a kan subtrahere og dividere.

Oppgave 2. Vis at dH (x, y) = dH (0, x − y) for alle vektorer x og y med elementer fra en kropp. Oppgave 3. Fant vi matrisen H ved et “mirakel”, eller kan du se noe system?

Oppgave 4. Kontroller at yH = 0 hvis og bare hvis y sammenfaller med et av ordene x0 P, x1 P, . . . , x7 P . 4.3. Lineær algebra →

Vi skal antyde hvordan vi med elementær lineær algebra kan generalisere eksempelet Seksjon (4.2). Dette illustrerer hvor nyttig abstrakt teori er for anvendelser, og hvor viktig det er ˚ a kjenne til generelle matematiske teorier. Vi starter med et alfabet K som er en kropp, det vil si, en mengde er vi kan addere, subtrahere, multiplisere og dividere, slik at de “vanlige” regnereglene gjelder (se for eksempel [F]). Det n’te Kartesiske produktet K n best˚ ar av alle n’tupler (a1 , a2 , . . . , an ) der a1 , a2 , . . . , an ligger i K. Vi kaller elementene i K n for vektorer. Vi kan addere to vektorer u = (a1 , a2 , . . . , an ) og v = (b1 , b2 , . . . , bn ) ved ˚ a addere komponentvis u + v = (a1 + b1 , a2 + b2 , . . . , an + bn ) og vi kan multiplisere vektorer med elementer a i K, eller som vi kaller skalarer ved av = (aa1 , aa2 , . . . , aan ). Det er klart at de “vanlige” regnereglene gjelder for addisjon av vektorer og multiplikasjon med skalarer.

22

DISKRET MATEMATIKK FINNES IKKE

4.3.1 Definisjon. En undermengde V av K n slik at om u og v er i V og a er i K s˚ a vil u + v og av være i V kaller vi et vektorrom. Mer spesifikt kaller vi V et underrom av K n . Elementene i V kalles vektorer. Vektorer v1 , v2 , . . . , vm i V som har egenskapen at a1 v1 + a 2 v2 + · · · + a m vm = 0 bare n˚ ar 0 = a1 = a2 = · · · = am sier vi er lineært uavhengige. Vi sier at en familie {vi }i∈I av vektorer vi genererer V om hver vektor v i V kan skrives p˚ a formen v = a 1 v i1 + a 2 v i2 + · · · + a m v im for et positivt heltall m, indekser i1 , i2 , . . . , im i I og elementer a1 , a2 , . . . , am in K. Vektorer v1 , v2 , . . . , vm som b˚ ade er lineært uavhengige og som genererer V kaller vi en basis for V . 4.3.2 Eksempel. La ei = (0, . . . , 0, 1, 0, . . . , 0) være vektoren med koordinat 1 i i’te posisjon og alle andre koordinater 0. Da vil e1 , e2 , . . . , en være en basis for K n . 4.3.3 Merk. La {vi }i∈I være en familie vektorer. Da vil samlingen av vektorer a 1 v i1 + a 2 v i2 + · · · + a m v im = 0 for alle positive heltall m, alle i1 , i2 , . . . , im i I og alle a1 , a2 , . . . , am i K danne et vektorrom. Vi sier at dette vektorromment er generert av vektorene v i for i ∈ I. 4.3.4 Merk. La {vi }i∈I være en samling vektorer. En Gauss-Jordan operasjon p˚ a disse vektorene er en av følgende 3 operasjoner: (1) Bytte av nummereringen p˚ a to av vektorene i {vi }i∈I . (2) Erstatte en vektor vj med vektoren vj + avi for et a i K og i i I. (3) Erstatte en vektor vi med vektoren avi for et ikke null element a i K. Det er klart at om vektorene v1 , v2 , . . . , vm er lineært uavhengige vil de m vektorene vi f˚ ar etter en Gauss-Jordan operasjon ogs˚ a være lineært uavhengige. Om familien av vektorer {vi }i∈I genererer et vektorrom V vil vektorene vi f˚ ar etter en Gauss-Jordan operasjon ogs˚ a generere V . 4.3.5 Lemma. La v1 , v2 , . . . , vm være lineært uavhengige vektorer i K n og la 

a11 a12 a21 a22

P =  .. .

... a1n ... a2n



.. . . ..  . . .

am1 am2 ... amn

være matrisen som har v1 , v2 , . . . , vm som rekker. Ved Gauss-Jordan operasjoner kan vi f˚ a matrisen P over p˚ a trappetrinnsformen 

b11 b12 b21 b22

 Q =  .. .

... b1n ... b2n



 .. . . ..  . . .

bm1 bm2 ... bmn

4.3. LINEÆR ALGEBRA

23

der m × m-matrisen som vi f˚ ar av søylene i1 , i2 , . . . , im i Q, med i1 < i2 < · · · < im er enhetsmatrisen og bkl = 0 for l < ik . Spesielt vil m ≤ n.

→

Proof. Ved Gauss-Jordan operasjoner kan vi alltid f˚ a matrisen p˚ a trappetrinnsform. For ˚ a vise lemmaet rekker det ˚ a vise at i denne formen er ingen rekke lik null. Men den eneste m˚ aten vi kan f˚ a null p˚ a ved en Gauss-Jordan operasjon er at wj + awi = 0 for noen vektorer wi og wj som har oppst˚ att av gjentatte Gauss-Jordan operasjoner og der a er i K. Med dette betyr at wi og wj er lineært avhengige og dette s˚ a vi var umulig i (4.3.4). Den siste delen av lemmaet følger av at vi bare kan velge ut en m × m-matrise fra Q om m ≤ n. 4.3.6 Setning. Hvert ikke null vektorrom V har en basis v1 , v2 , . . . , vm . Om u1 , u2 , . . . , uk er lineært uavhengige vektorer med s˚ a mange elementer k som mulig, og w1 , w2 , . . . , wl er generatorer for V med s˚ a f˚ a elementer l som mulig, s˚ a er b˚ ade u1 , u2 , . . . , uk og w1 , w2 , . . . , wl baser for V og k = l = m. Spesielt har alle baser samme antall elementer.

→

Proof. La {wi }i∈I være en familie av vektorer i V , ikke alle null. Velg v1 = wi1 en ikke null vektor. Vi velger ved induksjon etter j vektorer v1 = wi1 , v2 = wi2 , . . . , vj = wij slik at vj ikke er inneholdt i vektorrommet generert av de foreg˚ aende vektorene v1 , v2 , . . . , vj−1 . Da er v1 , v2 , . . . , vj lineært uavhengige. Det følger av Lemma (4.3.5) at j ≤ n. Derfor m˚ a prosessen stoppe. Det finnes derfor et endelig antall vektorer v1 , v2 , . . . , vm som genererer samme vektorrom som vektorene i {wi }i∈I , og som er lineært uavhengige. Om vi starter med {wi }i∈I best˚ aende av alle vektorer i V ser vi at v1 , v2 , . . . , vm er en basis for V , s˚ a vi har vist første delen av setningen. Spesielt finnes det en endelig mengde vektorer som genererer V . Om w1 , w2 , . . . , wl er et minimal antall generatorer for V gir prosessen ovenfor en undermengde v1 , v2 , . . . , vm av {w1 , w2 , . . . , wl } som er en basis. Derfor er m = k. La u1 , u2 , . . . , uk være lineært uavhengige vektorer med et maksimalt antall elementer. Da m˚ a de generere V , for ellers fantes det et u som ikke er i vektorromet de genererer. Ettersom k og l er det minimale antallet generatorer, respektive det maksimale antallet lineært uavhengige vektorer, f˚ ar vi for hver basis v1 , v2 , . . . , vm at l ≤ m ≤ k. Det gjenst˚ ar ˚ a vise at l = k. For dette bruker vi at ettersom w1 , w2 , . . . , wl er en basis kan hvert element v i V skrives entydig p˚ a formen v = a1 w1 + a2 w2 + · · · + am wm . Vi f˚ ar derfor en bijektiv avbildning V → Kl

→

som avbilder v = a1 w1 + a2 w2 + · · · + am wm til (a1 , a2 , . . . , am ). Det er klart at denne avbildningen “bevarer” addisjon av vektorer og multiplikasjon av vektorer med elementer i K. Derfor vil de lineært uavhengige vektorene u1 , u2 , . . . , uk i V avbildes til lineært uavhengige vektorer i K l . Det følger da av Lemma (4.3.5) at k ≤ l, som vi ville vise.

24

DISKRET MATEMATIKK FINNES IKKE

4.3.7 Definisjon. Antallet elementer i en basis for et underrom V av K n kaller vi dimensjonen av V . Vi betegner dimensjonen med dim(V ), eller n˚ ar vi vil markere at vi er over kroppen K, med dim(V ). Vi har en avbildning < , >: K n × K n → K

definert av

< (a1 , a2 , . . . , an ), (b1 , b2 , . . . , bn ) >= a1 b1 + a2 b2 + · · · + an bn . For hvert vektorrom V i K n skriver vi V ⊥ = {w ∈ V : < v, w >= 0

for alle v

i V },

det vil si, mengden V ⊥ best˚ ar av alle vektorer som st˚ ar perpendikulært p˚ a alle vek⊥ n torene i V . Det er klart at V er et underrom av K . Om v1 , v2 , . . . , vm er en basis for V er det klart at V ⊥ = {w ∈ V : < vi , w >= 0 for

i = 1, 2, . . . , m}.

Dette kan vi bruke til ˚ a tolke vektorene i V ⊥ som løsninger av lineære ligninger. Skriv  a11 a12 ... a1n  a21 a22 ... a2n

.. . . ..  . . .

P =  .. .

am1 am2 ... amn

der rekkene i P er vektorene v1 , v2 , . . . , vm i K n . Da er V ⊥ rommet av vektorer w = (b1 , b2 , . . . , bm ) som er løsninger til ligningssystemet  a11 a12 ... a1n   b1  a21 a22 ... a2n  b2  P w =  .. .. . . ..   ..  = 0 . . . . . am1 am2 ... amn

→

bn

med m ligninger i n ukjente. Den viktigste egenskapen ved Gauss-Jordan eliminasjonen er at den ikke endrer løsningen av ligningssytemet. Av Lemma (4.3.5) følger det derfor at ved ˚ a nummerere om koordinatene i K n slik at koordinatene i1 , i2 , . . . , im kommer i posisjonene 1, 2, . . . , m, respektive, s˚ a kan ligningssystemet skrives  1 0 ... 0 b   b ... b 1m+1

1m+2

1n

0 1 ... 0 b2m+1 b2m+2 ... b2n

  .. .. . . .. . . ..

.. .

.. .

..

  ..   ..  = 0. . . .

0 0 ... 1 bmm+1 bmm+2 ... bmn

Skriv



b1 b2

−b1m+j −b2m+j

bn



  ..   .    −bmm+j    0  wj =    .  ..      1   .. . 0

(4.3.7.1)

(4.3.7.2)

4.4. LINEÆR ALGEBRA

→

25

for j = 1, 2, . . . , n − m der koordinaten 1 st˚ ar i rekke nummer m + j. Vi ser at løsningene til ligningene (4.3.7.1) er gitt av a1 w1 + a2 w2 + · · · + an−m wn−m for alle a1 , a2 , . . . , an−m i K. Det vil si, vektorrommet V ⊥ er generert av vektorene w1 , w2 , . . . , wn−m . Av de siste n − m koordinatene i w1 , w2 , . . . , wn−m ser vi at disse vektorene ogs˚ a er lineært uavhengige, s˚ a de danner en basis for V ⊥ . 4.3.8 Setning. Vi har dim(V ) + dim(V ⊥ ) = n.

→

Proof. Vi s˚ a nettopp at om v1 , v2 , . . . , vm er en basis for V s˚ a er w1 , w2 , . . . , wn−m i (4.3.7.2) en basis for V ⊥ . 4.3.9 Korollar. Vi har at V = (V ⊥ )⊥ .

→

Proof. Det er klart at V er inneholdt i (V ⊥ )⊥ . Bruker vi setningen to ganger f˚ ar vi at dim((V ⊥ )⊥ ) = n − dim(V ⊥ ) = m. Men da følger av Setning (4.3.6) at V = (V ⊥ )⊥ . Oppgaver. Oppgave 1. La {vi }i∈I være en familie av vektorer. Vis at mengden av alle vektorer a1 vi1 + a2 vi2 + · · · am vim for alle positive heltall m, for alle i1 , i2 , . . . , im i I og alle a1 , a2 , . . . , am i K, danner et vektorrom. Oppgave 2. Vis at om v1 , v2 , . . . , vm er en basis for V s˚ a kan hver vektor skrives entydig p˚ a formen v = a1 v1 + a2 v2 + · · · + am vm , det vil si, de kan skrives slik for nøyaktig et valg av a1 , a2 , . . . , am . Oppgave 3. Vis at om vektorene v1 , v2 , . . . , vm er lineært uavhengige vil de vektorene vi f˚ ar etter en Gauss-Jordan operasjon fortsatt være lineært uavhengige. Oppgave 4. Vis at om familien av vektorer {vi }i∈I genererer et vektorrom V s˚ a vil vektorene vi f˚ ar etter en Gauss-Jordan operasjon ogs˚ a generere V . Oppgave 5. La v1 , v2 , . . . , vm være en basis for vektorrommet V . Vis at vi har en bijeksjon ϕ : V → K m som avbilder v = a1 v1 + a2 v2 + · · · am vm til (a1 , a2 , . . . , am ) og er slik at for alle u, v i V og a i K vil ϕ(u + v) = ϕ(u) + ϕ(v) og ϕ(av) = aϕ(v). Oppgave 6. Vis at V ⊥ er en underrom av K n . Oppgave 7. Vis at om v1 , v2 , . . . , vm er en basis for V s˚ a best˚ ar V ⊥ av alle vektorene w slik at < vi , w >= 0 for i = 1, 2, . . . , m.

→

Oppgave 8. Vis at vektorene w1 , w2 , . . . , wn−m i (4.3.2) er en basis for V ⊥ . Oppgave 9. Vis at V = (V ⊥ )⊥ .

26

DISKRET MATEMATIKK FINNES IKKE

4.4. Lineære koder → → →

Vi skal bruke teorien i Seksjon (4.2) til ˚ a generalisere eksemplene fra Seksjon (4.1) og (4.2). La alfabetet K være en kropp. En lineær kode er et underrom V av K n . Vi s˚ ai n Lemma (4.3.5) at vi, ved eventuelt ˚ a nummerere om koordinatene i K , kan finne en basis for V som best˚ ar av rekkene i paritetskontroll matrisen   1 0 ... 0 b b ... b 1m+1

1m+2

1n

0 1 ... 0 b2m+1 b2m+2 ... b2n

 P =  .. .. . . .. .. ..

.. .

.. .

..

 ..  . . .

0 0 ... 1 bmm+1 bmm+2 ... bmn

Vi ser at V best˚ ar av alle vektorene (c1 , c2 , . . . , cm )P = c1 v1 + c2 v2 + · · · + cm vm . her er alle elementene i K m ord i v˚ are meddelelser og vi koder meddelelsen (c1 , c2 , . . . , cm ) som kodeordet (c1 , c2 , . . . , cm )P av lengde n. Vi avkoder kodeordene ved ˚ a multiplisere med matrisen  −b1m+1 −b1m+2 ... −b1n−m  −b

 2m+1 ..   H =  −b .  mm+1  1 0 0

→ →

−b2m+2 ... −b2n−m

.. .

..

−bmm+2 0 1 0

... ... ... ...

.

   . −bmn−m   0 .. .

0 1

Som vi s˚ a i Seksjon (4.3) vil søylene w1 , w2 , . . . , wn−m i H være en basis for vektorrommet V ⊥ . Spesielt vil P H = 0. Om y er et ord i K n slik at yH = 0 vil y være i (V ⊥ )⊥ . Men av Korollar (4.3.9) er V = (V ⊥ )⊥ s˚ a y er i V . Med andre ord vil yH = 0 hvis og bare hvis y er et kodeord. Om vi mottar ordet y regner vi ut yH. Om yH = 0 vil y = xP for et entydig ord x in K m , og vi avkoder y som x. Om vi sendte et ord x og gjør en feil i j’te posisjon mottar vi y = xP + ej . Da vil yH = (xP + ej )H = xP + ej H = ej H som er j’te raden i H. Om v˚ ar kode kan rette en feil og vi mottar et ord y slik at yH er j’te rekke i H vil 0 = yH − ej H = (y − ej )H, og vi har at y − ej = xP for et entydig ord x. Vi avkoder derfor y til x og kan med denne avkodningen rette en feil. Oppgaver. Oppgave 2. Vis at om yH = 0 s˚ a vil y være i V . Oppgave 3. Vis at om x og x0 er i K m og xP = x0 P s˚ a er x = x0 . Oppgave 1. Hvordan ville du avkode om koden kan rette 2 feil?

5. ANALYSE P˚ A DE HELE TALLENE

5.1. Er de hele tallene ”diskrete”?

→ →

Om vi vil bruke v˚ ar intuisjon for ˚ a beskrive hva som bør være diskret matematikk ligger det nære ˚ a ta de hele tallen som et eksempel. Igjen blir vi bedratt av v˚ are følelser. Som vi s˚ a i Eksempel (2.3.6) finnes det p˚ a de hele tallene uendelig mange avstandsbegrep, en for hvert primtall, som alle gir viktig informasjon om de hele tallene og som har store anvendelsesomr˚ ader i og utenfor matematikken. Vi gjentar fra Eksempel (2.3.6) at vi f˚ ar den p-adiske metrikken p˚ a de hele tallen Z ved ˚ a fiksere et primtall p. Hvert ikke null helt tall n kan skrives entydig p˚ a formen n = pk m der k er et ikke negativt heltall, og m er heltall som ikke er delbart med p. Den p-adiske normen av et tall n er gitt ved |n|p = 1/pk og den p-adiske metrikken er gitt ved dp (m, n) = |n − m|p .

→

Vi s˚ a i Eksempel (2.3.6) at følgende tre egenskaper holder: (1) (2) (3) (4)

(Ikke degenerthet) |n|p = 0 hvis og bare hvis n = 0. (Symmetri) |n − m|p = |m − n|p . (Ikke arkimedisk triangelulikhet) |m + n|p ≤ max(|m|p , |n|p ). (Multiplikativitet) |mn|p = |m|p |n|p ,

og at det av disse egenskapene følger:

(1) (Ikke degenerthet) dp (x, y) = 0 hvis og bare hvis x = y. (2) (Symmetri) dp (m, n) = dp (n, m). (3) (Ikke arkimedisk triangelulikhet) |m + n|p ≤ max(|m|p , |n|p ).

I analysen har vi sett hvordan vi fra de rasjonale tallene med den vanlige normen kan konstruere de reelle tallene. Prosessen kalles komplettering og kan baseres p˚ a Cauchy sekvenser. Denne konstruksjonen er tatt med i mange lærebøker. Vi skal definere Cauchy sekvenser i metriske rom og vise hvordan vi kompletterer et vilk˚ arlig metrisk rom. Her skal vi vise hvordan denne konstruksjonen gjøres helt konkret for de hele tallene med den p-adiske metrikken dp . 27

28

DISKRET MATEMATIKK FINNES IKKE

5.2. p-adisk utvikling Hvert ikke negativt heltall n kan skrives p˚ a formen n = a 0 + a 1 p + · · · + a r pr der a1 , a2 , . . . , ar er et heltall slik at 0 ≤ ai < p. Dette gjelder selv om p ikke er primtall. For eksempel f˚ ar vi for p = 10 den vanlige desimalfremstillingen 1729 = 9 + 2 · 10 + 7 · 102 + 103 . Vi kaller fremstillingen n = a0 + a1 p + · · · + ar pr for den p-adiske utviklingen av n. For ˚ a frem formen n = a0 + a1 p + · · · + ar pr for et vilk˚ arlig tall n bestemmer vi først tallet r slik at pr ≤ n < pr+1 . Da vil ar pr ≤ n < (ar + 1)pr for et helt tall ar slik at 1 ≤ ar < p. Det følger at n − a r pr < p r , og vi kan fortsette prosessen med n − ar pr istedenfor n. 5.2.1 Eksempel. For eksempel vil 54 = 625 < 1729 < 55 = 3125 og 2 · 54 = 625 = 1250 ≤ 1729 0 finnes et tall m slik at dp (ni , nj ) < ε n˚ ar i, j ≥ m. For eksempel har vi for alle sekvenser av heltall b0 , b1 , . . . med 0 ≤ bi < p at n1 = b 0 ,

n2 = b0 + b1 p,

n 3 = b 0 + b 1 p + b 2 p2 ,

...

er en Cauchy sekvens, for om vi gir ε > 0 og lar m være et heltall slik at 1/p m < ε s˚ a har vi for j ≥ i at dp (ni , nj ) = |nj −ni |p = |bi pi +bi+1 pi+1 +· · ·+bj−1 pj−1 |p ≤ 1/pi < ε n˚ ar i ≥ m + 1. Tilsvarende f˚ ar vi dp (ni , nj ) < ε n˚ ar i ≥ j. 5.4.1 Setning. La n1 , n2 , . . . være en sekvens av hele tall og la ni = ai0 + ai1 p + · · · + airi pri

være den padiske utviklingen. Da er sekvensen n1 , n2 , . . . en Cauchy sekvens hvis og bare hvis vi for hvert positivt tall l kan finne et tall m slik at ai0 = aj0 , →

ai1 = aj1 ,

...,

ail = ajl

(5.4.1.1)

for alle i, j ≥ m.

Bevis. Om likhetene (5.4.1.1) i setningen holder har vi for gitt ε > 0 og 1/pl < ε, og for i, j ≥ m, at dp (ni , nj ) = |ni − nj |p

= |(ail+1 − ajl+1 )pl+1 + (ail+2 − ajl+2 )pl+2 + · · · |p < 1/pl < ε

s˚ a sekvensen n1 , n2 , . . . er Cauchy. Omvendt, anta at n1 , n2 , . . . er en Cauchy sekvens. Vi har at dp (ni , nj ) = 1/pι(ni −nj ) ,

→

s˚ a om vi velger ε = 1/pl−1 vil dp (ni , nj ) < ε hvis og bare hvis l ≤ ι(ni − nj ). Men l ≤ ι(ni − nj ) = ι((ai0 − aj0 ) + (ai1 − aj1 )p + · · · + (ail − ajl )pl medfører at ai0 = aj0 , ai1 = aj1 , . . . , ail = ajl . Det vil si, vi har at n1 , n2 , . . . er en Cauchy sekvens hvis og bare hvis ulikhetene (5.4.1.1) holder.

32

DISKRET MATEMATIKK FINNES IKKE

5.4.2 Korollar. En sekvens n1 , n2 , . . . av heltall er en Cauchy sekvens hvis og bare hvis det finnes heltall a0 , a1 , . . . , alle av samme tegn, med −p < ai < p for i = 0, 1, . . . , med egenskapen at det for hvert positivt heltall l finnes et tall m slik at ni = a0 + a1 p + · · · + al pl + bi pl+1 for alle i ≥ m, der bi er et heltall. Bevis. Korollaret følger umiddelbart av setningen. Korollaret leder oss til innføre mengden Zp av alle ∞-tupler (a0 , a1 , a2 , . . . ) der 0 ≤ ai < p. Mer suggestivt skriver vi et slikt tuppel a0 + a 1 p + a 2 p2 + · · · . Vi skal ogs˚ a skrive ∞-tuplet )a0 , a1 , · · · ) p˚ a formen (a0 .a1 a2 · · · )

→

for ˚ a f˚ a en bedre analogi med desimalutviklingen av tallene i R. Elementene i Zp kaller vi de p-adiske tallen. Disse tallene kan vi addere og multiplisere p˚ a en liknende m˚ ate som vi adderer og multipliserer desimaltall, men der vi tar restene av desimalene som den delen som overskyter p. Det er imidlertid lettere ˚ a bruke den iterative metoden som vi har antydet i Seksjon (5.3). For ˚ a bestemme koeffisientene c0 , c1 , . . . i produktet (a0 + a1 p + · · · )(b0 + b1 p + · · · ) = c0 + c1 p + · · · bestemmer vi koeffisientene c0 , c1 , . . . , cr i det endelige produktet (a0 + a1 p + · · · + ar pr )(b0 + b1 p + · · · + br pr ) = c0 + c1 p + · · · + cr pr + cpr+1

→

med c0 , c1 , . . . , cr av samme tegn og −p < ci < p, og der c er et heltall. Gjør vi dette for r = 0, 1, . . . følger det av Lemma (5.3.1) at vi f˚ ar bestemt c0 , c1 , . . . . Tilsvarende kan vi gjøre for addisjon av p-adiske tall. Ettersom addisjon og multiplikasjon av p-adiske tall er bestemt av addisjon og multiplikasjon av hele tall følger det at alle regneoperasjonene som gjelder for heltall ogs˚ a gjelder for p-adiske tall. Et positivt heltall n = a 0 + a 1 p + · · · + a r pr identifiserer vi med ∞-tuplet (a0 , a1 , . . . , ar , 0, 0, . . . ) i Zp , slik at a0 + a1 p + · · · + ar pr = a0 + a1 p + · · · + ar pr + 0 · pr+1 + 0 · pr+2 + · · · .

5.4. CAUCHY SEKVENSER OG P-ADISKE TALL

33

Det er interessant at vi ogs˚ a kan identifisere de negative tallene med p-adiske tall, tross at de p-adiske tallene er p˚ a formen a0 + a1 p + · · · med a0 , a1 , . . . ikke negative. Dette er fordi Zp har tilsvarende typer av egenheter som de reelle tallene der, for eksempel tallet 0.999 · · · er lik 1. For de p-adiske tallene har vi at 1 + ((p − 1) + (p − 1)p + · · · + (p − 1)pr ) = 1 + (p − 1)(1 + p + · · · + pr )

= 1 + (p − 1)(pr − 1)/(p − 1) = 1 + pr − 1 = pr .

Det følger av den iterative definisjonen av addisjon og multiplikasjon at 1 + ((p − 1) + (p − 1)p + · · · ) = 0 i Zp . Det vil si −1 = (p − 1) + (p − 1)p + · · · = (p − 1)(1 + p + p2 + · · · ). vi kan nu identifisere et negativt tall a0 + a 1 p + · · · + a r pr der −p < ai ≤ 0 med det p-adiske tallet a0 + a1 p + · · · + ar pr = (−1)(−a0 − a1 p − · · · − ar pr )

= (p − 1)(1 + p + p2 + · · · )(−a0 − a1 p − · · · − ar pr ).

Defor kan vi betrakte de hele tallene som en undermengde av de p-adiske tallene Z p . Hver Cauchy sekvens n1 , n2 , . . . med ni = ai0 + ai1 p + · · · + airi pri bestemmer, som vi har sett, et entydig element a0 + a 1 p + a 2 p2 + · · · i Zp ved at det for hvert positivt heltall l finnes et tall m slik at aj = aij for j = 0, 1, . . . , l og i ≥ m. Omvendt gir hvert element a0 + a 1 p + a 2 p2 + · · · i Zp en entydig Cauchy sekvens a0 , a0 + a1 p, a0 + a1 p + a2 p2 , . . . . Vi kan derfor identifisere Zp med Cauchy sekvenser i Z. Oppagver. Oppgave 1. Vis at om ι(n) er den minste indeksen i slik at ai 6= 0 i n = a0 + a1 p + · · · + ar pr s˚ a vil |n|p = 1/pι(n) . Oppgave 2. Vis hvordan et helt tall p˚ a p-adisk form a0 + a1 p + · · · + ar pr kan adderes, subtraheres og multipliseres p˚ a en liknende m˚ ade som desimaltallene.

34

→

DISKRET MATEMATIKK FINNES IKKE

Oppgave 3. Formuler en analogi til Lemma (5.3.1) for addisjon av tall. Oppgave 4. Vis at det p-adiske tallet n = a0 + a1 p + · · · er invertibelt, det vil si, det finnes et p-adisk tall m = b0 + b1 p + · · · slik at mn = 1, hvis og bare hvis a0 6= 0. Oppgave 5. Vis at de p-adiske tallene kan adderes, subtraheres, og multipliseres p˚ a en liknende m˚ ate som desimaltallene. Oppgave 6. Vis at noen av de vanlige regnereglene gjelder for de p-adiske tallene. Oppgave 7. Vis at egenskapene (1)-(4) holder for ||p p˚ a Zp .

→

Oppgave 8. Vis at egenskapene (1)-(3) i (5.4.?) holder for dp p˚ a Zp . Oppgave 9. Vis at egenskapene (1)-(4) holder for den ||p p˚ a Zp . Oppgave 10. Vi at egenskapene (1), (2), (3) holder for dp p˚ a Zp . Oppgave 11. Vis at normen og metrikken p˚ a Zp anvendt p˚ a heltallene gir normen og metrikken p˚ a Z. 5.5. Komplettering av de hele tallene Vi kan definere en norm p˚ a Zp som gir opphav til en metrikk p˚ a Zp . For det p-adiske tallet x = a0 + a1 p + · · · lar vi ι(a0 + a1 p + · · · ) være den minste indeksen i slik at ai 6= 0. Om a0 + a1 p + · · · ikke er null setter vi |a0 + a1 p + · · · |p = 1/pι(a0 +a1 p+··· ) og vi setter |0|p = 0. Som for de hele tallene følger det at vi har egenskapene: (1) (2) (3) (4)

(Ikke degenerthet) |n|p = 0 hvis og bare hvis n = 0. (Symmetri) |n − m|p = |m − n|p . (Ikke arkimedisk triangelulikhet) |m + n|p ≤ max(|m|p , |n|p ). (Multiplikativitet) |mn|p = |m|p |n|p .

Vi kaller |x|p for den p-adiske normen til x. For p-adiske tall x og y setter vi

dp (x, y) = |x − y|p . Som for de hele tallene viser vi at følgende egenskaper følger av egenskapene (1), (2), (3) for normen: (1) (Ikke degenerthet) dp (x, y) = 0 hvis og bare hvis x = y. (2) (Symmetri) dp (m, n) = dp (n, m). (3) (Ikke arkimedisk triangelulikhet) |m + n|p ≤ max(|m|p , |n|p ).

5.6. KOMPLETTERING AV DE HELE TALLENE

→

35

Det er klart av definisjonene at n˚ ar vi andvender normen ||p og metrikken dp p˚ a heltallene Z s˚ a f˚ ar vi den p-adiske normen, og metrikken som vi definerte i Seksjon (5.3). Det er derfor vi kan velge samme notasjon for norm og metrikk p˚ a Z som p˚ a Zp . En Cauchy sekvens i Zp er en sekvens x1 , x2 , . . . av p-adiske tall slik at for hver ε > 0 finnes det et tall m slik at dp (xi , xj ) < ε n˚ ar i, j ≥ m. Som for de hele tallene ser vi at en sekvens x1 , x2 , . . . av p-adiske tall der xi = ai0 + ai1 p + · · · er en Cauchy sekvens hvis og bare hvis det for hvert positivt heltall l finnes et tall m slik at ai0 = aj0 ,

ai1 = aj1 ,

··· ,

ail = ajl

for i, j ≥ m. N˚ ar x1 , x2 , . . . er en Cauchy sekvens i Zp velger vi l suksessivt lik 1, 2, . . . og lar m1 , m2 , . . . være heltallene tilsvarende ε1 = 1/pl1 , ε2 = 1/pl2 , . . . , respektive. Setter vi ak = aik for k = 0, 1, . . . , l n˚ ar i ≥ mi s˚ a f˚ ar vi bestemt et p-adisk tall x = a0 + a1 p + · · · slik at dp (x, xi ) < 1/pl n˚ ar i ≥ ml . Det vil si, sekvensen x1 , x2 , . . . konvergerer mot det p-adiske tallet x = a0 + a1 p + · · · . I Zp konvergerer følgelig alle Cauchy sekvenser. Vi sier at Zp er komplett med hensyn til metrikken dp og at Zp er kompletteringen til Z med hensyn til den padiske metrikken p˚ a Zp . Dette skiller de p-adiske tallene fra de hele tallene. For eksempel er n1 = 1, n2 = 1 + p, n3 = 1 + p + p2 en Cauchy sekvens i Z men den konvergerer ikke mot noe heltall n = a0 + a1 p + · · · + ar pr , for vi m˚ atte i s˚ a fall ha a0 = a1 = · · · = ar = 1. Men dp (n, ni ) = 1/pr+1 n˚ ar i ≥ r + 1 s˚ a dp (ni , nj ) g˚ ar ikke mot 0 n˚ ar i blir stor. Dette er helt analogt med at de reelle tallene er kompleetteringen av de rasjonale tallene med hensyn til den euklidske metrikken. Vi skal i neste seksjon se noen av fordelene med ˚ a kunne regne i et komplett metrisk rom. Oppgaver. Oppgave 1. Vis at om xi = ai0 + ai1 p + · · · for i = 1, 2, . . . s˚ a er x1 , x2 , . . . en Cauchy sekvens i Zp hvis og bare hvis det for hvert positivt heltall l finnes et tall m slik at ai0 = aj0 , ai1 = aj1 , . . . , ail = ajl n˚ ar i, j ≥ m.

36

DISKRET MATEMATIKK FINNES IKKE

5.6. Løsning av ligninger modulo primtall Vi vil nu illustrere at det er like lett ˚ a regne med p-adiske utviklinger som med desimalutviklinger, fordi algoritmene for addisjon, subtraksjon, multiplikasjon og divisjon for desimalutviklinger kan overføres direkte til p-adiske utviklinger med ubetydelige endringer. Samtidig viser vi hvor nyttige de p-adiske tallene kan være. Vi vil løse ligninger p˚ a formen f (X) ≡ 0 (mod m) for alle tall m og heltallspolynomer f (X). Slike ligninger forekommer overalt i matematikken og dens anvendelser. Vi p˚ aminner om at vi bruker Gauss’ (1777-1853) geniale notasjon n ≡ l (mod m) for ˚ a uttrykke at m deler n − l, og at en løsning av ligningen f (X) ≡ 0 (mod m) er et heltall n slik at f (n) er delbar med m. For eksempel er tallene 1, 2, 3, 4, 5, 6 alle løsninger til ligningen X6 − 1 ≡

(mod 7).

Dette er et spesialtilfelle av Fermats Lille Sats som sier at for alle primtall p er 1, 2, . . . , p − 1 løsninger til ligningen X p−1 ≡ 1

(mod p).

Av den Kinesiske Restsatsen følger det at for ˚ a løse ligningen f (X) ≡ 0 (mod m) s˚ a rekker det ˚ a løse ligningen f (X) ≡ 0 (mod pk ) for alle primtall p og alle positive heltall k. La oss se p˚ a ligningen X2 ≡ 2

(mod 7k ).

Det finnes et 7-adisk tall x = (3.12612124 · · · )7 = 3 + 7 + 2 · 72 + 6 · 73 + · · · slik at x2 = 2 i Z7 . Tallet x er alts˚ a en kvadratrot til 2 i Z7 . Vi ser lett at de endelige 7-adiske utviklingene (3), (3.1), (3.12), dots vi f˚ ar ved ˚ a bryte av den uendelige 7adiske utviklingen til x gir løsninger som kommer stadig nærmere tallet 2. Det vil si 32 ≡ 2 (mod 7), (3 + 7)2 ≡ 2 (mod 72 ),

(3 + 7 + 2 · 72 ) ≡ 2 (mod 73 ),

(3 + 7 + 2 · 72 + 6 · 73 ) ≡ 2 (mod 74 )

og s˚ a videre. Med andre ord, vi har |32 − 2|7 ≤ 1/7, |(3 + 7)2 − 2|7 ≤ 1/72 ,

|(3 + 7 + 2 · · · 72 )2 − 2|7 ≤ 1/73 ,

|(3 + 7 + 2 · 72 + 6 · 73 )2 − 2|7 ≤ 1/74 ,

....

Hvis vi kjente hele den 7-adiske utviklingen til x ville vi dermed ha løst alle kongruensene X 2 ≡ 2 (mod 7k ), men vi kan like lite kjenne hele √ den 7-adiske utviklingen til x i Z7 som vi kan kjenne hele desimalutviklingen til 2 i R.

5.6. LØSNING AV LIGNINGER MODULO PRIMTALL

37

Hensels Lemma. Det finnes et enkelt og hendig kriterium, kalt Hensels Lemma, som garanterer at ligningene f (X) ≡ 0 (mod pk ) har en løsning for alle k:

Anta at vi har et heltall a0 slik at f (a0 ) ≡ 0 (mod p) og f 0 (a0 ) 6≡ 0 (mod p). Da finnes et entydig p-adisk tall x = a0 + a1 p + · · · med 0 ≤ ai < p i Zp slik at f (x) = 0 i Zp . Ekvivalent, vil f (a0 + a1 p + · · · + am pm ) ≡ 0

(mod pm+1 )

for

m = 0, 1, . . . .

Bevis. Vi bruker induksjon etter m. For m = 0 er lemmaet forutsetningen f (a0 ) ≡ 0 (mod p). Anta at vi har vist at den siste ligningen i lemmaet holder for m − 1, det vil si, vi har f (a0 + a1 p + · · · + am−1 pm−1 ) = cpm og velg et vilk˚ arlig tall am som vi vil bestemme. Taylors formel, som er triviell for polynomer, sier at for alle polynomer g(t) med heltallskoeffisienter vil g(a + h) = g(a) + hg 0 (a) + h2 e(t) der e(X, Y ) er et polynom med heltallskoeffisienter. Bruker vi først Taylors formel p˚ a f 0 (t) med a = a0 og h = a1 p + a2 p2 + · · · + am pm f˚ ar vi f 0 (a0 + a1 p + · · · + am pm ) ≡ f 0 (a0 ) (mod p), og bruker vi den p˚ a f (t) med a = a0 + a1 p + · · · + am−1 pm−1 og h = am pm f˚ ar vi f (a + am pm ) ≡ f (a) + am pm f 0 (a) ≡ pm (c + am f 0 (a0 )) (mod pm+1 ). Ettersom f 0 (a0 ) 6≡ 0 (mod p) ved antagelsen finnes det et entydig tall am slik at 0 ≤ am < p og c + am f 0 (a0 ) ≡ (mod p). For dette tallet vil f (a0 + a1 p + · · · + am pm ) ≡ f (a + am pm ) ≡ 0 (mod pm+1 ) og vi har vist lemmaet. Merk. Betingelsen f 0 (a0 ) 6≡ 0 (mod p) m˚ a være oppfylt for at vi skal være sikre p˚ a at Hensels Lemma holder. For eksempel vil ligningen X 2 ≡ 2 (mod 2k ) ha løsningen x = 0 for k = 1, men ingen løsning for k = 2 fordi 02 − 2 ≡ 2 (mod 4), 12 − 2 ≡ 3 (mod 4), 22 = 2 ≡ 2 (mod 4) og 32 − 2 ≡ 3 (mod 4). I dette tilfellet er den deriverte av polynomet X 2 − 2 lik 2X som er identisk med null modulo 2.

Newtons metode. For ˚ a finne en løsning til kongruensene f (X) ≡ 0 (mod pk ) for store k er det nok ˚ a finne tilstrekkelig gode rasjonale tilnærminger a til x i Q 7 . Grunnen til dette er at |x − a|7 er liten hvis og bare hvis differensen x − a er delelig med en høy potens av 7. Vi trenger alts˚ a en effektiv metode for ˚ a finne rasjonale 2 tilnærminger til en løsning til likningen f (X) = X − 2 = 0 i Q7 . Newton’s metode egner seg utmerket til form˚ alet. Vi setter opp iterasjonen an+1 = an −

f (an ) 1 2 = (an + ) 0 f (an ) 2 an

38

DISKRET MATEMATIKK FINNES IKKE

og starter den med et rasjonalt tall a1 som ligger nær x i Q7 . Vi kan for eksempel velge a1 = 3, for dette viser seg ˚ a være nær nok til at Newton-iterasjonen konvergerer til x. I s˚ a fall f˚ ar vi tilnærmingene a2 = 11/6 = (3.11111111...)7 som har to korrekte 7-adiske siffer, og a3 = 193/132 = (3.12603325...)7 som har fire korrekte siffer. Akkurat som n˚ ar vi bruker Newton’s metode i R, kan vi regne med en dobling av antall korrekte siffer i hvert steg hvis startpunktet er nær nok til roten. S˚ a dette er en svært effektiv algoritme for ˚ a løse f (X) ≡ 0 (mod p k ) for store k. Det er interessant ˚ a observere at den samme følgen a1 = 3, a2 = 11/6, a3 = 193/132, . . . av rasjonale tall konvergerer til to forskjellige kvadratrøtter til 2, den ene i R og den andre i Q7 . Men de to konvergensbegrepene er svært forskjellige. Dette sees for eksempel ved at følgen divergerer i Q5 , for kongruensen X 2 ≡ 2 (mod 5) har ingen løsning, og dermed kan ikke 2 ha noen kvadratrot i Q5 . 5.7. Komplettering av metriske rom Vi skal nu vise hvordan konstrusjonen av de p-adiske tallene fra de hele tallene med den p-adiske metrikken kan gjøres helt generellt for metriske rom. Konstruksjonen kalles komplettering og forekommer i mange situasjoner i matematikken. Kompletteringen gir en fin trening p˚ a˚ a bruke fundamentale begreper fra analysen. 5.7.1 Definisjon. La (X, dX ) være et metrisk rom. En sekvens x1 , x2 , . . . av punkter i X konvergerer mot et punkt x om det for hvert tall ε > 0 finnes et tall m slik at dX (x, xi ) < ε n˚ ar i ≥ m. Vi sier at en sekvens x1 , x2 , . . . er en Cauchy sekvens om det for hvert ε > 0 finnes et tall m slik at dX (xi , xj ) < ε n˚ ar i, j ≥ m. Om hver Cauchy sekvens i X konvergerer sier vi at det metriske rommet (X, d X ) er komplett. 5.7.2 Eksempel. En av de fundamentale egenskapene ved de reelle tallene er at de er komplette med hensyn til den euklidske metrikken. Det samme gjelder det n dimensjonale Euklidske rommet Rn med den euklidske metrikken. La X0 være mengden av alle Cauchy sekvenser i X. Vi betegner en Cauchy sekvens x1 , x2 , . . . i X0 med {xi } for korthets skyld. Definer en relasjon ∼ relasjon mellom Cauchy sekvenser ved: La {xi } og {yi } være et par av Cauchy sekvenser. Skriv {xi } ∼ {yi } om sekvensen dX (x1 , y2 ), dX (x2 , y2 ), . . . av relle tall konvergerer mot 0 i den eukliske metrikken, det vil si, for hvert ε > 0 finnes et tall m slik at dX (xi , yi ) < ε n˚ ar i ≥ m.

5.7. KOMPLETTERING AV METRISKE ROM

39

Relasjonen ∼ er en ekvivalensrelasjon. Det vil si, den tilfredsstiller følgende egenskaper: For alle Cauchy sekvenser {xi }, {yi }, {zi } i X har vi (1) (Refleksivitet) {xi } ∼ {xi }. (2) (Symmetri) Om {xi } ∼ {yi } s˚ a vil {yi } ∼ {xi }. (3) (Transitivitet) Om {xi } ∼ {yi } og {yi } ∼ {zi } s˚ a vil {xi } ∼ {z1 }.

Egenskapene (1) og (2) følger umiddelbart av definisjonen p˚ a relasjonen ∼. Forutsetningen i (3) er at sekvensene {dX (xi yi )} og {dX (yi , zi )} av reelle tall konvergerer mot 0, det vil si, vi kan finne tall m1 og m2 slik at dX (xi , yi ) < ε/2 n˚ ar i ≥ m1 og dX (yi zi ) < ε/2 n˚ ar i ≥ m2 . Vi m˚ a vise at for hvert ε > 0 finnes et m slik at for i ≥ m vil dX (xi , zi ) < ε. Velg tallet m større eller lik m1 og m2 . Da følger av triangelulikheten at n˚ ar i ≥ m s˚ a vil dX (xi , zi ) ≤ dX (xi , yi ) + dX (yi , zi ) < ε/2 + ε/2 = ε, som vi ville vise. b være klassene til ekvivalensrelasjonen ∼, det vil si, hvert element x i X b La X best˚ ar av alle Cauchy sekvenser {yi } som er evivalente med en gitt Cauchy sekvens {xi }. Klassen som best˚ ar av alle Cauchy sekvenser ekvivalente med {x i } skriver vi [xi ]. Dette betyr at vi har en avbildning b u : X0 → X

gitt ved u({xi }) = [xi ] der u−1 ([xi ]) best˚ ar av alle Cauchy sekvensene som er ekvivalente med {xi }. Videre har vi en avbildning b v:X→X

definert av v(x) = [xi ] der xi = x for i = 1, 2, . . . . Denne avbildningen er injektiv, for de to Cauchy sekvensene x, x, . . . og y, y, . . . kan bare være ekvivalente om x = y. b Det vil Ved hjelp av avbildningen v skal vi betrakte X som en undermengde av X. si, vi setter x = [xi ] der xi = x for i = 1, 2, . . . . b Det vil si, vi skal finne Vi skal nu utvide metrikken dX til en metrikk dXb p˚ a X. b slik at d b restriserer til dX p˚ en metrikk dXb p˚ aX a X. X

5.7.3 Lemma. Om {xi } og {yi } er Cauchy sekvenser i X s˚ a vil {dX (xi , yi )} være en Cauchy sekvens i R. Bevis. La ε > 0. Vi kan velge m1 og m2 slik at dX (xi , xj ) < ε/2 for i, j ≥ m1 , og dX (yi , yj ) < ε/2 for i, j ≥ m2 . Velg m større eller lik m1 og m2 . Da f˚ ar vi av triangelulikheten anvendt to ganger at dX (xi , yi ) 5 dX (xi , xj ) + dX (xj , yi ) < ε/2 + dX (xj , yj ) + dX (yi , yj ) < ε/2 + dX (xj , yj ) + ε/2

40

DISKRET MATEMATIKK FINNES IKKE

for i, j ≥ m. Det vil si dX (xi , yi ) − dX (xj , yj ) < ε n˚ ar i, j ≥ m. Tilsvarende f˚ ar vi for i, j ≥ m at dX (xj , yj ) − dX (xi , yi ) < ε. Vi har derfor |dX (xi , yi ) − d(xj , yj )| < ε n˚ ar i, j ≥ m. Det vil si {dX (xi , yi )} er en Cauchy sekvens i R. →

Ettersom alle Cauchy sekvenser i R konvergerer følger det av Lemma (5.7.3) at vi for alle Cauchy sekvenser {xi } og {yi } i X kan definere dX0 ({xi }, {yi }) = lim dX (xi , yi ). i→∞

5.7.4 Lemma. La {xi } ∼ {x0i } og {yi } ∼ {yi0 } være Cauchy sekvenser i X. Da vil dX0 ({xi }, {yi }) = dX0 ({x0i }, {yi0 }). Proof. Det rekker ˚ a vise at dX0 ({xi }, {yi }) = dX0 ({x0i }, {yi }), for bruker vi dette p˚ a Cauchy sekvensene {yi }, {yi0 }, {x0i } istedenfor p˚ a {xi }, {x0i }, {yi } betyr dette at 0 0 0 ogs˚ a dX0 ({yi }, {xi }) = dX0 ({yi }, {xi }), s˚ a vi f˚ ar av symmetrien til ekvivalensre0 lasjonen at dX0 ({xi }, {yi }) = dX0 ({xi }, {yi }) = dX0 ({yi }, {x0i }) = dX0 ({yi0 }, {x0i }) = dX0 ({x0i }, {yi0 }). For ˚ a vise at dX0 ({xi }, {yi }) = dX0 ({x0i }, {yi }) setter vi a = dX0 ({xi }, {yi }) = limi→∞ dX (xi , yi ) og b = dX0 ({x0i }, {yi }) = limi→∞ dX (x0i , yi ), og skal vise at a = b. La ε > 0. Da kan vi finne tall m1 og m2 slik at |a − dX (xi , yi )| < ε/3 n˚ ar i ≥ m1 , at 0 0 ar i ≥ m3 . La m være et ar i ≥ m2 , og at |dX (xi , xi )| < ε/3 n˚ |b − dX (xi , yi )| < ε/3 n˚ tall som er større eller lik m1 , m2 , m3 . Da f˚ ar vi av triangelulikheten at om i ≥ m s˚ a vil a < dX (xi , yi ) + ε/3 ≤ dX (xi , x0i ) + dX (x0i , yi ) + ε/3 ≤ ε/3 + b + ε/3 + ε/3 = b + ε. Tilsvarende f˚ ar vi at b < a + ε. Vi har derfor at |a − b| < ε for alle ε > 0. Derfor er a = b som vi ville vise. →

Lemma (5.7.4) viser at følgende definisjon har en mening: b Vi setter 5.7.5 Definisjon. La x, y være i X.

dXb (x, y) = dXb ([xi ], [yi ]) = dX0 ({xi }, {yi }) = lim dX (xi , yi ) i→∞

der {xi } og {yi } er vilk˚ arlige Cauchy sekvenser i ekvivalensklassen gitt av x og y. b 5.7.6 Setning. Vi har at dXb er en metrikk p˚ a X.

Bevis. Først viser vi at dXb (x, y) = 0 hvis og bare hvis x = y. Det er klart at om x = y s˚ a er dXb (x, y) = 0. Omvendt, anta at dXb (x, y) = 0. Velg Cauchy sekvenser {xi } og {yi } i ekvivalensklassene til x, respektive y. Da betyr dXb (x, y) = 0 at limi→∞ dX (xi , yi ) = 0. Men, per definisjon, betyr dette at {xi } ∼ {yi }, det vil si x = y. Likheten dXb (x, y) = dXb (y, x) følger direkte av definisjonene. For ˚ a vise triangelulikheten bruker vi at om a1 , a2 , . . . og b1 , b2 , . . . er konvergente sekvenser i R s˚ a vil limi→∞ (ai + bi ) = limi→∞ ai + limi→inf ty bi og om ai ≤ bi for i = 1, 2, . . . vil limi→∞ ai ≤ limi→∞ bi .

5.7. KOMPLETTERING AV METRISKE ROM

41

Velg Cauchy sekvenser {xi }, {yi }, {zi } slik at x = [xi ], y = [yi ], z = [zi ]. Vi f˚ ar av triangelulikheten i X at dXb (x, z) = lim dX (xi , zi ) ≤ i→∞

lim

i→inf oty

(dX (xi , yi ) + dX (yi , zi ))

≤ lim dX (xi , yi ) + lim dX (yi , zi ) = dXb (x, y) + dXb (x, z). i→∞

i→∞

5.7.7 Definisjon. La T være et topologisk rom. Vi sier at en undermengde X av Y er tett om hver ˚ apen mengde inneholder minst et pukt i X. b 5.7.8 Lemma. La (X, dX ) være et metrisk rom. Da er X tett i X.

b : d b (y, z) < r} med radius Bevis. Vi m˚ a vise at hver sfære Sr (y) = {z ∈ X X r og et punkt y inneholder et punkt x i X. For ˚ a se dette skriver vi y = [yi ] der {yi } er en Cauchy sekvens i X og velg ε slik at 0 < ε < r. Da finnes et heltall m slik at dX (yi , yj ) < ε n˚ ar i, j ≥ m. spesielt vil dX (yi , ym ) < ε n˚ ar i ≥ m, og derfor vil limi→∞ dX (yi , ym ) ≤ ε. Sett x = ym . Da vil dXb (y, x) = dXb (x, y) = limi→∞ dX (x, yi ) = limi→inf ty dX (ym , yi ) ≤ ε < r s˚ a x er i Sr (y) og vi har vist Lemmaet. 5.7.9 Merk. Om x, x0 er i X vil dXb (x, x0 ) = limi→∞ dX (x, x0 ) = dX (x, x0 ) s˚ a restriksjonen av dXb til X gir dX . 5.7.10 Proposisjon. La (T, dY ) være et metrisk rom og la X ⊆ Y være en dfntett undermengde. Om hver Cauchy sekvens {xi } med elementer xi fra X konvergerer i Y s˚ a vil hver Cauchy sekvens {yi } med elementer yi fra Y konvergere i Y . Bevis. La {yi } være en Cauchy sekvens i Y . Ettersom X er tatt i Y kan vi for hvert positivt heltall k finne et element xik i X slik at dY (xik , yi ) < 1/k Spesielt vil sekvensen xi1 , xi2 , . . . konvergere mot yi . Vi viser først at sekvensen x11 , x22 , . . . er en Cauchy sekvens i X. La ε > 0. Vi kan velge heltall m1 og m2 , slik at dY (yi , yj ) < ε/3 for i, j ≥ m1 , respektive dY (yj , xjj ) < ε/3, og et heltall l slik at 1/l < ε/3. Velg m større eller lik m1 , m2 , l. Om i, j ≥ m f˚ ar vi av triangelulikheten brukt tre ganger dY (xii , xjj ) = dY (xii , yi ) + dY (yi , xjj ) ≤ dY (xii , yi ) + dY (yi , yj ) + dY (yj , xjj )

< 1/i + ε/3 + 1/j < ε/3 + ε/3 + ε/ = ε.

Vi har dermed vist at x11 , x22 , . . . er en Cauchy sekvens. Ved antagelsen i setningen konvergerer sekvensen x11 , x22 , . . . mot et element z i Y . Vi skal vise at Cauchy sekvensen {yi } ogs˚ a konvergerer mot z. For ˚ a vise dette gir vi ε > 0. Det finnes da et tall m slik at 1/m < ε/2 og dY (xii , z) < ε/2 n˚ ar i > m. For i > m f˚ ar vi derfor av triangelulikheten at dY (yi , z) ≤ dY (yi , xii ) + dY (xii , z) < 1/i + ε/2 < pm + ε/2 < ε/2 + ε/2 = ε. Det vil si, sekvensen {yi } konvergerer mot z, og vi har vist Proposisjonen.

42

DISKRET MATEMATIKK FINNES IKKE

b d b ) et komplett 5.7.11 Korollar. La (X, dX ) være et metrisk rom. Da er (X, X metrisk rom. →

Bevis. Korollaret følger umiddelbart av Lemma (5.7.8) og proposisjonen. Vi har vist at for hvert metrisk rom (X, dX ) finnes det et komplett metrisk rom b b og slik at dX er restriksjonen av d b (X, dXb ) slik at X er en tett undermengde av X, X b d b ) for kompletteringen til (X, dX ). Det er ganske lett ˚ til X. Vi kaller (X, a vise at X kompletteringen er entydig (se Oppgave 4). Oppgaver. Oppgave 1. Vis at sekvensen x1 , x2 , . . . der xi = x for i = 1, 2, . . . er en Cauchy sekvens. Oppgave 2. Vis at om sekvensen x1 , x2 , . . . konvergerer s˚ a vil den være en Cauchy sekvens. Oppgave 3. Vis at de to Cauchy sekvensene x, x, . . . og y, y, . . . er ekvivalente hvis og bare hvis x = y. Oppgave 4. La (X, dX ) og (Y, dY ) være metriske rom og anta at (Y, dY ) er komplett, at X er en undermengde av Y og at metrikken dY restrisert til X induserer metrikken dX . Vis at det finnes en entydig avbildning b →Y u:X

slik at dX (x, x0 ) = dY (u(x), u(x0 )) for alle x, x0 i X.

APPENDIX. AMS-KLASSIFIKASJONEN

A.1Hovedomr˚ ader 00 01 03 05 06 08 11 12 13 14 15 16 17 18 19 20 22 26 28 30 31 32 33 34 35 37 39 40 41 42 43 44 45 46

General History and biography Mathematical logic Combinatorics Order, lattices, ordered algebraic structures General algebraic systems Number theory Field theory and polynomials Commutative rings and algebras Algebraic geometry Linear and multilinear algebra; matrix theory Associative rings and algebras Nonassociative rings and algebras Category theory, homological algebra K-theory Group theory and generalizations Topological groups, Lie groups Real functions Measure and integration Functions of a complex variable Potential theory Several complex variables and analytic spaces Special functions Ordinary differential equations Partial differential equations Dynamical systems and ergodic theory Finite differences and functional equations Sequences, series, summability Approximations and expansions Fourier analysis Abstract harmonic analysis Integral transforms, operational calculus Integral equations Functional analysis 43

44

47 49 51 52 53 54 55 57 58 60 62 65 68 70 73 76 78 80 81 82 83 85 86 90 91 92 93 94 97

DISKRET MATEMATIKK FINNES IKKE

Operator theory Calculus of variations and optimal control Geometry Convex and discrete geometry Differential geometry General topology Algebraic topology Manifolds and cell complexes Global analysis, analysis on manifolds Probability theory and stochastic processes Statistics Numerical analysis Computer science Mechanics of particles and systems Mechanics of deformable solids Fluid mechanics Optics, electromagnetic theory Classical thermodynamics, heat transfer Quantum Theory Statistical mechanics, structure of matter Relativity and gravitational theory Astronomy and astrophysics Geophysics Economics, operations research, programming Game theory, economics, social and behavioral sciences Biology and other natural sciences Systems theory; control Information and communication, circuits Mathematics education

A.2DELOMR˚ ADER AV ALGEBRAISK GEOMETRI

A.2Delomr˚ ader av Algebraisk Geometri 14-XX Algebraic geometry 14Axx Foundations 14Bxx Local theory 14Cxx Cycles and subschemes 14Dxx Families, fibrations 14Exx Birational Geometry 14Fxx (Co)homology theory [See also 13Dxx] 14Gxx Arithmetic problems. Diophantine geometry [See also] 14Hxx Curves 14Jxx Surfaces and higher-dimensional varieties (For analytic theory, see 32Jxx) 14Kxx Abelian varieties and schemes 14Lxx Algebraic Groups (For linear algebraic groups, see 20Gxx; 14Mxx Special varieties 14Nxx Projective and enumerative geometry 14Pxx Real algebraic and real analytic geometry 14Qxx Computational aspects in algebraic geometry 14Rxx Affine Geometry

45

46

DISKRET MATEMATIKK FINNES IKKE

A.3Spesialomr˚ adene av Algebraisk Geometri 14-XX Algebraic geometry 14-00 14-01 14-02 14-04

14-06 14-99

General reference works (handbooks, dictionaries, bibliographies, etc.) Instructional exposition (textbooks, tutorial papers, etc.) Research exposition (monographs, survey articles) Historical (must also be assigned at least one classification number from Section 01) Explicit machine computation and programs (not the theory of computation or programming) Proceedings, conferences, collections, etc. Algebraic geometry (not classified at a more specific level)

14Axx 14A05 14A10 14A15 14A20 14A22 14A25 14A99

Local theory Relevant commutative algebra [See also 13-xx] Varieties and morphisms Schemes and morphisms Generalizations (algebraic spaces, stacks) Noncommutative algebraic geometry Elementary questions None of the above, but in this section

14Bxx 14B05 14B07 14B10 14B12

Local theory Singularities [See also 14E15, 14H20, 4J17, 32Sxx, 58Kxx] Deformations of singularities [See also 14D15, 32S30] Infinitesimal methods [See also 13D10] Local deformation theory, Artin approximation, etc. [See also 13B40, 13D10] Local cohomology [See also 13D45, 32C36] Formal neighborhoods Local structure of morphisms: tale, flat, etc. [See also 13B40] None of the above, but in this section

14-04

14B15 14B20 14B25 14B99 14Cxx 14C05 14C15 14C17 14C20 14C21 14C22 14C25 14C30 14C34 14C35 14C40 14C99

Cycles and subschemes Parametrization (Chow and Hilbert schemes) Chow groups and rings Intersection theory, characteristic classes, intersection multiplicities [See also 13H15] Divisors, linear systems, invertible sheaves Pencils, nets, webs [See also 53A60] Picard groups Algebraic cycles Transcendental methods, Hodge theory [See also 14D07, 32G20, 32J25, 32S35], Hodge conjecture Torelli problem [See also 32G20] Applications of methods of algebraic K-theory [See also 19Exx] Riemann-Roch theorems [See also 19E20, 19L10] None of the above, but in this section

A.3SPESIALOMR˚ ADENE AV ALGEBRAISK GEOMETRI

14Dxx 14D05 14D06 14D07 14D10 14D15 14D20

Families, fibrations Structure of families (Picard-Lefschetz, monodromy, etc.) Fibrations, degenerations Variation of Hodge structures [See also 32G20] Arithmetic ground fields (finite, local, global) Formal methods; deformations [See also 13D10, 14B07, 32Gxx] Algebraic moduli problems, moduli of vector bundles (For analytic moduli problems, see 32G13) 14D21 Applications of vector bundles and moduli spaces in mathematical physics (twistor theory, instantons, quantum field theory) 14D22 Fine and coarse moduli spaces 14D99 None of the above, but in this section 14Exx 14E05 14E07 14E08 14E15 14E20 14E22 14E25 14E30 14E99

Birational Geometry Rational and birational maps Birational automorphisms, Cremona group and generalizations Rationality questions Global theory and resolution of singularities [See also 14B05, 32S20, 32S45] Coverings [See also 14H30] Ramification problems [See also 11S15] Embeddings Minimal model program (Mori theory, extremal rays) None of the above, but in this section

14Fxx (Co)homology theory [See also 13Dxx] 14F05 Vector bundles, sheaves, related constructions [See also 14H60, 14J60, 18F20, 32Lxx, 46M20] 14F10 Differentials and other special sheaves [See also13Nxx, 32C38] 14F17 Vanishing theorems [See also 32L20] 14F20 tale and other Grothendieck topologies and cohomologies 14F22 Brauer groups of schemes [See also 12G05, 16K50] 14F25 Classical real and complex cohomology 14F30 p-adic cohomology, crystalline cohomology 14F35 Homotopy theory; fundamental groups [See also 14H30] 14F40 de Rham cohomology [See also 14C30, 32C35, 32L10] 14F42 Motivic cohomology 14F43 Other algebro-geometric (co)homologies (e.g., intersection, equivariant, Lawson, Deligne (co)homologies) 14F45 Topological properties 14F99 None of the above, but in this section 14Gxx Arithmetic problems. Diophantine geometry [See also 11Dxx, 11Gxx] 14G05 Rational points 14G10 Zeta-functions and related questions [See also 11G40] (Birch-Swinnerton-Dyer conjecture) 14G15 Finite ground fields 14G20 Local ground fields

47

48

14G22 14G25 14G27 14G32

DISKRET MATEMATIKK FINNES IKKE

14G99

Rigid analytic geometry Global ground fields Other nonalgebraically closed ground fields Universal profinite groups (relationship to moduli spaces, projective and moduli towers, Galois theory) Modular and Shimura varieties [See also 11F41, 11F46, 11G18] Arithmetic varieties and schemes; Arakelov theory; heights [See also 11G50] Applications to coding theory and cryptography [See also 94A60, 94B27, 94B40] None of the above, but in this section

14Hxx 14H05 14H10 14H15 14H20 14H25 14H30 14H37 14H40 14H42 14H45 14H50 14H51 14H52 14H55 14H60 14H70 14H81 14H99

Curves Algebraic functions; function fields [See also 11R58] Families, moduli (algebraic) Families, moduli (analytic) [See also 30F10, 32Gxx] Singularities, local rings [See also 13Hxx, 14B05] Arithmetic ground fields [See also 11Dxx, 11G05, 14Gxx] Coverings, fundamental group [See also 14E20, 14F35] Automorphisms Jacobians, Prym varieties [See also 32G20] Theta functions; Schottky problem [See also 14K25, 32G20] Special curves and curves of low genus Plane and space curves Special divisors (gonality, Brill-Noether theory) Elliptic curves [See also 11G05, 11G07, 14Kxx] Riemann surfaces; Weierstrass points; gap sequences [See also 30Fxx] Vector bundles on curves and their moduli [See also 14D20, 14F05] Relationships with integrable systems Relationships with physics None of the above, but in this section

14G35 14G40 14G50

14Jxx Surfaces and higher-dimensional varieties (For analytic theory, see 32Jxx) 14J10 Families, moduli, classification: algebraic theory 14J15 Moduli, classification: analytic theory; relations with modular forms [See also 32G13] 14J17 Singularities [See also 14B05, 14E15] 14J20 Arithmetic ground fields [See also 11Dxx, 11G25, 11G35, 14Gxx] 14J25 Special surfaces For Hilbert modular surfaces, see 14G35 14J26 Rational and ruled surfaces 14J27 Elliptic surfaces 14J28 K3 surfaces and Enriques surfaces 14J29 Surfaces of general type 14J30 3-folds 14J32 Calabi-Yau manifolds, mirror symmetry 14J35 4-folds 14J40 n-folds (ngt; 4)

A.3SPESIALOMR˚ ADENE AV ALGEBRAISK GEOMETRI

14J45 14J50 14J60

49

14J70 14J80 14J81 14J99

Fano varieties Automorphisms of surfaces and higher-dimensional varieties Vector bundles on surfaces and higher-dimensional varieties, and their moduli [See also 14D20, 14F05, 32Lxx] Hypersurfaces Topology of surfaces (Donaldson polynomials, Seiberg-Witten invariants) Relationships with physics None of the above, but in this section

14Kxx 14K02 14K05 14K10 14K12 14K15 14K20 14K22 14K25 14K30 14K99

Abelian varieties and schemes Isogeny Algebraic theory Algebraic moduli, classification [See also 11G15] Subvarieties Arithmetic ground fields [See also 11Dxx, 11Fxx, 11Gxx, 4Gxx] Analytic theory; abelian integrals and differentials Complex multiplication [See also 11G15] Theta functions [See also 14H42] Picard schemes, higher Jacobians [See also 14H40, 32G20] None of the above, but in this section

14Lxx Algebraic Groups (For linear algebraic groups, see 20Gxx; for Lie algebras, see 17B45) 14L05 Formal groups, p-divisible groups [See also 55N22] 14L10 Group varieties 14L15 Group schemes 14L17 Affine algebraic groups, hyperalgebra constructions [See also 17B45, 18D35] 14L24 Geometric invariant theory [See also 13A50] 14L30 Group actions on varieties or schemes (quotients) [See also 13A50, 14L24] 14L35 Classical groups (geometric aspects) [See also 20Gxx, 51N30] 14L40 Other algebraic groups (geometric aspects) 14L99 None of the above, but in this section 14Mxx Special varieties 14M05 Varieties defined by ring conditions (factorial, Cohen-Macaulay, seminormal) [See also 13F45, 13H10] 14M06 Linkage [See also 13C40] 14M07 Low codimension problems 14M10 Complete intersections [See also 13C40] 14M12 Determinantal varieties [See also 13C40] 14M15 Grassmannians, Schubert varieties, flag manifolds [See also 32M10, 51M35] 14M17 Homogeneous spaces and generalizations [See also 32M10, 53C30, 57T15] 14M20 Rational and unirational varieties 14M25 Toric varieties, Newton polyhedra [See also 52B20] 14M30 Supervarieties [See also 32C11, 58A50]

50

DISKRET MATEMATIKK FINNES IKKE

14M99 None of the above, but in this section 14Nxx Projective and enumerative geometry 14N05 Projective techniques [See also 51N35] 14N10 Enumerative problems (combinatorial problems) 14N15 Classical problems, Schubert calculus 14N20 Configurations of linear subspaces 14N25 Varieties of low degree 14N30 Adjunction problems 14N35 Gromov-Witten invariants, quantum cohomology [See also 53D45] 14N99 None of the above, but in this section 14Pxx Real algebraic and real analytic geometry 14P05 Real algebraic sets [See also 12Dxx] 14P10 Semialgebraic sets and related spaces 14P15 Real analytic and semianalytic sets [See also 32B20, 32C05] 14P20 Nash functions and manifolds [See also 32C07, 58A07] 14P25 Topology of real algebraic varieties 14P99 None of the above, but in this section 14Qxx Computational aspects in algebraic geometry 14Q05 Curves 14Q10 Surfaces, hypersurfaces 14Q15 Higher-dimensional varieties 14Q20 Effectivity 14Q99 None of the above, but in this section 14Rxx Affine Geometry 14R05 Classification of affine varieties 14R10 Affine spaces (automorphisms, embeddings, exotic structures, cancellation problem) 14R15 Jacobian problem 14R20 Group actions on affine varieties [See also 13A50, 14L30] 14R25 Affine fibrations [See also 14D06] 14R99 None of the above, but in this section

BIBLIOGRAFI

[AMS] AMS subject classification 2000, American Mathematica Society, Providence, RI, 2000. [CG] D. Cass & G. Wildenberg, Math bite: A novel proof of the infinitude of primes, revisited, Mathematics Magzine 76 (3) (June 2003), 203. [F] J.B. Fraleigh, A first course in abstract algebra, Addison-Wesley, Reading Massachusetts, 1999. [L] Dan Laksov, Diskret matematikk finnes ikke, NORMAT 52 (2004), 21-38. [R] P. Ribenboim, The little book of big primes, Springer Verlag, New Yord, 1991. [S] V¨ alj specialarbete i Matematik, Redaktør Dan Laksov. Se ogs˚ a nettversjonen http://www.math.kth.se/~laksov, THD AB, Bandhagen, 1989.

51

52

DISKRET MATEMATIKK FINNES IKKE

53

INDEX

generere, 22 grafer, 2

addisjon, 19, 21 addisjonstabell, 19 alfabet, 17–21, 26 algebraisk geometri, 1 American Mathematical Society, 1 AMS-klassifikasjonen, 1 aritmetisk operasjon, 19 avkode, 19, 20, 26 avstand, 3–5, 8, 9, 17, 27

Hamming distanse, 18, 20 Hamming metrikk, 6, 8, 17, 18 Hamming, Richard, 6 helt tall, 3 Hensels Lemma, 37 identitesavbildning, 9 identitets savbildning, 9 ikke arkimedisk triangelulikhet, 7, 8, 27, 34 ikke degenerert, 4, 5, 7, 8, 27, 34 indusert metrikk, 5, 7

basis, 22, 24 blokk-kode, 18, 20 byte, 17 Cauchy sekvens, 27, 31, 33, 35, 38

kartesisk produkt, 6, 8, 21 Kinesiske Restsatsen, 36 kode, 17, 26 kodeord, 17, 18, 20, 21, 26 kodning, 19 kombinatorikk, 1 kompleks linje, 12 komplekse tall, 19 komplett, 35, 42 komplett rom, 38 komplettering, 27, 35, 38, 42 komponentvis addisjon, 19 konstant avbildning, 10 kontinuerlig, 3 kontinuitet, 3, 4, 9, 11, 13 kontrollsiffer, 17, 20 konvergens, 35, 38 kropp, 19, 21, 26

datalogi, 1 datamaskiner, 2 desimaltall, 28 dimensjon, 24 diskret metrikk, 5, 8 diskret topologi, 12 divisjon, 19, 21 ekvivalensrelasjon, 39 endelig komplement topologi, 12 endelig kropp, 19 epsilon omegn, 11 euklidsk metrikk, 5–8, 35, 38 euklidsk rom, 4, 5, 11, 38 feilrettende kode, 17 Fermats Lille Sats, 36 F¨ urstenberg, H., 13 Galois kropp, 19 Gauss-Jordan eliminasjon, 24 Gauss-Jordan operasjon, 22 generator, 23

lengde, 17, 26 lineær algebra, 21 lineær kode, 20, 26 53

refleksiv, 39 relasjon, 38

lineært uavhengig, 21–23 matematik diskret, 1 matematisk logikk, 1 matrisemultiplikasjon, 20 mengder, 2 metrikk, 5, 34 metrisk rom, 4, 5, 8, 12, 27, 38 multiplikasjon, 19, 21 multiplikasjonstabell, 19 multiplikativitet, 4, 7, 8

sannsynlighetsteori, 1 sfære, 11, 18 skalar, 21 Skolverket, 1, 2 subtraksjon, 19, 21 symmetri, 4, 5, 7, 8, 27, 34, 39 taksimetrikk, 6, 8 tallinje, 3 tallteori, 1 Taylors formel, 37 tett, 41, 42 to-adisk metrikk, 7 tomme mengden, 11 topologi, 11–13 topologisk rom, 11–13, 41 transitiv, 39 trappetrinnsmatrise, 22 triangelulihet, 8 triangelulikhet, 4–7, 18 triviell topologi, 12

norm, 34 ord, 17, 26 p-adisk, 29 p-adisk metrikk, 7, 8, 27, 35 p-adisk norm, 27, 31, 34 p-adisk tall, 29, 32–35, 38 p-adisk utvikling, 28, 31 paritet, 20 paritetskontroll, 17, 19, 20 paritetskontroll matrise, 26 periode, 12, 13 periodisk mengde, 12, 13 permutasjon, 2 perpendikulær, 24 primtall, 11, 12, 27

uavhengige ligninger, 21 uendeligtupler, 32 ukjent, 21 underrom, 22, 24

radius, 18 rasjonalt tall, 3, 19 reelle linjen, 5 reelt tall, 3, 19

vektor, 19, 21, 22 vektorrom, 21, 22 ˚ apen, 11, 41

54