Tellbare mengder

Tellbarhet er en slags motstykke til størrelsen på mengder, for ved uendelige mengder kan vi ikke regne med antall elementer, siden antall elementer uventet nok er … uendelig. Størrelsen på en mengde kalles også kardinalitet.

Størrelsen på en uendelig mengde

Å bestemme størrelsen på en endelig mengde er enkelt, vi teller bare elementene. Mengden M = {a, b, c, d, e} har størrelse 5, og vi skriver |M| = 5.

For uendelige mengder er situasjonen en del mer komplisert. Hvordan kan vi sammenligne størrelsen på uendelige mengder? Går det i det hele tatt, eller er alle uendelige mengder «like store»?

La oss som eksempel ta mengden av naturlige tall og mengden av naturlige partall. Vi har da mengdene ℕ = {1, 2, 3, 4, 5, 6, …} og S = {2, 4, 6, …}. Det er fristende å si at mengden av naturlige tall er større enn mengden av partall, for de naturlige tallene inneholder alle partallene og dessuten noen elementer til — oddetallene.

Vi kunne altså skrive at S ⊂ ℕ, mengden S er en ekte delmengde av mengden ℕ. Og vi kunne si at hvis S ⊂ ℕ, så er mengden ℕ større — den inneholder jo flere elementer enn mengden S.

Én grunn til at vi ikke kan måle mengder ved relasjonen delmengde, er at mengder kan ha ulik størrelse selv om ingen av dem er en delmengde av den andre. Det kan vi vise også med endelige mengder: A = {1, 3, 4, 9} og B = {b, u, r, z, m}. Det gjelder |A| = 4 og |B| = 5. Mengden B er større enn mengden A, men likevel gjelder ikke A ⊂ B. For uendelige mengder kan vi se det med partall og oddetall. Ingen av mengdene er en delmengde av den andre.

Relasjonen delmengde er altså ikke noen god kandidat til å avgjøre om en mengde er større enn en annen.

Bijeksjon

Vi prøver en annen tilnærming. Vi har to mengder, A og B. Vi kan si at de har samme størrelse hvis det finnes en bijektiv avbildning mellom dem. Hva betyr det? At vi tar et element fra mengden A, et element fra mengden B og lager et par (a, b). Disse elementene fjerner vi fra mengdene og fortsetter. Hvis vi klarer å «tømme» begge mengdene, har vi funnet en bijektiv avbildning.

Eksempel med endelige mengder: A = {a, b, c} og B = {1, 2, 3}. Det første paret kunne være (a, 1), det neste (b, 2) og til slutt (c, 3). Vi har brukt opp alle elementene i begge mengdene og har funnet en bijektiv avbildning. Det er viktig at dette ikke er den eneste bijektive avbildningen. Dette er også en gyldig løsning: (a, 3), (b, 1), (c, 2).

For uendelige mengder er det litt mer interessant. Vi prøver med oddetall og partall blant de naturlige tallene. Intuitivt føler vi at det burde være like mange. Vi prøver. Vi tar det første oddetallet og avbilder det på det første partallet: (1, 2). Så det andre oddetallet og det andre partallet: (3, 4). Osv. Da får vi parene (1, 2), (3, 4), (5, 6), (7, 8), … Vi kunne skrive at hvert oddetall l avbildes på partallet l + 1, og hvert partall s er bildet av oddetallet s − 1. For hvert oddetall og hvert partall har vi dermed et par som inneholder tallet. Mengdene av oddetall og partall er altså like store.

Partall mot naturlige tall

Nå prøver vi den samme fremgangsmåten og sammenligner mengden av naturlige tall og partall. Vi har mengdene ℕ = {1, 2, 3, 4, 5, 6, …} og S = {2, 4, 6, …}. Intuitivt venter vi at mengden av naturlige tall er større.

