Teorija skupova

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretragu

Teorija skupova je matematička teorija dobro definisanih kolekcija objekata koje zovemo skupovima. Ovi objekti se zovu elementi skupa. Čista teorija skupova je ona teorija u kojoj su elementi skupa opet skupovi. Srž teorije skupova je proučavanje beskonačnih skupova. U teoriji skupova skupovi su dati aksiomatski, tj njihovo postojanje i osnovna svojstva su data odgovarajućim formalnim aksiomama. Formalni jezik čiste teorije skupova dopuštaju da se formalizuju svi matematički pojmovi. Na taj način teorija skupova postaje standardna osnova matematike pošto svaki matematički objekt može da se vidi kao skup i svaka teorema matematike može logički biti izvedena predikatskim računom iz aksioma teorije skupova.

Oba aspekta teorije skupova, kao matematičke nauke o beskonačnom i kao osnove matematike, imaju svoje filozofsko značenje. Da bi se mogao u potpunosti razumeti ovaj članak, potrebno je prvo ovladati Osnovama teorije skupova

Ishodišta

[uredi | uredi kod]

Ocem teorije skupova, kao posebne matematičke discipline, se smatra Georg Kantor (Georg Cantor). Njegovo fundamentalno otkriće je bilo da je skup realnih brojeva neprebrojiv tj. i pored toga da su skupovi prirodnih i realnih brojeva beskonačni, više je realnih brojeva nego prirodnih što je dovelo do zaključka da postoje različite vrednosti beskonačnosti.

Prema Kantoru dva skupa i su iste veličine, tj. kardinalnosti, ako se elementi skupa mogu 1-u-1 preslikati u elemente skupa . Na taj način skupovi prirodnih i realnih brojeva imaju različite kardinalnosti. Time je Kantor definisao njegovu hipotezu kontinuuma koja tvrdi da svaki beskonačni skup realnih brojeva je ili prebrojiv ili nije tj. ima kardinalnost skupa , ili kardinalnost skupa . Do danas, Kantorova hipoteza kontinuuma niti je oborena niti dokazana. Pokušaji da se ova hipoteza dokaže doveli su do saznanja da se sama hipoteza ne može niti dokazati niti oboriti na osnovi postojeće aksiomatike moderne teorije skupova.

Naivno shvatanje da skup mora da ima uvek neko svojstvo ili karakteristiku dovelo je do otkrića tzv. Raselovog (Bertrand Russell) paradoksa (koji je pre Rasela bio poznat Cermelou (Ernst Zermelo)) koji glasi

Neka je dato svojstvo skupova po kome skupovi nisu elementi samih sebe. Ako ovo svojstvo definiše skup, nazovimo ga skup , tada je element samoga sebe ako nije element samoga sebe.

Na taj način neke kolekcije kao što su kolekcija svih skupova, kolekcija svih ordinalnih brojeva, kolekcija svih kardinalnih brojeva, nisu skupovi. Ovakve kolekcije se zovu prave klase.

Da bi se izbegli paradoksi i dobila čvrsta osnova teorije, teorija skupova je aksiomatizovana. Prvu aksiomatizaciju teorije je dao Cermelo koji je izbegao Raselov paradoks aksiomom razdvajanja koja kvantificira svojstva skupa preko tvrdnje drugog reda. Skolem (Thoralf Skolem) i Frenkel (Abraham Fraenkel) su aksiomu razdvajanja formalizovali formulama prvog reda a zatim uveli aksiomu zamene koja je bila nužna da bi se podupro razvoj teorije transfinitnih ordinala i kardinala. Dalji rad u cilju poboljšanja Cermelove teorije je bio na dokazivanju osnovnih činjenica teorije skupova kao što je tvrdnja da se svaki skup sadrži u nekom tranzitivnom skupu, tj. skupu koji sadrži sve elemente sopstvenih elemenata. Fon Nojman (John von Neumann) je dodao aksiomu osnove čime je stvoren standardni aksiomatički sistem teorije skupova koji se zove Cermelo-Frenkel aksiome sa aksiomom izbora.

Aksiome teorije skupova

[uredi | uredi kod]

