Two-to-one structures
Douglas Cenzer, Valentina Harizanov, Jeffrey B. Remmel · Journal of Logic and Computation · 2013
We investigate computability-theoretic properties of computable structures with single unary functions f such that, for every x in the image, f−1(x) has exactly two elements, which we call 2:1 structures. We also investigate structures for which f−1(x) has either exactly two or zero elements, which we call (2,0):1 structures. In particular, we are interested in the complexity of isomorphisms between these structures. We prove that a computable 2:1 structure A is computably categorical if and only if A has only finitely many ℤ-chains. We show that every computable 2:1 structure is Δ20-categorical. We further investigate computable and higher level categoricity of various natural subclasses of (2,0):1 structures, including highly computable and locally finite strufctures.