Computable categoricity relative to a c.e. degree

2024/01/12 by Java Darleen Villano, Villano, Java Darleen
Computer Science · #03D25 #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2401.06641

openalex publication_date 2024/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A computable graph G is computably categorical relative to a degree d if and only if for all d-computable copies B of G, there is a d-computable isomorphism f:G\toB. In this paper, we prove that for every computable partially ordered set P and computable partition P=P₀\sqcup P₁, there exists a computable computably categorical graph G and an embedding h of P into the c.e. degrees where G is computably categorical relative to all degrees in h(P₀) and not computably categorical relative to any degree in h(P₁). This is a generalization of a 2021 result by Downey, Harrison-Trainor, and Melnikov.

Related

• Extensions of categoricity relative to a degree
• Notes on degrees of relative computable categoricity
• Degrees of Categoricity Above Limit Ordinals
• Degrees of categoricity and treeable degrees
• Isomorphism Spectra and Computably Composite Structures