Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn bi-embeddable categoricity of algebraic structures
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct a pair of structures which is learnable but no computable learner can learn it.
We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the class $mathbf{InfEx}_{cong}$, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures $mathfrak{K}$ is $mathbf{InfEx}_{cong}$-learnable if and only if the structures from $mathfrak{K}$ can be distinguished in terms of their $Sigma^{mathrm{inf}}_2$-theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
