Tellbare tall

Mengden av reelle tall er ikke tellbar

Mengden av hele tall og mengden av reelle tall er begge uendelige, men likevel har de forskjellig størrelse! Mengden av hele tall er minst. Vi sier at denne mengden er tellbar, som betyr at vi kan finne en regel som nummererer alle tallene i mengden, eller setter dem opp i rekkefølge. Vi kan f.eks. skrive alle hele tall på følgende måte:

0, 1, -1, 2, -2, 3, -3, ...

og vi kan på en systematisk måte angi hvilket nummer ethvert helt tall har i denne rekkefølgen. Uendelige mengder som har denne nummereringsegenskapen kalles tellbare mengder. Mengden av rasjonale tall er tellbar, f.eks. ved følgende rekkefølge (dette er de positive, de negative kan vi inkludere på samme måte som over):

0/1, 0/2, 1/1, 0/3, 1/2, 2/1, 0/4, 1/3, 2/2, 3/1, ...

Med denne nummereringen (hvordan er systemet?) blir noen tall gjentatt, men det spiller ingen rolle for begrepet tellbarhet. Ser vi derimot på mengden av reelle tall så får vi ikke dette til. Matematikeren Georg Cantor lagde for mange år siden et bevis for dette. Her er hans bevis:

Teorem
Mengden av reelle tall er ikke tellbar.

Bevis
Anta at mengden av reelle tall (alle desimaltall) er tellbar. Da kan vi nummerere dem

a₁ = 0 ,a₁₁ a₁₂ a₁₃ a₁₄ …
a₂ = 0 ,a₂₁ a₂₂ a₂₃ a₂₄ …
a₃ = 0 ,a₃₁ a₁₂ a₃₃ a₃₄ … ..

Alle desimalene a₁₁ a₁₂ a₁₃ a₃₂ a₆₇ osv. i denne oppstillingen er ett av tallene 0,1,2,3,..,9.
Det første tallet a₁ = 0 ,a₁₁ a₁₂ a₁₃ a₁₄ … kan for eksempel være 0,380219976….
Det spiller ikke så stor rolle, det viktigste er at vi tar det for gitt at vi kan lage en slik liste. Vårt håp er nå at alle reelle tall er med i denne uendelige oppramsingen av desimaltall.
Men obs-obs, se på følgende tall:

b = 0 ,b₁ b₂ b₃ b₄ …

som er laget på følgende måte, b₁ velges forskjellig fra a₁₁ (dette går greit siden vi har 10 siffer å velge mellom og kun ett av dem er uaktuelt). Tilsvarende gjør vi for b₂ (velges forskjellig fra a₂₂) b₃, og så videre. Dermed har vi kokt opp et desimaltall (reelt tall) b som ikke er lik noen av tallene a₁, a₂, og så videre. Tallet er jo forskjellig fra hver av disse på minst én plass. Men vi antok jo at dette skulle være alle desimaltall. Så her er det noe krøll. Vi har fått en motsigelse.

Altså må antakelsen være gal, vi kan ikke skrive opp alle reelle tall i en slik rekkefølge, og mengden er derfor ikke tellbar. Q.E.D. (som er forkortelse for Quod Erat Demonstrandum, som er latin og betyr "det er bevist")