Hostname: page-component-8448b6f56d-tj2md Total loading time: 0 Render date: 2024-04-23T08:29:25.073Z Has data issue: false hasContentIssue false
  • English
  • Français

Computable categoricity of trees of finite height

Published online by Cambridge University Press:  12 March 2014

Steffen Lempp ,
Charles McCoy ,
Russell Miller  and
Reed Solomon
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin-Madison, 480 Lincoln Drive, Madison, Wisconsin 53706-1388, USA, E-mail: lempp@math.wisc.edu
Charles McCoy
Affiliation:
Moreau Seminary, Notre Dame, Indiana 46556, USA, E-mail: cmccoyl@nd.edu
Russell Miller
Affiliation:
Department of Mathematics, Queens College —C.U.N.Y., 65-30 Kissena Blvd., Flushing, New York 11367, USA, E-mail: rmiller@forbin.qc.edu
Reed Solomon
Affiliation:
Department of Mathematics, University of Connecticut, 196 Auditorium Road, Storrs, Connecticut 06269-3009, USA, E-mail: solomon@math.uconn.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a -condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n ≥ 1 in ω, there exists a computable tree of finite height which is Σ30-categorical but not Δn3-categorical

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 1 , March 2005 , pp. 151 - 215
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ash, C. J., Categoricity in hyperarithmetical degrees, Annals of Pure and Applied Logic, vol. 34 (1987), pp. 1–14.CrossRefGoogle Scholar
[2]Ash, C. J. and Knight, J. F., Computable structures and the hyperarithmetic hierarchy, Elsivier Science, Amsterdam, 2000.Google Scholar
[3]Ash, C. J., Knight, J. F., Mannasse, M., and Slaman, T., Generic copies of countable structures, Annals of Pure and Applied Logic, vol. 42 (1989), pp. 195–205.CrossRefGoogle Scholar
[4]Chisholm, J., On intrisically 1-computable trees, unpublished manuscript.Google Scholar
[5]Crossley, J. N., Manaster, A. B., and Moses, M. F., Recursive categoricity and recursive stability, Annals of Pure and Applied Logic, vol. 31 (1986), pp. 191–204.CrossRefGoogle Scholar
[6]Downey, R. G., On presentations of algebraic structures, Complexity, logic, and recursion theory (Sorbi, A., editor), Dekker, New York, 1997, pp. 157–205.Google Scholar
[7]Downey, R. G. and Jockusch, C. G., Every low Boolean algebra is isomorphic to a recursive one, Proceedings of the American Mathematical Society, vol. 122 (1994), pp. 871–880.CrossRefGoogle Scholar
[8]Goncharov, S. S., Autostability and computable families of constructivizations, Algebra and Logic, vol. 14 (1975), pp. 647–680 (Russian), 392–409 (English translation).CrossRefGoogle Scholar
[9]Goncharov, S. S., The problem of the number of non-self-equivalent constructivizations, Algebra and Logic, vol. 19 (1980), pp. 401–414 (English translation).CrossRefGoogle Scholar
[10]Goncharov, S. S., Groups with a finite number of constructivizations, Soviet Mathematics Doklady, vol. 19 (1981). pp. 58–61.Google Scholar
[11]Goncharov, S. S., Nonequivalent constructivizations, Nauka, Novosibirsk, 1982.Google Scholar
[12]Goncharov, S. S., Autostable models and algorithmic dimensions. Handbook of Recursive Mathematics, vol. 1, Elsevier, Amsterdam, 1998.Google Scholar
[13]Goncharov, S. S. and Dzgoev, V. D., Autostability of models, Algebra and Logic, vol. 19 (1980), pp. 45–58 (Russian), 28–37 (English translation).Google Scholar
[14]Goncharov, S. S., Lempp, S., and Solomon, R., The computable dimension of ordered abelian groups, Advances in Mathematics, vol. 175 (2003), pp. 102–143.CrossRefGoogle Scholar
[15]Goncharov, S. S., Molokov, A. V., and Romanovskii, N. S., Nilpotent groups of finite algorithmic dimension, Siberian Mathematics Journal, vol. 30 (1989), pp. 63–68.CrossRefGoogle Scholar
[16]Hirschfeldt, D. R., Khoussainov, B., Shore, R. A., and Slinko, A. M., Degree spectra and computable dimension in algebraic structures, Annals of Pure and Applied Logic, vol. 115 (2002), pp. 71–113.CrossRefGoogle Scholar
[17]Khoussainov, B. and Shore, R. A., Computable isomorphisms, degree spectra of relations, and Scott families, Annals of Pure and Applied Logic, vol. 93 (1998), pp. 153–193.CrossRefGoogle Scholar
[18]Khoussainov, B., Effective model theory: the number of models and their complexity, Models and computability: Invited papers from Logic Colloquium '97 (Cooper, S. B. and Truss, J. K., editors), London Mathematical Society Lecture Note Series, vol. 259, Cambridge University Press, Cambridge, 1999, pp. 193–240.CrossRefGoogle Scholar
[19]Kruskal, J. B., Well quasi-ordering, the tree theorem, and Vázsonyi's conjecture, Transactions of the American Mathematical Society, vol. 95 (1960). pp. 210–225.Google Scholar
[20]Kudinov, O. V., An integral domain with finite algorithmic dimension, unpublished manuscript.Google Scholar
[21]Kudinov, O. V., An autostable 1-decidable model without a computable Scott family of ∃ formulas, A Igebra and Logic, vol. 35 (1996), pp. 255–260 (English translation).CrossRefGoogle Scholar
[22]LaRoche, P., Recursively presented Boolean algebras, Notices of the American Mathematical Society, vol. 24 (1977), pp. A–552, research announcement.Google Scholar
[23]Metakides, G. and Nerode, A., Effective content offield theory, Annals of Mathematical Logic, vol. 17 (1979), pp. 289–320.CrossRefGoogle Scholar
[24]Miller, R. G., The Δ20 spectrum of a linear order, this Journal, vol. 66 (2001), pp. 470–486.Google Scholar
[25]Miller, R. G., The computable dimension of trees of infinite height, this Journal, vol. 70 (2005). pp. 111–141.Google Scholar
[26]Nash-Williams, C. St. J. A., On well-quasi-ordering finite trees, Proceedings of the Cambridge Philosophical Society, vol. 59 (1963), pp. 833–835.CrossRefGoogle Scholar
[27]Nurtazin, A. T., Strong and weak constructivizations and enumerable families, Algebra and Logic, vol. 13 (1974), pp. 177–184.CrossRefGoogle Scholar
[28]Nurtazin, A. T., Computable classes and algebraic criteria of autostability, thesis, Mathematical Institute of the Siberian Branch of SSSR Academy of Sciences, Novosibirsk, 1974 (Russian).Google Scholar
[29]Remmel, J. B., Recursive isomorphism types of recursive Boolean algebras, this Journal, vol. 46 (1981), pp. 572–594.Google Scholar
[30]Remmel, J. B., Recursively categorical linear orderings, Proceedings of the American Mathematical Society, vol. 83 (1981), pp. 387–391.CrossRefGoogle Scholar
[31]Simpson, S. G., Nonprovability of certain combinatorial properties of finite trees, Harvey Friedman's research on the foundations of mathematics (Harrington, L. A., Morley, M. D., Scedrov, A., and Simpson, S. G., editors), North-Holland, Amsterdam, 1985, pp. 87–117.CrossRefGoogle Scholar
[32]Slaman, T. A., Relative to any nonrecursive set, Proceedings of the American Mathematical Society, vol. 126 (1998), pp. 2117–2122.CrossRefGoogle Scholar
[33]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, New York, 1987.CrossRefGoogle Scholar
[34]Wehner, S., Enumerations, countable structures, and Turing degrees, Proceedings of the American Mathematical Society, vol. 126 (1998), pp. 2131–2139.CrossRefGoogle Scholar
[35]White, W., On the complexity of categoricity in computable structures, Mathematical Logic Quarterly, vol. 49 (2003), no. 6, pp. 603–614.CrossRefGoogle Scholar