Computability theoretic properties of isomorphisms between partial computable injection structures

NERDS: New England Recursion & Definability SeminarSaturday, October 18, 20142:00 pmAssumption College, Worcester, MA

Leah Marshall

Computability theoretic properties of isomorphisms between partial computable injection structures

George Washington University

A partial computable injection structure consists of a computable set of natural numbers and a partial computable, injective (1-1) function. Clearly, the isomorphism type of such a structure is determined by the kinds and number of orbits of the elements under the function application. First, we investigate partial computable injection structures always having computable isomorphisms to other isomorphic structures, and we analyze what goes wrong in structures without such computable isomorphisms. Additionally, we do the same for partial computable injection structures under Δ2-isomorphisms and Δ3-isomorphisms.

Leah Marshall is a graduate student at George Washington University, working on a doctorate in computability theory under the supervision of Valentina Harizanov.

Posted by on September 16th, 2014