Nije li PA sigurno konzistentna jer ima za model prirodne brojeve?

 To je svakako zanimljivo pitanje. Prvo treba precizirati što si zapravo htio reći - vjerojatno to da je _skup_ prirodnih brojeva, zajedno s odgovarajućim funkcijama za operacije, i relacijom uređaja, i nulom kao istaknutim elementom, struktura prvog reda u kojoj vrijede svi aksiomi PA. No kako točno znaš da ta struktura postoji? (Ne direktno povezano, ali da ti pokažem koliko su stvari komplicirane: čak i ako postoji, kako znaš da je jedinstvena do na izomorfizam? Jesi li siguran da neka od brojnih hipoteza o prirodnim brojevima (npr. Collatzov problem) nije zapravo nezavisna od aksioma, što bi bila prilična besmislica ako doista vjerujemo u _the_ strukturu opisanu tim aksiomima?:)

Iako je točno da "skup" gore ne mora značiti "ono što je opisano punom teorijom skupova" (npr. teorija Triv koja se sastoji samo od formule "postoji x postoji y ne (x jednako y)" očito ima za model bilo kakav naivni skup od dva različita elementa - recimo, same varijable 'x' i 'y' mogu poslužiti:), za beskonačne skupove praktički nemamo drugi način konstrukcije. Praktički jedina općeprihvaćena struktura unutar koje imamo beskonačne skupove (ne potencijalno, nego aktualno beskonačne) je kumulativna hijerarhija.

Dakle, ono što si zapravo htio reći, u drugoj aproksimaciji, je da, popikani na prava mjesta, u kumulativnoj hijerarhiji skupova opisanoj aksiomima ZF, žive točno oni skupovi koji tebi trebaju: \N, 0, ', +, *, <. No sad je jasno da si samo zamijenio problem težim: kumulativna hijerarhija je model za ZF jednako kao što je struktura prirodnih brojeva model za PA. Dakle, ono što si zapravo rekao, u trećoj aproksimaciji, je da unutar svakog modela od ZF živi model za PA. Ta relacija među teorijama je dobro poznata u logici, i zove se interpretabilnost. Dakle, u četvrtoj aproksimaciji, tvoja tvrdnja glasi: PA je interpretabilna u ZF. I to je sasvim točno, jedino što takva tvrdnja daje samo relativnu konzistentnost. _Ako_ je ZF konzistentna, _tada_ je i PA konzistentna. ("U svakom modelu od ZF živi model za PA" ne povlači "postoji model za PA" ako nemamo još pretpostavku "ZF je konzistentna".) Odnosno, obratom po kontrapoziciji, ako je PA inkonzistentna, tada je i ZF inkonzistentna. No tada ionako imamo većih problema. :-D

