Na drugom Seminaru za matematičku logiku i računarstvo, u ponedjeljak 28. listopada 2024. u 17:15 sati, u predavaonici 201 (PMF-MO),

Vedran Čačić će održati predavanje

 

Ovjereni algoritam za stratifikaciju

 

Sažetak: Quineova teorija Novih temelja, obogaćena Jensenovim atomima, plodno je tlo za razvoj novih metoda bavljenja matematikom u suradnji čovjeka i računala, budući da objedinjuje ljudsku intuiciju teorije skupova s računalnom strogošću teorije tipova. Osnovni alat za postizanje toga je definicija novih pojmova kao skupova, koristeći komprehenziju po stratificiranim formulama. Ipak, potreba za iteriranjem takve konstrukcije (novi pojmovi često se definiraju koristeći već prethodno definirane pojmove) iziskuje karakterizaciju stratificiranih formula obogaćenih termima dobivenih komprehenzijama.

 

Tri su uobičajena pristupa: eliminacija (svođenjem na osnovne formule), pridjeljivanje tipova (shvaćajući ih kao nove varijable s posebnim uvjetima stratifikacije) i imenovanje (proširenjem signature novim konstantskim i funkcijskim simbolima). Prije dvije godine pojavila se ideja usklađivanja ta tri pristupa, pokazujući da svi vode do "istog" skupa stratificiranih formula u proširenom jeziku.

 

Na studijskom boravku u Edinburghu, u suradnji s Markom Dokom razvijen je ovjereni (formalno dokazano korektni) algoritam za stratifikaciju, i dokazano je da (do na zanimljiv izuzetak s konstantskim termima) eliminacija komprehenzijskih terma vodi do istih stratificiranih formula kao njihova tipizacija. Na seminaru će biti prikazani ti rezultati.