U ovoj sekciji izložićemo, u kratkim crtama, Cermelo-Frenkel aksiome sa aksiomom izbora (CFI). Cela aksiomatika se može izložena u logici prvog reda sa samo jednom binarnom relacijom pripadnosti . Ovde odstupamo od tog pravila kako bi tekst članka bio čitljiviji onom ko se prvi put susreće sa ovom teorijom.

  • Aksioma proširenja: Dva skupa i su jednaki ako imaju iste elemente.
  • Aksioma praznog skupa: Skup koji nema elemente zove se prazan skup i označava sa .
  • Aksioma para: Ako su dati skupovi i , tada postoji skup koji sadrži samo i kao svoje elemente. Postoji takođe skup čiji je jedan jedini element skup .
  • Aksioma partitivnog skupa: Za svaki skup postoji skup koji se zove partitivni skup skupa čiji su elementi svi podskupovi skupa .
  • Aksioma unije: Za svaki skup postoji skup koji se zove unija skupa a čiji su elementi elementi skupa .
  • Aksioma beskonačnosti: Postoji beskonačan skup, tj. postoji skup koji sadrži i takav da ako je tada je .
  • Aksioma razdvajanja: Za svaki skup i svako dato svojstvo skupa postoji skup koji sadrži elemente skupa koji imaju pomenuto svojstvo skupa. Svojstvo skupa je definisano formulom u logici prvog reda. Na taj je način aksiom razdvajanja u suštini aksiom šema tj. beskonačna lista aksioma, gde je svaka aksioma data formulom .
  • Aksioma zamene: Za svaku funkciju koja se može definisati na skupu kao svom domenu postoji skup čiji su elementi sve vrednosti ove funkcije. Zamena je takođe aksioma šema jer su funkcije definisane formulama.
  • Aksioma osnove: Svaki neprazni skup sadrži neki -minimalni element tj.element koji ne sadrži ni jedan drugi element skupa .
  • Aksioma izbora: Za svaki skup uzajamno disjunktnih nepraznih skupova postoji skup koji sadrži tačno jedan element iz svakog skupa koji pripada skupu .

Problemi i sumnje u valjanost ove aksiome potiču od činjenice da aksioma tvrdi da postoje skupovi koji ne mogu biti eksplicitno definisani. Ove sumnje su uklonjene Gedelovim (Kurt Gödel) dokazom da je aksioma izbora saglasna sa ostalim Cermelo-Frenkel aksiomama. Aksioma izbora je ekvivalentna principu dobre uređenosti koji tvrdi da svaki skup može da se dobro uredi tj. svaki skup može da se linearno uredi tako da svaki njegov neprazan podskup ima neki minimalni element.

U teoriji skupova se pored simbola koriste pomoćni simboli podskupa , unije , preseka , uređenog para i Dekartovog proizvoda koji nisu nužni. Detaljnije o ovim pomoćnim simbolima vidi u Osnove teorije skupova,

Teorija transfinitnih ordinala i kardinala

[uredi | uredi kod]

Cermelo-Frenkelove aksiome (CF) zajedno sa aksiomom izbora mogu se koristiti pri razvoju Kantorove teorije transfinitnih (tj. beskonačnih) tipova uređenja: ordinala i kardinala.

Prvi ordinalni broj je . Ako je dat ordinal , onda je njegov neposredni sledbenik definisan kao skup . Ako je dat neprazan skup ordinala takav da je za svako njegov sledbenik takođe u , može se dobiti granični ordinal . Lako se pokazuje da je svaki ordinal strogo dobro uređen preko relacije , tj. linearno je uređen preko i ne postoji beskonačno -opadajući niz. Svaki dobro uređeni skup je izomorfan nekom jedinstvenom ordinalu koji se zove tip uređenja.

Operacije sabiranja i množenja prirodnih brojeva se mogu proširiti na ordinale. Ordinal je tip uređenja dobrog uređenja koje se dobija spajanjem dobro uređenog skupa tipa uređenja i dobro uređenog skupa tipa uređenja . Niz ordinala dobro uređenih po , je

Ordinali zadovoljavaju princip transfinitne indukcije: pretpostavimo da je klasa ordinala takva da kad god sadrži sve ordinale koji su manji od nekog ordinala , tada je takođe u . Na taj način klasa sadrži sve ordinale. Koristeći transfinitnu indukciju može se u CFI (za šta je potrebna i aksioma zamene) dokazati princip transfinitne rekurzije koji kaže da ako je data klasa-funkcija koja se može definisati , onda se može definisati klasa-funkcija takva da je vrednost funkcije primenjene na funkciju koja je ograničena na . Transfinitna rekurzija se koristi, na primer, da se definišu aritmetičke operacije sabiranja, množenja i eksponenta na ordinalima.

