Seminar za matematičku logiku i osnove matematike

lokacija: 
PMF Matematički odsjek
vrijeme: 
30.01.2017 - 17:00 - 18:00

Na Seminaru za matematičku logiku i osnove matematike, u ponedjeljak 30.
siječnja 2017. u 17 sati, u predavaonici 104, PMF-MO,
Lucija Validžić će
održati predavanje
Maksimalne strukture izračunljivosti

Sažetak: Struktura izračunljivosti \( S \) na metričkom prostoru \( (X,d) \) je skup nizova u \( X \) koji ima sljedeća svojstva: (i) ako su \( (x_i),(y_i) \in S \), tada je funkcija \( (i,j) \mapsto d(x_i,y_j) \) rekurzivna \( \mathbb{N}^2 \to \mathbb{R} \); (ii) ako je \( (x_i) \in S \) i \( (y_i) \) niz u \( X \) takav da postoji rekurzivna funkcija \( F: \mathbb{N}^2 \to \mathbb{N} \) takva da je \( d(y_i,x_{F(i,k)}) < 2^{-k} \), za sve \( i,k \in \mathbb{N} \), tada je \( (y_i) \in S \).
Ukoliko \( S \) sadrži niz \( \alpha \) koji je gust u \( (X,d) \), reći ćemo da je \( S \) separabilna. Pokazuje se da je tada \( (X,d,\alpha ) \) izračunljiv metrički prostor, a \( S \) je upravo skup svih izračunljivih nizova u \( (X,d,\alpha ) \). Također, za proizvoljni izračunljiv
metrički prostor \( (X,d,\alpha ) \) , skup svih izračunljivih nizova u \( (X,d,\alpha ) \) je separabilna struktura izračunljivosti. Stoga vidimo da \( (X,d) \) možemo promatrati kao izračunljiv metrički prostor ako i samo ako postoji separabilna struktura izračunljivosti na \( (X,d) \). Na predavanju će nam od posebnog interesa biti maksimalne strukture izračunljivosti, odnosno stukture izračunljivosti koje su maksimalne obzirom na inkluziju.
Nije teško vidjeti da je svaka separabilna struktura izračunljivosti maksimalna, no obrat te tvrdnje općenito ne mora vrijediti. Budući da na proizvoljnom metričkom prostoru uvijek postoje maksimalne strukture izračunljivosti, prirodno je pitati se možemo li uz neke uvjete zaključiti da su neke od njih separabilne. Na predavanju ćemo se baviti tom problematikom u \( \mathbb{R}^n \). Detaljno ćemo okarakterizirati maksimalne strukture izračunljivosti na \( X \subseteq \mathbb{R}^n \) i pokazat ćemo da su strukture izračunljivosti koje su maksimalne na \( \mathbb{R}^n \) nužno separabilne. Nadalje, pomoću dobivenih rezultata odredit ćemo kardinalitet skupa svih separabilnih struktura izračunljivosti na segmentu u \( \mathbb{R} \).

Share this