Logika predikata. Kompaktnost, Skolemov teorem i nestandardni modeli

U devetom nastavku serijala o logici, Zvonimir Šikić pokazuje kako aksiomi prvog reda ne mogu jednoznačno odrediti beskonačne matematičke strukture. Zbog tog ograničenja, poznati sustavi poput aritmetike, realnih brojeva i teorije skupova neizbježno imaju i svoje nestandardne modele.

• Naslovna fotografija: Thoralf Skolem (Midjourney v7)

• Prethodni članci u seriji: Logika predikata. Potpunost i korektnost Gentzenovog sekventnog Q-sustava, Propozicijske, monadske i poliadske forme. Kvantifikacija i prirodni jezici, Bulovska logika pojmova. Forme, strukture i implikacije, Aristotelova silogistika. Jednostavna i jedina simbolička logika kroz dva milenija, Formalizacije logike sudova. Frege i Kneale, generatori i testovi, Logička korektnost, potpunost i kompaktnost. Gentzenov IF-sustav i Bethova semantička stabla, Zaključivanje u prirodnom i artificijelnom jeziku. Od Aristotela prema Fregeu, Logika sudova. Kondicionali, bikondicionali i implikacije

1. Kompaktnost i Skolemov teorem

Sustav dokazivanja je kompaktan (v. 3. poglavlje) ako za beskonačne \(\small \Gamma\) i \(\small \Delta\) vrijedi da:

\(\small \Gamma \models \Delta\) akko postoje konačni \(\small \Gamma’ \subseteq \Gamma\) i \(\small \Delta’ \subseteq \Delta\) takvi da \(\small \Gamma’ \models \Delta’\).

Da bismo dokazali kompaktnost logike predikata najprije cikličku metodu moramo modificirati tako da bude primjenjiva na beskonačne sekvente. To činimo kao i u IF–slučaju. Dakle, Bethova ciklička metoda za \(\small \dots, A_3, A_2, A_1 \not\models B_1, B_2, B_3, \dots\) sastoji se od sljedećih koraka.

1. korak: Polazeći od zahtjeva \(\small A_1^\top\) provedimo jedan ciklus cikličke metode.
2. korak: Na kraju svih otvorenih grana dobivenih u prethodnom koraku dopišemo zahtjev \(\small B_1^\bot\), pa provedemo još jedan ciklus cikličke metode.
3. korak: Na kraju svih otvorenih grana dobivenih u prethodnom koraku dopišemo zahtjev \(\small A_2^\top\) pa provedemo još jedan ciklus cikličke metode.

I tako dalje…

Postupak će stati ako se u nekom koraku sve grane zatvore ili neće nikada stati ako u svakom koraku bar jedna grana ostane otvorena. U prvom slučaju stablo sadrži konačno mnogo početnih formi \(\small A_n, \dots, A_1, B_1, \dots, B_m\) i za njih vrijedi \(\small A_n, \dots, A_1 \models B_1, \dots, B_m\). U drugom slučaju stablo je beskonačno, pa ima bar jednu beskonačnu granu. Na njoj se pojavljuju sve forme \(\small A_1, B_1, A_2, B_2, \dots\) i svi atomi od kojih su one izgrađene. Razmotrimo interpretaciju koju ti atomi imaju na toj grani. Prema semantičkim pravilima za izgradnju stabla, u toj interpretaciji sve forme na toj grani imaju točno onu vrijednost s kojom su označene. Dakle, \(\small A_1, A_2 \dots\) imaju vrijednost \(\small \top\), a \(\small B_1, B_2, \dots\) imaju vrijednost \(\small \bot\). No, to znači da \(\small \dots, A_3, A_2, A_1 \not\models B_1, B_2, B_3, \dots\)

Rezimirajmo, Bethova ciklička metoda za beskonačnu sekventu \(\small \Gamma \not\models \Delta\):

1. stane u konačno mnogo koraka i tada za konačne \(\small \Gamma’ \subseteq \Gamma\) i \(\small \Delta’ \subseteq \Delta\) vrijedi \(\small \Gamma’ \models \Delta’\), ili
2. ona ne stane, tj. generira beskonačno stablo, i tada vrijedi \(\small \Gamma \not\models \Delta\).

Odavde odmah slijedi kompaktnost relacije \(\small \models\). Naime, ako vrijedi \(\small \Gamma \models \Delta\) onda 2. slučaj ne može nastupiti pa postoje konačni \(\small \Gamma’ \subseteq \Gamma\) i \(\small \Delta’ \subseteq \Delta\) takvi da \(\small \Gamma’ \models \Delta’\).

Zanimljiv je slučaj u kojem pokušavamo naći strukturu u kojoj sve forme \(\small A_1, A_2 \dots\) imaju vrijednost \(\small \top\); najčešće su to aksiomi neke matematičke teorije. Ako takva struktura postoji onda kažemo da je ona model tih aksioma.

Primijenimo li cikličku metodu na takav slučaj (tj. na \(\small \dots, A_3, A_2, A_1 \not\models\))

1. ona staje u n-tom koraku i tada \(\small A_n, \dots, A_1 \models\) tj. već prvih n aksioma nema modela, ili
2. ona ne staje, tj. generira beskonačno stablo, i s njegove beskonačne grane možemo „očitati“ model koji zadovoljava cijeli niz aksioma \(\small A_1, A_2 \dots\)

