Na Seminaru za matematičku logiku i osnove matematike i Seminaru za
topologiju, u utorak 13. lipnja 2017. u 14 sati, u predavaonici 002,
PMF-MO, Bojan Pažek će održati predavanje i javnu obranu teme doktorske
disertacije
Izračunljivost skupova s nepovezanim komplementima

*Sažetak:* U izračunljivom metričkom prostoru korekurzivno prebrojiv
(zatvoren) skup S ne treba biti izračunljiv. Štoviše, ne mora niti
sadržavati izračunljivu točku. Ispostavlja se ipak da ovdje topologija može
igrati važnu ulogu. Ako skupu S dodamo neka topološka svojstva onda nam ta
svojstva mogu omogućiti da korekurzivno prebrojiv skup S postane
izračunljiv. Općenito je poznato da u izračunljivom metričkom prostoru
(X,d,α), koji ima svojstvo efektivnog pokrivanja te svojstvo da su u njemu
sve zatvorene kugle ujedno i povezane, svaki korekurzivno prebrojiv podskup
S od X, koji ima svojstvo da na efektivan način možemo razlikovati
komponenete povezanosti skupa X \ S i da svaka točka skupa S leži na rubu
barem dvije komponenete povezanosti od X \ S, mora biti i izračunljiv. Mi
ćemo se fokusirati na slučaj kada je izračunljiv metrički prostor
(X,d,α) *efektivno
lokalno povezan *te kada možemo na efektivan način razlikovati komponente
povezanosti komplementa korekurzivno prebrojivog skupa S. Opisat ćemo
rezultat koji pokazuje da prethodno navedena tvrdnja također vrijedi bez
navedenih pretpostavki na izračunljiv metrički prostor (X,d,α), ako
pretpostavimo da je promatrani prostor (X,d,α) efektivno lokalno povezan.

Nadalje, na seminaru će se opisati tvrdnja koja poopćava takozvanu
izračunljivu verziju teorema srednje vrijednosti. Konkretno, promatrat će
se izračunljiv metrički prostor (X,d,α) i u dva njemu disjunktna i
izračunljivo prebrojiva skupa U i V te izračunljiv kontinuum K koji siječe
oba skupa U i V. Ako se sada skup W definira kao unija skupova U i V, a
skup S kao komplement skupa W, onda je dovoljan uvjet da presjek skupa K sa
skupom S sadrži izračunljivu točku to da je K luk. Opisat će se i
općenitiji slučaj kada je skup K lančasti kontinuum i obrazložit će se da u
tom slučaju presjek skupa K sa skupom S sadrži izračunljivu točku ako je
taj isti promatrani presjek *totalno nepovezan*. Također će se pokušati
ovaj problem opisati i u slučaju kada na promatrani presjek maknemo
pretpostavku totalne nepovezanosti.

Seminar će se završiti proučavanjem uvjeta uz koje poluizračunljiv skup u
izračunljivom metričkom prostoru postaje izračunljiv. Koncentrirat ćemo se
na proučavanje poluizračunljivog (topološkog) Varšavskog diska i njegova
ruba Varšavske kružnice. Predočit će se rezultat koji kaže da
poluizračunljiv Varšavski disk postaje izračunljiv ako je njegov rub,
Varšavska kružnica, poluizračunljiv skup.