Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-01-13T23:44:26.791Z Has data issue: false hasContentIssue false
  • English
  • Français

COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY

Published online by Cambridge University Press:  25 January 2017

MATTHEW HARRISON-TRAINOR ,
ALEXANDER MELNIKOV ,
RUSSELL MILLER  and
ANTONIO MONTALBÁN
MATTHEW HARRISON-TRAINOR
Affiliation:
GROUP IN LOGIC AND THE METHODOLOGY OF SCIENCE UNIVERSITY OF CALIFORNIA BERKELEY, CA, USAE-mail: [email protected]: http://math.berkeley.edu/∼mattht
ALEXANDER MELNIKOV
Affiliation:
THE INSTITUTE OF NATURAL AND MATHEMATICAL SCIENCES MASSEY UNIVERSITY, NEW ZEALANDE-mail: [email protected]: https://dl.dropboxusercontent.com/u/4752353/homepage/index.html
RUSSELL MILLER
Affiliation:
MATHEMATICS DEPT., QUEENS COLLEGE; PH.D. PROGRAMS IN MATHEMATICS & COMPUTER SCIENCE GRADUATE CENTER, CITY UNIVERSITY OF NEW YORK, USAE-mail: [email protected]: http://qcpages.qc.cuny.edu/∼rmiller
ANTONIO MONTALBÁN
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA BERKELEY, CA, USAE-mail: [email protected]: www.math.berkeley.edu/∼antonio
Get access Rights & Permissions [Opens in a new window]

Abstract

Our main result is the equivalence of two notions of reducibility between structures. One is a syntactical notion which is an effective version of interpretability as in model theory, and the other one is a computational notion which is a strengthening of the well-known Medvedev reducibility. We extend our result to effective bi-interpretability and also to effective reductions between classes of structures.

Keywords

computable functoreffective interpretabilityƩ-reducibility
Type
Articles
Information
The Journal of Symbolic Logic , Volume 82 , Issue 1 , March 2017 , pp. 77 - 97
Copyright
Copyright © The Association for Symbolic Logic 2017 

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, Chris, Knight, Julia, Manasse, Mark, and Slaman, Theodore, Generic copies of countable structures . Annals of Pure and Applied Logic, vol. 42 (1989), no. 3, pp. 195–205.Google Scholar
Chisholm, John, Effective model theory vs. recursive model theory, this Journal, vol. 55 (1990), no. 3, pp. 1168–1191.Google Scholar
Ershov, Yuri L., Definability and Computability. Siberian School of Algebra and Logic. Consultants Bureau, New York, 1996.Google Scholar
Hirschfeldt, Denis R., Khoussainov, Bakhadyr, Shore, Richard A., and Slinko, Arkadii M., Degree spectra and computable dimensions in algebraic structures . Annals of Pure and Applied Logic, vol. 115 (2002), no. 1–3, pp. 71–113.CrossRefGoogle Scholar
Hodges, Wilfrid, Model Theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993.CrossRefGoogle Scholar
Kalimullin, I. Sh., Relations between algebraic reducibilities of algebraic systems . Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, vol. 53 (2009), no. 6, pp. 71–72.Google Scholar
Marker, David, Model Theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002.Google Scholar
Melnikov, Alexander G., Computable ordered abelian groups and fields , In Programs, Proofs, Processes, Lecture Notes in Computer Science, vol. 6158, Springer, Berlin, 2010, pp. 321–330.Google Scholar
Melnikov, Alexander G., Effective properties of completely decomposable abelian groups . Ph.D. Thesis, Novosibirsk State University, 2012.Google Scholar
Morozov, Andrei S. and Korovina, Margarita V., On Ʃ-definability without equality over the real numbers . Mathematical Logic Quarterly, vol. 54 (2008), no. 5, pp. 535–544.CrossRefGoogle Scholar
Marker, David and Miller, Russell, Turing degree spectra of differentially closed fields, 2016, preprint.Google Scholar
Montalbán, Antonio, Computability theoretic classifications for classes of structures , Proceedings of ICM 2014, vol. 2 (2014), pp. 79–101.Google Scholar
Montalbán, Antonio, Notes on the jump of a structure . In Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, vol. 5635, Springer, Berlin, 2009, pp. 372–378.CrossRefGoogle Scholar
Montalbán, Antonio, Rice sequences of relations . Philosophical Transactions of the Royal Society, A: Mathematical, Physical & Engineering Sciences, vol. 370 (2012), no. 1971, pp. 3464–3487.Google Scholar
Montalbán, Antonio, A fixed point for the jump operator on structures, this Journal, vol. 78 (2013), no. 2, pp. 425–438.Google Scholar
Miller, R., Poonen, B., Schoutens, H., and Shlapentokh, A., A computable functor from graphs to fields, to appear.Google Scholar
González, Victor Ocasio, Computability in the Class of Real Closed Fields , Ph.D. Thesis, Notre Dame University, 2014.Google Scholar
Puzarenko, V. G., On a certain reducibility on admissible sets . Sibirskii Matematicheskii Zhurnal, vol. 50 (2009), no. 2, pp. 415–429.Google Scholar
Soskova, Alexandra A. and Soskov, Ivan N., A jump inversion theorem for the degree spectra . Journal of Logic and Computation, vol. 19 (2009), no. 1, pp. 199–215.Google Scholar
Stukachev, Alexey, Degrees of presentability of models. I . Algebra Logika, vol. 46 (2007), no. 6, pp. 763–788, 793–794.Google Scholar
Stukachev, Alexey, On degrees of presentability of models. II . Algebra Logika, vol. 47 (2008), no. 1, pp. 108–126, 131.Google Scholar
Stukachev, Alexey, Effective model theory: an approach via Ʃ-definability , Effective Mathematics of the Uncountable, Lecture Notes in Logic, vol. 41, pp. 164–197, Association of Symbolic Logic, La Jolla, CA, 2013.Google Scholar