Dakle, kompaktnost logike predikata može se izraziti i na sljedeći način.

TEOREM KOMPAKTNOSTI

Ako svaki konačni podskup niza aksioma (koji su kvantificirane forme) ima model onda i cijeli niz ima model.

Drugim riječima, da bismo dokazali da neki niz aksioma (koji su kvantificirane forme) ima model dovoljno je dokazati da svaki njegov konačni podskup ima model.

Iz primjene Bethove cikličke metode na nalaženje strukture u kojoj sve kvantificirane forme \(\small A_1, A_2 \dots\) imaju vrijednost \(\small \top\) (tj. iz njene primjene na \(\small \dots, A_3, A_2, A_1 \not\models\)) odmah slijedi i slavni Skolemov teorem.

SKOLEMOV TEOREM

Ako niz aksioma (koji su kvantificirane forme) ima model onda ima i prebrojivi model.

Struktura je prebrojiva ako je njen univerzum U prebrojiv, tj. ako se njegovi elementi mogu nanizati. Na primjer, skup prirodnih brojeva N očito je prebrojiv, a skup realnih brojeva R nije prebrojiv. Dokaz Skolemovog teorema je lagan. Ako niz aksioma ima model onda ciklička metoda generira beskonačno stablo, i s njegove beskonačne grane možemo „očitati“ model čiji univerzum U čini niz svih objekata uvedenih na toj grani.

(Da se realni brojevi ne mogu nanizati, tj. da R nije prebrojiv, dokazujemo Cantorovim dijagonalnim argumentom. Ograničimo se na realne brojeve između 0 i 1. Svaki je predstavljen beskonačnim decimalnim razvojem oblika \(\small 0.a_1 a_2 a_3 a_4 a_5 \dots\) u kojem su \(\small a_i\) znamenke 0, 1, 2, 3, 4, 5, 6, 7, 8 ili 9. Naime, svaki konačni razvoj, npr. 0.235 možemo zamijeniti beskonačnim razvojem \(\small 0.2349999\dots\). Promotrimo bilo koji niz takvih beskonačnih razvoja:

\(\small 0.a_1^1 a_2^1 a_3^1 a_4^1 a_5^1 \dots\)

\(\small 0.a_1^2 a_2^2 a_3^2 a_4^2 a_5^2 \dots\)

\(\small 0.a_1^3 a_2^3 a_3^3 a_4^3 a_5^3 \dots\)

\(\small 0.a_1^4 a_2^4 a_3^4 a_4^4 a_5^4 \dots\)

\(\small 0.a_1^5 a_2^5 a_3^5 a_4^5 a_5^5 \dots\)

·    ·    ·   ·   ·

·    ·    ·   ·   ·

Očito je da se broj \(\small 0.d_1 d_2 d_3 d_4 d_5 \dots\) definiran tako da je \(\small d_i \neq a_i^i\) i \(\small d_i \neq 0\), od i-tog broja u nizu razlikuje na i-tom decimalnom mjestu pa se taj „dijagonalni“ broj razlikuje od svih brojeva u tom nizu. No, tu konstrukciju možemo ponoviti sa svakim nizom pa slijedi da nijedan niz ne sadrži sve realne brojeve između 0 i 1.)

2. Logika predikata s jednakošću i operacijama

Prije nego opišemo nestandardne modele aritmetike i teorije skupova, moramo logiku predikata proširiti s jednakošću i operacijama, jer ih koristimo u aksiomatizacijama tih teorija.

Jednakost (identitet) je toliko jednostavna relacija da ju je teško objasniti, osim korištenjem sinonima. Dakle, a i b su identični akko su jedno te isto. Sve je identično samo sebi i ničem drugom. Ta jednostavnost izaziva i određenu zbunjenost. Koja je korist od relacije identiteta ako je identificiranje bilo čega sa samim sobom trivijalno, a s bilo čim drugim netočno? No, nije svaki identitet trivijalan. Iskaz „Ferić = Ferić“ je trivijalna i ne-informativna istina, međutim „Ferić = pisac Kalendara Maja“ i „Ferić ≠ pisac Kiklopa“ su netrivijalne i informativne istine. Zanimljivi iskazi identičnosti su oni u kojima su imenovane stvari iste ali su različita njihova imena, proizašla iz njihovih različitih definicija. Još jedan primjer je „Večernica = Danica“.

Osim toga, uz ekspresivnu moć kvantifikacije relacija identiteta omogućava i forme poput:

\(\small \forall x \forall y (C(x) \land C(y) \rightarrow x=y)\)

\(\small \exists x (C(x) \land \forall y (C(y) \rightarrow x=y))\)

\(\small \exists x \exists y (C(x) \land C(y) \land x \neq y)\)

\(\small \forall x \forall y \forall z (C(x) \land C(y) \land C(z) \rightarrow x=y \lor y=z \lor z=x)\)

Ako C interpretiramo kao “biti car“, lako ćete se uvjeriti da te kvantificirane forme s jednakošću na hrvatskom  imaju sljedeća značenja:

Postoji najviše jedan car.

Postoji točno jedan car.

Postoje bar dva cara.

Postoje najviše dva cara.

Dakle, kvantifikacija obogaćena relacijom identiteta omogućava razne forme brojevnih iskaza. Ali i mnogih drugih. Na primjer,

