U elementarnog teoriji skupova, Kantorova teorema je fundamentalni rezultat koji tvrdi da je za bilo koji skup , skup svih podskupova od (partitivni skup od , označen sa ) ima strogo veću kardinalnost od samog . Za konačne skupove, može se videti da je Kantorova teorema tačna putem jednostavnog nabrajanja broja podskupova. Računajući prazan skup kao podskup, skup sa članova ima ukupno podskupova, tako da ako je onda je , i teorema važi jer je istinito za sve nenegativne brojeve.

Kardinalnost skupa {x, y, z} je tri, dok postoji osam elemenata u njegovom partitivnom skupu (3 < 23 = 8), ovde uređenih u odnosu na inkluziju.

Mnogo je značajnije Kantorovo otkriće argumenta koji je primenljiv na bilo koji skup, čime je pokazano da teorema važi za beskonačne skupove, brojive ili nebrojive, kao i za konačne. Kao posebno važna posledica, partitivni skup skupa prirodnih brojeva, prebrojivo beskonačnog skupa s kardinalnošću ℵ0 = card(ℕ), neprebrojivo je beskonačan i ima istu veličinu kao i skup realnih brojeva, kardinalnost veća od one za skup prirodnih brojeva koja se često naziva kardinalnost kontinuuma: 𝔠 = card(ℝ) = card(𝒫(ℕ)). Odnos između ovih kardinalnih brojeva često se simbolično izražava jednakošću i nejednakošću .

Ova teorema je nazvana po nemačkom matematičaru Georgu Kantoru, koji ju je prvi objavio i dokazao krajem 19. veka. Kantorova teorema je imala neposredne i važne posledice za filozofiju matematike. Na primer, iterativnim uzimanjem partitivnog skupa beskonačnog skupa i primenom Kantorove teoreme, dobija se beskrajna hijerarhija beskonačnih kardinala, svaki strogo veći od onog pre njega. Shodno tome, teorema implicira da ne postoji najveći kardinalni broj (kolokvijalno, „nema najveće beskonačnosti”).

Dokaz

uredi

Kantorov argument je elegantan i izuzetno jednostavan. Kompletan dokaz predstavljen je u nastavku, sa detaljnim objašnjenjima koja slede.

Teorema (Kantor). Neka je   mapa iz skupa   na njegov partitivni skup  . Onda   nije surjektivno. Konsekventno,   važi za svaki skup  .

Dokaz: Razmotrimo skup  . Pretpostavimo suprotno da   je surjektivno. Onda postoji   takvo da je  . Međutim po konstrukciji,  . Ovo je kontradikcija. Stoga,   ne može da bude surjektivno. S druge strane,   definisano sa   jeste injektivna mapa. Konsekventno, mora biti  . 

Po definiciji kardinalnosti važi da je card(X) < card(Y) za svaka dva seta X i Y ako i samo ako postoji injektivna funkcija ali ne i bijektivna funkcija od X do Y. Dovoljno je da se pokaže da nema surjekcije od X do Y. Ovo je suština Kantorove teoreme: ne postoji surjektivna funkcija od bilo kog skupa A do njegovog partitivnog skupa. Da bi se to uspostavilo, dovoljno je da se pokaže da nijedna funkcija f koja preslikava elemente iz A u podskupove od A ne može da dosegne svaki mogući podskup, tj. samo se mora dokazati postojanje podskupa A koji nije jednak f(x) za bilo koje xA. (Treba imati u vidu da je svako f(x) podskup A.) Takav podskup daje sledeća konstrukcija, koja se ponekad naziva i Kantorov dijagonalni skup f:[1][2]

 

To znači, po definiciji, da za svako x u A, x ∈ B ako i samo ako x ∉ f(x). Za svako x skupovi B i f(x) ne mogu da budu isti jer je B konstruisano iz elemenata A čije preslikavanje (pod f) nije obuhvatalo njih same. Specifičnije ako se razmotri svako x ∈ A, onda bilo x ∈ f(x) ili x ∉ f(x). U prvom slučaju, f(x) ne može da bude jednako B, jer x ∈ f(x) po pretpostavci, a x ∉ B po konstrukciji B. U potonjem slučaju, f(x) ne može biti jednako B, jer x ∉ f(x) po pretpostavci i x ∈ B konstrukcijom B.

