Hostname: page-component-5cf477f64f-tgq86 Total loading time: 0 Render date: 2025-03-31T22:25:04.460Z Has data issue: false hasContentIssue false
  • English
  • Français

THE TREE OF TUPLES OF A STRUCTURE

Part of: Computability and recursion theory Model theory

Published online by Cambridge University Press:  07 September 2020

MATTHEW HARRISON-TRAINOR  and
ANTONIO MONTALBÁN
MATTHEW HARRISON-TRAINOR
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTON, NEW ZEALAND and THE INSTITUTE OF NATURAL AND MATHEMATICAL SCIENCES MASSEY UNIVERSITY, NEW ZEALANDE-mail: [email protected]: http://homepages.ecs.vuw.ac.nz/~harrism1/
ANTONIO MONTALBÁN
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA, BERKELEY, CA, USAE-mail: [email protected]: http://www.math.berkeley.edu/~antonio/index.html
Get access Rights & Permissions [Opens in a new window]

Abstract

Our main result is that there exist structures which cannot be computably recovered from their tree of tuples. This implies that there are structures with no computable copies which nevertheless cannot code any information in a natural/functorial way.

Keywords

computable structure theoryback-and-forthcoding

MSC classification

Primary: 03D45: Theory of numerations, effectively presented structures
Secondary: 03C57: Effective and recursion-theoretic model theory
Type
Article
Information
The Journal of Symbolic Logic , Volume 87 , Issue 1 , March 2022 , pp. 21 - 46
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

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

Downey, R. G., Kach, A. M., Lempp, S., Lewis-Pye, A. E. M., Montalbán, A., and Turetsky, D. D., The complexity of computable categoricity. Advances in Mathematics , vol. 268 (2015), pp. 423–466.CrossRefGoogle Scholar
Ershov, Y. L., Definability and computability , Siberian School of Algebra and Logic, Consultants Bureau, New York, 1996.Google Scholar
Friedman, H. and Stanley, L., A Borel reducibility theory for classes of countable structures. this Journal , vol. 54 (1989), no. 3, pp. 894–914.Google Scholar
Goncharov, S., Harizanov, V., Knight, J., McCoy, C., Miller, R., and Solomon, R., Enumerations in computable structure theory. Annals of Pure and Applied Logic , vol. 136 (2005), no. 3, pp. 219–246.CrossRefGoogle Scholar
Harrison-Trainor, M., Melnikov, A., Miller, R., and Montalbán, A., Computable functors and effective interpretability. this Journal , vol. 82 (2017), no. 1, pp. 77–97.Google Scholar
Kalimullin, I., Enumeration degrees and enumerability of families. Journal of Logic and Computation , vol. 19 (2009), no. 1, pp. 151–158.10.1093/logcom/exn032CrossRefGoogle Scholar
Kalimullin, I., Algorithmic reducibilities of algebraic structures. Journal of Logic and Computation , vol. 22 (2012), no. 4, pp. 831–843.CrossRefGoogle Scholar
Kalimullin, I. S. and Puzarenko, V. G., Reducibility on families. Algebra Logika , vol. 48 (2009), no. 1, pp. 31–53, 150, 152.10.1007/s10469-009-9037-1CrossRefGoogle Scholar
Knight, J. F., Degrees coded in jumps of orderings, this Journal , vol. 51 (1986), no. 4, pp. 1034–1042,Google Scholar
Knight, J., Soskova, A., and Vatev, S., Coding in graphs and linear orderings. Preprint. https://doi.org/10.1017/jsl.2019.91 CrossRefGoogle Scholar
Miller, R., Poonen, B., Schoutens, H., and Shlapentokh, A., A computable functor from graphs to fields, this Journal , vol. 83 (2018), no. 1, pp. 326–348.Google Scholar
Montalbán, A., A fixed point for the jump operator on structures, this Journal , vol. 78 (2013), no. 2, pp. 425–438.Google Scholar
Montalbán, A., A fixed point for the jump operator on structures, this Journal , vol. 78 (2013), no. 2, pp. 425–438.Google Scholar
Montalbán, A., Computability theoretic classifications for classes of structures , Proceedings of the International Congress of Mathematicians (Seoul 2014), vol. II (Jang, S. Y., Kim, Y. R., Lee, D.-W., and Yie, I., editors), Kyung Moon Sa Co., Seoul, 2014, pp. 79–101.Google Scholar
Montalbán, A., Computable structure theory: Within the arithmetic. In preparation, P1.Google Scholar