Hostname: page-component-6bf8c574d5-mggfc Total loading time: 0 Render date: 2025-02-20T07:00:14.490Z Has data issue: false hasContentIssue false
  • English
  • Français

STRUCTURAL HIGHNESS NOTIONS

Part of: Model theory Computability and recursion theory

Published online by Cambridge University Press:  28 April 2022

WESLEY CALVERT Open the ORCID record for WESLEY CALVERT [Opens in a new window] ,
JOHANNA N. Y. FRANKLIN Open the ORCID record for JOHANNA N. Y. FRANKLIN [Opens in a new window]  and
DAN TURETSKY
WESLEY CALVERT*
Affiliation:
SCHOOL OF MATHEMATICAL AND STATISTICAL SCIENCES SOUTHERN ILLINOIS UNIVERSITY MAIL CODE 4408, 1245 LINCOLN DRIVE CARBONDALE, IL 62901, USA URL: http://lagrange.math.siu.edu/calvert
JOHANNA N. Y. FRANKLIN
Affiliation:
DEPARTMENT OF MATHEMATICS HOFSTRA UNIVERSITY ROOM 306, ROOSEVELT HALL HEMPSTEAD, NY 11549-0114, USA E-mail: [email protected] URL: http://www.johannafranklin.net
DAN TURETSKY
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTON WELLINGTON, NEW ZEALAND E-mail: [email protected]
*
E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.

Keywords

highness for isomorphismScott rankHarrison orderingsjump hierarchiestraceability

MSC classification

Primary: 03C57: Effective and recursion-theoretic model theory
Secondary: 03D28: Other Turing degree structures 03D45: Theory of numerations, effectively presented structures
Type
Article
Information
The Journal of Symbolic Logic , Volume 88 , Issue 4 , December 2023 , pp. 1692 - 1724
Check for updates
Copyright
© The Author(s), 2022. 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

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
Bartoszyński, T. and Judah, H., Set Theory: On the Structure of the Real Line , A K Peters, Wellesley, 1995.Google Scholar
Barwise, J., Back-and-forth through infinitary logic , Studies in Model Theory (Morley, M. D., editor), Studies in Mathematics, vol. 8, Mathematical Association of America, Buffalo, 1973, pp. 5–34.Google Scholar
Calvert, W., Knight, J. F., and Millar, J., Computable trees of Scott rank ${\omega}_1^{CK}$ , and computable approximation, Journal of Symbolic Logic, vol. 71 (2006), pp. 283–298.Google Scholar
Chong, C. T. and Yu, L., Recursion Theory , De Gruyter Series in Logic and Its Applications, vol. 8, De Gruyter, Berlin, 2015.CrossRefGoogle Scholar
Csima, B., Degrees of categoricity and related notions, BIRS Computable Model Theory Workshop , 2013.Google Scholar
Downey, R., Hirschfeldt, D., and Khoussainov, B., Uniformity in the theory of computable structures . Algebra and Logic , vol. 42 (2003), no. 5, pp. 566–593, 637.CrossRefGoogle Scholar
Fokina, E. B., Friedman, S.-D., Harizanov, V., Knight, J. F., McCoy, C., and Montalbán, A., Isomorphism relations on computable structures, Journal of Symbolic Logic, vol. 77 (2012), pp. 122–132.Google Scholar
Franklin, J. N. Y., Lowness and highness properties for randomness notions , Proceedings of the 10th Asian Logic Conference (Arai, T., Brendle, J., Kikyo, H., Chong, C. T., Downey, R., Feng, Q., and Ono, H. editors), World Scientific, Hackensack, 2010, pp. 124–151.Google Scholar
Franklin, J. N. Y. and McNicholl, T. H., Degrees of and lowness for isometric isomorphism . Journal of Logic and Analysis , vol. 12 (2020), Article no. 6, 23 pp.Google Scholar
Franklin, J. N. Y. and Solomon, R., Degrees that are low for isomorphism . Computability , vol. 3 (2014), no. 2, pp. 73–89.Google Scholar
Franklin, J. N. Y. and Solomon, R., Lowness for isomorphism, countable ideals, and computable traceability . Mathematical Logic Quarterly , vol. 66 (2020), no. 1, pp. 104–114.Google Scholar
Franklin, J. N. Y., Stephan, F., and Yu, L., Relativizations of randomness and genericity notions . Bulletin of the London Mathematical Society , vol. 43 (2011), no. 4, pp. 721–733.CrossRefGoogle Scholar
Franklin, J. N. Y. and Turetsky, D., Lowness for isomorphism and degrees of genericity . Computability , vol. 7 (2018), no. 1, pp. 1–6.Google Scholar
Franklin, J. N. Y. and Turetsky, D., Taking the path computably traveled . Journal of Logic and Computation , vol. 29 (2019), no. 6, pp. 969–973.Google Scholar
Friedman, H., Recursiveness in ${\varPi}_1^1$ paths through ${\mathcal{O}}$ . Proceedings of the American Mathematical Society , vol. 54 (1976), pp. 311–315.Google Scholar
Gandy, R. O., Kreisel, G., and Tait, W. W., Set existence . Bulletin L’Académie Polonaise des Science, Série des Sciences Mathématiques, Astronomiques et Physiques , vol. 8 (1960), pp. 577–582.Google Scholar
Le Goh, J., Inseparable ${\varPi}_1^1$ sets, in preparation.Google Scholar
Goncharov, S. S., Harizanov, V. S., Knight, J. F., and Shore, R. A., ${\varPi}_1^1$ relations and paths through $\mathbf{\mathcal{O}}$ , Journal of Symbolic Logic, vol. 69 (2004), no. 2, pp. 585–611.Google Scholar
Goncharov, S. S. and Knight, J., Computable structure and antistructure theorems . Algebra and Logic , vol. 41 (2002), no. 6, pp. 639–681, 757.Google Scholar
Jockusch, C. G. Jr. and Simpson, S. G., A degree-theoretic definition of the ramified analytical hierarchy . Annals of Mathematical Logic , vol. 10 (1976), pp. 1–32.Google Scholar
Kurtz, S. A., Notions of weak genericity, Journal of Symbolic Logic, vol. 48 (1983), no. 3, pp. 764–770.Google Scholar
Sacks, G. E., Higher Recursion Theory , Perspectives in Logic, vol. 2, Cambridge University Press, Cambridge, 2016.Google Scholar
Slaman, T. A. and Solovay, R. M., When oracles do not help , Fourth Annual Workshop on Computational Learning Theory , Morgan Kaufman, Los Altos, 1991, pp. 379–383.Google Scholar
Soare, R., The Friedberg–Muchnik theorem re-examined . Canadian Journal of Mathematics , vol. 24 (1972), pp. 1070–1078.Google Scholar
Suggs, J., Degrees that are low for $\mathbf{\mathcal{C}}$ isomorphism . Ph.D. thesis, University of Connecticut, 2015.Google Scholar