Computable isomorphisms for certain classes of infinite graphs. (English) Zbl 1522.03129
Summary: We investigate (2,1):1 structures, which consist of a countable set \(A\) together with a function \(f : A \rightarrow 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 \(\mathcal{A}\) is computably categorical if there exists a computable isomorphism between any two computable copies of \(\mathcal{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.
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03D45 | Theory of numerations, effectively presented structures |
| 05C63 | Infinite graphs |
References:
| [1] | Ash, C. J.; Knight, J. F., Computable Structures and the Hyperarithmetical Hierarchy, (2000), Elsevier · Zbl 0960.03001 |
| [2] | Calvert, W.; Cenzer, D.; Harizanov, V.; Morozov, A., Effective categoricity of equivalence structures, Ann. Pure Appl. Logic, 141, 61-78, (2006) · Zbl 1103.03037 |
| [3] | Cenzer, D.; Harizanov, V.; Remmel, J. B., Computability-theoretic properties of injection structures, Algebra Logic, 53, 39-69, (2014) · Zbl 1323.03045 |
| [4] | Cenzer, D.; Harizanov, V.; Remmel, J. B., Two-to-one structures, J. Logic Comput., 23, 1195-1223, (2013) · Zbl 1327.03026 |
| [5] | Csima, B.; Khoussainov, B.; Liu, J., Computable categoricity of graphs with finite components, Lecture Notes Comput. Sci., 5028, 139-148, (2008) · Zbl 1142.03344 |
| [6] | Dzgoev, V. D.; Goncharov, S. S., Autostability of models, Algebra Logic, 19, 28-37, (1980) · Zbl 0468.03023 |
| [7] | Goncharov, S.; Lempp, S.; Solomon, R., The computable dimension of ordered abelian groups, Adv. Math., 175, 102-143, (2003) · Zbl 1031.03058 |
| [8] | LaRoche, P., Recursively presented Boolean algebras, Notices Am. Math. Soc., 24, A552-A553, (1977) |
| [9] | Lempp, S.; McCoy, C.; Miller, R.; Solomon, R., Computable categoricity of trees of finite height, J. Symbolic Logic, 70, 151-215, (2005) · Zbl 1104.03026 |
| [10] | Miller, R., The computable dimension of trees of infinite height, J. Symbolic Logic, 70, 111-141, (2005) · Zbl 1098.03049 |
| [11] | Remmel, J. B., Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic, 46, 572-594, (1981) · Zbl 0543.03031 |
| [12] | Remmel, J. B., Recursively categorical linear orderings, Proce. Am. Math. Soc., 83, 387-391, (1981) · Zbl 0493.03022 |
| [13] | Soare, R. I., Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets, (1987), Spring-Verlag, Berlin · Zbl 0623.03042 |
| [14] | H. J. Walker, Computable isomorphisms of directed graphs and trees, Ph.D. Thesis, The George Washington University, Washington, D.C.. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
