ï»ż

 

Cantors teorem, som ble bevist ved hjelp av Cantors diagonalargument, etter den tyske matematikeren Georg Cantor, sier at uansett hvilken mengde vi betrakter, finnes det en mengde som er stĂžrre. Dette er trivielt for endelige mengder, men ikke for uendelige mengder.


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.

Cantor viste ogsÄ 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^1_2 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.