Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-20T08:35:02.490Z Has data issue: false hasContentIssue false
  • English
  • Français

UNIFORM PROCEDURES IN UNCOUNTABLE STRUCTURES

Published online by Cambridge University Press:  01 August 2018

NOAM GREENBERG ,
ALEXANDER G. MELNIKOV ,
JULIA F. KNIGHT  and
DANIEL TURETSKY
NOAM GREENBERG
Affiliation:
SCHOOL OF MATHEMATICS VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, NEW ZEALANDE-mail:[email protected]
ALEXANDER G. MELNIKOV
Affiliation:
INSTITUTE OF NATURAL AND MATHEMATICAL SCIENCES MASSEY UNIVERSITY AUCKLAND, NEW ZEALANDE-mail:[email protected]
JULIA F. KNIGHT
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF NOTRE DAME NOTRE DAME, IN 46556, USAE-mail:[email protected]
DANIEL TURETSKY
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF NOTRE DAME NOTRE DAME, IN 46556, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This article contributes to the general program of extending techniques and ideas of effective algebra to computable metric space theory. It is well-known that relative computable categoricity (to be defined) of a computable algebraic structure is equivalent to having a c.e. Scott family with finitely many parameters (e.g., [1]). The first main result of the article extends this characterisation to computable Polish metric spaces. The second main result illustrates that just a slight change of the definitions will give us a new notion of categoricity unseen in the countable case (to be stated formally). The second result also shows that the characterisation of computably categorical closed subspaces of ${\Cal R}^n $ contained in [17] cannot be improved. The third main result extends the characterisation to not necessarily separable structures of cardinality κ using κ-computability.

Keywords

03D45relative computable categoricityeffective Polish spacesadmissible recursion theory
Type
Articles
Information
The Journal of Symbolic Logic , Volume 83 , Issue 2 , June 2018 , pp. 529 - 550
Copyright
Copyright © The Association for Symbolic Logic 2018 

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

Ash, C. J. and Knight, J., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland, Amsterdam, 2000.Google Scholar
Ben Yaacov, I. and Usvyatsov, A., Continuous first order logic and local stability. Transactions of the American Mathematical Society, vol. 362 (2010), no. 10, pp. 5213–5259.CrossRefGoogle Scholar
Carson, J., Johnson, J., Knight, J., Lange, K., McCoy, C., and Wallbaum, J., The arithmetical hierarchy in the setting of ${\omega _1}$. Computability, vol. 2 (2013), no. 2, pp. 93–105.Google Scholar
Downey, R., Hirschfeldt, D., and Khoussainov, B., Uniformity in the theory of computable structures. Algebra Logika, vol. 42 (2003), no. 5, pp. 566–593.CrossRefGoogle Scholar
Ershov, Y. L. and Goncharov, S. S., Constructive Models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000.CrossRefGoogle Scholar
Gončarov, S. S., The problem of the number of nonautoequivalent constructivizations. Algebra i Logika, vol. 19 (1980), no. 6, pp. 621–639.Google Scholar
Greenberg, N., Turetsky, D., and Westrick, L. B., Finding bases of uncountable free abelian groups is usually difficult. Transactions of the American Mathematical Society, to appear.Google Scholar
Greenberg, N., Kach, A. M., Lempp, S., and Turetsky, D. D., Computability and uncountable linear orders I: Computable categoricity, this Journal, vol. 80 (2015), no. 1, pp. 116–144.Google Scholar
Greenberg, N., Kach, A. M., Lempp, S., and Turetsky, D. D., Computability and uncountable linear orders II: Degree spectra, this Journal, vol. 80 (2015), no. 1, pp. 145–178.Google Scholar
Greenberg, N. and Knight, J. F., Computable structure theory on ${\omega _1}$ using admissibility, Effective Mathematics of the Uncountable (Greenberg, N., Hamkins, J. D., Hirschfeldt, D., and Miller, R., editors), Lecture Notes in Logic, vol.41, Association for Symbolic Logic, La Jolla, CA, 2013, pp. 50–80.CrossRefGoogle Scholar
Hirschfeldt, D. R., Khoussainov, B., Shore, R. A., and Slinko, A. M., Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic, vol. 115 (2002), no. 1–3, 71–113.CrossRefGoogle Scholar
Johnson, J., Computable categoricity for pseudo-exponential fields of size $aleph _1$. Annals of Pure and Applied Logic, vol. 165 (2014), no. 7–8, pp. 1301–1317.CrossRefGoogle Scholar
Johnson, J. W., Computable model theory for uncountable structures, Ph.D. thesis, University of Notre Dame, ProQuest LLC, Ann Arbor, MI, 2013.Google Scholar
McNicholl, T. H., A note on the computable categoricity of lp spaces, Evolving Computability - 11th Conference on Computability in Europe, CiE 2015 (Beckmann, A., Mitrana, V., and Soskova, M., editors), Springer, Cham, 2015, pp. 268–275.Google Scholar
Melleray, J., Some geometric and dynamical properties of the Urysohn space. Topology and its Applications, vol. 155 (2008), no. 14, pp. 1531–1560.CrossRefGoogle Scholar
Melnikov, A. and Ng, K. M., Computable structures and operations on the space of continuous functions. Fundamenta Mathematica, vol. 233 (2016), no. 2, pp. 101–141.Google Scholar
Melnikov, A. G., Computably isometric spaces, this Journal, vol. 78 (2013), no. 4, pp. 1055–1085.Google Scholar
Melnikov, A. G. and Nies, A., The classification problem for compact computable metric spaces, The Nature of Computation (Bonizzoni, P., Brattka, V., and Löwe, B., editors), Lecture Notes in Computer Science, vol. 7921, Springer, Heidelberg, 2013, pp. 320–328.Google Scholar
Miller, R. G., Locally computable structures, Computation and Logic in the Real World (Cooper, S. B., Löwe, B., and Sorbi, A., editors), Lecture Notes in Computer Science, vol. 4497, Springer, Berlin, 2007, pp. 575–584.CrossRefGoogle Scholar
Morozov, A. S., On some presentations of the real number field. Algebra Logika, vol. 51 (2012), no. 1, pp. 96–128, 151, 154–155.CrossRefGoogle Scholar
Pour-El, M. B. and Richards, J. I., Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989.CrossRefGoogle Scholar
Sacks, G. E., Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990.CrossRefGoogle Scholar
Shore, R. A., Priority arguments in alpha-recursion theory, Ph.D. thesis, Massachusetts Institute of Technology, ProQuest LLC, Ann Arbor, MI, 1972.Google Scholar
Weihrauch, K., Computable Analysis, Texts in Theoretical Computer Science, An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction.CrossRefGoogle Scholar