Search

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers ω , having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak precompleteness of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for Δ 2 0 equivalence relations, starting with the Π 2 - 1 level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree d , there exists a weakly precomplete c.e. equivalence E admitting a d -computable diagonal function. We observe that a Turing degree d can compute a diagonal function for every Δ 2 0 equivalence relation E if and only if d computes 0 ′ . On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if d computes diagonal functions for all c.e. E, then d must be a DNC degree. [ABSTRACT FROM AUTHOR]

The paper studies Heyting algebras within the framework of computable structure theory. We prove that the class K containing all Heyting algebras with distinguished atoms and coatoms is complete in the sense of the work of Hirschfeldt et al. (Ann Pure Appl Logic 115(1-3):71-113, 2002). This shows that the class K is rich from the computability-theoretic point of view: for example, every possible degree spectrum can be realized by a countable structure from K. In addition, there is no simple syntactic characterization of computably categorical members of K (i.e., structures from K possessing a unique computable copy, up to computable isomorphisms). [ABSTRACT FROM AUTHOR]

For a non-zero natural number n, we work with finitary Σ n 0 -formulas ψ (x) without parameters. We consider computable structures S such that the domain of S has infinitely many Σ n 0 -definable subsets. Following Goncharov and Kogabaev, we say that an infinite list of Σ n 0 -formulas is a Σ n 0 -classification for S if the list enumerates all Σ n 0 -definable subsets of S without repetitions. We show that an arbitrary computable S always has a 0 (n) -computable Σ n 0 -classification. On the other hand, we prove that this bound is sharp: we build a computable structure with no 0 (n - 1) -computable Σ n 0 -classifications. [ABSTRACT FROM AUTHOR]

Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies limit computable sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice. In this paper, we combine the Ershov Hierarchy and fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. [ABSTRACT FROM AUTHOR]

We investigate the degree spectra of computable relations on canonically ordered natural numbers (ω,<)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\omega ,<)$$\end{document} and integers (ζ,<)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\zeta ,<)$$\end{document}. As for (ω,<)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\omega ,<)$$\end{document}, we provide several criteria that fix the degree spectrum of a computable relation to all c.e. or to all Δ2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Delta _2$$\end{document} degrees; this includes the complete characterization of the degree spectra of so-called computable block functions that have only finitely many types of blocks. Compared to Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022), we obtain a more general solution to the problem regarding possible degree spectra on (ω,<)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\omega ,<)$$\end{document}, answering the question whether there are infinitely many such spectra. As for (ζ,<)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\zeta ,<)$$\end{document}, we prove the following dichotomy result: given an arbitrary computable relation R on (ζ,<)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\zeta ,<)$$\end{document}, its degree spectrum is either trivial or it contains all c.e. degrees. This result, and the proof techniques required to solve it, extend the analogous theorem for (ω,<)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\omega ,<)$$\end{document} obtained by Wright (Computability 7:349–365, 2018), and provide initial insight to Wright’s question whether such a dichotomy holds on computable ill-founded linear orders. This article is an extended version of Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022). [ABSTRACT FROM AUTHOR]

Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ⩽ c . This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the Δ 2 0 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by ⩽ c on the Σ a - 1 \ Π a - 1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees. [ABSTRACT FROM AUTHOR]

We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) Δ α 0 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 Δ α 0 bi-embeddable categoricity and relative Δ α 0 bi-embeddable categoricity coincide for equivalence structures for α = 1 , 2 , 3 . We also prove that computable equivalence structures have degree of bi-embeddable categoricity 0 , 0 ′ , or 0 ′ ′ . We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability. [ABSTRACT FROM AUTHOR]

A major theme in the study of degree structures of all types has been the question of the decidability or undecidability of their first order theories. This is a natural and fundamental question that is an important goal in the analysis of these structures. In this paper, we study decidability for theories of upper semilattices that arise from the theory of numberings. We use the following approach: given a level of complexity, say Σα0, we consider the upper semilattice RΣα0 of all Σα0-computable numberings of all Σα0-computable families of subsets of N. We prove that the theory of the semilattice of all computable numberings is computably isomorphic to first order arithmetic. We show that the theory of the semilattice of all numberings is computably isomorphic to second order arithmetic. We also obtain a lower bound for the 1-degree of the theory of the semilattice of all Σα0-computable numberings, where α≥2 is a computable successor ordinal. Furthermore, it is shown that for any of the theories T mentioned above, the Π5-fragment of T is hereditarily undecidable. Similar results are obtained for the structure of all computably enumerable equivalence relations on N, equipped with composition. [ABSTRACT FROM AUTHOR]

We investigate effective categoricity for polymodal algebras (i.e., Boolean algebras with distinguished modalities). We prove that the class of polymodal algebras is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. In particular, this implies that every categoricity spectrum is the categoricity spectrum of a polymodal algebra. [ABSTRACT FROM AUTHOR]