Logic Seminar

Speaker: Hakim Walker, GWU

Title: Diagonalizing against Scott families

Abstract: A computable structure M is computably categorical if for every computable copy C of M, there is a computable isomorphism from M to C. Furthermore, a computable structure M is relatively computably categorical if for every copy B of M, there is an isomorphism computable in the atomic diagram of B. Goncharov showed that M is relatively computably categorical if and only if M has a formally computably enumerable Scott family. Every relatively computably categorical structure is also computably categorical, but the converse does not hold. We will present the construction of a directed graph that is computably categorical but not relatively so, by demonstrating the technique of diagonalizing against Scott families.