Bilo koji beskonačni skup je prebrojiv ako se može 1-u-1 preslikati u , tj. koji je bijetivan sa . Svi ordinali koje smo spomenuli gore su ili konačni ili prebrojivi. Skup svih konačnih i prebrojivih ordinala je takođe ordinal, označen sa , koji nije prebrojiv. Na isti način skup svih ordinala koji su bijektivni sa nekim ordinalom koji je manji od ordinala je takođe ordinal, označen sa , i koji nije bijektivan sa , itd.

Kardinal se definiše kao ordinal koji nije bijektivan sa nekim manjim ordinalom. Time je svaki konačni ordinal i kardinal. Beskonačni kardinali se zapisuju slovom alef () i indeksiraju ordinalima.

Za svaki kardinal postoji veći kardinal i granica rastućeg niza kardinala je opet kardinal. Klasa svih kardinala nije skup nego prava klasa.

Beskonačni kardinal je regularan ako nije unija manje od manjih kardinala. je regularni kardinal kao i svi njegovi beskonačni sledbenici kardinali kao što je . Ne-regularni beskonačni kardinal se zove singularni kardinal. Prvi singularni kardinal je i unija je prebrojivo mnogo manjih kardinala, tj. .

Kofinalnost kardinala , u oznaci , je najmanji kardinal takav da je unija -mnogo manjih ordinala, tj. .

Po aksiomi izbora svaki skup se može dobro urediti, tj. bijektvan je sa nekim jedinstvenim kardinalom koji se zove kardinalnost skupa . Suma dvaju kardinala i se definiše kao kardinalnost skupa koji je unija bilo koja dva disjunktna skupa gde je kardinalnost jednoga a drugoga . Proizvod se definiše kao kardinalnost Dekartovog proizvoda . Operacije sume i proizvoda dvaju beskonačnih kardinala i se definišu kao .

Eksponent kardinala je izuzetno kompleksan problem pa ćemo ga izostaviti.

Univerzum svih skupova

[uredi | uredi kod]

CF aksiome, sa izuzetkom aksiome proširljivosti, služe pri gradnji kumulativne hijerarhije skupova. Koristeći transfinitnu rekurziju definišemo klasu-funkciju koja koja dodeljuje svakom ordinalu skup na sledeći način:

kad god je granični ordinal.

Aksioma partitivnog skupa se koristi da se od dobije . Aksiome zamene i unije se koriste da se dobije za granični ordinal. Aksioma beskonačnosti se koristi da se dokaže postojanje a time i transfinitni niz ordinala. Aksioma osnove, uz pretpostavku važenja ostalih aksioma, je ekvivalentna tvrdnji da svaki skup pripada nekom za neki ordinal . Na taj način CF dokazuje da teoretski univerzalni skup, označen sa , je unija svih , gde je neki ordinal.

Prava klasa , zajedno sa relacijom , zadovoljava sve CFI aksiome a je time i jedan model CFI. CFI nije kompletan opis što ćemo upravo pokazati.

Dokazano i značajno svojstvo koje se može dokazati pomoću CFI je takozvani princip refleksije. Za svaku formulu CFI dokazuje da postoji neki ordinal takav da ga reflektuje, tj za svaki

važi u ako i samo ako ) važi u

Otud se ne može opisati nekom rečenicom, pošto bilo koja rečenica koja važi u mora da takođe važi u nekom inicijalnom segmentu od . Otud dolazimo do zaključka da CFI nije finalno aksiomatizovana jer bi u protivnom CFI dokazala da, za neograničeno mnogo ordinala , je neki model CFI, što protivreči drugoj Gedelovoj teoremi.

Princip refleksije je suština CF teorije skupova pošto je ovaj princip ekvivalentan aksiomama beskonačnosti i zamene uz važenje ostalih CF aksioma.

Teorija skupova kao osnova matematike

[uredi | uredi kod]

