We introduce agreement reducibility and highlight its major features. Given subsets A and B of, we write if there is a total computable function satisfying for all,.We shall discuss the central role plays in this reducibility and its connection to strong‐hyper‐hyper‐immunity. We shall also compare agreement reducibility to other well‐known reducibilities, in particular s1‐ and s‐reducibility. We came upon this reducibility while studying the computable reducibility of a class of equivalence relations on based on set‐agreement. We end by describing the (...) origin of agreement reducibility and presenting some results in that context. (shrink)

Universality has been an important concept in computable structure theory. A class C of structures is universal if, informally, for any structure of any kind there is a structure in C with the same computability-theoretic properties as the given structure. Many classes such as graphs, groups, and fields are known to be universal. This paper is about the class of finitely generated groups. Because finitely generated structures are relatively simple, the class of finitely generated groups has no hope of being (...) universal. We show that finitely generated groups are as universal as possible, given that they are finitely generated: for every finitely generated structure, there is a finitely generated group which has the same computability-theoretic properties. The same is not true for finitely generated fields. We apply the results of this investigation to quasi Scott sentences, and also answer a question of Alvir, Knight, and McCoy. (shrink)

We investigate effective categoricity for polymodal algebras. 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.

We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time generalization of the (...) countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $\Delta^1_2$ reductions, and hence to the infinite time computable reductions. (shrink)

Mereological theories are based on the binary relation “being a part of”. The systematic investigations of mereology were initiated by Leśniewski. More recent authors (including Simons, Casati and Varzi, Hovda) formulated a series of first‐order mereological axioms. These axioms give rise to a plenitude of theories, which are of great philosophical interest. The paper considers first‐order mereological theories from the point of view of computable (or effective) algebra. Following the approach of Hirschfeldt, Khoussainov, Shore, and Slinko, we isolate two important (...) computability‐theoretic properties P (namely, degree spectra of structures, and effective dimensions), and consider the following problem: for a given mereological theory T, is it true that its models can realize every possible variant of the property P? If the answer is positive, then we say that the theory T is ‐universal. We obtain the following results about known mereological theories. Any theory T which is weaker than Extensional Closure Mereology (CEM) is ‐universal. A similar fact is true for the theory GM2. On the other hand, any theory stronger that CEM + (C) + (G) is not ‐universal. In particular, General Extensional Mereology is not ‐universal. (shrink)