A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to $2$. In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong $\eta $ -representation with no computable copy that is the simplest possible example.

We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by these relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a $\boldsymbol {\Sigma }^1_1$ complete equivalence relation. We then investigate the algorithmic properties of this reduction. We obtain that elementary bi-embeddability on the class of computable graphs is $\Sigma ^1_1$ complete with respect (...) to computable reducibility and show that the elementary bi-embeddability and bi-embeddability spectra realized by graphs are related. (shrink)

We study the position of the computable setting in the “common theory of locality” developed in [4, 5] for local problems on $\Delta $ -regular trees, $\Delta \in \omega $. We show that such a problem admits a computable solution on every highly computable $\Delta $ -regular forest if and only if it admits a Baire measurable solution on every Borel $\Delta $ -regular forest. We also show that if such a problem admits a computable solution on every computable maximum (...) degree $\Delta $ forest then it admits a continuous solution on every maximum degree $\Delta $ Borel graph with appropriate topological hypotheses, though the converse does not hold. (shrink)

We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, (...) Melnikov, R. Miller, and Montalbán. This proof allows the possibility that the elements of F are represented by tuples in $H(F)$ of no fixed arity. The second proof is direct, giving explicit finitary existential formulas that define the interpretation, with elements of F represented by triples in $H(F)$. Looking at what was used to arrive at this parameter-free interpretation of F in $H(F)$, we give general conditions sufficient to eliminate parameters from interpretations. (shrink)

We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel (...) quotient of the reals reduces to it. (shrink)

Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual presentation of$\omega $, then every cohesive power of$\mathcal {L}$has order-type$\omega + (...) \zeta \eta $. However, there are computable copies of$\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$\omega + \zeta \eta $. For example, we show that there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \eta $. Our most general result is that if$X \subseteq \mathbb {N} \setminus \{0\}$is a Boolean combination of$\Sigma _2$sets, thought of as a set of finite order-types, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$denotes the shuffle of the order-types inXand the order-type$\omega + \zeta \eta + \omega ^*$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X)$. (shrink)

A celebrated result by Davis, Putnam, Robinson, and Matiyasevich shows that a set of integers is listable if and only if it is positive existentially definable in the language of arithmetic. We investigate analogues of this result over structures endowed with a listable presentation. When such an analogue holds, the structure is said to have the DPRM property. We prove several results addressing foundational aspects around this problem, such as uniqueness of the listable presentation, transference of the DPRM property under (...) interpretation, and its relation with positive existential bi-interpretability. A first application of our results is the rigorous proof of (strong versions of) several folklore facts regarding transference of the DPRM property. Another application of the theory we develop is that it will allow us to link various Diophantine conjectures to the question of whether the DPRM property holds for global fields. This last topic includes a study of the number of existential quantifiers needed to define a Diophantine set. (shrink)

Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite $\Pi _1^0 $ chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable (...) antichain. Our hardest result is that there is an infinite computable weakly stable poset with no infinite $\Pi _1^0 $ chains or antichains. On the other hand, it is easily seen that every infinite computable stable poset contains an infinite computable chain or an infinite $\Pi _1^0 $ antichain. In Reverse Mathematics, we show that SCAC, the principle that every infinite stable poset contains an infinite chain or antichain, is equivalent over RCA₀ to WSCAC, the corresponding principle for weakly stable posets. (shrink)

We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $ -formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$. As (...) a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $\mathcal {K}$ be positively computably embeddable in $\mathcal {K}'$ by $\Phi $, then for every $\Pi ^p_\alpha $ formula $\xi $ in the vocabulary of $\mathcal {K}'$ there is a $\Pi ^p_\alpha $ formula $\xi ^{*}$ in the vocabulary of $\mathcal {K}$ such that for all $\mathcal {A}\in \mathcal {K}$, $\mathcal {A}\models \xi ^{*}$ if and only if $\Phi (\mathcal {A})\models \xi $. We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings. (shrink)

We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.

The main question of this article is whether there is a family closed under finite differences (i.e., if A belongs to the family and B=∗A, then B also belongs to the family) that can be enumerated by any noncomputable c.e. degree, but which cannot be enumerated computably. This question was formulated by Greenberg et al. (2020) in their recent work in which families that are closed under finite differences, close to the Slaman–Wehner families, are deeply studied.

Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short and simple proofs (...) where possible, followed by a survey of recent advances. (shrink)

We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, and thus these applications are (...) not necessarily direct or expected. (shrink)

Computable limits and colimits are “recursive counterparts” of the suitable classical concepts from category theory. We present mainly some interesting problems related to computable products. Moreover, some “computable counterparts” of well-known classical facts from category theory are given. MSC: 03D45, 18A30.

In the present paper we concentrate on fundamental problems concerning ω-operations over partial enumerated sets. The notion of “HOM-lifts” seems to be an adequate tool for this kind of investigations. MSC: 03D45, 18A30.

Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the (...) other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element. (shrink)

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings . To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements of (...) a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

$\eta $ -representations are a way of coding sets in computable linear orders that were first introduced by Fellner in his thesis. Limitwise monotonic functions have been used to characterize the sets with $\eta $ -representations, and give characterizations for several variations of $\eta $ -representations. The one exception is the class of sets with strong $\eta $ -representations, the only class where the order type of the representation is unique.We introduce the notion of a connected approximation of a set, (...) a variation on $\Sigma ^0_2$ approximations. We use connected approximations to give a characterization of the many-one degrees of sets with strong $\eta $ -representations as well new characterizations of the variations of $\eta $ -representations with known characterizations. (shrink)

We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is$0''$. We also prove that, with a bit of work, the latter result can be pushed beyond$\Delta ^1_1$, thus showing that punctually categorical structures can possess arbitrarily complex (...) automorphism orbits.As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations; equivalently, in these classes every rich enough interpretation technique must necessarily involve unbounded existential quantification or infinite disjunction. In contrast, it is well-known that both classes are universal for Turing computability. (shrink)