Naslov Jedinstvenost struktura izračunljivosti Naslov (engleski) Uniqueness of computability structures Autor Lucija Validžić Mentor Zvonko Iljazović (mentor)Član povjerenstva Marko Horvat (predsjednik povjerenstva)Član povjerenstva Zvonko Iljazović (član povjerenstva)Član povjerenstva Tin Perkov (član povjerenstva)Član povjerenstva Vedran Čačić (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2022-05-20, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Univerzalna decimalna klasifikacijaUDC ) 51 - Matematika Sažetak Struktura izračunljivosti na metričkom prostoru je skup nizova s određenim svojstvima koji nam omogućava da klasične koncepte teorije izračunljivosti prenesemo u proizvoljan metrički prostor. U disertaciji će poseban naglasak biti na strukturama izračunljivosti koje su maksimalne s obzirom na inkluziju te strukturama izračunljivosti koje sadrže gust niz, to jest separabilnim strukturama izračunljivosti. Svaka separabilna struktura izračunljivosti je maksimalna, no obrat općenito ne vrijedi. U radu će se precizno opisati maksimalne strukture na euklidskom prostoru \(\mathbb{R}^n\) te će biti dokazano da je svaka maksimalna struktura izračunljivosti na nekom podskupu od \(\mathbb{R}^n\) zapravo izometrična slika strukture izračunljivosti koja se sastoji od izračunljivih nizova u \(\mathbb{R}^n\), to jest kanonske strukture izračunljivosti. Iz te veze maksimalnih i kanonskih struktura slijedit će da je svaka maksimalna struktura izračunljivosti na \(\mathbb{R}^n\) separabilna. Nadalje, u disertaciji ćemo se fokusirati i na pronalaženje uvjeta pod kojima je separabilna struktura izračunljivosti na metričkom prostoru jedinstvena ili jedinstvena do na izometriju. Pri tome ćemo se ograničiti na efektivno kompaktne metričke prostore. Općenito pitanje je povlači li efektivna kompaktnost metričkog prostora njegovu izračunljivu kategoričnost. Poznato je da je odgovor potvrdan u slučaju kada postoji samo konačno mnogo izometrija tog prostora. U disertaciji ćemo taj rezultat proširiti dokazom da ako dva efektivna separirajuća niza dijele izračunljiv skup za koji postoji samo konačno mnogo izometrija prostora koje ga fiksiraju, tada ta dva niza moraju biti ekvivalentna. Osim toga, dokazat ćemo da je orbita izračunljive točke pri djelovanju grupe izometrija koizračunljivo prebrojiv skup te ćemo to iskoristiti kako bismo dokazali da su određeni efektivno kompaktni podskupovi euklidskog prostora izračunljivo kategorični. Iz tih rezultata slijedit će da na podskupovima od \(\mathbb{R}^2\) i \(\mathbb{R}^3\) efektivna kompaktnost zaista povlači izračunljivu kategoričnost. Na kraju ćemo se baviti prostorima koji su efektivno kompaktni čim na njima postoji efektivan separirajući niz, to jest kategorički efektivno kompaktnim prostorima. Pokazat ćemo kako je pitanje kategoričke efektivne kompaktnosti povezano s pitanjem povlači li izračunljiva prebrojivost skupa njegovu izračunljivost te ćemo dokazati kategoričku efektivnu kompaktnost rubova otvorenih omeđenih konveksnih skupova u \(\mathbb{R}^n\)
Sažetak (engleski) A computability structure on a metric space is a set of sequences with certain properties that enables us to introduce classical concepts of computability theory into an arbitrary metric space. In the dissertation, special emphasis will be on computability structures that are maximal with respect to inclusion and computability structures that contain a dense sequence, i.e. separable computability structures. Any separable computability structure is maximal, but the converse is in general not true. In the dissertation, maximal computability structures on Euclidean space \(\mathbb{R}^n\) will be described precisely and it will be proved that any maximal computability structure on a subset of \(\mathbb{R}^n\) is actually an isometric image of the computability structure which consists of computable sequences in \(\mathbb{R}^n\), i.e. canonical computability structure. From that bond between maximal and canonical computability structures, it will follow that any maximal computability structure on \(\mathbb{R}^n\) is separable. We will also focus on finding the conditions under which a separable computability structure on a metric space is unique or unique up to an isometry. In doing so, we will limit ourselves to effectively compact metric spaces. A general question is whether effective compactness of a metric space implies its computable categoricity. It is known that this implication is true for metric spaces which have only finitely many isometries. In the dissertation we will expand that result with the fact that if two effective separating sequences share a computable set which has the property that there are only finitely many isometries of the underlying space which fix that set, then the sequences have to be equivalent. Moreover, we will prove that the orbit of a computable point under the isometry group is a co-computably enumerable set and we will use this to prove that certain effectively compact subsets of Euclidean space are computably categorical. From these results, it will follow that in \(\mathbb{R}^2\) and \(\mathbb{R}^3\) effective compactness implies computable categoricity. Lastly, we will examine spaces which are effectively compact if they contain at least one effective separating sequence, i.e. categorically effectively compact spaces. We will show how the question of categorical effective compactness is connected to the question whether computable enumarability of a set implies its computability and we will show categorical effective compactness for boundaries of open bounded convex subsets of \(\mathbb{R}^n\).
Ključne riječi
izračunljiv metrički prostor
efektivan separirajući niz
struktura izračunljivosti
separabilna struktura izračunljivosti
maksimalna struktura izračunljivosti
izračunljivo kategoričan metrički prostor
kategorički efektivno kompaktan metrički prostor
Ključne riječi (engleski)
computable metric space
effective separating sequence
computability structure
separable computability structure
maximal computability structure
computably categorical metric space
categorically effectively compact metric space
Jezik hrvatski URN:NBN urn:nbn:hr:217:099599 Datum promocije 2022 Studijski program Naziv: Matematika Vrsta resursa Tekst Opseg vii, 104 str. Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2022-06-15 06:56:39