Nitko drugi ne voli ljude koji vole sami sebe.

ima sljedeću formu (gdje je \(\small V(x,y)\) forma od „x voli y“):

\(\small \forall x (\forall y (V(x,y) \rightarrow x=y) \rightarrow \forall y (x \neq y \rightarrow \neg V(y,x)))\)

Izražajna snaga koju donosi relacija identiteta neupitna je. Njenu logiku, tj. logiku kvantificiranih formi koje sadrže i binarni predikat \(\small =\), iz očitih razloga zovemo logikom predikata s jednakošću. Relacijske strukture u kojima ih interpretiramo, predikatu \(\small =\) pridružuju relaciju identiteta na U, čije je značenje fiksno u svim strukturama, tj. \(\small =\) smatramo logičkom konstantom poput veznika i kvantifikatora.

Istinitost zatvorene forme u interpretaciji definiramo kao za kvantificirane forme uz dodatak da \(\small U \models a=b\) akko \(\small a=b\). Valjane forme u toj proširenoj logici mogu biti poput \(\small \forall x (\exists y (x=y \land F(x)) \rightarrow \exists y (x=y))\) koja je valjana za svaki predikat \(\small G(x,y)\) supstituiran za \(\small x=y\). Njena valjanost ne ovisi o značenju predikata \(\small =\). Ili mogu biti poput formi (tzv. aksioma jednakosti):

\(\small \forall x (x=x)\) i \(\small \forall x \forall y (x=y \land F(x) \rightarrow F(y))\)

koje su valjane baš zbog značenja predikata \(\small =\). Gödel je 1930. dokazao da ta dva aksioma, zajedno s ostalim aksiomima i pravilima logike predikata, čine potpuni sustav logike predikata s relacijom identiteta.

Tim aksiomima identiteta u Bethovoj metodi semantičkih stabala odgovaraju sljedeća pravila njihove izgradnje:

\(\small a = a \top\)	\(\small a = b \top\)	\(\small a = b \top\)
	\(\small F(a/x) \top\)	\(\small F(a/x) \bot\)
	\(\small F(b/x) \top\)	\(\small F(b/x) \bot\)

Prvo pravilo znači da se u bilo kojem koraku izgradnje stabla može uvesti \(\small a=a \top\). Druga dva znače da se svaka grana na kojoj se nalaze \(\small a=b \top\) i \(\small F(a/x) \top\) (odnosno \(\small a=b \top\) i \(\small F(a/x) \bot\)) može produžiti s \(\small F(b/x) \top\) (odnosno s \(\small F(b/x) \bot\)).

Dokaz potpunosti Bethove metode prevodi se u dokaze potpunosti raznih sustava dokazivanja na doslovno isti način kao u logici predikata. Sam dokaz potpunosti Bethove metode u logici koja je proširena relacijom \(\small =\) i njenim pravilima, provodi se tako da se cikličkoj metodi semantičkih stabala doda četvrti korak:

(iv) primijenimo pravila za \(\small =\) na sve moguće načine, sa svim individualnim konstantama uvedenim na grani na kojoj se pravila primjenjuju.

Tako dopunjena ciklička metoda za \(\small \Gamma \not\models \Delta\) i dalje osigurava da svaki zahtjev prije ili kasnije bude analiziran. Zato izgradnja stabla ili završava zatvaranjem stabla što dokazuje \(\small \Gamma \models \Delta\) ili generira bar jednu (konačnu ili beskonačnu) otvorenu i potpuno razvijenu granu s koje očitavamo interpretaciju koja dokazuje \(\small \Gamma \not\models \Delta\). Na toj grani zahtjev \(\small a=b^\top\) znači da a i b treba identificirati. Za to nema nikakvih prepreka jer smo korakom (iv) osigurali da zamjenom a i b u bilo kojem zahtjevu dobijamo zahtjev iste istinosne vrijednosti.

Povijesno je logika predikata s jednakošću bila zanimljiva jer omogućava definicije numeričkih kvantifikatora, što je otvorilo mogućnost da se aritmetika (a potom i cijela matematika) reducira na logiku. To je bio Fregeov logicistički program koji nije uspio (osim ako logikom ne držimo i teoriju skupova, na koju je redukcija moguća).

Da postoji bar jedan F izričemo lako:

\(\small \exists_1 x F(x) \stackrel{def}{\iff} \exists x F(x)\)

Da postoje bar dva F-a izričemo s:

\(\small \exists_2 x F(x) \stackrel{def}{\iff} \exists x (F(x) \land \exists_1 y F(y) \land x \neq y)\)

Da postoje bar tri F-a izričemo s:

\(\small \exists_3 x F(x) \stackrel{def}{\iff} \exists x (F(x) \land \exists_2 y F(y) \land x \neq y)\)

i tako dalje. Rekurzivna definicija je jasna:

\(\small \exists_{n+1} x F(x) \stackrel{def}{\iff} \exists x (F(x) \land \exists_n y F(y) \land x \neq y)\)

Da postoji točno n F-ova, oznakom \(\small \exists!_n x F(x)\), rekurzivno definiramo s:

\(\small \exists!_0 x F(x) \stackrel{def}{\iff} \neg \exists x F(x)\)

\(\small \exists!_{n+1} x F(x) \stackrel{def}{\iff} \exists x (F(x) \land \exists!_n y F(y) \land x \neq y)\)

