Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T15:41:25.362Z Has data issue: false hasContentIssue false
  • English
  • Français

Index sets for classes of high rank structures

Published online by Cambridge University Press:  12 March 2014

W. Calvert ,
E. Fokina ,
S. S. Goncharov ,
J. F. Knight ,
O. Kudinov ,
A. S. Morozov  and
V. Puzarenko
W. Calvert
Affiliation:
Department of Mathematics & Statistics, Murray State University, Murray, Kentucky, USA. E-mail: [email protected]
E. Fokina
Affiliation:
Sobolev Institute of Mathematics, Kortyug Prosr 4, 630090, Novosibirsk, Russia. E-mail: [email protected]
S. S. Goncharov
Affiliation:
Sobolev Institute of Mathematics, Kortyug Prosr 4, 630090, Novosibirsk, Russia. E-mail: [email protected]
J. F. Knight
Affiliation:
Department of Mathematics, University of Notre Dame, 255 Hurley Hall, Notre Dame, Indiana 46556, U.S.A.. E-mail: [email protected]
O. Kudinov
Affiliation:
Sobolev Institute of Mathematics, Kortyug Prosr. 4, 630090, Novosibirsk, Russia. E-mail: [email protected]
A. S. Morozov
Affiliation:
Sobolev Institute of Mathematics, Kortyug Prosr. 4, 630090, Novosibirsk, Russia. E-mail: [email protected]
V. Puzarenko
Affiliation:
Sobolev Institute of Mathematics, Kortyug Prosr. 4, 630090, Novosibirsk, Russia. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper calculates, in a precise way. the complexity of the index sets for three classes of computable structures: the class of structures of Scott rank , the class , of structures of Scott rank , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete is m-complete relative to Kleene's and is m-complete relative to .

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 4 , December 2007 , pp. 1418 - 1432
Copyright
Copyright © Association for Symbolic Logic 2007

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. and Knight, J. F., Pairs of recursive structures, Annals of Pure and Applied Logic, vol. 46 (1990), pp. 211–234.CrossRefGoogle Scholar
[2]Ash, C. J. and Knight, J. F., Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000.Google Scholar
[3]Barwise, J., Admissible sets and structures: An approach to definability theory, Springer, 1975.CrossRefGoogle Scholar
[4]Calvert, W., Goncharov, S. S., and Knight, J. F., Boolean algebras of Scott rank , preprint.Google Scholar
[5]Calvert, W., Goncharov, S. S., and Knight, J. F., Computable structures of Scott rank in familiar classes, Proceedings of the North Texas Logic Conference, October, 2004, Contemporary Mathematics, American Mathematical Society, to appear in Advances in Logic.Google Scholar
[6]Calvert, W., Harizanov, V. S., Knight, J. F., and Miller, S., Index sets for computable structures, Algebra and Logic, vol. 45 (2006), pp. 306–325.CrossRefGoogle Scholar
[7]Calvert, W., Knight, J. F., and Millar, J., Trees of Scott rank and computable approximability, this Journal, vol. 71 (2006), pp. 283–298.Google Scholar
[8]Goncharov, S. S., Harizanov, V. S., Knight, J. F., and Shore, R., relations and paths through , this Journal, vol. 69 (2004), pp. 585–611.Google Scholar
[9]Goncharov, S. S. and Knight, J. F., Computable structure and non-structure theorems, Algebra and Logic, vol. 41 (2002), pp. 351–373.CrossRefGoogle Scholar
[10]Harrison, J., Recursive pseudo well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.CrossRefGoogle Scholar
[11]Keisler, H. J., Model theory for infinitary logic, North-Holland, 1971.Google Scholar
[12]Knight, J. F., A computable structure of Scott rank whose computable infinitary theory is not ℵ0 categorical, in preparation.Google Scholar
[13]Knight, J. F. and Millar, J., Computable structures of rank , Journal of Mathematical Logic, submitted.Google Scholar
[14]Makkai, M., An example concerning Scott heights, this Journal, vol. 46 (1981), pp. 301–318.Google Scholar
[15]Millar, J. and Sacks, G., Atomic models higher up, preprint.Google Scholar
[16]Nadel, M., Scott sentences and admissible sets, Annals of Mathematical Logic, vol. 7 (1974), pp. 267–294.CrossRefGoogle Scholar
[17]Rogers, H. Jr., Theory of recursive functions and effective comput ability, McGraw-Hill, 1967.Google Scholar
[18]Sacks, G. E., Higher recursion theory, Springer-Verlag, 1990.CrossRefGoogle Scholar
[19]Scott, D., Logic with denumerably long formulas and finite strings of quantifiers, The theory of models (Addison, J., Henkin, L., and Tarski, A., editors), North-Holland, 1965, pp. 329–341.Google Scholar
[20]White, W., Characterizations for computable structures, PhD dissertation, Cornell University, 2000.Google Scholar
[21]White, W., On the complexity of categoricity in computable structures, Mathematical Logic Quarterly, vol. 49 (2003), pp. 603–614.CrossRefGoogle Scholar