La oss nå prøve å finne en slik bijektiv avbildning. Vi kan si at hvert naturlig tall n avbildes på det dobbelte, på 2n. Da får vi parene (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … For hvert naturlig tall n har vi dermed paret (n, 2n), og for hvert partall s har vi paret (s/2, s). Vi har funnet en bijektiv avbildning, så mengden av partall og mengden av naturlige tall er like store, de har samme kardinalitet.

Dette kan virke forvirrende, for de naturlige tallene inneholder jo flere elementer enn partallene. De naturlige tallene inneholder alle partallene og dessuten alle oddetallene. Men vi kan finne en bijeksjon, så begge mengdene er like store.

Sammenligning med de naturlige tallene

De naturlige tallene angir egentlig den minste størrelsen en uendelig mengde kan ha. Om en annen mengde har samme størrelse som mengden av naturlige tall, kan ofte avgjøres ganske enkelt — det er nok å finne en bijeksjon til de naturlige tallene, og i praksis betyr det at det er nok at vi klarer å nummerere elementene i mengden M, å ordne dem.

Hvis vi altså klarer å ordne elementene i en mengde slik at vi kan avgjøre hvilket element som er det første, hvilket som er det andre, tredje, fjerde, tiende osv., så er mengden like stor som ℕ. Om en slik mengde sier vi at den er tellbar.

Vi ser lett at partall og oddetall blant de naturlige tallene er tellbare, for vi kan bestemme det første, andre, tredje osv. partallet/oddetallet. Hva med partallene blant heltallene? Altså mengden S = {…, −4, −2, 0, 2, 4, …}. Klarer vi å ordne dem? Ja, vi tar den samme rekkefølgen som sist og skriver rett etter hvert positive partall også den negative varianten: S = {0, 2, −2, 4, −4, 6, −6, …}. På tilsvarende måte for eksempel for heltallene.

Størrelsen på de rasjonale tallene

Et mer interessant eksempel er de rasjonale tallene, brøkene. Klarer vi å ordne dem? Ja, men det blir litt mer komplisert. Vi lager en tabell med uendelig mange rader og kolonner. I hver rute står en brøk. I n-te kolonne og m-te rad har vi brøken n/m. Altså har vi $\frac{1}{2}$ i 1. kolonne og 2. rad, og 3/4 i tredje kolonne og fjerde rad.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Hvordan skal vi nå ordne og nummerere disse tallene? Vi kan ikke nummerere dem rad for rad eller kolonne for kolonne, for da ville vi drukne i den første raden/kolonnen. I stedet tar vi tallene langs diagonalene: (første diagonal:) 1/1, (andre diagonal:) 2/1, 1/2, (tredje diagonal:) 3/1, 2/2, 1/3, (fjerde diagonal:) 4/1, 3/2, 2/3, 1/4, … Her er det fortsatt mange gjentatte brøker, men det gjør ikke noe. Verre er det at de negative tallene mangler. Det kan løses enkelt: hver gang vi skriver en brøk, setter vi den negative varianten rett etter. Og så mangler bare null helt i begynnelsen. Og det var alt, nå har vi alle de rasjonale tallene i en følge.

Til sammen får vi følgen: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Størrelsen på de reelle tallene

Er de reelle tallene like mange som de naturlige tallene? Avgjørelsen blir enda vanskeligere enn for de rasjonale tallene. Vi fører et motsigelsesbevis. Anta at de reelle tallene er tellbare og at det finnes en bijektiv avbildning på de naturlige tallene. Anta altså at de kan ordnes. Og la oss si at denne avbildningen er den ordningen:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

I tabellen står de første sju reelle tallene i ordningen vår. Ordningen kan selvsagt være helt vilkårlig, tallene trenger ikke være sortert etter størrelse.

Ifølge antakelsen er alle de reelle tallene ordnet i denne uendelige tabellen. (Tabellen er altså uendelig, her ser du bare de sju første oppføringene.) Nå prøver vi å finne/konstruere et tall som er reelt, men ikke står i denne tabellen. Hvis vi finner et slikt tall, er det i motstrid med at alle de reelle tallene står i tabellen, og vi kan konkludere med at mengden av reelle tall ikke er tellbar.

Tallet som ikke står i tabellen, konstruerer vi slik:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Vi begynner med å skrive 0,… Slik ser det nye reelle tallet vårt ut i begynnelsen. På første desimal setter vi et siffer som ikke er første siffer i det første reelle tallet i ordningen vår (i tabellen er det uthevet med en ramme). Der står sifferet 3, så vi velger for eksempel 1, og får tallet 0,1…

Vi fortsetter. På andre plass kommer et siffer som ikke er andre siffer i det andre reelle tallet. Der står 9, så for eksempel 2. Vi får tallet 0,12… På tredje plass kommer et siffer som er forskjellig fra tredje siffer i det tredje reelle tallet. Der står 3, så vi velger for eksempel 7. Vi får 0, 127…

Og så videre og så videre. På n-te plass i det nye tallet står alltid et siffer som er forskjellig fra sifferet på n-te plass i det n-te tallet i ordningen vår.

Hva oppnår vi med det? Vi får et tall som skiller seg fra alle tallene i ordningen vår i minst ett siffer. La oss ta det siste foreløpige resultatet: 0,127… Dette tallet skiller seg sikkert fra det første tallet i ordningen vår i minst det første sifferet — for vi har konstruert det slik. Fra det andre tallet skiller det seg i minst det andre sifferet. Fra det tredje i det tredje sifferet. Generelt skiller dette nye tallet seg fra tallet som står på n-te plass i ordningen, i minst sifferet på n-te plass.

Det nykonstruerte tallet finner vi altså ikke i tabellen, som skulle symbolisere en bijeksjon mellom de naturlige tallene og de reelle tallene. De reelle tallene er dermed flere enn de naturlige tallene. De reelle tallene er ikke tellbare, de er overtellbare.