Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHonest elementary degrees and degrees of relative provability without the cupping property
111
0
0.0
(
0
)
Authors
Paul Shafer
Ask ChatGPT about the research
No Arabic abstract
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 that 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
rate research
Read More
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. We 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$.
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.
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 computable 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 nonzero 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 between 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
