Cantors teorem

Cantors teorem, som ble bevist ved hjelp av Cantors diagonalargument, etter den tyske matematikeren Georg Cantor, sier at alle mengder (i elementær mengdelære) er mindre enn antall delmengder av den mengden. For endelige mengder er dette et enkelt kombinatorisk spørsmål (størrelsen på en mengdes potensmengde er $2^{n}$ for en mengde på størrelse n), men for uendelige mengder er det mindre trivielt. Ikke før i 1891, i Cantors artikkel «Über eine elementare Frage der Mannigfaltigkeitslehre», ble dette formelt satt opp og bevist.

En mengdes størrelse kalles dens kardinalitet, og tilsvarer antallet elementer i mengden. Mengden av naturlige tall er uendelig. Man kan vise at dens kardinalitet er identisk med kardianliteten til mengden av oddetall ved å vise at det finnes en en-til-en-korrespondanse $f$ mellom de to mengdene. I dette tilfellet er $f$ gitt som $f(x)=2x-1$. Gitt denne funksjonen vil ethvert naturlig tall tilsvare et unikt oddetall, og ethvert oddetall vil tilsvare et unikt naturlig tall. Dermed må de to mengdene ha samme kardinalitet. Uendelige mengder kan defineres som mengder som har slike propre delmengder med samme kardinalitet som seg selv. Mengder som ikke har slike delmengder er endelige.

Cantors diagonalargument

Cantor viste, som et spesialtilfelle av teoremet, at mengden av rasjonale tall (tall som kan uttrykkes som en brøk) har samme kardinalitet som mengden av naturlige tall. Vi kan forestille oss en (uendelig) liste av alle tenkelige brøker slik:

Liste av alle rasjonale tall

${\frac {1}{1}}$	${\frac {2}{1}}$	${\frac {3}{1}}$	$\cdots$
${\frac {1}{2}}$	${\frac {2}{2}}$	${\frac {3}{2}}$	$\cdots$
${\frac {1}{3}}$	${\frac {2}{3}}$	${\frac {3}{3}}$	$\cdots$
$\vdots$	$\vdots$	$\vdots$	$\ddots$

Man kan nå finne en en-til-en-korrespondanse mellom de naturlige og de rasjonelle tallene på følgende måte. Man "teller" de rasjonelle tallene fra øverste rad ved ta diagonalene nedover mot venstre. 1 tilsvarer ${\frac {1}{1}}$, 2 tilsvarer ${\frac {2}{1}}$, og 3 tilsvarer ${\frac {1}{2}}$. Så går vi til øverste rad og begynner på det neste tallet vi ikke har telt ennå, ${\frac {3}{1}}$, som tilsvarer 4, og teller videre diagonalt ned mot venstre fra det tallet. Igjen kan vi se at hvert rasjonelle tall tilsvarer et unikt naturlig tall og vise versa.

Cantor viste at det ikke finnes noen en-til-en-korrespondanse mellom de naturlige og de reelle tallene (de som kan uttrykkes med desimaler) og at mengden av reelle tall mellom 0 og 1 er større enn mengden av naturlige tall . Dette beviste han ved et reductio ad absurdum bevis: Han viste at, dersom man antar at det finnes en slik en-til-en-korrespondanse, ender man opp i en selv-motsigelse. Derfor kan det ikke finnes noen slik en-til-en-korrespondanse.

Før vi kan se hvordan han beviste dette må vi finne en måte å representere alle de reelle tallene mellom 0 og 1 på. De kan alle representeres som null, etterfulgt av en uendelig rekke desimaler. For eksempel har vi at $1=0,999\dots$ (tenk på at $1=3\cdot {\frac {1}{3}}=3\cdot 0,333\dots =0,999\dots$). $0=0,000\dots$ osv.

Nå kan vi se hvordan Cantor beviste at det finnes flere reelle tall mellom 0 og 1 enn det finnes naturlige tall. Tenk deg at det finnes en en-til -en korrespondanse $f$ mellom de naturlige tallene og de reelle tallene. Den vil kunne representeres som en uendelig liste, slik:

• $f(1)\quad =\quad 0,a_{1}^{1}a_{1}^{2}a_{1}^{3}\dots$

• $f(2)\quad =\quad 0,a_{2}^{1}a_{2}^{2}a_{2}^{3}\dots$

• $f(3)\quad =\quad 0,a_{3}^{1}a_{3}^{2}a_{3}^{3}\dots$

• $\vdots$

"$a_{1}^{1}$" er den første desimalen i det første reelle tallet, mens $a_{1}^{2}$ er den andre desimalen i dette tallet, mens $a_{2}^{1}$ er den første desimalen i det andre reelle tallet, osv. Vi kan nå vise at, uansett hvordan denne listen er konstruert, vil det finnes minst ett tall som ikke er på den. Dette tallet kan vi konstruere slik. Det er forskjellig fra det første tallet i den første desimalen, og forskjellig fra det andre tallet i den andre desimalen: For alle naturlige tall n er vårt tall forskjellig fra $f(n)$ i desimal $a_{n}^{n}$. Dermed er det altså forskjellig fra alle tallene på vår liste, så dette tallet kan ikke være på listen. Dette viser at vår antakelse var feil: $f$ er ikke en en-til-en-korrespondanse. Siden vi ikke har lagt noen begrensning på $f$, vi har for eksempel ikke sagt noe om hvilke reelle tall som tilsvarer hvilke naturlige tall og vise versa, betyr det at det ikke finnes noen en-til-en korrespondanse mellom de naturlige og de reelle tallene mellom 0 og 1: Når vi har tilordnet reelle tall til alle de naturlige tallene, finnes det fortsatt flere reelle tall som ikke har blitt tilordnet noe naturlig tall, uansett hvordan vi tilordner reelle tall til naturlige tall. Derfor finnes det altså flere reelle tall mellom 0 og 1 enn det finnes naturlige tall, så mengden av reelle tall er en større uendelighet enn mengden av naturlige tall. Dette reductio ad absurdum argumentet kalles ofte for Cantors diagonalargument.

Cantor viste også at det finnes uendeligheter som er enda større enn mengden av reelle tall, og at det finnes en uendelig rekke av «størrelser» på uendeligheter. Cantor viste at mengden av reelle tall har samme kardinalitet som potensmengden til mengden av naturlige tall. Det er vanlig å bruke tegnet $\aleph _{0}$ (alef null) for kardinaliteten til mengden av naturlige tall. Mengden av reelle tall har dermed kardinaliteten $2^{\aleph _{0}}$. Mengder som er endelige, eller har kardinalitet $\aleph _{0}$ kalles tellbare mengder. Mengder med kardinalitet $2^{\aleph _{0}}$ eller høyere er ikke tellbare.

Eksterne lenker

• (en) Eric W. Weisstein, Cantor's Theorem i MathWorld.
• (en) Eric W. Weisstein, Cantor Diagonal Method i MathWorld.