Cermelo-Frenkel teorija skupova

Cermelo-Frenkel teorija skupova sa aksiomom izbora (skraćeno CFI), je standardni oblik aksiomatske teorije skupova, i kao takav se najčešće uzima za osnovu matematike.

Uvod

1908, Ernst Cermelo je predložio prvu aksiomatsku teoriju skupova, Cermelo teoriju skupova. Ova aksiomatska teorija nije omogućavala konstrukciju ordinalnih brojeva; iako se veći deo obične matematike može razviti bez korišćenja ordinalnih brojeva, oni su osnovna alatka u većini proučavanja u teoriji skupova. Štaviše, Cermelove aksiome su uvele koncept konačnog svojstva, čije je operaciono značenje bilo dvosmisleno. 1922, Abraham Frenkel i Toralf Skolem su nezavisno predložili definicije konačnog svojstva, kao svojstva koje se može formulisati u logici prvog reda, tako da sve atomske formule uključuju pripadnost skupu ili jednakost. Iz njihovog rada je nastala aksioma zamene. Dodavanjem ove aksiome, kao i aksiome regularnosti, Cermelovoj teoriji skupova je nastala teorija označena kao CF.

Dodavanjem aksiome izbora (AI) uz CF, dobija se CFI. Kada matematički rezultat zahteva aksiomu izbora, to se ponekad naglašava eksplicitno. Razlog zbog koga se aksoma izbora ovako izdvaja je to što je ona inherentno nekonstruktivna; ona postulira postojanje skupa (skup izbora), bez naznačavanja kako se taj skup konstruiše. Stoga rezultati dokazani pomoću AI mogu da uključuju skupove, za koje iako je moguće dokazati da postoje, nije ih moguće konstruisati eksplicitno. Na primer, aksioma izbora podrazumeva postojanje dobre uređenosti na bilo kom skupu. Iako ne možemo da konstruišemo dobru uređenost za skup realnih brojeva, R, aksioma izbora garantuje postojanje takve uređenosti.

CFI ima beskonačan broj aksioma, jer je aksioma zamene u stvari šema aksioma. Poznato je da ni CFI ni CF ne mogu da budu aksiomatizovane konačnim skupom aksioma; ovo je prvi pokazao Ričard Montagju (1961). sa druge strane, Fon Nojman-Bernajz-Gedelova teorija skupova (NBG) može biti konačno aksiomatizovana. Ontologija NBG uključuje klase uz skupove; skup je klasa koja je član druge klase. NBG i CFI su ekvivalentne teorije skupova, u smislu da svaka teorema o skupovima (to jest ona koja ne pominje klase) koja može biti dokazana jednom od ovih teorija, može biti dokazana i drugom.

Usled Gedelove druge teoreme nepotpunosti, konzistentnost CFI se ne može dokazati unutar same CFI (osim ako je nekonzistentna). Konzistentnost CFI potiče iz postojanja slabo nedostupnog kardinala, čije postojanje nije dokazivo u CFI (osim ako je CFI nekonzistentna). Međutim, skoro niko ne gaji strahove da se unutar CFI nalazi neka neprimećena kontradikcija; uvreženo je mišljenje da da je CFI nekonzistentna, to bi do sada bilo otkriveno. Ovoliko je sigurno – CFI ne pada tako lako kao naivna teorija skupova na svoja tri velika paradoksa: Raselovom paradoksu, Burali-Forti paradoksu, i Kantorovom paradoksu.

Među manama CFI koje su istaknute u literaturi su:

• Jača je nego što je neophodno za gotovo celokupnu svakodnevnu matematiku (ovo su istakli Saunders Meklejn i Solomon Feferman);
• Upoređena sa nekim drugim aksiomatizacijama teorije skupova, CFI je relativno slaba. Na primer, ne priznaje postojanje univerzalnog skupa (kao Nove osnove) ili klase (kao NBG), usled opasnosti od Raselovog paradoksa;
• Saunders Meklejn (osnivač teorije kategorija) i drugi smatraju da sve aksiomatske teorije skupova ne odgovaraju načinu na koji matematika deluje u praksi. Oni smatraju da se u matematici ne radi o kolekcijama apstraktnih objekata i njihovih svojstava, već o strukturi i preslikavanjima koja očuvavaju strukturu.

Aksiome

Postoji više ekvivalentnih formulacija aksioma CFI; Sledeći skup aksioma je dao Kunen [1980]; Opisi su dodati zarad jasnoće.

1) Aksioma ekstenzionalnosti: Dva skupa su ista ako imaju iste elemente.

$\forall x\forall y(\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y)$

2) Aksioma regularnosti (takođe poznata kao aksioma osnove): Svaki neprazan skup x sadrži nekog člana y tako da su x i y disjunktni skupovi.

$\forall x[\exists y(y\in x)\Rightarrow \exists y(y\in x\land \lnot \exists z(z\in y\land z\in x))]$

3) Aksioma šema specifikacije: Ako je z skup, i $\phi \!$ je bilo koje svojstvo koje mogu da poseduju elementi x iz z, onda postoji podskup y od z koji sadrži one x iz z koji poseduju to svojstvo. Restrikcija na z je neophodna da bi se izbegao Raselov paradoks i njegove varijante. Formalno: za bilo koju formulu $\phi \!$ u jeziku CFI sa slobodnim promenljivima među $x,z,w_{1},\ldots ,w_{n}\!$:

$\forall z\forall w_{1}\ldots w_{n}\exists y\forall x(x\in y\Leftrightarrow (x\in z\land \phi ))$

