اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComparing the degrees of enumerability and the closed Medvedev degrees
94
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We compare the degrees of enumerability and the closed Medvedev degrees and find that many situations occur. There are nonzero closed degrees that do not bound nonzero degrees of enumerability, there are nonzero degrees of enumerability that do not bound nonzero closed degrees, and there are degrees that are nontrivially both degrees of enumerability and closed degrees. We also show that the compact degrees of enumerability exactly correspond to the cototal enumeration degrees.
قيم البحث
اقرأ أيضاً
An element $a$ of a lattice cups to an element $b > a$ if there is a $c < b$ such that $a cup c = b$. An element of a lattice has the cupping property if it cups to every element above it. We prove that there are non-zero honest elementary degrees th
at do not have the cupping property, which answers a question of Kristiansen, Schlage-Puchta, and Weiermann. In fact, we show that if $mathbf b$ is a sufficiently large honest elementary degree, then there is a non-zero honest elementary degree $mathbf a <_{mathrm E} mathbf b$ that does not cup to $mathbf b$. For comparison, we modify a result of Cai to show that in sever
A computable structure A is x-computably categorical for some Turing degree x, if for every computable structure B isomorphic to A there is an isomorphism f:B -> A with f computable in x. A degree x is a degree of categoricity if there is a computabl
e A such that A is x-computably categorical, and for all y, if A is y-computably categorical then y computes x. We construct a Sigma_2 set whose degree is not a degree of categoricity. We also demonstrate a large class of degrees that are not degrees of categoricity by showing that every degree of a set which is 2-generic relative to some perfect tree is not a degree of categoricity. Finally, we prove that every noncomputable hyperimmune-free degree is not a degree of categoricity.
The Posner-Robinson Theorem states that for any reals $Z$ and $A$ such that $Z oplus 0 leq_mathrm{T} A$ and $0 <_mathrm{T} Z$, there exists $B$ such that $A equiv_mathrm{T} B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus 0$. Consequently, any non
zero Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a Turing jump relative to some $B$. Here we prove the hyperarithmetical analog, based on an unpublished proof of Slaman, namely that for any reals $Z$ and $A$ such that $Z oplus mathcal{O} leq_mathrm{T} A$ and $0 <_mathrm{HYP} Z$, there exists $B$ such that $A equiv_mathrm{T} mathcal{O}^B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus mathcal{O}$. As an analogous consequence, any nonhyperarithmetical Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a hyperjump relative to some $B$.
We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure $mathcal A$ as the family of Turing degrees that compute embeddings b
etween any computable bi-embeddable copies of $mathcal A$; the degree of bi-embeddable categoricity of $mathcal A$ is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and we show that every degree d.c.e. above $mathbf{0}^{(alpha)}$ for $alpha$ a computable successor ordinal and $mathbf{0}^{(lambda)}$ for $lambda$ a computable limit ordinal is a degree of bi-embeddable categoricity. We also give examples of families of degrees that are not bi-embeddable categoricity spectra.
We study pairs of reals that are mutually Martin-L{o}f random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgens Theorem holds for non-computable probability measures, too. W
e study, for a given real $A$, the emph{independence spectrum} of $A$, the set of all $B$ so that there exists a probability measure $mu$ so that $mu{A,B} = 0$ and $(A,B)$ is $mutimesmu$-random. We prove that if $A$ is r.e., then no $Delta^0_2$ set is in the independence spectrum of $A$. We obtain applications of this fact to PA degrees. In particular, we show that if $A$ is r.e. and $P$ is of PA degree so that $P otgeq_{T} A$, then $A oplus P geq_{T} 0$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
