Two-to-one structures
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 Z-chains. We show that every computable 2: 1 structure is Delta(0)(2)-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.
computability theory two-to-one functions injections effective categoricity locally finite structures trees chains