Computable Isomorphisms of Directed Graphs and Trees Open Access
Downloadable ContentDownload PDF
One of the main goals of computable model theory is to classify mathematical structures up to computable isomorphism. Two computable structures A and B are computably isomorphic if there exists a computable bijection from A to B that preserves all of the functions and relations in the structure. Furthermore, we say that A is computably categorical if every two computable copies of A are computably isomorphic. Significant work on computable categoricity has been done for a variety of mathematical structures, including linear orders, abelian groups, Boolean algebras, trees, and many others.We define a (2,1):1 structure, which consists of a countable set A, together with a function f on that set such that for every element x in A, f maps either exactly one or exactly two elements of A to x. These structures are in a similar class as the injection structures, two-to-one structures, and (2,0):1 structures studied by Cenzer, Harizanov, and Remmel, all of which can be thought of as directed graphs. In particular, (2,1):1 structures can contain two types of connected components: K-cycles, which consist of a directed cycle of k elements, each of which has an infinite (or empty) binary tree, and Z-chains, which consist of an infinite directed chain of elements, each of which has attached an infinite (or empty) binary tree.We investigate the isomorphism problem for computable (2,1);1 structures, and show that deciding if two such structures are isomorphic is Pi^0_4 in the arithmetical hierarchy. Furthermore, we prove that all (2,1):1 structures are Delta^0_4-categorical. We then introduce two additional functions on our structures: the branching function, which determines if an element has one or two pre-images, and the branch isomorphism function, which determines if an element with two branches has isomorphic trees. We prove that all computable (2,1):1 structures with a computable branching function in every computable copy are Delta^0_3-categorical, and that all such structures without Z-chains are Delta^0_2-categorical. We also give examples of a (2,1):1 structure with no computable branching function, and a structure with computable branching but no computable branch isomorphism function.We make significant progress toward classifying computable categoricity for (2,1):1 structures, by providing sufficient and necessary conditions for such graphs to be computably categorical. We construct a computable (2,1):1 structure that is computably categorical, but not relatively computably categorical, demonstrating the difficulty of classifying computable categoricity for such structures. Lastly, we present an interesting connection between our theory and the Collatz conjecture, also known as the 3n + 1 conjecture. We observe that the Collatz graph is also a computable (2,1):1 structure with computable branching and branch isomorphism functions. Moreover, we use this result to prove that the connected component of the Collatz graph containing 1 is computably categorical, and that if the full Collatz structure is not computably categorical, then the Collatz conjecture does not hold.