Dokaz da je 2+3=5 postaje dokaz valjanosti sljedeće logičke forme:

\(\small \exists!_2 x (F(x) \land G(x)) \land \exists!_3 x (F(x) \land \neg G(x)) \rightarrow \exists!_5 x F(x)\)

To je obećavajući početak redukcije aritmetike na logiku. No, problemi počinju kada želimo kvantificirati po univerzumu svih prirodnih brojeva (npr. kada tvrdimo da je svaki prirodni broj jednak zbroju dva prosta broja), jer tada nije dovoljno definirati svaki pojedini prirodni broj nego treba definirati opći pojam broja. To je moguće u teoriji skupova ali ne i u logici s jednakošću.

Jedno zanimljivo svojstvo logike s  jednakošću je da je njen monadski dio odlučiv, iako je = binaran predikat. Naime, može se dokazati da je poliadska logika sa samo jednim binarnim predikatom neodlučiva pa bismo mogli očekivati da će dodavanje binarnog predikata = monadskoj logici rezultirati neodlučivošću. No nije tako, jer predikat = ima fiksnu interpretaciju koja ga čini odlučivim.

U jeziku matematike važno mjesto zauzimaju operacije, koje su korisne i u drugim kontekstima, pa ih je zanimljivo uvesti i u logiku predikata s jednakošću. Zato joj dodajemo simbole za operacije koje interpretiramo kao operacije na univerzumu interpretacije U. To iskazujemo na sljedeći način koji samo precizira tu osnovnu ideju.

U definiciju kvantificiranih formi dodajemo

• operacijske konstante \(\small f_0^n, f_1^n, f_2^n, f_3^n, \dots\); za sve \(\small n \geq 0\).

Termi su sada izgrađeni prema sljedećim pravilima:

• Varijable i individualne konstante su termi.
• Ako su \(\small t_1, \dots, t_n\) termi onda je \(\small f_i^n(t_1, \dots, t_n)\) term.

U praksi ćemo umjesto \(\small f_i^n\) koristiti \(\small f, g, h, \dots\) , a mjesnost od npr. \(\small f\) bit će određena brojem njenih argumenata. Dakle, \(\small f(x)\) i \(\small f(x,y)\) su 1-mjesna i 2-mjesna operacija koje su međusobno različite. Zbog veće preglednosti, atomarne forme ćemo također zapisivati sa zagradama oko terma i zarezima među njima. Dakle, umjesto \(\small Pfag(x,fy)\) pisat ćemo \(\small P(f(a), g(x, f(y)))\).

Operacijska konstanta \(\small f_i^n\) predstavlja n-mjesnu funkciju koja na argumentima \(\small t_1, \dots, t_n\) prima vrijednost \(\small f_i^n(t_1, \dots, t_n)\). To znači da je interpretacija takve operacijske konstante u strukturi s univerzumom \(\small U\) funkcija definirana na \(\small U^n\) s vrijednostima u \(\small U\). Takve interpretacije zovemo relacijsko operacijskim strukturama.

Istinitost zatvorene forme u relacijsko operacijskoj strukturi definira se kao u relacijskoj strukturi uz dodatnu interpretaciju terma:

(i) \(\small |a|\) i \(\small |f_i^n|\) definirani su relacijsko operacijskom strukturom.

(ii) \(\small |f_i^n(t_1, \dots, t_n)| = |f_i^n|(|t_1|, \dots, |t_n|)\).

Metoda semantičkih stabala za ovako proširene kvantifikacijske forme ima i proširena kvantifikacijska pravila:

­ ­

I uz konačni broj individualnih i operacijskih konstanti na nekoj grani, broj terma koji one generiraju i koji se dopisuju uz \(\small \forall \top\) i \(\small \exists \bot\) je beskonačan. Zato treba definirati cikličku Bethovu metodu koja osigurava da svaki zahtjev na svakoj grani prije ili kasnije bude analiziran.

Jasno je kako se to može učiniti i tada kao i prije možemo dokazati potpunost Bethove metode za kvantificirane forme s jednakošću i operacijama. Zbog beskonačno mnogo terma koje generira konačni broj individualnih i operacijskih konstanti, već i monadska logika predikata s jednakošću i operacijama nije odlučiva.

3. Aritmetika i njeni nestandardni modeli

Već smo rekli da svaki skup aksioma (ako je konzistentan) definira strukturu u kojoj su ti aksiomi istiniti i da tada kažemo da je ta struktura model tog skupa aksioma.

Dedekind je 1888. definirao strukturu prirodnih brojeva \(\small (N,s,+,\cdot)\). Najprije je na proizvoljnom beskonačnom skupu \(\small U\) odabrao neki element \(\small 0\) kao početni broj. Potom je definirao funkciju sljedbenika \(\small s\) sa svojstvima:

(A0) 0 nije ničiji sljedbenik	(As) Različiti brojevi imaju različite sljedbenike.
(A0) \(\forall x(s(x) \neq 0)\)	(As) \(\forall x \forall y(x \neq y \rightarrow s(x) \neq s(y))\)

Zatim je skup prirodnih brojeva \(\small N\) definirao kao najmanji podskup od \(\small U\) koji sadrži \(\small 0\) i sljedbenike svih svojih elemenata:

