We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$, $\Pi _{\alpha }$, or $\mathrm {d-}\Sigma _{\alpha }$. We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit (...) ordinal. This answers a question left open by A. Miller.We also construct examples of computable structures of high Scott rank with Scott complexities $\Sigma _{\omega _1^{CK}+1}$ and $\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$. There are three other possible Scott complexities for a computable structure of high Scott rank: $\Pi _{\omega _1^{CK}}$, $\Pi _{\omega _1^{CK}+1}$, $\Sigma _{\omega _1^{CK}+1}$. Examples of these were already known. Our examples are computable structures of Scott rank $\omega _1^{CK}+1$ which, after naming finitely many constants, have Scott rank $\omega _1^{CK}$. The existence of such structures was an open question. (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)

EveryK-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.

LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure is isomorphic to${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by$\omega /E$; formally,${\cal K}\left = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties ofEand algebraic properties of linearly ordered sets realized (...) byE. One can also define the following pre-order$ \le _{lo} $on the class of all c.e. equivalence relations:$E_1 \le _{lo} E_2 $if every linear order realized byE1is also realized byE2. Following the tradition of computability theory, thelo-degrees are the classes of equivalence relations induced by the pre-order$ \le _{lo} $. We study the partially ordered set oflo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among thelo-degrees. (shrink)

A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...) is still noncomputable.In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting. (shrink)

Using new techniques for controlling the categoricity spectrum of a structure, we construct a structure with degree of categoricity but infinite spectral dimension, answering a question of Bazhenov, Kalimullin and Yamaleev. Using the same techniques, we construct a computably categorical structure of non-computable Scott rank.

We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing limitwise monotonic sets on certain domains.

We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.

We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.

We review the current knowledge concerning strong jump-traceability. We cover the known results relating strong jump-traceability to randomness, and those relating it to degree theory. We also discuss the techniques used in working with strongly jump-traceable sets. We end with a section of open questions.

We examine the sequences A that are low for dimension, i.e. those for which the effective dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension (...) 1 relative to A, and lowishness for K, namely, that the limit of KA/K is 1. We show that there is a perfect [Formula: see text]-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension is jump-traceable in order nε, for any ε > 0. (shrink)

We give two new characterizations of K-triviality. We show that if for all Y such that Ω is Y-random, Ω is -random, then A is K-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of K-triviality and answering a question of Yu. We also prove that if A is K-trivial, then for all Y such that Ω is Y-random, ≡LRY. This answers a question of Merkle and Yu. The other direction is immediate, so (...) we have the second characterization of K-triviality.The proof of the first characterization uses a new cupping result. We prove that if A≰LRB, then for every set X there is a B-random set Y such that X is computable from Y⊕A. (shrink)

We show that the fact that the first player wins every instance of Galvin’s “racing pawns” game is equivalent to arithmetic transfinite recursion. Along the way we analyze the satisfaction relation for infinitary formulas, of “internal” hyperarithmetic comprehension, and of the law of excluded middle for such formulas.

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.