Tellbarhet og kardinaltal

Kardinaltalet (eller kardinaliteten) til ei mengde er rett og slett lik antal element i mengden. For endelige mengder er det enkelt: Mengden A = {2, 4, 6} inneheld 3 element, og har derfor kardinalitet 3. Men kva med uendelige mengder? Ein skulle tru at uendelig er undelig, og ferdig med det. Men når ei ser nærmare på dette viser det seg at det er forskjellige former for uendelighet. Dette har med begrepet tellbarhet å gjera.

Kan vi telja alle brøkar?

Einten ei mengde er endelig eller ikkje, så kallar vi den for ei tellbar mengde hvis det er mulig å telja, eller nummerera alle elementa ved hjelp av dei naturlige tala. Det spelar ingen rolle om det tar uendelig tid. Poenget er om det fins ein regel slik at vi kan tilordna kvart element eit nummer. Det seier seg sjøl at mengden av dei naturlige tala N (1, 2, 3, ... ) er tellbar, for det er jo akkurat disse tala som vi tel med! Men mengden av dei heile tala Z, (som inkluderer negative tal) er også ei tellbar mengde. (Les om talmengder) Vi kan enkelt visa det: Det er bare å starta i 0, og så telja seg utover vekselvis på pluss- og minus-sida slik: 0, 1, -1, 2, -2, 3, -3, 4 osv. Alle slike tellbare mengder blir per definisjon tildelt kardinatalet  , (uttalt alef 0*) og den tyske matematikaren Georg Cantor viste at alle ubegrensa delmengder av N har dette kardinaltalet. Det betyr at både partal, oddetal, primtal, fibonaccital osv. er tellbare mengder.

Intuitivt skulle ein kanskje tru at mengden av alle rasjonale tal Q, er av ein annan type. Q er mengden av alle tal som kan skrivast som ein brøk med heiltal både i teljar og nevnar. Og vi har følelsen av at dei "mange fleire" fordi det jo fins uendelig mange brøkar mellom 0 og 1. Men det viser seg at faktisk også Q er ei tellbar mengde. For å visa dette, kan vi tenkja oss ein uendelig tabell der vi puttar inn dei rasjonale tal på denne måten:

Som vi ser representerer radene teljaren og kolonnene nevnaren. I første rad finn vi alle brøkar som har 1 som teljar og 1, 2, 3 osv. i nevnaren. Brøken 361/217 vil derfor befinna seg i rad 361 og kolonne 217. Så alle rasjonale tal kan dermed plasserast i tabellen. Faktisk fins alle tall (uendelig) mange plasser, for 2/2 er jo det same som 1/1 osv. Men det er ikkje noke problem, for no kan vi definera ein regel for å telja (nummerera) alle distinkte tal: Vi starter oppe i det venstre hjørne med 1/1. Så går vi ned til 2/1 og så går vi diagonalt opp til høgre til 1/2. Deretter til høgre og så diagonalt nedover til venstre. Der hoppar vi over 2/2 fordi det er allerede talt. Slik fortset vi i pilretningane og tel alle brøkane som ikkje allerede er talt opp. Sjøl om vi må kan telja i all evighet uten å bli ferdige, så fins det ein metode, og det er det vi treng: Vi ser altså at Q er ei tellbar mengde, og den har også kardinaltalet .

Kva så med R?

Men når vi går over til mengden av alle reelle tal R, så funkar ikkje dette. Cantor beviste at det ikkje er mulig å telja dei reelle tala. Han gjorde det ved et såkalt Reductio ad Absurdum-argument (bevis ved sjølmotsigelse). La oss sjå på det:

Beviset, på denne formen, bruker det faktum at alle tal kan skrivast som binærtal. Talet 7 kan feks skrivast som 111, 8 som 1000 osv. Så la oss anta at vi har funne ein måte å telja alle reelle tal. Då kan vi kalla dei s og nummerera dei frå 1 og oppover. Vi har altså ei uendelig liste med tal som vi kaller s₁, s₂, s₃ osv. Det spelar ingen rolle korleis vi har laga denne lista. Poenget er at vi antar at det fins ein måte å gjera det på. No vi skriv dei opp i ein tabell på denne måten:

Problemet no er at vi ut frå denne uendelige tabellen kan danna eit nytt tal s som ikkje fins i tabellen: Metoden er enkel, men genial. Først plukkar vi første siffer i s₁, andre siffer i s₂, tredje i s³, osv. (disse er markert med rødt) og deretter bytter vi om. Hvis det var ein 0, så får vi ein 1 på den plassen, og omvendt. I vårt eksempel får vi dei raude siffera 01000101100 ... Når vi så bytter om disse får vi eit nytt tal som er s = 10111010011... Dette talet fins ikkje i tabellen vår fordi kvart einaste tal i tabellen er forskjellig på minst ein plass. Men dette strir mot antagelsen vår, nemlig at tabellen inneheld alle reelle tal. Dermed må vi konkludera at det ikkje er mulig å laga ei tellbar liste med alle reelle tal. Sagt på ein annan måte: mengden R har større kardinaltal* enn mengden N.

På grunn av måten dette beviset er bygd opp på kallast det Cantors diagonalargument. Denne teknikken som Cantor her brukte er ein kraftig metode som seinare har blitt brukt på mange forskjellige bevis, inkludert det første av Gödels ufullstendighetsteorem og Alan Turing's sitt svar på det såkalte Entscheidungsproblem. Teknikken gir også opphave til kontradiksjonar som Russells paradoks og Richards paradox.

LENKER