Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDegrees that are not degrees of categoricity
196
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
A computable structure $mathcal{A}$ has degree of categoricity $mathbf{d}$ if $mathbf{d}$ is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of $mathcal{A}$. Fokina, Kalimullin, and Miller showed that every degree d.c.e. in and above $mathbf{0}^{(n)}$, for any $n < omega$, and also the degree $mathbf{0}^{(omega)}$, are degrees of categoricity. Later, Csima, Franklin, and Shore showed that every degree $mathbf{0}^{(alpha)}$ for any computable ordinal $alpha$, and every degree d.c.e. in and above $mathbf{0}^{(alpha)}$ for any successor ordinal $alpha$, is a degree of categoricity. We show that every degree c.e. in and above $mathbf{0}^{(alpha)}$, for $alpha$ a limit ordinal, is a degree of categoricity. We also show that every degree c.e. in and above $mathbf{0}^{(omega)}$ is the degree of categoricity of a prime model, making progress towards a question of Bazhenov and Marchuk.
We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) $Delta^0_alpha$ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of $Delta^0_alpha$ bi-embeddable categoricity and relative $Delta^0_alpha$ bi-embeddable categoricity coincide for equivalence structures for $alpha=1,2,3$. We also prove that computable equivalence structures have degree of bi-embeddable categoricity $mathbf{0},mathbf{0}$, or $mathbf{0}$. We obtain results on index sets of computable equivalence structure with respect to bi-embeddability.
Let $I_A$ be a toric ideal. We prove that the degrees of the elements of the Graver basis of $I_A$ are not polynomially bounded by the true degrees of the circuits of $I_A$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
