STRUCTURAL HIGHNESS NOTIONS

DOI10.1017/JSL.2022.35MaRDI QIDQ6140191zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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)