\( \small N \overset{\text{def}}{=} \bigcap \{Y : 0 \in Y \land (\forall x)(x \in Y \rightarrow s(x) \in Y)\} \)

To je očito ekvivalentno sljedećem zahtjevu (tzv. aksiomu indukcije) koji mora zadovoljavati tako definirani univerzum brojeva \(\small N\):

\( \small \text{AI} \quad \forall Y (0 \in Y \land \forall x(x \in Y \rightarrow sx \in Y) \rightarrow \forall x Y(x)) \)

Ta tri definirajuća svojstva jednoznačno određuju kako izgleda struktura \(\small (N,s)\):

­­

Naime, ona mora sadržavati početni broj \(\small 0\) (zbog A0), svaki sljedeći broj mora biti različit od svih prethodnih (zbog As) i osim brojeva u tom produženom nizu sljedbenika nule nema drugih brojeva (zbog AI).

Operacije \(\small +\) i \(\small \cdot\) definiraju se sljedećim induktivnim definicijama (te su operacije, zbog AI, jednoznačno određene).

(A+0) \(\small \forall x(x+0=x)\)

(A+s) \(\small \forall x \forall y(x+sy=sx+y)\)

(A\(\small \cdot\)0) \(\small \forall x(x \cdot 0=0)\)

(A\(\small \cdot\)s) \(\small \forall x \forall y(x \cdot s(y)=(x \cdot y)+x)\)

Dedekind, striktno gledano, nije aksiomatizirao prirodne brojeve nego ih je definirao unutar jednostavne i neformalne teorije skupova. Prva doslovna aksiomatizacija bila je Peanova iz 1889. u kojoj je on Dedekindova definirajuća svojstva tretirao kao aksiome. Oni su od tada poznati kao Peanovi aksiomi (mada ih je Peano držao Dedekindovima).

Dakle, Peanovi aksiomi (A0), (As), (A+0), (A+s), (A\(\small \cdot\)0), (A\(\small \cdot\)s) i (AI) imaju u biti samo jedan model \(\small (N,s,+,\cdot)\) koji je standardni model tih aksioma (točnije kazano svi modeli Peanovih aksioma međusobno su izomorfni).

Uočimo, međutim, da aksiom indukcije (AI) nije uobičajena kvantificirana forma. Istinitost zatvorene forme \(\small \forall xF(x)\) u \(\small N\) definiramo kao istinitost zatvorene forme \(\small F(a/x)\) za sve moguće interpretacije konstante \(\small a\) kao broja iz \(\small N\). Istinitost zatvorene forme \(\small \forall YF(Y)\) u \(\small N\) definiramo kao istinitost zatvorene forme \(\small F(A/Y)\) za sve moguće interpretacije konstante \(\small A\) kao podskupa od \(\small N\). Forme koje kvantificiraju po objektima univerzuma zovemo formama 1. reda, dok forme koje kvantificiraju po podskupovima univerzuma zovemo formama 2. reda. Kvantificirane forme logike predikata su 1. reda (pa se ta logika često zove logikom 1. reda). Međutim, aksiom indukcije (AI) je 2. reda.

Kvantificirane forme 2. reda nemaju potpuni postupak za generiranje implikacija, tj. logika 2. reda nije potpuna. S druge strane, sve postojeće matematičke teorije mogu se formulirati kao aksiomatske teorije 1. reda (aksiomi su im 1. reda i dokazi su im 1. reda). Konkretno, umjesto aksioma indukcije 2. reda u matematičkoj praksi uvijek se može koristiti sljedeća shema aksioma indukcije 1. reda.

\( \small \text{(SAI)} \quad P(0) \land (\forall x)(P(x) \rightarrow P(s(x))) \rightarrow (\forall x)P(x) \)

Radi se o shemi aksioma, jer imamo po jedan aksiom za svako aritmetičko svojstvo \(\small P(x)\) koje je 1. reda. Teorija čiji su aksiomi (A0), (As), (A+0), (A+s), (A\(\small \cdot\)0), (A\(\small \cdot\)s) i (SAI), dakle teorija s beskonačno mnogo aksioma 1. reda, zove se Peanovom aritmetikom 1. reda i kraće se označava PA.

Dodamo li toj teoriji beskonačno mnogo aksioma \(\small \omega>0, \omega>1, \omega>2, \dots\) dolazimo do skupa aksioma čiji svaki konačni podskup ima model. Naime, standardni model je jedan takav model. U njemu vrijede svi stari aksiomi pa i svaki njihov konačni podskup. Što se tiče novih aksioma, svaki njihov konačni podskup ima \(\small n\) takav da \(\small \omega>n, n+1, n+2, \dots\) nisu u tom podskupu pa je standardni model u kojem je \(\small \omega=n\) model tog konačnog podskupa. Ali ako svaki konačni podskup beskonačnog skupa aksioma 1. reda

\( \small \text{A0, As, A+0, A+s, A\cdot 0, A\cdot s, SAI, } \omega>0, \omega>1, \omega>2, \dots \)

ima model onda ga, prema teoremu kompaktnosti, ima i cijeli taj skup aksioma. No, taj model sigurno nije standardni model, jer u njemu postoji beskonačni broj \(\small \omega\) koji je veći od svih standardnih brojeva \(\small 0, 1, 2, 3, \dots\) . Takvih nestandardnih modela ima mnogo, prilično su složeni i tema su matematičkih istraživanja kojima se ovdje nećemo baviti.

