Izračunljivost 1-mnogostrukosti

disertacija

• Naslov (engleski): Computability of 1-manifolds
• Autor: Konrad Burnik
• Mentor: Zvonko Iljazović (mentor)
• Član povjerenstva: Mladen Vuković (predsjednik povjerenstva)
• Član povjerenstva: Zvonko Iljazović (član povjerenstva)
• Član povjerenstva: Šime Ungar (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2015-12-16, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika
• Univerzalna decimalna klasifikacija (UDC): 51 - Matematika

Sažetak

Glavni problem kojim se bavimo u ovom radu je utvrditi vrijedi li neki analogon implikacije koja je dokazana u [9] za poluizračunljive kompaktne mnogostrukosti M i koja glasi \(\partial M\) izračunljivo kompaktan \(\Rightarrow M\) izračunljivo kompaktan \((\star)\) također i za \(M\) koji je 1-mnogostrukost u nekom izračunljivom metričkom prostoru. U uvodnom poglavlju dajemo pregled dosadašnjih rezultata vezanih za implikaciju \((\star)\). U poglavlju 2 dajemo pregled osnovnih pojmova iz klasične teorije izračunljivosti koje koristimo u ostatku rada. U poglavlju 3 poopćujemo pojam izračunljivosti na metričke prostore. Izračunljiv metrički prostor je glavni ambijent u kojem iskazujemo i dokazujemo glavne rezultate. Poglavlje 4 je pripremno poglavlje. U njemu uvodimo pojmove formalne izračunljivosti usko vezane za izračunljive metričke prostore. Svojstvo efektivnog pokrivanja, zajedno sa svojstvom da izračunljiv metrički prostor ima kompaktne zatvorene kugle pokazuje se ključno ako želimo dokazati da je korekurzivno prebrojiva zraka s izračunljivom krajnjom točkom izračunljiva. Dovoljan uvjet da metrički prostor ima svojstvo efektivnog pokrivanja iskazujemo i dokazujemo u poglavlju 5. Na kraju tog poglavlja raspisujemo i dokaz da \(\mathbb{R}^n\) ima svojstvo efektivnog pokrivanja. Pokazuje se da svojstvo efektivnog pokrivanja nije uvijek nužno kako bi dokazali implikaciju \((\star)\). Stoga u poglavlju 6 uvodimo pojmove poluizračunljivo kompaktan na zatvorenim kuglama i izračunljivo kompaktan na zatvorenim kuglama. U slučaju kada ambijentni prostor ima svojstvo efektivnog pokrivanja i kompaktne zatvorene kugle tada je svojstvo poluizračunljive kompaktnosti na zatvorenim kuglama ekvivalentno sa svojstvom korekurzivno prebrojive zatvorenosti skupa. Svojstvo efektivnog pokrivanja i svojstvo da prostor ima kompaktne zatvorene kugle vrijede uniformno u čitavom prostoru i kao takva su jaka svojstva, no kako bi dobili općenitije rezultate mi ih zamjenjujemo sa svojstvima koje vrijede samo lokalno, na nekim podskupovima prostora, dakle svojstvom izračunljive kompaktnosti na zatvorenim kuglama. Stoga rezultate za topološku zraku te za topološku liniju iskazujemo i dokazujemo bez pretpostavke da ambijentni prostor ima svojstvo efektivnog pokrivanja i kompaktne zatvorene kugle. U poglavlju 7 dajemo dokaz glavnog rezultata za topološku zraku, a u poglavlju 8 sličan rezultat dokazujemo za topološku liniju. U poglavlju 9 proučavamo nužnost dodatnih uvjeta na ambijentni prostor kao što su svojstvo efektivnog pokrivanja te kompaktne zatvorene kugle, te dajemo primjere prostora koji pokazuju da u slučaju da izračunljiv metrički prostor ima samo jedno od ta dva svojstva da tada zaista mora imati i drugo (i obratno) kako bi dobili rezultate iskazane korolarima iz poglavlja 7 i 8. Zajedno s već poznatim rezultatima o izračunljivosti za lančaste i cirkularno lančaste kontinuume iz [6], rezultati iz poglavlja za topološku zraku i liniju doveli su do pitanja izračunljivosti 1-mnogostrukosti što je glavna tema ovog rada. U poglavlju 10 proučavamo 1-mnogostrukosti u izračunljivim metričkim prostorima i dokazujemo glavni rezultat ovog rada: svaka poluizračunljivo kompaktna na zatvorenim kuglama 1-mnogostrukost čiji rub je poluizračunljiv i koja ima konačno mnogo komponenata povezanosti je izračunljivo kompaktna na zatvorenim kuglama.

Sažetak (engleski)

In this paper we investigate whether some analogue of the implication that was proved in [9] for semi-computable compact manifolds M and which states \(\partial M\) computably compact \(\Rightarrow M\) computably compact \((\star)\) also holds when \(M\) is a 1-manifold in some computable metric space. In the first introductory chapter we give an overview of the known results regarding the implication \((\star)\). In chapter 2 we give an overview of the basic notions from classic computability theory which we use in subsequent chapters. In chapter 3 we generalize computability to metric spaces. A computable metric space is the main ambient space in which we state and prove our main results. Chapter 4 is preparatory. In this chapter, we introduce the notions of formal computability properties occurring in computable metric spaces. The effective covering property, together with the property of compact closed balls is shown to be key if we want to prove that each co-recursively enumerable topological ray with a computable endpoint is computable. A sufficient condition when a metric space has the effective covering property [6] is stated and proved in chapter 5. At the end of that chapter, we write out a proof that \(\mathbb{R}^n\) has the effective covering property. It turns out that the effective covering property is not always necessary to prove the main implication \((\star)\). Therefore, in chapter 6 we introduce new notions of semi-computable compact on closed balls and computable compact on closed balls. In the case when the ambient space does have the effective covering property and compact closed balls, then the notion of semi-computable compact on closed balls is equivalent to the notion of corecursively enumerable set. The effective covering property and the property of having compact closed balls are properties that hold uniformly in the whole space, which are strong assumptions, so to obtain more general results we had replaced them with a local property of semi-computable compactness on closed balls. Therefore, the main results for the topological ray and line we state and prove without the assumption on the ambient space that it has the effective covering property and compact closed balls and instead we use the newly introduced notions. In chapter 7 we give the proof of the main result for the topological ray and in chapter 8 we prove a similar result for the topological line. In chapter 9 we study further the necessity of additional conditions on the ambient space. We give examples of spaces which show that in case the computable metric space has exactly one of the two additional conditions then the conclusions of chapters 7 and 8 fail to be true. Together with the well known results on computability of chainable and circularly chainable continua given in [6], the results for the topological ray and line have led us to the main result of this thesis, the computability of 1-manifolds. In the final chapter 10 we study the computability of 1-manifolds in computable metric spaces and prove the main result of this thesis: every semicomputable compact on closed balls 1-manifold with computable boundary and finitely many connected components is computable compact on closed balls.

• Ključne riječi: poluizračunljive kompaktne mnogostrukosti; klasična teorija izračunljivosti; izračunljiv metrički prostor
• Ključne riječi (engleski): semi-computable compact manifolds; classic computability theory; computable metric space
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:594704
• Studijski program: Naziv: Matematika; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski doktorski; Akademski / stručni naziv: doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika (dr. sc.)
• Vrsta resursa: Tekst
• Opseg: iv, 118 str.
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-03-07 12:26:56