118 Normat 53:3, 118–129 (2005)
Det tellbare og det overtellbare
Lars Kristiansen
Ingeniørutdanningen, Høgskolen i Oslo
Matematisk institutt, Universitetet i Oslo
larskri@iu.hio.no
«. . . – Hvorfor jager dere den vesle geitekillingen? spurte oksen.
– Han teller oss, rautet kalven. – Men vi skal ta’n, sa bjellekua.
– Jeg er en og kalven er to og kua er tre og oksen fire, 1-2-3-4, sa
geitekillingen. – Å, nå telte han deg også, rautet kalven. – Han
kan bare prøve, brølte oksen og ble med de andre for å ta
geitekillingen.»
– fra Geitekillingen som kunne telle til ti av Alf Prøysen
Kardinaliteter
Geitekillingen setter elementene i en ikketom endelig mengde i en-til-en korrespon-
danse med et initialsegment av de positive heltallene. På folkemunne kalles dette
å telle. Det er denne aktiviteten vi skal analysere og generalisere. La oss starte
med å filosofere litt over hvorfor geitekillingen, kalven og bjellekua er færre enn
geitekillingen, kalven, bjellekua og oksen? Vi skal si at en mengde som består av
geitekillingen, kalven og bjellekua har mindre kardinalitet enn en mengde som be-
står av geitekillingen, kalven, bjellekua og oksen, og at en mengde som består av
geitekillingen, kalven, bjellekua og oksen har større kardinalitet enn en mengde
som består av geitekillingen, kalven og bjellekua.
Definisjon 1. En mengde X har mindre eller lik kardinalitet enn en mengde Y
dersom det er mulig å avbilde ethvert element i X på et unikt element i Y .
Ved å avbilde et element på et annet element mener vi ikke noe mer mystisk enn
at det er mulig å trekke en pil fra det ene elementet til det andre. Så hvis A
er mengden s om består av nettopp geitekillingen, kalven og bjellekua, og B er
Normat 3/2005 Lars Kristiansen 119
mengden som består av geitekillingen, kalven, bjellekua og oksen, så har A mindre
eller lik kardinalitet som B siden vi f.eks. kan se tte opp følgende avbildning
bjellekua ! geitekillingen
kalven ! kalven
geitekillingen ! oksen
bjellekua
Vi ser at pilene som går fra elementene i A treffer hvert sitt element i B. Det
finnes ikke to piler som treffer samme element i B. Derfor har A mindre eller lik
kardinalitet som B. Det finnes selvsagt flere mulige avbildninger som viser at A
har mindre eller lik kardinalitet som B. I avbildningen
bjellekua ! bjellekua
geitekillingen ! kalven
kalven ! oksen
geitekillingen
avbildes også hvert element i A på et unikt element i B.
Definisjon 2. En mengde X har ekte større kardinalitet
1
enn en mengde Y dersom
1. Y har mindre eller lik kardinalitet som X, og
2. det ikke er slik at X har mindre eller lik kardinalitet som Y .
Så dersom X har ekte større kardinalitet enn Y , så kan ethvert element i Y avbildes
på et unikt element i X, mens det er ikke mulig å avbilde hvert element i X på
et unikt element i Y . Det betyr at mengden B (den som består av geitekillingen,
kalven, bjellekua og oksen) har ekte større kardinalitet enn mengden A (den som
består av geitekillingen, kalven og bjellekua). Hvert element i A kan avbildes på et
unikt element i B (så kardinaliteten til A er mindre eller lik kardinaliteten til B),
mens ethvert forsøk på å avbilde elementene i B på unike elementer i A, vil skjære
seg . . .
oksen ! bjellekua
geitekillingen ! kalven
kalven ! geitekillingen
bjellekua
. . . og på hvilket element skal vi avbilde bjellekua? Alle elementene i A er opptatt.
Man behøver ikke akkurat være en Einstein for å se at alle andre forsøk på å avbilde
elementene i B på unike elementer i A også vil skjære seg. Så mengden B har større
kardinalitet enn mengden A.
1
Av stilistiske grunner sier vi leilighetsvis «større» istedet for «ekte større».
120 Lars Kristiansen Normat 3/2005
Definisjon 3. En mengde X har ekte mindre kardinalitet
2
enn en mengde Y
dersom Y har ekte større kardinalitet enn X.
Definisjon 4. To m engder X og Y har samme kardinalitet dersom
1. X har mindre eller lik kardinalitet som Y , og
2. Y har mindre eller lik kardinalitet som X.
Så mengden som består av Faderen, Sønnen og bikkja deres
3
har samme kardi-
nalitet som mengden som består av kalven, kua og oksen. Vi kan avbilde ethvert
element i den første mengden på et unikt element i den andre mengden, f.eks. slik
Faderen ! kalven
Sønnen ! kua
Den hellige hund ! oksen
og vice versa, vi kan avbilde hvert element i den andre mengden på et unikt element
i den første mengden, f.eks. slik
oksen ! Faderen
kua ! Sønnen
kalven ! Den hellige hund
Dermed har de to mengdene samme kardinalitet i følge definisjonen.
Noen gremmer seg kanskje nå. Hva skal disse infantile definisjonene tjene til?
At en mengde f.eks. har større kardinalitet enn en annen mengde betyr åpenbart
at det er flere elementer i den ene mengden enn den andre. Har to mengder samme
kardinalitet, så betyr det at det er like mange elemente r i de to mengdene. Hvorfor
ikke bare si det og bli ferdig med det? Vi ve t alle hva ord som «flere», «færre»
og «like mange» betyr. Vel, det er først når vi begynner å snakke om uendelige
mengder at våre definisjoner komm er til sin rett. Definisjonene gjør det mulig å
snakke om grader av uendelighet. Vi skal se at en uendelig mengde kan ha større
kardinalitet enn, eller mindre kardinalitet enn, eller samme kardinalitet som, en
annen uendelig mengde. Mengden av primtall har for eksempel samme kardinalitet
som mengden av partall. Vi kan sette elementene i den ene mengden i en-til-en
korrespondanse med elementene i den andre mengden, f.eks. slik
2 ! 0
3 ! 2
5 ! 4
7 ! 6
11 ! 8
13 ! 10
.
.
.
2
. . . og vi sier av og til «mind re» istedet for «ekte mindre».
3
Den hellige hund.
Normat 3/2005 Lars Kristiansen 121
Når vi kan sette opp en slik en-til-en korrespondanse mellom elementene i to meng-
der, så har de to mengdene samme kardinalitet. Da kan jo hvert element i den første
mengden avbildes på et unikt element i den andre mengden, og vice versa, hvert
element i den andre mengden kan avbildes på et unikt element i den første mengden.
Enhver endelig mengde har åpenbart en kardinalitet som svarer til et naturlig
tall. Vi sier at en endelig mengde som består av n elementer har kardinalitet n.I
stigende rekkefølge har vi kardinalitetene
kardinalitet 0 – kardinaliteten til den tomme mengden ;
kardinalitet 1 – som f.eks. er kardinaliteten til mengden {0}
kardinalitet 2 – som f.eks. er kardinaliteten til mengden {0, 1}
kardinalitet 3 – som f.eks. er kardinaliteten til mengden {0, 1, 2}
kardinalitet 4 – som f.eks. er kardinaliteten til mengden {0, 1, 2, 3}
.
.
.
Etter denne rekken av endelige kardinaliteter følger kardinaliteten det er vanlig å
kalle @
0
. (Tegnet @ er den første bokstaven i det hebraiske alfabetet, og den uttales
«aleff» med trykk på første stavelse.) Dette er kardinaliteten til alle mengder som
kan settes i en-til-en korrespondanse med de naturlige tallene. Mengden av partall
og mengden av primtall er eksempler på mengder som har kardinalitet @
0
. Så
i stigende rekkefølge har vi kardinalitetene 0, 1, 2, 3, 4, 5,...,@
0
. Finnes det flere
kardinaliteter? Ja, den minste kardinaliteten større enn @
0
kalles @
1
. Merkelig nok
er vi ikke sikre på hvilke me ngder som har denne kardinaliteten. Dette kommer vi
tilbake til. I første omgang skal vi se nærmere på kardinaliteten @
0
.
Det tellbare
En mengde med kardinalitet @
0
kalles en tellbart uendelig mengde. Elementene
i den kan settes i en-til-en korrespondanse med de naturlige tallene. Det er med
andre ord mulig å liste opp, eller telle opp, elementene i en slik mengde. Vi har
allerede nevnt et par slike mengder: mengden av primtall og mengden av partall.
Mengden av heltall, positive som negative, har også kardinalitet @
0
. Vi kan f.eks.
telle heltallene opp etter mønsteret
0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5,...
Hva med mengden av positive rasjonale tall? Dette er mengden av tall som kan
uttrykkes som en brøk m/n der m og n er naturlige tall ekte større enn 0. Kan
122 Lars Kristiansen Normat 3/2005
denne mengden telles opp? Svaret finner vi hjelp av denne figuren:
123456
1 0 1 3 6 10 15
2 2 4 7 11 16
3 5 8 12 .
4 9 13 .
5 14 .
6
Vi ser hjørnet av en uendelig stor matrise. I feltene i matrisen finner vi de naturlige
tallene systematisk listet opp. Hvert felt i matrisen har to naturlige tall s om koor-
dinater, en vertikalkoordinat og en horisontalkoordinat. Brøken m/n kan assosieres
med det naturlige tallet som har horisontalkoordinat m og vertikalkoordinat n. Vi
har altså
0 !
1
1
1 !
2
1
2 !
1
2
3 !
3
1
4 !
2
2
5 !
1
3
.
.
.
Har vi derme d en en-til-en korrespondanse mellom de positive rasjonale tallene
og de naturlig tallene? Nei, mange av brøkene i listen angir samme rasjonale tall,
f.eks. brøkene
1
2
og
2
4
. Dermed er det ikke en en-til-en korrespondanse mellom de
naturlige tallene og de positive rasjonale tall vi har satt opp. Det er snarere en
en-til-en korrespondanse mellom de naturlige tallene og en mengde uttrykk (eller
notasjoner) for rasjonale tall. Likevel viser opptellingen vår at mengden av rasjonale
tall har kardinalitet @
0
. En en-til-en korrespondanse mellom de naturlige tallene og
de rasjonale tallene, kan man få ved å fjerne alle brøker som ikke er forkortet helt
ned fra listen
1
1
,
2
1
,
1
2
,
3
1
,
2
2
,
1
3
,
4
1
,.... Listen vi da sitter igjen med
1
1
,
2
1
,
1
2
,
3
1
,
1
3
,
4
1
,...
inneholder nøyaktig ett uttrykk for hvert rasjonale tall. Elementene i denne listen
kan settes i en en-til-en korrespondanse med de naturlige tallene. Så mengden av
rasjonale tall har kardinalitet @
0
.
Mengden av alle endelige bitsekvenser har også kardinalitet @
0
. Bitsekvenser kan
listes opp etter mønsteret.
0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010,...(*)
Først lister vi alle bitsekvenser med lengde én. (Det finnes to slike.) Deretter lister
vi alle bitsekvenser med lengde to. (Det finnes fire slike.) Dere tter alle strenger med
lengde tre. (Det er 8 stykker.) Slik fortsetter det, og vi ender opp med en uendelig
Normat 3/2005 Lars Kristiansen 123
lang liste der elementene kan settes i en-til-en korrespondanse med de naturlige
tallene.
En bitsekvens er en sekvens over alfabetet som består av tegnene 0 og 1. Hvis et
alfabet har mer en to tegn, f.eks. 10 tegn, kan vi også liste opp alle endelige sekven-
ser av tegn fra alfabetet etter mønsteret i (*). Først lister vi opp alle sekvensene
som består av ett tegn. Det er 10 stykker. Deretter lister vi opp alle sekvensene
som består av to tegn. Det er 100 stykker. Og så videre.
Dersom hvert element i en mengde X kan refereres til ved en endelig sekvens av
tegn fra et alfabet, så må X ha kardinalitet mindre eller lik @
0
. Hvorfor det? Jo,
fordi mengden av alle endelige sekvenser over det aktuelle alfabetet har kardinalitet
@
0
, og ethvert element i X kan åpenbart avbildes på et unikt element i mengden
som inneholder alle endelige sekvenser. Dersom flere sekvenser refererer til samme
element a 2 X, velger vi bare en av s ekvensene og avbilder a på den. Dermed
er kardinaliteten til X mindre eller lik kardinaliteten til mengden av alle endelige
sekvenser over alfabetet, den er med andre ord mindre eller lik @
0
. Mengden av
rasjonale tall e r et eksempel på en mengde hvor ethvert element kan refereres til
ved en endelig sekvens av tegn fra et alfab e t. Et rasjonalt tall kan jo refereres til
ved en streng hvor tegnene er hentet fra alfabetet som består av sifrene ’0’, . . . , ’9’,
en brøkstrek og fortegnet ’’ (minus). Mengden av reelle tall er ikke et eksempel
på en slik mengde. Et reelt tall kan jo ha e n uendelig desimalutvikling. Men så har
da heller ikke mengden av reelle tall kardinalitet @
0
.
Det overtellbare
Mengder som har kardinalitet større enn @
0
kalles gjerne overtellbare mengder. Det
er på en måte for mange elementer i disse mengdene til at de kan telles opp. Det er
ikke mulig å sette elementene i en overtellbar mengde i en en-til-en korrespondanse
med de naturlige tallene. Vi har sett at mengden av alle endelige bitsekvenser er
tellbar. Vi skal nå forsøke å forstå hvorfor mengden av alle uendelige bitsekvenser
ikke har kardinalitet mindre eller lik @
0
. Den har kardinalitet ekte større enn @
0
og er me d andre ord overtellbar. For å overbevise oss selv om at det faktisk er slik,
må vi ty til diagonaliseringsteknikk. Det er en bevisteknikk som kan spores tilbake
til Georg Cantor.
4
Det finnes mange varianter av teknikken, men vi skal benytte
den i sin aller reneste form.
Tenk deg en matrise hvor elementene kan være 0 eller 1. La oss si at den er
7 ⇥ 7-stor. Ta f.eks. matrisen
1 000000
0 0 01111
101 1000
0001 001
00000 10
001010 0
1100110
4
Russisk-tysk matematiker, 1845–1918.
124 Lars Kristiansen Normat 3/2005
I hver av matrisens rader finner vi en syvbitssekvens. I den første raden finner
vi sekvensen 1000000, i den andre sekvensen 0001111, og så videre. Bitene på
diagonalen fra det øvre venstre til det nedre høyre hjørnet, er uthevet. De gir også
en syvbitssekvens.
(diagonal) 1011000
La oss forandre hvert eneste bit i denne sekvensen. Vi gjør enerne om til nuller og
nullene om til enere. Syvbitssekvensen vi ender opp med kalles matrisens modifi-
serte diagonal.
(modifisert diagonal) 0100111
Matrisens modifiserte diagonal kan ikke være blant syvbitssekvensene vi finner
som rader i matrisen. Den er jo forskjellig fra sekvensen i første rad i det første
bitet, forskjellig fra sekvensen i andre rad i det andre bitet, . . . kort sagt, den er
forskjellig fra sekvensen i n’te rad i det n’te bitet for n =1, 2, 3, 4, 5, 6, 7. En uendelig
bitmatrise har en uendelig modifisert diagonal. Den er forskjellig fra sekvensen i
n’te rad i det n’te bitet for n =1, 2, 3,.... Den uendelige modifiserte diagonalen
kan ikke være blant de uendelig mange uendelige bitsekvensene vi finner som rader
i den uendelige matrisen.
Vi skal altså overbevise oss selv om at mengden av alle uendelige bitsekvenser
ikke har kardinalitet mindre eller lik @
0
. Vi antar nå at dette er galt! Vi antar nå
at denne mengden av sekvenser har mindre eller lik kardinalitet som mengden av
naturlige tall. Det b etyr at enhver uendelig bitsekvens kan avbildes på et unikt
naturlig tall. Vi har ikke lov til å trekke noen konklusjoner om hvordan denne
avbildningen ser ut, men vi har lov til å trekke den konklusjon at en slik avbildning
finnes. Det er jo nettopp det det betyr at denne mengden av se kvenser har mindre
eller lik kardinalitet som mengden av naturlige tall. Det er slik vi har definert at
en mengde har mindre eller lik kardinalitet som en annen mengde. Så la S
0
være
sekvensen som er avbildet på tallet 0. La S
1
være sekvensen som er avbildet på
tallet 1, S
2
være sekvensen som er avbildet på 2 og så videre. Vi kan nå sette opp
sekvensene S
0
,S
1
,S
2
,... linje for linje slik at vi får e n uendelig matrise:
S
0
: 00101···
S
1
: 10011···
S
2
: 10111···
S
3
: 01010···
.
.
.
Vi vet altså ikke hvordan sekvensen S
0
, eller s ekvensen S
1
, eller S
19
, eller noen av
de andre radene i matrisen ser ut. Vi har bare slengt inn noen bit i det øvre høyre
hjørnet for å illustrere at matrisen er faktisk fylt opp, men det er helt avgjørende
å få med seg at argumentasjonen vår ikke hviler på hvor i matrisen de enkelte
nullene og enerne er plassert. Argumentet vårt holder for, og det må holde for,
enhver distribusjon av nuller og enere i denne matrisen. Noen av linjene i matrisen
Normat 3/2005 Lars Kristiansen 125
kan også være tomme. Det kan jo hende at noen tall ikke har fått avbildet en
sekvens på seg. I disse linjene s etter vi inn en uendelig sekvens av nuller.
Matrisen over ble konstruert fra en avbildning. De uendelige bitsekvensene er
avbildet på de naturlige tallene slik at hver sekvens er avbildet på minst ett tall,
og to forskjellige sekvenser er aldri avbildet på samme tall. Det betyr at enhver
uendelig bitsekvens forekommer som en rad i denne matrisen. Men det kan ikke
være riktig! Matrisens modifiserte diagonal er en uendelig bitsekvens, og den kan
ikke forekomme som som en rad i matrisen. Dermed leder antagelsen om at mengden
av uendelig bitsekvenser har kardinalitet mindre eller lik @
0
til noe vi vet er galt.
Dermed trekker vi konklusjonen at mengden ikke kan ha kardinalitet mindre eller
lik @
0
. Den må ha større kardinalitet. Den må være overtellbar.
Vi har nettopp gjennomført et ad absurdum argument. Det er en meget vanlig
matematisk argumentasjonsform basert på at enten p eller «ikke p» er sann. (Her
står p for en vilkårlig påstand.) Dersom «ikke p» har absurde konsekvenser, så
kan det ikke være slik at «ikke p» er sann, ergo må det være p som e r sann.
I vårt tilfelle har det absurde konsekvenser at mengden ikke er overtellbar: At
den modifiserte diagonalen forekommer som en rad i matrisa er en selvmotsigelse.
Dermed konkluderer vi at mengden er overtellbar.
Har du blitt overbevist om at det finnes kardinaliteter som er ekte større en
@
0
? Det finnes mennesker som tilsynelatende aldri lar seg overbevise om dette. Det
finnes en egen rase som på engelsk går under betegnelsen «mathematical cranks». Vi
kan kalle dem vinkeltredelere på norsk. Dette er mennesker som ikke vil, eller ikke
kan, godta standard og alment akseptert matematikk. Og de stiller seg heller ikke
likegyldig eller uforstående til denne matematikken. Tvertimot. De har en tendens
til å legge betydelig arbeid og e nergi i å motbevise hva generasjoner av seriøst
arbeidende matematikere har kommet fram til. Ja, enkelte vier faktisk livet sitt til
dette. De forsøker for eksempel å tredele en vinkel ved hjelp av passer og linjal. Det
er umulig. Det kan bevises at det er umulig. Man forsøker å fortelle dem at det er
umulig, men det biter liksom ikke på dem. De går løs på oppgaven med friskt mot.
Produserer den ene avhandlingen etter den andre hvor de hevder at det umulige er
mulig. Utallige av avhandlingene har gjennom årenes løp blitt donert mate matiske
institusjoner verden over. En venn av meg fant egenhendig et lite knippe da han
ryddet i et gammelt arkiv på Matematisk institutt ved Universitetet i Oslo. Det
var etter sigende underholdende lesning, blant annet kunne en pensjonert lærer
fra Forsvarets radarskole fortelle at verdien av det velkjente irrasjonale tallet e lå
atskillig nærmere 3 enn hva man tidligere hadde tenkt seg. (Dersom vi ogs å kunne
få redusert verdien av ⇡ litt, så . . . ja, hvem vet, kanskje e = ⇡?)
Et yndet tema for vinkeltredelere er eksistensen av overtellbare kardinaliteter
(se [3]). De liker tydeligvis ikke at slike kardinaliteter finnes. Den måten vi har
argumentert på over, finner de slett ikke overbevisende. De later til å mene at det
burde være mulig å sette opp matrisen så smart og snedig at diagonaliseringsargu-
mentet slår feil. (Det er selvsagt bare tøv. Uansett hvordan matrisen settes opp,
vil den ha en diagonal, og har den en diagonal så har den en modifisert diagonal.)
Internett og e postlister er tumleplass numme r én for vinkeltredelere. Der kan de
virkelig boltre seg. Gödels ufullstendighetsteoremer er et annet tema de har en
tendens til å beskjeftige seg med. Så vær på vakt. Enkelte vinkeltredelere kan til
tider virke relativt tilforlatelige.
126 Lars Kristiansen Normat 3/2005
Kontinuumshypotesen
Tenk deg en linje – en rett strek – se tt 0 i den ene enden på denne linjen og 1 i
den andre. Da har du en slags målestokk. Mellom 0 og 1 på målestokken ligger
en rekke punkter. Hvert punkt svarer til det som kalles et reelt tall mellom null
og én. At et punkt x ligger til høyre for et punkt y på linjen betyr det samm e
som at x svarer til et tall som er større enn y. Et punkt kan svare til et tall som
har en uendelig lang desimalutvikling. Det er ikke mulig å skrive ned den nøyak-
tige verdien av tallet dersom man skriver sifre etter et komma. Man kan begynne
0,32938374939394847 ..., men man blir aldri ferdig. Dersom man regner om et tall
fra brøkrepresentasjon til desimalrepresentasjon, vil man enten ende opp med en
endelig desimalutvikling eller en desimalutvikling der en desimalsekvens repeteres
i det uendelige. Regner man f.eks. om
1
8
får man den endelige desimalutviklingen
0,125, regner man om
1
7
får man utviklingen 0,142857142857142 ...hvor sekvensen
142857 repeteres i det uendelige. Noen av punktene på linjen vil således svare til
tall som ikke kan representeres som brøker. De svarer til tall som har en uendelig
ikkerepeterende desimalutvikling, til såkalte irrasjonale tall.
Denne omtalte linjen av punkter kalles kontinuum, og mengden av punkter på
linjen kalles gjerne kontinuumsmengden. Per definisjon er det altså like mange
elementer i kontinuumsmengden som det er reelle tall mellom null og én, og hvor
mange er det? Hva er kardinaliteten til kontinuumsmengden? Vel, det er relativt
lett å bevise at kontinuumsmengden har samme kardinalitet som mengden av alle
uendelige bitsekvenser. Vi skal ikke gjøre det, men det er ikke vanskeligere enn at
de skarpeste av leserne bør få det til på egenhånd. (Se forøvrig figur 1.) Vi har sett
at mengden av alle uendelige bitsekvenser er overtellbar. Det betyr at mengden av
punkter på kontinuum også e r overtellbar. Den har altså en kardinalitet som er
ekte større enn @
0
. Spørsmålet er hvor mye større?
La oss oppsummere litt. Vi har kardinalitetene til de endelige mengdene. En
endelig mengde har en kardinalitet som svarer til et naturlig tall, og det er van-
lig å benytte de naturlige tallene som navn på disse kardinalitetene. Vi har da
i stigende rekkefølge kardinalitetene 0,1,2,3,. . . . Etter disse kardinalitetene følger
kardinaliteten som kalles @
0
– kardinaliteten til mengden av naturlige tall. Vi har
da i stigende rekkefølge kardinalitetene 0, 1, 2, 3,...@
0
. Dette er (per definisjon)
de tellbare kardinalitetene, og disse kardinalitetene er uproblematiske. Det er også
helt uproblematisk at det finnes mengder som ikke har tellbar kardinalitet. Men
så begynner moroa. Hvilken kardinalitet følger etter @
0
? Vel, selve spørsmålet kan
faktisk bedra og villede. Er det nå så sikkert at en bestemt kardinalitet følger etter
@
0
? Kunne vi ikke tenke oss at det kommer to kardinaliteter
1
og
2
etter @
0
?
Det finnes ingen kardinalitet mellom @
0
og
1
, og det finnes ingen kardinalitet @
0
og
2
, men likevel er ikke
1
mindre eller lik
2
, og
2
er ikke mindre eller lik
1
. De to kardinalitetene
1
og
2
er på en måte usammenlignbare. Joda, det er
slett ikke helt fjernt å tenke seg en slik situasjon, men nå forholder det seg slik at
dersom man godtar utvalgsaksiomet,
5
så kan man bevise at det følger én, og bare
5
Det finnes mange formuleringer av utvalgsaksiom et i litteraturen. I matematikken er det ofte
slik at to prinsipp som ser forskjellige ut ved første øyekast, er ekvivalente i den forst and at de
medfører nøyaktig det samme. En vanl ig og tilgjengelig formulering av utvalgsaksiomet lyder slik:
Anta at du har en samling ikketomme mengder A
0
,A
1
,A
2
,..., gjerne overtellbart mange. Anta
videre at mengdene i samlingen er disjunkte. Det betyr at hvis x er med i én av mengdene, så
er ikke x med i noen av de andre mengdene. Dersom det finnes en mengde som inneholder alle
Normat 3/2005 Lars Kristiansen 127
Figur 1 : Utrolig nok kan ethvert punkt på den positive delen av den reelle tallinjen
avbildes på et unikt punkt som ligger mellom 0 og 1 på den samme tallinjen. Punktet
a på den positive delen av x-aksen i koordinatsystemet avbildes på punktet a
0
som
ligger mellom 0 og 1 på x-aksen. Avbildningen skjer ved at det trekkes en linje fra a
til punktet 1 på y-aksen. Linjen som er stiplet i figuren, vil alltid skjære diagonalen
i det inntegnede kvadratet, dvs. linjen trukket mellom punktene med koordinater
(0, 0) og (1, 1). Fra punktet hvor linjen skjærer diagonalen trekkes en loddrett linje
ned på x-aksen. Den loddrette linjen treffer punktet a
0
som vil ligge mellom 0 og 1.
(Studer hva som skjer når a selv ligger mellom 0 og 1.) Figuren viser at dersom a og
b er to forskjellige punkter på x-aksen, så vil de også avbildes på forskjellige punkter
i intervallet 0 til 1. Mengden av positive reelle tall må altså ha samme kardinalitet
som kontinuumsmengden. Leseren kan selv forsikre seg om at mengden av alle reelle
tall, positive som negative, også har samme kardinalitet som kontinuumsmengden.
én, kardinalitet umiddelbart etter @
0
. Denne kardinaliteten har man døpt til @
1
.
Utvalgsaksiomet er et matematisk prinsipp, eller kanskje m an skulle si lov, som de
fleste matematikere ikke finner alt for kontroversiell. Man vil helst unngå å bruke
utvalgsaksiomet når man beviser noe, men samtidig vet man at enkelte teoremer
ikke lar seg vise dersom man unnlater å benytte dette prinsippet. Et eksempel
på et slikt teorem er nettopp teoremet som sier at det kommer én, og bare én,
kardinalitet etter @
0
. Under forutsetning at utvalgsaksiomet holder, så finnes det
faktisk en entydig rekke av kardinaliteter etter @
0
. @
0
, @
1
, @
2
, @
3
,.... For ethvert
naturlig tall i så kan det altså vises at det kommer én, og bare én, kardinalitet
umiddelbar e tter @
i
. Denne kardinaliteten heter per definisjon @
i+1
. Videre kan
man vise at den entydige stigende følgen av kardinaliteter også fortsetter etter den
uendelige rekken @
0
, @
1
, @
2
,.... Da følger en kardinalitet som kalles @
!
.(! er den
mengdene i samlingen, så finnes det også en mengde B som inneholder nøyaktig ett element fra
hver av mengdene i samlingen. Så aksiomet tillater deg på en måte å lage en ny meng de B fra
en mengde av mengder. Dette kan jo se ut som et uskyldig og ufarlig prinsipp, men aksiomet
har noen underlige konsekvenser. Legg merke til at aksiomet ikke krever at du forteller hvilket
element som skal velges fra A
0
, hvilket eleme nt som skal velges fra A
1
, hvilket eleme nt som skal
velges fra A
2
, osv.
128 Lars Kristiansen Normat 3/2005
siste bokstaven i det greske alfabetet. Den uttales «omega».) Etter @
!
følger @
!+1
,
så følger @
!+2
osv. Vi har altså i stigende rekkefølge kardinalitetene
0, 1, 2, 3,... @
0
, @
1
, @
2
, @
3
,... @
!
, @
!+1
, @
!+2
, @
!+3
,...(†)
og det fortsetter og fortsetter og fortsetter. Hvor langt dette fortsetter, avhenger
av hvilke matematiske prinsipper man er villig til å godta.
Alt dette var Georg Cantor klar over allerede i 1877. Han vet at kontinuums-
mengden har kardinalitet ekte større enn @
0
, og han ser for seg den stigende rek-
ken av kardinaliteter @
0
, @
1
, @
2
,...@
!
, @
!+1
,..., men klarer ikke å finne en mengde
som har kardinalitet ekte større enn @
0
og ekte mindre enn kardinaliteten til kon-
tinuumsmengden. Dermed gjetter han at kontinuumsmengden har kardinalitet @
1
.
Denne gjetningen har fått navnet kontinuumshypotesen. Han har altså intet presist
matematisk argument som tvinger oss til å godta at det er slik. Det han kan be-
vise, under forutsetning at utvalgsaksiomet holder, er at det må finnes en mengde
X med egenskapene
1. kardinaliteten til X er ekte større enn @
0
2. det finnes ingen mengde som både har kardinalitet ekte større enn @
0
og ekte
mindre enn X
3. enhver annen mengde har enten større kardinalitet enn X, mindre kardinalitet
enn X eller samme kardinalitet som X.
Kardinaliteten til X heter per definisjon @
1
. Kontinuumshypotesen sier at konti-
nuumsmengden har kardinalitet @
1
. Det er en gjetning.
Like før andre verdenskrig beviste Kurt Gödel
6
at det er konsistent med alle
kjente matematiske prinsipper og sannheter at kontinuumshypotesen er riktig. Han
viste altså ikke at kontinuumshypotesen er riktig. Han avledet den ikke fra andre
matematiske prinsipper og sannheter, men han viste at det er konsistent med all
annen kjent og alment godtatt matematikk at kontinuumshypotesen er sann. Det
virker merkelig at det går an å vise noe sånt, men det gjør det altså. I 1963 viste
Paul Cohen
7
at det også er konsistent med den samme matematikken at kontinu-
umshypotesen er gal. Og dette virker jo skikkelig me rkelig. Det er m erkelig at det
er sånn, og det er merkelig at det er mulig å føre et bevis for at det er sånn. Det
betyr at du kan velge hvorvidt du vi vil tro på kontinuumshypotesen eller ikke.
Du kan velge i den forstand at uansett hva du velger å tro, så velger du ikke å tro
på noe som er i konflikt med den øvrige matematikken. Dette låter mystisk. Det
er ikke mystisk, men man må studere en del avansert mengdelære og matematisk
logikk for å innse det. (Noen mennesker har en tendens til å overfortolke vitenskap
de ikke forstår.)
Etterord. Man kan nok få et visst grep om forskjellen mellom det tellbare og det
overtellbare ved lese en enkel liten artikkel s om dette, men vil man ha en dypere for-
ståelse av kontinuumshypotesen og dens filosofiske og matematiske implikasjoner,
må man jobbe for det. Så da e r det bare å gå igang å lese: Kamke [4], Devlin [2] og
6
Tysk-amerikansk matematiker, 1906–1974.
7
Amerikansk matematiker, født 1934.
Normat 3/2005 Lars Kristiansen 129
Kuhnen [5] har vært undertegnedes lærebøker i mengdelære. Kamke [4] er lettlest
og anbefales som innføringslektyre, Devlin [2] er ikke fullt så lettlest, mens Kuhnen
[5] er en omfattende bok som krever sitt. Mengdelære er nært relatert til formell
logikk, og det finnes et utall av innføringsbøker i logikk. Barwise & Etchemendy [1]
er en lettlest bok som også tar opp sammenhengen me llom mengdelære og formell
logikk – innføringsbøker i logikk gjør vanligvis ikke det. Shoenfield [6] er en tung
og omfattende, men meget god, logikklærebok som inneholder mye mengdelære.
Slik forfatteren har formulert seg over, er det et åpent spørsmål om kontinu-
umshypotesen gir mening dersom utvalgsaksiomet ikke holder. I en vanlig lærebok
i mengdelære utvikles en raffinert og omstendelig teori hvor kardinalitetsbegrepet
defineres ved hjelp av såkalte velordninger. Hvis man ser det hele med en lekmanns
øyne, ender en slik utvikling essensielt opp med det samme kardinalitetsbegrepet
som utvikles i denne artikkelen. Imidlertid vil man ikke ha behov for utvalgsaksio-
met når man skal vise at kardinalitetene kan ordnes lineært i stigende rekkefølge
slik (†) antyder. Det betyr at kardinaliteten @
1
er veldefinert selv om utvalgsaksio-
met er galt. Dermed blir kontinuumshypotesen, som jo sier at kontinuumsmengden
har kardinalitet @
1
, meningsfull uavhengig av hvorvidt utvalgsaksiomet holder. Det
er forøvrig vist at utvalgsaksiomet har samme status som kontinuumshypotesen.
Aksiomet er uavhengig av all annen kjent og alment akseptert matematikk. Gö-
del viste at det er konsistent med denne matematikken at utvalgsaksiomet holder,
Cohen viste at det er konsistent at det ikke holder.
Referanser
[1] Barwise J. og Etchemendy J. The Language of First-Order Logic. CSLI Lecture
Notes, 1993.
[2] Devlin, K. The Joy of Sets. Springer, 2nd ed., 1993.
[3] Hodges, W. An editor recalls some hopeless papers. Bull. Symbolic Logic 4 (1998),
1-16.
[4] Kamke, E. Theory of Sets. Dover, New York, 1950.
[5] Kuhnen, K. Set Theory. An Introduction to Independence Proofs. North-Holland,
1980.
[6] Shoenfield, J.R. Mathematical logic. A. K. Peters.