Spomenimo tek da se postojanje nestandardnih modela teorije realnih brojeva može dokazati na doslovno isti način. Kao i u slučaju prirodnih brojeva, aksiomi koji jednoznačno determiniraju strukturu \(\small (R,<,+,\cdot)\) sadrže jedan aksiom (aksiom kontinuiteta) koji je 2. reda. Jednoznačnost je dokazao Hörder krajem 19. stoljeća. Ako se ograničimo na aksiome 1. reda (možemo čak uzeti sve tvrdnje 1. reda koje su istine u standardnom modelu) onda dodavanjem aksioma \(\small \omega>0, \omega>1, \omega>2, \dots\) na isti način dokazujemo da postoji nestandardni model koji sadrži beskonačno veliki broj \(\small \omega\). Budući da realni brojevi imaju inverze, nestandardni model sadrži i beskonačno mali broj, tj. infinitezimal, \(\small 1/\omega\). Tako je Robinson 1961. dokazao da postoji struktura hiperrealnih brojeva \(\small (R^*,<,+,\cdot)\) koja sadrži infinitezimale i čija se sva svojstva 1. reda poklapaju sa svojstvima od \(\small (R,<,+,\cdot)\). Dokazi u \(\small R^*\) uglavnom su jednostavniji od onih u \(\small R\), no ako je teorem koji smo dokazali 1. reda on vrijedi i u \(\small R\). To je Robinsonov princip transfera koji je Leibniz zvao principom kontinuiteta. Tim principom je Leibniz postulirao, ali nije dokazao da sve funkcije i relacije definirane na realnim brojevima imaju proširenja na hiperrealne brojeve uz očuvanje njihovih svojstava. Međutim, očito se ne čuvaju sva svojstva. Leibniz i ostali korisnici infinitezimalnog računa najčešće su mislili na algebarska svojstva, a Robinson je dokazao da se radi o svojstvima 1. reda. Na primjer, u \(\small (R^*,<,+,\cdot)\) vrijedi:

\( \small y=x^2 \rightarrow \frac{dy}{dx} = \frac{(x+dx)^2-x^2}{dx} = \frac{x^2+2x dx+dx^2-x^2}{dx} = 2x+dx := 2x \)

Zadnja jednakost je prevođenje hiperrealnog broja u njegov standardni dio (Leibniz je smatrao evidentnom istinom da je svaki konačni hiperrealni broj beskonačno blizu točno jednom realnom, što je Robinson dokazao). No, to znači da u \(\small (R,<,+,\cdot)\) vrijedi \(\small y=x^2 \rightarrow \frac{dy}{dx}=2x\).

4. Teorija skupova i Skolemov paradoks

U drugoj polovici 19. stoljeća mnogi su matematičari počeli razmišljati o strožem utemeljenju matematike. To je rezultiralo njenim utemeljenjem u teoriji skupova, a početkom 20. stoljeća u aksiomatiziranoj teoriji skupova ZFC (proširenoj, ako je to potrebno, aksiomima o postojanju velikih kardinalnih brojeva). Što to zapravo znači? Najjednostavnije, da se svi matematički pojmovi mogu definirati u toj teoriji te da se iz njenih aksioma mogu izvesti svi matematički teoremi. Nešto detaljnije, to znači da se matematički objekti (poput brojeva, funkcija i sl.) mogu definirati kao određeni skupovi, te da se matematički teoremi (poput osnovnog teorema algebre, analize i sl.) mogu promatrati kao izjave o skupovima koje su dokazive iz aksioma teorije skupova. To uranjanje matematike u teoriju skupova danas je toliko dobro poznato da često zaboravljamo koliko je ono zapanjujuće.

Mnogi ovu “redukciju” klasične matematike na teoriju skupova vide kao nastavak i bar djelomično ostvarenje Fregeovog logicizma. Fregeov projekt bio je epistemološki: ako se matematika može svesti na logiku, tada se matematička spoznaja svodi na logičku (što pobija Kantovu tezu da je matematička spoznaja sintetička). Pod pretpostavkom da je logička spoznaja temeljnija od matematičke to je jasni epistemološki dobitak. Kada se Fregeov logicizam pokazao nekonzistentnim, teorija skupova zauzela je njegovo mjesto, ali epistemološka analiza je sačuvana: za matematičke teoreme znamo da su istiniti jer znamo da logički slijede iz aksioma teorije skupova za koje znamo da su istiniti. Tako je problem spoznavanja matematičkih istina sveden na problem spoznavanja istinitosti aksioma teorije skupova i valjanosti logičkih dedukcija.

No, već je Russell upozorio, a to zna i svaki matematičar koji je ikada dokazao neki složeniji teorem, da naša matematička znanja ne izviru logičkim slijedom iz aksioma, nego se ti aksiomatski sljedovi izgrađuju naknadno, kada je već skupljen veliki fond matematičkih znanja. Dakle, redukcija na teoriju skupova možda je logička, ali sigurno nije epistemološka.

