An effective version of definability in metric structures

Document Type : Original Article


Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran


In this paper, a computably definable predicate in metric structures is defined and characterized. Then, it is proved that every separable infinite-dimensional Hilbert structure in an effectively presented language is computable. Moreover, every definable predicate in these structures is computable.


[1] I. Ben-Yaacov, Positive model theory and compact abstract theories, J. Math. Log., 3 (2003), pp. 85–118.
[2] I. Ben Yaacov, A. Berenstein, C. W. Henson, and A. Usvyatsov, Model theory for metric structures, in Model theory with applications to algebra and analysis. Vol. 2, vol. 350 of London Math. Soc. Lecture Note Ser., Cambridge Univ. Press, Cambridge, 2008, pp. 315–427.
 [3] V. Brattka and A. Yoshikawa, Towards computability of elliptic boundary value problems in variational formulation, J. Complexity, 22 (2006), pp. 858–880.
[4] C.-c. Chang and H. J. Keisler, Continuous model theory, Annals of Mathematics Studies, No. 58, Princeton University Press, Princeton, N.J., 1966.
 [5] I. Goldbring, Definable operators on Hilbert spaces, Notre Dame J. Form. Log., 53 (2012), pp. 193–201.
[6] T. Grubba, K. Weihrauch, and Y. Xu, Effectivity on continuous functions in topological spaces, in Pro[1]ceedings of the Fourth International Conference on Computability and Complexity in Analysis (CCA 2007), vol. 202 of Electron. Notes Theor. Comput. Sci., Elsevier Sci. B. V., Amsterdam, 2008, pp. 237–254.
 [7] A. Grzegorczyk, Computable functionals, Fund. Math., 42 (1955), pp. 168–202.
[8] E. D. Habil, Double sequences and double series, IUG Journal of Natural Studies, 14 (2016), pp. 219–233.
[9] C. W. Henson, Nonstandard hulls of Banach spaces, Israel J. Math., 25 (1976), pp. 108–144.
 [10] C. W. Henson and L. C. Moore, Jr., Nonstandard analysis and the theory of Banach spaces, in Nonstandard analysis—recent developments (Victoria, B.C., 1980), vol. 983 of Lecture Notes in Math., Springer, Berlin, 1983, pp. 27–112.
 [11] D. Lacombe, Extension de la notion de fonction r´ecursive aux fonctions d’une ou plusieurs variables r´eelles. II, III, C. R. Acad. Sci. Paris, 241 (1955), pp. 13–14, 151–153.
[12] A. G. Melnikov, Computably isometric spaces, J. Symbolic Logic, 78 (2013), pp. 1055–1085.
 [13] M. Pourmahdian, N. R. Tavana, and F. Didehvar, Effective metric model theory, Math. Structures Comput. Sci., 25 (2015), pp. 1779–1798.
 [14] N. R. Tavana and K. Weihrauch, Turing machines on represented sets, a model of computation for analysis, Log. Methods Comput. Sci., 7 (2011), pp. 2:19, 21.
[15] A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Soc. (2), 42 (1936), pp. 230–265.
[16] K. Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer[1]Verlag, Berlin, 2000. An introduction.
 [17]____ , On computable metric spaces Tietze-Urysohn extension is computable, in Computability and complexity in analysis (Swansea, 2000), vol. 2064 of Lecture Notes in Comput. Sci., Springer, Berlin, 2001, pp. 357–368.