Computable categoricity, linear orders and permitting

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20162:30 pmLocklin Hall, Room 232, Springfield College

Marie Nicholson

Computable categoricity, linear orders and permitting

University of Connecticut

Remmel showed that a computable linear order L is computably categorical if and only if the order type of L has only a finite number of successivities. As part of the proof, Remmel assumes that L has infinitely many successivities and constructs another computable linear order R, which is not computably isomorphic to L, and a Δ02-isomorphism f such that f is an isomorphism from L onto R. Hence showing that L is not computably categorical. In this talk I will discuss the conditions under which we can use permitting arguments to construct f below certain types of Δ02 degrees.

Posted by on March 9th, 2016