Na taj su način razmišljali Zermelo i drugi začinjavci, kada su teoriju skupova držali onom granom matematike čiji je zadatak matematički istražiti temeljne pojmove “broj”, “uređaj”, “funkcija” i sl. te tako uspostaviti logičke temelje aritmetike i analize. Naknadni razvoj proširio je doseg teorije skupova na cijelu klasičnu matematiku. Teorija skupova time je jasno pokazala da je matematika jedinstvena znanost s jedinstvenim predmetom i metodologijom. I ranije su matematičari uspješno povezivali naizgled daleka područja (npr. geometriju, kompleksnu aritmetiku i teoriju funkcija, što je amblemski predstavljeno slavnom formulom \(\small e^{i\pi} = -1\)), ali teorija skupova je tome dala jasan i sveobuhvatan matematički okvir.

Tako je postalo moguće da se nešto kaže pa i dokaže o cjelokupnoj klasičnoj matematici. Kada je ona skupljena u jedan paket (koji je teorija skupova) može se npr. postaviti pitanje njezine konzistentnosti, što je učinila Hilbertova škola. Gödel se pobrinuo, svojim teoremima nepotpunosti, da projekt ne uspije onako kako su se nadali Hilbert i njegovi sljedbenici, ali činjenica je da ni Gödelov rezultat (ako je konzistentna, klasična matematika ne može dokazati vlastitu konzistentnost) nije moguć bez uranjanja cijele klasične matematike u teoriju skupova ili neki ekvivalentni okvir.

Otkako je Gödel dokazao nedokazivost konzistentnosti klasične matematike (u njenom skupovno-teorijski formaliziranom obliku) dokazana je nedokazivost i mnogih drugih specifično matematičkih tvrdnji; u teoriji brojeva, analizi, algebri, beskonačnoj kombinatorici, teoriji skupova itd. Mnoge od njih moguće je dokazati u teoriji skupova proširenoj nekim aksiomom o postojanju skupova s velikim kardinalnim brojem (\(\small \text{ZFC} + \aleph\)) čime se, katkada ne veoma neočekivane načine, proširio „sveobuhvatni matematički okvir“. Naime, dosta je neočekivano (iako smo danas na to već navikli) da za dokaz neke tvrdnje o prirodnim brojevima, koji čine najmanji beskonačni skup, katkada trebamo pretpostaviti postojanje enormno velikih beskonačnih skupova.

Ako prihvatimo da dokazivanja ovakvih općih tvrdnji o klasičnoj matematici jest nešto za nju „temeljno”, onda ovdje sigurno nalazimo temeljnu ulogu teorija skupova.

Zermelo-Fraenkelova aksiomatizacija teorije skupova, oznakom ZF, teorija je 1. reda u kojoj je binarni predikat \(\small \in\) jedina nelogička konstanta. U daljnjoj formulaciji njenih aksioma koristit ćemo se sa \(\small (\exists u \in x)A(u)\) kao pokratom za \(\small \exists u(u \in x \land A(u))\), sa \(\small \forall u \in x A(u)\) kao pokratom za \(\small \forall u(u \in x \rightarrow A(u))\) te sa \(\small \exists! x A(x)\) kao pokratom za \(\small \exists x A(x) \land \forall y(A(y) \rightarrow x=y)\).

1. Aksiom ekstenzije: dva su skupa jednaka (tj. isti su skup) akko imaju iste elemente.

\(\small \forall y \forall z (\forall x (x \in y \leftrightarrow x \in z) \leftrightarrow y=z)\)

2. Shema aksioma separacije: postoji skup elemenata koje iz skupa \(\small z\) izdvaja njihove elemente sa svojstvom \(\small P\) (radi se o shemi, jer imamo po jedan aksiom za svaku otvorenu formu \(\small P\) koja ne sadrži \(\small y\)).

\(\small \forall z \exists y \forall x (x \in y \leftrightarrow (x \in z \land P(x)))\)

Prva dva aksioma jamče da za svaki \(\small P\) postoji jedinstveni skup \(\small \{x \in z : P(x)\}\) koji čine svi \(\small x \in z\) takvi da \(\small P(x)\). Restrikcija \(\small x \in z\) je nužna jer ne postoji uvijek \(\small x : Px\). Na primjer, ne postoji Russellov skup \(\small r \overset{\text{def}}{=} \{x : x \notin x\}\) jer je kontradiktoran. Naime, \(\small r \in r \iff r \notin r\).

3. Aksiom unije: za svaki skup postoji skup koji je unija njegovih elemenata.

\(\small \forall x \exists z (z = \bigcup x) \quad \bigcup x \overset{\text{def}}{=} \{y : (\exists u \in x)(y \in u)\}\)

4. Aksiom partitivnog skupa: za svaki skup postoji skup svih njegovih podskupova.

\(\small \forall x \exists z (z = \mathcal{P}(x)) \quad \mathcal{P}(x) \overset{\text{def}}{=} \{y : y \subseteq x\} \quad y \subseteq x \overset{\text{def}}{\iff} (\forall u \in y)(u \in x)\)

5. Aksiom beskonačnosti: postoji skup koji je beskonačan.

\(\small \exists u (u = \bigcap \{z : \emptyset \in z \land \forall x(x \in z \rightarrow x \in z)\}) \quad \bigcap x \overset{\text{def}}{=} \{y : (\forall u \in x)(y \in u)\}\)

Skup \(\small u\) je beskonačan jer sadrži \(\small \emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \dots\) . Da su svi ti skupovi međusobno različiti slijedi iz aksioma utemeljenja.