4) Aksioma uparivanja: Ako su x i y skupovi, onda postoji skup koji ih sadrži oba.

$\forall x\forall y\exists z(x\in z\land y\in z)$

5) Aksioma unije: Za svaki skup ${\mathcal {F}}$ postoji skup A koji sadrži svaki skup koji je član nekog člana ${\mathcal {F}}$.

$\forall {\mathcal {F}}\,\exists A\,\forall Y\,\forall x(x\in Y\land Y\in {\mathcal {F}}\Rightarrow x\in A)$

6) Aksioma šema zamene: Za svaku formalno definisanu funkciju f čiji domen je skup postoji skup koji sadrži opseg f (podvrgnut restrikciji kako bi se izbegli paradoksi). Formalno: za svaku formulu $\phi \!$ u jeziku CFI sa slobodnim promenljivima među $x,y,A,w_{1},\ldots ,w_{n}\!$:

$\forall A\,\forall w_{1},\ldots ,w_{n}[(\forall x\in A\exists !y\phi )\Rightarrow \exists Y\forall x\in A\exists y\in Y\phi ].$

Ovde kvantifikator $\exists !y$ označava da jedinstven takav $y\!$ postoji, do na jednakost.

Sledeća aksioma koristi notaciju $S(x)=x\cup \{x\}\!$. Aksiome 1 do 6 dokazuju da $S(x)\!$ postoji i da je jedinstveno za svaki skup $x\!$. One takođe impliciraju da ako bilo koji skup postoji, onda prazan skup $\varnothing$ postoji i jedinstven je.

7) Aksioma beskonačnosti: Postoji skup X takav da je prazan skup član X i kada god je y u X, takođe je i S(y).

$\exists X\left(\varnothing \in X\land \forall y(y\in X\Rightarrow S(y)\in X)\right)$

8) Aksioma partitivnog skupa: Za svaki skup x postoji skup y koji se sastoji od svakog podskupa od x.

$\forall x\exists y\forall z(z\subseteq x\Rightarrow z\in y)$

Ovde je $z\subseteq x$ skraćenica za $\forall q(q\in z\Rightarrow q\in x)$.

9) Aksioma izbora: Za svaki skup X postoji binarna relacija R koja dobro uređuje X. Ovo znači da je R linearno uređenje na X i svaki neprazan podskup od X ima element koji je minimalan u odnosu na R.

$\forall X\exists R(R\;{\mbox{dobro-uredjuje}}\;X)$

Kunen takođe uključuje suvišnu aksiomu koja kaže da barem jedan skup postoji. Postojanje skupa sledi iz aksiome beskonačnosti. Aksioma uparivanja se može dedukovati iz aksiome beskonačnosti, aksiome specifikacije i aksiome zamene.

Često se javljaju alternativni oblici prvih osam aksioma. Na primer, aksioma uparivanja (#4) je često izmenjena tako da glasi da za svake skupove x i y postoji skup koji sadrži tačno x i y. Slično, aksiome unije, zamene i partitivnog skupa su često napisane tako da tvrde da željeni skup sadrži samo one skupove koje mora da sadrži. Ponekad se dodaje aksioma koja tvrdi da postoji prazan skup. Za primer nekih od ovih varijacija, videti spisak aksioma koje je dao Ječ [2003].

Aksioma izbora ima mnogo ekvivalentnih iskaza (to jest, postoji mnogo iskaza za koje prvih 8 aksioma dokazuje da su ekvivalentne aksiomi 9). Među njima je iskaz da svaki skup nepraznih skupova ima funkciju izbora; ime aksiome je dobijeno iz ovog ekvivalentnog oblika.

Gornji spisak uključuje dve beskonačne šeme aksioma. Poznato je da ne postoji konačna aksiomatizacija CFI, i stoga svaka aksiomatizacija mora da uključuje barem jednu ovakvu šemu. Alternativna verzija šeme zamene implicira šemu uključivanja; ovo omogućava aksiomatizaciju CFI sa tačno jednom beskonačnom šemom aksioma.

Vidi još

• Aksiomatska teorija skupova
• Cermelova teorija skupova
• Vajthed-Raselove aksiome
• Fon Nojman-Bernajz-Gedelova teorija skupova
• Spisak iskaza neodlučivih u Cermelo-Frenkel teoriji skupova sa aksiomom izbora
• Z notacija

Literatura

• Abian, Alexander, 1965. The Theory of Sets and Transfinite Arithmetic. W B Saunders.
• Keith Devlin, 1996 (1984). The Joy of Sets. Springer.
• Abraham Fraenkel, Yehoshua Bar-Hillel, and Azriel Levy, 1973 (1958). Foundations of Set Theory. North Holland.
• Hatcher, William, 1982 (1968). The Logical Foundations of Mathematics. Pergamon.
• Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.
• Kunen, Kenneth, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9.
• Suppes, Patrick, 1972 (1960). Axiomatic Set Theory. Dover.
• Tourlakis, George, 2003. Lectures in Logic and Set Theory, Vol. 2. Cambridge Univ. Press.
• Jean van Heijenoort, 1967. From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press.

Spoljašnje veze

• Stanfordova enciklopedija filozofije: Teorija skupova -- Tomas Ječ.
• Metamath. Onlajn projekat za matematičke dokaze koji koriste apstraktan jezik, koje može da verifikuje računarski program.
• Cermelo-Frenkel aksiome na sajtu PlanetMath