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 Δ2-categoricity, giving sufficient conditions for relative Δ2-categoricity, and exploring many of the other conditions to show non-Δ2-categoricity. Finally, we show that all partial computable injection structures must be relatively Δ3-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.

Author

• Marshall, Leah

Language

• en

Keyword

• Computable categoricity
• Trees
• Computable functors
• Computable structures
• Partial injection structures
• Nested equivalence structures

Date created

• 2015

Type of Work

• Dissertation

License

• All rights reserved

Rights statement

• In Copyright

GW Unit

• Mathematics

Degree

• Ph.D.

Advisor

• Harizanov, Valentina

Committee Member(s)

• Miller, Russell
• Friend, Michele
• Przytycki, Jozef
• Robinson Jr., E. A.

Persistent URL

•  https://scholarspace.library.gwu.edu/etd/z890rt430