6. Shema aksioma zamjene: funkcijska slika svakog skupa je skup (radi se o shemi, jer imamo po jedan aksiom za svaku funkcijsku formu \(\small F\) koja ne sadrži \(\small y\)).

\(\small \forall z (\forall x \in z \exists! y F(x,y) \rightarrow \exists u(u = \{v : \exists x \in z F(x,v)\}))\)

\(\small \forall x \in z \exists! y F(x,y)\) znači da je \(\small F\) funkcija koja svakom \(\small x \in z\) pridružuje točno jedan \(\small y\). \(\small u = \{v : \exists x \in z F(x,v)\}\) znači da je skup \(\small u\) \(\small F\)-slika skupa \(\small z\). Dakle, cijeli aksiom tvrdi da je \(\small F\)-slika skupa i sama skup.

7. Aksiom utemeljenosti: ni za jedan skup \(\small x\) ne postoji beskonačni niz \(\small \dots \in x_3 \in x_2 \in x_1\).

\(\small \forall x (x \neq \emptyset \rightarrow (\exists y \in x)(y \cap x = \emptyset))\)

Skup \(\small x = \{x_1, x_2, x_3, \dots\}\) očito ne zadovoljava aksiom i svaki skup koji ga ne zadovoljava očito sadrži elemente \(\small \dots \in x_3 \in x_2 \in x_1\).

Ovih 7 aksioma aksiomatizira teoriju skupova ZF, a ako dodamo aksiom izbora dobivamo ZFC.

8. Aksiom izbora: Ako je \(\small x\) neprazni skup nepraznih skupova onda postoji skup \(\small y\) koji ima točno jedan zajednički element sa svakim \(\small u \in x\) (skup \(\small y\) iz svakog skupa \(\small u \in x\) „izabire“ taj jedan zajednički element).

\(\small \exists y \forall u \in x (\exists! z \in u)(z \in y)\)

U ZF lako se dokazuje da svaki skup \(\small S\) ima kardinalni broj koji je strogo manji od kardinalnog broja njegovog partitivnog skupa \(\small \mathcal{P}(S)\). To je dokazao Cantor 1891. Naime, pretpostavimo da je \(\small j\) bilo koja funkcija koja elementima iz \(\small S\) pridružuje podskupove od \(\small S\). Tada podskup od \(\small S\) definiran sa \(\small A = \{x \in S : x \notin j(x)\}\) sigurno nije pridružen nijednom elementu, jer da postoji \(\small a \in S\) takav da je \(\small j(a)=a\) imali bismo kontradikciju:

\( \small a \in A \iff a \notin j(a) \iff a \notin A. \)

Kontradikcija dokazuje da svako „prebrajanje“ podskupova od \(\small S\) elementima iz \(\small S\) promašuje bar jedan podskup, tj. podskupova od \(\small S\) uvijek je više nego elemenata iz \(\small S\). Taj je teorem matematičarima otvorio vrata Cantorovog raja u kojem beskonačnostima nema kraja (kako se poetski izrazio Hilbert u Über das Unendliche, 1926.). Nakon najmanje beskonačnosti \(\small N\) koja je kardinalni broj prebrojivog skupa \(\small N\), nižu se sve veće i veće neprebrojive beskonačnosti \(\small \mathcal{P}(N), \mathcal{P}(\mathcal{P}(N)), \mathcal{P}(\mathcal{P}(\mathcal{P}(N))), \dots\) . Tako je to u standardnom modelu teorije skupova.

Međutim, Skolemov teorem nam govori da svaki niz aksioma 1. reda ima prebrojivi model. Dakle, osim standardnog Cantorovog raja, aksiomi ZFC imaju i nestandardne modele s prebrojivim univerzumom \(\small U\). Kada je Skolem 1922. to dokazao mnogi su smatrali da se radi o paradoksu, jer je nemoguće da prebrojiva struktura (koja postoji prema Skolemovom teoremu) sadrži neprebrojive skupove (koji postoje prema Cantorovom teoremu). Međutim nestandardni model kojeg generira Bethova metoda interpretira \(\small \in\) tako da zadovoljava aksiome ZFC, a ne nužno i naše standardno razumijevanje relacije \(\small \in\), pa \(\small a \in b\) ne mora nužno značiti da su \(\small a\) i \(\small b\) skupovi u standardnom smislu niti da je \(\small a \in b\) u standardnom smislu. No, onda ni neprebrojivost nije standardna u toj interpretaciji. Čak ni Skolemova originalna konstrukcija u kojoj su objekti nestandardne strukture zaista skupovi, a relacija \(\small \in\) jest relacija pripadanja elementa skupu, nije paradoksalna. Naime, neprebrojivost skupa \(\small a\) znači da ne postoji jednoznačno pridruženje elemenata od \(\small a\) prirodnim brojevima pa čak i ako je \(\small a\) u standardnom smislu prebrojiv on u Skolemovoj nestandardnoj strukturi ipak može biti neprebrojiv jer u toj strukturi nema potrebnog pridruženja.

Radi se naprosto o tome da aksiomima 1. reda nikada ne možemo jednoznačno determinirati beskonačnu strukturu. Aksiomi 1. reda uvijek će imati više bitno različitih (ne izomorfnih) modela, a ne samo onaj standardni koji smo mi htjeli aksiomatizirati.