اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn bi-embeddable categoricity of algebraic structures
113
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 catego
ricity. 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 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.
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 n
eeded 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 whos
e 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 e
very 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
