Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-24T15:54:29.727Z Has data issue: false hasContentIssue false
  • English
  • Français

Turing computable embeddings

Published online by Cambridge University Press:  12 March 2014

Julia F. Knight ,
Sara Miller  and
M. Vanden Boom
Julia F. Knight
Affiliation:
University of Notre Dame, Department of Mathematics, 255 Hurley Building, Notre Dame, IN 46556-4618, USA. E-mail: [email protected]
Sara Miller
Affiliation:
University of Notre Dame, Department of Mathematics, 255 Hurley Building, Notre Dame, IN 46556-4618, USA. E-mail: [email protected]
M. Vanden Boom
Affiliation:
University of Notre Dame, and, 14904 Lynbrook Drive, Baton Rouge, LA 70816, USA. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In [3]. two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility. while the second, called Turing computable embedding, is based on uniform Turing reducibility. While [3] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [3]. We give a “Pull-back Theorem”, saying that if Ф is a Turing computable embedding of K into K′, then for any computable infinitary sentence φ in the language of K′, we can find a computable infinitary sentence φ* in the language of K such that for all A ∈ K A ⊨ φ* iff Φ (A) ⊨ φ and φ* has the same “complexity” as φ (i.e., if φ is computable Σα or computable Πα, for α ≥ 1, then so is φ*). The Pull-back Theorem is useful in proving non-embeddability, and it has other applications as well.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 3 , September 2007 , pp. 901 - 918
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

[1] Ash, C. J. and Knight, J. F., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, Elsevier, 2000Google Scholar
[2] Buechler, S., Essential Stability Theory, Springer, 1996.CrossRefGoogle Scholar
[3] Calvert, W., Cummins, D., Miller, S., and Knight, J. F., Comparing classes of finite structures. Algebra and Logic, vol. 43 (2004), pp. 365–373.CrossRefGoogle Scholar
[4] Camerlo, R. and Gao, S., The completeness of the isomorphism relation for countable Boolean algebras, Transactions of the American Mathematical Society, vol. 353 (2001), pp. 491–518.Google Scholar
[5] Chisholm, J., Knight, J. F., and Miller, S., Solution to a problem on computable embeddings, this Journal, vol. 72 (2007), pp. 1031–1040.Google Scholar
[6] Friedman, H. and Stanley, L., A Borel reducibility theory for classes of countable structures, this Journal, vol. 54 (1989), pp. 894–914.Google Scholar
[7] Greenberg, N., conversations, Spring, 2005.Google Scholar
[8] Greenberg, N., e-mail correspondence, 01, 2006.Google Scholar
[9] Hjorth, G., The isomorphism relation on countable torsion-free Abelian groups, Fundament a Mathematicae, vol. 175 (2002), pp. 241–257.Google Scholar
[10] Hjorth, G. and Kechris, A. S., Recent developments in the theory of Borel reducibility, Fundamenta Mathematicae, vol. 170 (2001), pp. 21–52.CrossRefGoogle Scholar
[11] Kalimullin, I., e-mail correspondence, 06–July, 2005.Google Scholar
[12] Knight, J. F., A result on the degree structure associated with computable embedding, unpublished.Google Scholar
[13] Marker, D., Model Theory: An Introduction, Springer, 2002.Google Scholar
[14] Boom, M. Vanden, Effective Borel hierarchy, Fundamenta Mathematicae, to appear.Google Scholar