اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComputability on quasi-Polish spaces
73
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 s
pace 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 simi
lar 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 qu
asi-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 i
ntegrable 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
