Title Izračunljivost poopćenih grafova Title (english) Computability of generalized graphs Author Matea Jelić Mentor Zvonko Iljazović (mentor)Committee member Marko Horvat (predsjednik povjerenstva)Committee member Goran Erceg (član povjerenstva)Committee member Zvonko Iljazović (član povjerenstva)Committee member Vedran Čačić (član povjerenstva)Granter University of Zagreb Defense date and country 2023-12-07, Croatia Scientific / art field, NATURAL SCIENCES Universal decimal classificationUDC ) 51 - Mathematics Abstract U izračunljivom topološkom prostoru, svaki izračunljiv skup je ujedno i poluizračunljiv, ali obrat općenito ne vrijedi. Zato u ovom radu prvo proučavamo uvjete uz koje je spomenuti obrat istinit. Pri tome će topološka svojstva skupa biti od izrazite važnosti, što znači da ova disertacija spada u područje izračunljive analize, ali i topologije. Kasnije, proučavamo i uvjete uz koje se poluizračunljiv skup, budući da općenito nije izračunljiv, može aproksimirati nekim svojim izračunljivim podskupom do na zadanu točnost. Prvo se bavimo lančastim i cirkularno lančastim kontinuumima i njihovim utjecajem na izračunljive skupove. Točnije, pokazujemo da je poluizračunljiv skup T u nekom izračunljivom topološkom prostoru i izračunljiv ako je \(T = S \cup K_0 \cup \dots \cup K_n\), gdje je \(S\) izračunljiv skup, a \(K_0,...,K_n\) konačan niz lančastih ili cirkularno lančastih kontinuuma koji se sijeku, međusobno ili s \(S\), samo u krajnjim točkama (u slučaju lančastih kontinuuma) ili u jednoj fiksiranoj točki (u slučaju barem jednog cirkularno lančastog kontinuuma). Rezultat primijenjen na lukove i topološke kružnice alternativno iskazujemo koristeći terminologiju adjunkcijskih prostora. Nadalje, definiramo lančasti graf kao topološki prostor koji se može prikazati kao unija konačno mnogo izoliranih točaka i konačno mnogo lančastih kontinuuma takvih da se svaka dva različita kontinuuma sijeku u najviše konačno mnogo točaka. Pokazujemo da pojam lančastog grafa poopćuje pojam topološkog grafa i da je izračunljiv, uvjetno govoreći, svaki onaj lančasti graf koji je poluizračunljiv i čije su krajnje točke izračunljive (što je također vrijedilo i za topološke grafove). Taj se dokaz oslanja na činjenicu da za kontinuum \(K\) lančast od \(a\) do \(b\) i za neki \(c \in K\) te za proizvoljni \(\varepsilon > 0\) postoji netrivijalni kontinuum \(L \subseteq K\) takav da je \(c \in L\) i \(L \subseteq B(c,\varepsilon)\), koju također dokazujemo. Na kraju, tražimo uvjete uz koje se poluizračunljiv skup S može, do na zadanu točnost, aproksimirati nekim svojim izračunljivim podskupom \(\hat{S}\). Dokazujemo da se svaki poluizračunljiv kontinuum \(S\) lančast od \(a\) do \(b\), gdje je \(a\) izračunljiva točka, može po volji dobro aproksimirati nekim svojim izračunljivim potkontinuumom \(\hat{S}\) lančastim od \(a\) do \(c\), gdje je \(c\) izračunljiva točka. U tu svrhu koristimo niz relacija definiranih na skupu \(\mathbb{N}\), a rezultat iskazujemo i u izračunljivom metričkom prostoru koristeći Hausdorffovu metriku.
Abstract (english) Every computable set in an arbitrary computable topological space is also semicomputable, but reverse does not hold in general. Therefore, in this thesis we examine conditions which force a semicomputable set to be a computable one. Topological properties of a set are of a great importance, which means that this thesis belongs to the field of computable analysis, as well as topology. Later, we study the conditions under which every semicomputable set, since it is not computable in general, can be approximated by its computable subset for any given precision. Firstly, we examine chainable and circularly chainable continua and how can they impact computable sets. Actually, we show that a semicomputable set T in an arbitrary topological space is also computable if \(T = S \cup K_0 \cup \dots \cup K_n\), where \(S\) is a computable set and \(K_0,...,K_n\) a finite sequence of chainable or circularly chainable continua which intersect, one another or S, in endpoints (in case of chainable continua) or in one fixed point (in case of at least one circularly chainable continuum). The result applied to arcs and topological circles is also stated using terminology of adjunction spaces. Furthermore, we define the notion of a chainable graph as a topological space that can be expressed as the union of finitely many isolated points and finitely many chainable continua such that every two of them intersect in at most finitely many points. We show that a chainable graph generalizes a topological graph. Also, we prove that every semicomputable chainable graph with computable endpoints is computable (which is also true for topological graphs). The proof relies on a fact that for given continuum \(K\) chainable from \(a\) to \(b\) and arbitrary \(c \in K\) and \(\varepsilon > 0\), there exists a nontrivial continuum \(L \subseteq K\) such that \(c \in L\) and \(L \subseteq B(c,\varepsilon)\). We also prove the aforementioned statement. Finally, we examine the conditions under which a semicomputable set \(S\) can be, up to an arbitrary precision, approximated by some computable subset \(\hat{S}\). We prove that every semicomputable continuum \(S\) chainable from \(a\) to \(b\), where \(a\) is a computable point, can by approximated good enough with some computable subcontinuum \(\hat{S}\) chainable from \(a\) to \(c\), where \(c\) is a computable point. For that purpose we use relations defined on \(\mathbb{N}\), and we state the previous result using Hausdorff metric, as well.
Keywords
izračunljiv topološki prostor
lančasti kontinuum
cirkularno lančasti kontinuum
adjunkcijski prostor
izračunljiv tip
lančasti graf
\(\mathscr{U}\)–blizu
Keywords (english)
computable topological space
chainable continuum
circularly chainable continuum
adjunction space
computable type
chainable graph
\(\mathscr{U}\)–close
Language croatian URN:NBN urn:nbn:hr:217:528268 Promotion 2023 Study programme Title: Doctoral study Type of resource Text Extent viii, 94 str. File origin Born digital Access conditions Open access Terms of use Created on 2023-12-20 12:24:09
