STRUCTURAL HIGHNESS NOTIONS

DOI10.1017/JSL.2022.35arXiv2109.07619OpenAlexW3199451800MaRDI QIDQ6140191FDOQ6140191

Authors: Wesley Calvert, Johanna N. Y. Franklin, Dan Turetsky 

Publication date: 22 December 2023

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2109.07619

Recommendations

• Isomorphism relations on computable structures
• Strong isomorphism reductions in complexity theory
• Degrees that Are Low for Isomorphism
• Degrees of categoricity on a cone via \(\eta\)-systems
• Degrees of and lowness for isometric isomorphism

zbMATH Keywords

degree high for isomorphismdegree high for isomorphism for Harrison ordersdegree high for pathsdegree highness for descending sequencesHarrison orderjump complete degreeScott complete degree

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45)

Cites Work

• Title not available (Why is that?)
• Computable structures and the hyperarithmetical hierarchy
• Title not available (Why is that?)
• Isomorphism relations on computable structures
• Notions of weak genericity
• Relativizations of randomness and genericity notions
• Title not available (Why is that?)
• Degrees that Are Low for Isomorphism
• The Friedberg-Muchnik Theorem Re-Examined
• Higher recursion theory
• Title not available (Why is that?)
• A degree-theoretic definition of the ramified analytical hierarchy
• Π₁¹ relations and paths through
• Computable trees of Scott rank ω₁^CK, and computable approximation
• Title not available (Why is that?)
• Recursion theory. Computational aspects of definability
• Lowness for isomorphism and degrees of genericity
• Degrees of and lowness for isometric isomorphism
• Recursiveness in Π 1 1 Paths Through | mathscrO
• Lowness for isomorphism, countable ideals, and computable traceability
• Taking the path computably traveled

This page was built for publication: STRUCTURAL HIGHNESS NOTIONS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6140191)