Computability-Theoretic Properties of Partial Injections, Trees, and Nested Equivalences

We examine computable isomorphisms and other related computability-theoretic properties of three types of countable structures -- partial injection structures, full finite height trees, and nested equivalence structures.;We generalize the notion of injection structures -- consisting of a set of natural numbers and an injective (1-1) function -- and define partial injection structures by considering only partial functions. We make significant progress towards completely classifying computable categoricity for partial injection structures by giving two sufficient conditions for relative computable categoricity. We furthermore explore the other conditions on partial injection structures, and show non-computable categoricity. We do the same for [specail characters omitted]-categoricity, giving sufficient conditions for relative [specail characters omitted]-categoricity, and exploring many of the other conditions to show non-[specail characters omitted]-categoricity. Finally, we show that all partial computable injection structures must be relatively [specail characters omitted] -categorical.;We next explore finitely nested equivalence structures and show that they can be represented as trees. Furthermore, we show that every tree under certain conditions, specifically being full and of finite height ≥ 2, can be represented as a nested equivalence structure. Moreover, we do this in an algorithmic manner and build a functor between the two types of structures. We show that this functor behaves nicely -- it is full, faithful, essentially onto, and computable. We then leverage the ability to go between trees and nested equivalence structures, and transfer results between the two. We provide previously unknown answers to questions related to computable categoricity and the Turing degree spectra of nested equivalence structures.