Ekvivalentno, i donekle formalnije, dokazuje se da postojanje ξ ∈ A takvo da f(ξ) = B podrazumeva sledeću protivrečnost:

 

Stoga, prema reductio ad absurdum, pretpostavka mora biti pogrešna.[3] Proizilazi da ne postoji ξ ∈ A takvo da je f(ξ) = B; drugim rečima, B nije u preslikavanju f i f se ne mapira u svaki element partitivnog skupa od A, i.e., f nije surjektivno.

Konačno, da se kompletira dokaz neophodno je da se pokaže injektivna funkcija iz A u njegov partitivni skup. Nalaženje takve funkcije je trivijalno: samo se mapira x u singltonski skup {x}. Argument je sada potpun i utvrđena je stroga nejednakost za bilo koji skup A da je card(A) < card(𝒫(A)).

Drugačiji način da se razmišlja o dokazu je da je B, prazan ili neprazan, uvek u partitivnom skupu od A. Da bi f bila uključena, neki element A se mora preslikati u B. Ali to dovodi do kontradikcije: ni jedan element B se ne može preslikati na B, jer bi to bilo u suprotnosti sa kriterijumom članstva u B, te stoga element koji se preslikava u B ne može da bude element B, što znači da zadovoljava kriterijum za članstvo u B, još jedna kontradikcija. Dakle, pretpostavka da se element A preslikava u B mora biti lažna; i f ne može biti uključeno.

Zbog dvostruke pojave x u izrazu „xf(x)”, ovo je dijagonalni argument. Za brojiv (ili konačan) skup, argument gore navedenog dokaza može se ilustrovati konstrukcijom tabele u kojoj je svaki red označen jedinstvenim x iz A = {x1, x2, ...}, u tom redosledu. Pretpostavlja se da A prihvata linearni redosled, tako da se takva tabela može konstruisati. Svaka kolona tabele je označena jedinstvenim y iz partitivnog skupa A; kolone su poređane argumentom za f, tj. oznake kolona su f(x1), f(x2), ..., u tom redosledu. Presek svakog reda x i kolone y beleži istinski/lažni bit da li xy. S obzirom na redoslijed izabran za oznake redova i kolona, glavna dijagonala D ove tabele beleži da li je xf(x) za svako x in A. Skup B izgrađen u prethodnim paragrafima se podudara sa oznakama redova za podskup unosa na toj glavnoj dijagonali D, gde tabela beleži da je xf(x) lažno.[3] Svaka kolona beleži vrednosti indikatorske funkcije skupa koja odgovara koloni. Indikatorska funkcija za B podudara se sa logički negiranim (istinito ↔ lažno) zapisima glavne dijagonale. Stoga se indikatorska funkcija za B ne slaže ni sa jednom kolonom u bar jednom unosu. Prema tome, nijedna kolona ne predstavlja B.

Za konačni skup, dokaz isto tako može da bude ilustrovan koristeći prozaičniju prezentaciju poznatu kao paradoks berberina.[4]

Uprkos jednostavnosti gornjeg dokaza, prilično je teško da se proizvede automatizovanim dokazivačem teorema. Glavna poteškoća leži u automatizovanom otkrivanju Kantorovog dijagonalnog skupa. Lorens Polson je napomenuo 1992. godine da Otter to nije mogao učiniti, dok je Isabelle mogla, iako s određenim brojem uputstava u smislu taktike, što se možda može smatrati varanjem.[2]

Reference

uredi
  1. ^ Abhijit Dasgupta (2013). Set Theory: With an Introduction to Real Point Sets. Springer Science & Business Media. стр. 362—363. ISBN 978-1-4614-8854-5. 
  2. ^ а б Lawrence Paulson (1992). Set Theory as a Computational Logic (PDF). University of Cambridge Computer Laboratory. стр. 14. 
  3. ^ а б Graham Priest (2002). Beyond the Limits of Thought. Oxford University Press. стр. 118—119. ISBN 978-0-19-925405-7. 
  4. ^ Albert Geoffrey Howson (1990). The Popularization of Mathematics. Cambridge University Press. стр. 197. ISBN 978-0-521-40319-1. 

Literatura

uredi

Spoljašnje veze

uredi