Cela matematika se može formalizovati unutar CFI što znači da je moguće samu matematiku proučavati matematički. Svakom pitanju o postojanju nekog matematičkog objekta ili mogućnosti dokazivanja neke pretpostavke ili hipoteze može se dati precizna matematička formulacija. Pitanje o mogućnosti dokaza neke matematičke tvrdnje postaje smisleno matematičko pitanje. Kad je već reč o nerešenom matematičkom problemu ili dilemi ima smisla da se upitamo da li je moguće rešiti ih unutar formalnog CFI sistema. Odgovor može ne biti ni da ni ne jer je CFI nekompletan sistem. Navedimo nekoliko primera gde je moguće formalizovati matematičke objekte unutar CFI. Skup prirodnih brojeva se može identfikovati sa konačnim ordinalima, tj. . Skup celih brojeva može da se definiše kao skup klasa ekvivalencije parova prirodnih brojeva gde je relacija ekvivalencije ako i samo ako . Ako se svaki prirodni broj identifikuje sa klasom ekvivalencije para onda se operacije sume i proizvoda prirodnih brojeva mogu prirodno proširiti na skup celih brojeva . Skup racionalnih brojeva se može da definiše kao skup klasa ekvivalencije parova celih brojeva pri čemu je i pri relaciji ekvivalencije ako i samo ako je . Operacije sume i proizvoda na mogu se prirodno proširiti na . Poredak na skupu racionalnih brojeva je definisan sa: ako i samo ako postoji takvo da je . Realni brojevi se mogu definisati kao Dedekindovi preseci u , tj. realni broj je dat parom dvaju disjunktnih nepraznih skupova takvih da je , i za svako i . Opreacije sume, proizvoda i uređenosti na , se mogu proširiti na skup realnih brojeva .

CFI model je par gde je neprazan skup a je binarna relacija na takva da su sve CFI aksiome istinite ako se interpretiraju u . Na taj način ako je neka tvrdnja u teoriji skupova onda se može naći neki CFI model za koji je tvrdnja važeća, tada se negacija ne može dokazati u CFI. Ako se može naći model za i model za , tada se ne može dokazati niti oboriti u CFI. U tom se slučaju kaže da je nezavisna od CFI. Gedelova teorema kompletnosti logike prvog reda kaže da je CFI konsistentna aksiomatika ako se može naći CFI model. Kosistentnost ovde znači da CFI aksiome nisu protivrečne jedna drugoj.

Gedelove teoreme nekompletnosti pokazuju da bilo koji formalni sistem u matematici koji ima smisla je obavezno nekompletan. Ako je CFI konsistentan onda u CFI postoje tvrdnje koje su nezavisne od CFI. Gedelova druga teorema nekompletnosti dokazuje da formala aritmetička tvrdnja CON(CFI) koja pokazuje da je CFI konsistentan sistem ne može biti dokazana u CFI kao što ne može biti dokazana njena negacija, tj. CON(CFI) je nezavisna od CFI.

Ako je CFI konsistentan, tada nije moguće dokazati postojanje CFI modela jer bi u suprotnom bilo moguće da se u CFI dokaže konistentnost samog CFI. Na taj način je dokaz konsistentnosti ili nezavisnosti neke tvrdnje uvek dokaz relativne konsistentnosti, tj. ako se pretpostavi da je CFI konsistentan onda CFI ima model a time se može konstruisati drugi model za koju je tvrdnja istinita.

Lebeg (Henri Léon Lebesgue) je uveo pojam mere skupa kao apstrakciju dužine za skupove na realnoj pravoj. CFI pokazuje da postoje skupovi koji nemaju Lebegovu meru što praktično znači da za verovatnoću na realnim brojevima postoje događaji bez verovatnoće i da se svaki događaj može umetnuti između dva događaja bez verovatnoće. Da li i koje posledice ova činjenica ima u naukama koje se bave realnim svetom, niko još nije razmišljao.

Vidi još

[uredi | uredi kod]

Literatura

[uredi | uredi kod]
  • Godehard Link (editor): One Hundred Years of Russell's Paradox: Mathematics, Logic, Philosophy, Walter de Gruyter, Berlin-New York 2004
  • Aleksandar Perović, Aleksandar Jovanović, Boban Veličković: Teorija skupova, ISBN 978-86-7589-058-4, Matematički fakultet, Beograd
  • Andras Hajnal, Peter Hamburger: Set Theory, Cambridge University Press, Nov 11, 1999

Spoljašnje veze

[uredi | uredi kod]