Tag Archives: Georg Cantor

1.6. Cantorov dijagonalni dokaz: jesu li neke beskonačnosti veće od drugih? (neprebrojivost)

Ako parnih brojeva ili racionalnih brojeva ima koliko i prirodnih, odnosno {\displaystyle \aleph _{0}}, pa su stoga prebrojivi (mada ih je beskonačno), ima li toliko i realnih brojeva? I jednih i drugih ima beskonačno, dakle ima ih jednako? Zapravo ne. Cantor je pokazao da skup realnih brojeva nije prebrojiv, odnosno da realnih brojeva nema koliko i prirodnih.

Njegov tzv. „dijagonalni“ dokaz je zgodan. Zasnovan je na postupku reductio ad absurdum: najprije nešto pretpostavimo, potom u tome pronalazimo proturječje, i iz toga slijedi da je početna pretpostavka pogrešna.

Početna pretpostavka (koju želimo pobiti) jest da je skup realnih brojeva prebrojiv, odnosno, da realnih brojeva ima isto koliko i racionalnih (i prirodnih). Problem je kako poredati realne brojeve tako da ih možemo brojati. I racionalni brojevi i realni brojevi nemaju jasne prethodnike i sljedbenike; ipak za racionalne nije teško smisliti shemu, ali za realne je to pravi problem. No, pretpostavimo da smo uspjeli nekako poredati sve realne i ta ih stoga možemo brojati. To je, dakle, početna pretpostavka (koju želimo pobiti): poredali smo sve realne brojeve u neku shemu. To ne ovisi o shemi po kojoj smo poredali realne brojeve – naprosto zamislimo da su poredani, kako god da se to dogodilo.

Drugi korak dokaza je pokazati da je ta pretpostavka da su svi realni brojevi poredani pogrešna. Za to je potrebno konstruirati realni broj koji sigurno nije na popisu. To možemo napraviti ovako: pogledamo prvu znamenku iza decimalnog zareza prvoga broja. Naš broj će imati različitu prvu znamenku od prve znamenke prvog broja (da bi se razlikovao od njega). Dakle, uzmemo neku različitu vrijednost prve znamenke (na slici prva znamenka iza decimalnog zareza prvoga broja jest 2, uzimamo neku drugu vrijednost npr. 7).

Reductio ad absurdum: uzmemo pretpostavljeni popis svih realnih brojeva i potom konstruiramo realni broj koji sigurno nije na popisu (za ovaj popis to je npr. 0.746894310875…).

Potom idemo na drugu znamenku i ponavljamo taj postupak: moramo uzeti neku različitu od druge znamenke drugoga broja da bismo bili sigurni da se naš broj razlikuje i od drugoga broja na listi (na slici je to različito od 9, npr. 4). I taj postupak nastavljamo u beskonačno – svaki korak osigurava da je naš broj različit od sljedećeg realnog broja. Na taj način konstruiramo realni broj koji sigurno nije na listi, odnosno, kojemu nije pridružen nijedan prirodni broj.

Time smo pokazali da je početna pretpostavka pogrešna, odnosno, da nema načina da poredamo sve realne brojeve tako da bi ih mogli prebrojati. Uvijek možemo konsturirati neki koji nije na popisu.

(Vidite li zašto isti ovakav dokaz ne vrijedi za racionalne brojeve?)

Dakle, skup realnih brojeva je neprebrojiv. Znači li to da realnih brojeva ima više nego racionalnih? Jesu li neke beskonačnosti veće od drugih?

1.5. ima li više parnih ili prirodnih brojeva? (prebrojivost)

Ima li više parnih prirodnih brojeva ili prirodnih brojeva (dakle parnih i neparnih ukupno)? Naravno, ako brojimo do bilo koje konačne vrijednosti N, onda će prirodnih brojeva biti dvostruko više nego parnih. Pa se najprije može činiti da je time lako odgovoreno na naše pitanje. Ali, ako krenemo brojati parne brojeve, onda imamo nešto ovako

2   4   6   8   10   12  14  16 …

1   2   3   4     5     6    7    8 …

Dakle, svaki prirodni broj broji jedan parni te nema nijednog prirodnog broja kojemu ne bi odgovarao neki parni, po jednostavnoj formuli PARNI=2∙PRIRODNI. Koliko god ima članova s lijeve strane ove jednakosti, toliko ima i s desne. Odnosno, parnih brojeva ima jednako koliko i prirodnih.

Ali kako je to moguće? Prirodni brojevi se sastoje od parnih i ne-parnih. Kako je moguće da parnih i neparnih brojeva zajedno ima isto koliko i samo parnih? Ta stvar je zbunjivala i neke od napametnijih ljudi prošlog tisućljeća, poput Leibniza i Galilea.

Galileo je pisao o vrlo sličnom problemu s nizom prirodnih brojeva koji su kvadrati prirodnih brojeva, dakle 1, 4, 9, 16, 25, 36, 49, 64 … I ovdje se ponavlja isti obrazac – kad brojimo te brojeve nijedan prirodni broj neće biti preskočen, odnosno svakom prirodnom broju odgovara jedan kvadrat. Pa bi slijedilo da kvadratnih brojeva ima jednako koliko i prirodnih brojeva, mada su mnogi prirodni brojevi nisu kvadratni – to se naziva Galileov paradoks. Galileo zaključuje ovako:

Koliko vidim, možemo samo zaključiti da je ukupnost svih [prirodnih] brojeva beskonačna, da je broj kvadrata beskonačan, i da je broj njihovih korijena beskonačan; niti je broj kvadrata manji od ukupnosti svih brojeva, niti je ono prvo veće od drugoga; i konačno, oznake ‘veće’, ‘manje’ i ‘jednako’ nisu primjenjive na beskonačne nego samo na konačne veličine.

Leibniz je također smatrao da ih ne može biti jednako. To bi naime značilo da pravi podskup nekog skupa ima jednako članova koliko i sam taj skup, a to bi kršilo Euklidov aksiom: „Cjelina je veća od dijela.“

No, krajem 19. stoljeća Cantor je sve skupove koje možemo brojati na prethodno opisani način nazvao prebrojivim, i ustvrdio da svaki od njih ima točno jednako članova. Taj broj članova, koji je naravno beskonačan, označio je hebrejskim slovom „alef“ uz indeks nula, dakle „alef nula“, što se označava sa {\displaystyle \aleph _{0}}.

Zanimljivo je i da racionalnih brojeva ima točno toliko. To nije očito kao u prethodnim primjerima, jer u njima svi članovi skupova nakon prvoga imaju točno određene prethodnike i sljedbenike, pa je jasno kako ih brojati. Ali nije jasno kako brojati racionalne brojeve – neki racionalni broj, npr. 2/7, nema prethodnika ni sljedbenika. Ipak, moguće ih je poredati tako da svi budu obuhvaćeni pri brojanju, i tako pokazati da je skup racionalnih brojeva prebrojiv (mada beskonačan), odnosno da ima alef nula racionalnih brojeva.

rationals-countable

(Naravno, pri brojanju preskačemo one racionalne brojeve koje smo već brojali, npr. 2/4 budući da smo već brojali 1/2. Važno je samo da postoji poredak koji obuhvaća sve racionalne brojeve.)

A što vi mislite? Slažete li se s Galileom ili s Cantorom? Mislite li da su sve beskonačnosti jednako velike ili su neke veće od drugih? 🙂