2017/01/05 by Walker, Hakim J.
#FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1701.01227
We investigate (2,1):1 structures, which consist of a countable set A together with a function f: A → A such that for every element x in A, f maps either exactly one element or exactly two elements of A to x. These structures extend the notions of injection structures, 2:1 structures, and (2,0):1 structures studied by Cenzer, Harizanov, and Remmel, all of which can be thought of as infinite directed graphs. We look at various computability-theoretic properties of (2,1):1 structures, most notably that of computable categoricity. We say that a structure A is computably categorical if there exists a computable isomorphism between any two computable copies of A. We give a sufficient condition under which a (2,1):1 structure is computably categorical, and present some examples of (2,1):1 structures with different computability-theoretic properties.