Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDegrees of bi-embeddable categoricity of equivalence structures
89
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
In several classes of countable structures it is known that every hyperarithmetic structure has a computable presentation up to bi-embeddability. In this article we investigate the complexity of embeddings between bi-embeddable structures in two such classes, the classes of linear orders and Boolean algebras. We show that if $mathcal L$ is a computable linear order of Hausdorff rank $n$, then for every bi-embeddable copy of it there is an embedding computable in $2n-1$ jumps from the atomic diagrams. We furthermore show that this is the best one can do: Let $mathcal L$ be a computable linear order of Hausdorff rank $ngeq 1$, then $mathbf 0^{(2n-2)}$ does not compute embeddings between it and all its computable bi-embeddable copies. We obtain that for Boolean algebras which are not superatomic, there is no hyperarithmetic degree computing embeddings between all its computable bi-embeddable copies. On the other hand, if a computable Boolean algebra is superatomic, then there is a least computable ordinal $alpha$ such that $mathbf 0^{(alpha)}$ computes embeddings between all its computable bi-embeddable copies. The main technique used in this proof is a new variation of Ash and Knights pairs of structures theorem.
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.
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.
While most research in Gold-style learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In our core model the learner gets more and more information about which pairs of elements of a structure are related and which are not. The aim of the learner is to find (an effective description of) the isomorphism type of the structure presented in the limit. In accordance with language learning we call this learning criterion InfEx-learning (explanatory learning from informant). Our main contribution is a complete characterization of which families of equivalence structures are InfEx-learnable. This characterization allows us to derive a bound of $mathbf{0}$ on the computational complexity required to learn uniformly enumerable families of equivalence structures. We also investigate variants of InfEx-learning, including learning from text (where the only information provided is which elements are related, and not which elements are not related) and finite learning (where the first actual conjecture of the learner has to be correct). Finally, we show how learning families of structures relates to learning classes of languages by mapping learning tasks for structures to equivalent learning tasks for languages.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
