Switch to: Citations

References in:

Σ 1 0 and Π 1 0 equivalence structures

Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel

Annals of Pure and Applied Logic 162 (7):490-503 (2011)

Add references

You must login to add references.

Effective categoricity of equivalence structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.details We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures are relatively categorical, (...) Download Export citation Bookmark 22 citations
Recursively enumerable vector spaces.G. Metakides - 1977 - Annals of Mathematical Logic 11 (2):147.details Download Export citation Bookmark 60 citations
Equivalence structures and isomorphisms in the difference hierarchy.Douglas Cenzer, Geoffrey LaForte & Jeffrey Remmel - 2009 - Journal of Symbolic Logic 74 (2):535-556.details We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity. Download Export citation Bookmark 2 citations
Classifying positive equivalence relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.details Given two (positive) equivalence relations ∼ 1 , ∼ 2 on the set ω of natural numbers, we say that ∼ 1 is m-reducible to ∼ 2 if there exists a total recursive function h such that for every x, y ∈ ω, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$ . We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a "uniformity property" holds). This (...) Download Export citation Bookmark 26 citations
Combinational functors on co-r.e. structures.Jeffery B. Remmel - 1976 - Annals of Mathematical Logic 10 (3-4):261-287.details Download Export citation Bookmark 3 citations
Computably enumerable equivalence relations.Su Gao & Peter Gerdes - 2001 - Studia Logica 67 (1):27-59.details We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers. Download Export citation Bookmark 20 citations
Computable categoricity and the Ershov hierarchy.Bakhadyr Khoussainov, Frank Stephan & Yue Yang - 2008 - Annals of Pure and Applied Logic 156 (1):86-95.details In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for any recursive (...) ordinal α. (shrink) Download Export citation Bookmark 4 citations
Recursively Enumerable Equivalence Relations Modulo Finite Differences.André Nies - 1994 - Mathematical Logic Quarterly 40 (4):490-518.details We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq, thereby showing that Th has the same computational complexity as the true first-order arithmetic. Download Export citation Bookmark 5 citations
(1 other version)A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Mathematical Logic Quarterly 33 (1):43-46.details Download Export citation Bookmark 14 citations
(1 other version)A Note on Positive Equivalence Relations.A. H. Lachlan - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (1):43-46.details Download Export citation Bookmark 14 citations

1