Naravno, ovo ti se može činiti kao prevara, "sve visi na ZF". Ali za inherentno beskonačne strukture, to jest doista najbolje što imamo. Probajmo finitistički. Ti bi htio da se ne može u PA dokazati 0=1 (gdje je 1 oznaka za 0', sljedbenik od 0). Kao argument za to navodiš neku strukturu N koja je s početka sasvim jasna, a kraj joj se gubi u daljini. Kažeš da maglovit kraj uopće nije bitan ("don't pay attention to the infinity behind the curtain":), i pokazuješ prva dva objekta u njoj, i kažeš da su sasvim jasno vidljivi i očito različiti. Ja se slažem s tobom, ali iz toga nikako ne slijedi da PA ne može _dokazati_ da su različiti. Grozota inkonzistentnih teorija je upravo da mogu dokazati što god hoće. :-)

Ok, ono što ti zapravo želiš reći je da sve formule koje možemo dokazati u PA moraju biti _istinite_ u N, a 0=1 očito nije istinita u N. No problem je u bazi: za vidjeti da su svi aksiomi PA istiniti u N, trebalo bi istražiti i onaj magloviti dio, a to je problem - sve veći kako idemo dalje. A da se u maglovitom dijelu mogu skrivati svakakvi zmajevi, po mom mišljenju dobro pokazuje sljedeća pričica:

Znamo, po drugom Gödelovom teoremu, da se u PA (ako je konzistentna) ne može dokazati Con, formula koja na prirodan način iskazuje tvrdnju da je PA konzistentna. (Con je jednostavno formula oblika "ne postoji x (x je kod konačnog niza čiji je svaki element ili kod neke instance aksioma PA ili postoje elementi prije njega iz kojih je izveden pravilom generalizacije ili modus ponensa, i čiji je zadnji element kod formule 0=0')".) Međutim, opća je logička stvar (propozicija tamo negdje kod Lindenbaumove leme) da ako T ne dokazuje F, tada je T+{ne F} konzistentna teorija. Drugim riječima, postoji -PA, teorija koja je dobivena tako da se na aksiome od PA doda (ne Con), i ta teorija je konzistentna ako je PA konzistentna. Odnosno, ako postoji N, tada postoji i -N, model za -PA. Štoviše, -N i N ispočetka izgledaju skroz isto: imaš nulu, imaš njenog sljedbenika 1, imaš njegovog sljedbenika 2, 1+1=2, itd. Međutim, u -N je istinita tvrdnja (ne Con), što znači da negdje u njegovom maglovitom dijelu postoji objekt (s kojim treba valuirati x u (ne Con)), koji doista jest kod konačnog niza čiji svaki element je ili kod neke instance aksioma PA (ne -PA!) ili postoje elementi prije njega iz kojih je izveden pravilom generalizacije ili modus ponensa, i čiji je zadnji element kod formule 0=0'. S obzirom na to da je -N (između ostalog) model za PA (svi aksiomi od PA su ujedno i aksiomi od -PA), prirodno je njegove elemente zvati "prirodni brojevi", zar ne? A onda se čini da smo u velikom problemu, jer smo upravo našli prirodan broj koji kodira dokaz 0=1 u PA.

Jesmo li time dokazali da je PA inkonzistentna? Nipošto. Primijetimo da smo ga našli u modelu za -PA. Ako je PA inkonzistentna, tada je i -PA inkonzistentna, pa nema model, pa smo cijelu priču pričali uprazno. Ali ono što priča definitivno pokazuje, je da moramo obratiti pažnju i na magloviti dio - jer nam je netko, da je bio baš jako zločest, umjesto "lijepe" strukture prirodnih brojeva N mogao podvaliti -N. S početka ne bismo primijetili ništa, jer -N jest model za PA. A ipak, -N tamo negdje "iza zavjese beskonačnosti" sadrži objekt koji pokazuje da je PA inkonzistentna.

Sad se vjerojatno osjećaš još više prevarenim - pobogu, kako isti swindle ne prolazi za očito konzistentne teorije, poput one gornje teorije Triv? Kvaka je u prvom koraku. Drugi Gödelov teorem ne prolazi za prejednostavne teorije - između ostalog i zato što u njima nema smislenog pojma kodiranja jezika, formula i dokaza, pomoću kojeg se može konstruirati formula koja iskazuje konzistentnost. Čak ni beskonačnost modela nije dovoljan uvjet: recimo Presburgerova aritmetika, koja je otprilike "PA bez množenja", je odlučiva i time dokazivo konzistentna, a ima samo beskonačne modele. Ali je svakako nužan uvjet: svaki konačan model je u potpunosti opisiv s konačno mnogo formula.

Eto, mislim da ti je ovo pokazalo koliko "model od PA" može biti netrivijalna beštija. Naravno, ako imaš ZF, onda imaš aksiom beskonačnosti, koji više-manje kaže "postoji model za PA". Ali to je varanje - u smislu da si samo konzistentnost jedne teorije sveo na konzistentnost puno jače teorije. S druge strane, ako si platonist, onda vjerojatno vjeruješ u strukturu N neovisno o našoj spoznaji nje, PA je samo naša nesavršena sjena nastala pokušajem da je spoznamo, i ako nije konzistentna, to je samo jer nismo u potpunosti uspjeli. No u matematičkom platonizmu je izuzetno teško biti dosljedan: recimo, hardcore platonisti vjerojatno vjeruju i u _the_ kumulativnu hijerarhiju H, čiji je ZF samo neprecizni pokušaj spoznaje. No čujem da se baš i ne mogu složiti vrijedi li hipoteza kontinuuma u strukturi H. ;-D

Ograničenje na slobodne varijable

> U TS skripti u odjeljku "Pokrate i proširenja jezika", zašto u "postoji jedinstven x phi", tj. u onome za što je to pokrata, tražimo da y ne bude slobodna u phi?

Uzmite φ:=(𝒙∈𝒚). Tada biste očito htjeli da ψ:=∃!𝒙φ znači "𝒚 je jednočlan", a jednočlani skupovi postoje, pa to nije univerzalno lažna tvrdnja.

No ako biste to raspisali kao ∃𝒚∀𝒙(𝒙=𝒚↔φ), relativno se lako vidi da to jest univerzalno lažna tvrdnja (dokažite za vježbu). Dakle nije ekvivalentna onom što smo htjeli formalizirati.

To je skroz formalni odgovor, koji Vas možda zadovoljava a možda i ne -- možda mislite da samo treba malo drugačije sintaksno iskazati tu pokratu, i bit će u redu. To nije istina, i vidi se ovako: φ ima dvije slobodne varijable, 𝒙 i 𝒚. Ako vežete 𝒙 kvantifikatorom jedinstvene egzistencije, i dalje varijabla 𝒚 mora ostati slobodna. Dakle formula ψ "ovisi" o 𝒚, u smislu da govori o nekom konkretnom objektu označenom varijablom 𝒚. No ovaj raspis o kojem govorimo veže varijablu 𝒚, pa ne "ovisi" o konkretnom 𝒚.

Postoje samo dva načina kako to možemo razriješiti. Jedan je da ne vežemo nijednu varijablu osim 𝒙 u raspisu, no kako očito moramo govoriti o dvomjesnoj relaciji jednakosti, nije jasno kako to napraviti bez uvođenja nove varijable. To ne mora biti 𝒚, može biti recimo 𝒛 -- ali tada, ako je 𝒛 vezana, imamo isti problem s formulom 𝒙∈𝒛; a ako je slobodna u raspisu, odjednom raspis ovisi o nekom objektu o kojem pokrata uopće ne govori (imamo isti problem s druge strane).

Drugi način je da se pomirimo s tim da će raspis pored 𝒙 vezati još neku varijablu, recimo 𝒚, ali onda moramo zahtijevati da ta varijabla ne smije biti slobodna u φ, jer očito neće biti slobodna u pokrati.

Također, "𝒚 nije slobodna u φ" ne valja gledati kao na ograničenje na φ, već je bolje to gledati kao ograničenje na 𝒚. U smislu, nađemo neku varijablu koja se ne pojavljuje u φ, recimo (BSOMP) da je to 𝒚, i onda shvatimo ψ kao pokratu za formulu s tom varijablom. [To je osnovni razlog zašto zahtijevamo beskonačno mnogo varijabli -- sve što nam zapravo treba je da uvijek postoji "nova" varijabla koju možemo uzeti.]

Dakle, naravno da mi znamo i što znači ∃!𝒙(𝒙∈𝒚) [i naravno da zapravo nisam pazio na to ograničenje kasnije:], samo što stroga formalizacija toga zahtijeva suptilnije alate od ovih koje trenutno imamo.

Apsorpcija binomnih koeficijenata

> Jel bi mi mogao pojasniti Veljanov dokaz svojstva apsorpcije binomnih
> koeficijenata, mislim strana 66. u novoj knjizi. Iako mi je samo
> svojstvo kombinatorno jasno (bar se nadam - od n objekata mozemo
> izabrati r na n povrh r nacina ili prvo mozemo izabrati jednog na n
> nacina, a onda od preostalih n-1 jos na r-1 nacina. Buduci da poredak
> nije vazan, dobit cemo r istih odabira (jer smo prvo mogli izabrati
> prvi, pa drugi, .. pa r-ti), pa jos podijelimo sa r i to je to.
>
> On uspostavlja neku fantomsku bijekciju za koju tvrdi da stima, a ja
> bih htio razumjeti i formalno matematicki dokaz jer ipak treba znati
> na taj nacin razmisljati.

Pa... treba se znati tako izražavati, jer si onda siguran da je ono što intuitivno misliš istina. No naravno da je stvar zapravo ovo što si ti opisao, samo preciznije. :-)

Dakle, prvo što treba razjasniti je da u kombinatornim interpretacijama nema razlomaka -- bar ne onih netrivijalnih. :-) Dakle, da bi dokazao (n#r)=n/r*(n-1#r-1) , ide prvo to pretvoriti u manifestno prirodne brojeve, kako bi znao to interpretirati kao kardinalne brojeve nekih skupova (npr. desna strana bi mogla značiti Kartezijev produkt, ali prvi faktor mu očito ne može imati n/r elemenata, ako r(!|)n ).

So, pomnoži s r i dobije r*(n#r)=n*(n-1#r-1) . Sad može obje strane jednakosti interpretirati kao kardinalnosti konačnih skupova, preciznije Kartezijevih produkata. Što je na lijevoj strani? Uređeni parovi (a, A), gdje je A@([n]#r) te a@A. Drugim riječima, broji r-člane podskupove od [n], svaki skupa s nekim njegovim istaknutim elementom.

Što je na desnoj strani? Uređeni parovi (b, B), gdje je (na prvi pogled) B@([n-1]#r-1) te b@[n]. No ovaj [n-1] je malo šašav... zašto bismo izbacivali baš n iz [n]? Puno je bolje izbaciti neki koji već imamo, konkretno b. (Primijeti da je i na lijevoj strani veza između a i A, samo je tamo pozitivna a@A. Ovdje je negativna b(!@)B.) Dakle, zapravo, na desnoj strani brojimo (b, B) takve da je b@[n] i B@([n]\{b}#r-1).

Sad stvarno nije teško vidjeti bijekciju. Ako ti netko da (a, A), gdje A ima r elemenata među kojima je a, ti vratiš (a, A\{a}) -- to je očito par kojem drugi član ima r-1 elemenata među kojima nije prvi član (a). U suprotnom smjeru, ako ti netko da (b, B) gdje B ima r-1 elemenata među kojima nije b, vratiš (b, BU{b}) -- i to je očito na lijevoj strani.

Ta dva preslikavanja su jedno drugom inverzi (ako ubaciš b pa ga izbaciš, dobit ćeš isto ako b nije bio na početku unutra, a isto tako ako izbaciš a koji jest unutra pa ga vratiš, dobit ćeš isto), pa su bijekcije odnosno broj elemenata lijevog skupa jednak je broju elemenata desnog. Kved.