Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputability on quasi-Polish spaces
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We investigate the effectivizations of several equivalent definitions of quasi-Polish spaces and study which characterizations hold effectively. Being a computable effectively open image of the Baire space is a robust notion that admits several characterizations. We show that some natural effectivizations of quasi-metric spaces are strictly stronger.
rate research
Read More
A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of Polish spaces. We show that there exists a $0$-computable low$_3$ Polish space which is not homeomorphic to a computable one, and that, for any natural number $n$, there exists a Polish space $X_n$ such that exactly the high$_{2n+3}$-degrees are required to present the homeomorphism type of $X_n$. We also show that no compact Polish space has an easiest presentation with respect to Turing reducibility.
Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to image distribution if and only if it has a random preimage. This result (for computable distributions and mappings, and Martin-Lof randomness) was known for a long time (folklore); in this paper we prove its natural generalization for layerwise computable mappings, and discuss the related quantitative results.
We present the (Lascar) Galois group of any countable theory as a quotient of a compact Polish group by an $F_sigma$ normal subgroup: in general, as a topological group, and under NIP, also in terms of Borel cardinality. This allows us to obtain similar results for arbitrary strong types defined on a single complete type over $emptyset$. As an easy conclusion of our main theorem, we get the main result from our recent paper joint with Andand Pillay, which says that for any strong type defined on a single complete type over $emptyset$, smoothness is equivalent to type-definability. We also explain how similar results are obtained in the case of bounded quotients of type-definable groups. This gives us a generalization of a former result from the aforementioned paper about bounded quotients of type-definable subgroups of definable groups.
A quasi-order $Q$ induces two natural quasi-orders on $P(Q)$, but if $Q$ is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq showed that moving from a well-quasi-order $Q$ to the quasi-orders on $P(Q)$ preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on $P(Q)$ are Noetherian, which means that they contain no infinite strictly descending sequences of closed sets. We analyze various theorems of the form if $Q$ is a well-quasi-order then a certain topology on (a subset of) $P(Q)$ is Noetherian in the style of reverse mathematics, proving that these theorems are equivalent to ACA_0 over RCA_0. To state these theorems in RCA_0 we introduce a new framework for dealing with second-countable topological spaces.
We study the computational content of the Radon-Nokodym theorem from measure theory in the framework of the representation approach to computable analysis. We define computable measurable spaces and canonical representations of the measures and the integrable functions on such spaces. For functions f,g on represented sets, f is W-reducible to g if f can be computed by applying the function g at most once. Let RN be the Radon-Nikodym operator on the space under consideration and let EC be the non-computable operator mapping every enumeration of a set of natural numbers to its characteristic function. We prove that for every computable measurable space, RN is W-reducible to EC, and we construct a computable measurable space for which EC is W-reducible to RN.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
