Computable Functors between Nested Equivalence Structures and Full Trees of Finite Height

Model theory seminarFriday, May 8, 201512:30 pmGC 6417

Leah Marshall

Computable Functors between Nested Equivalence Structures and Full Trees of Finite Height

George Washington University

Trees have long been used throughout mathematics to better understand and represent many different types of objects and structures. In this talk we examine finitely nested equivalence structures. Such structures consist of a set of natural numbers and a finite number of equivalence relations which are nested inside of each other. (That is, their resulting equivalence classes are subsets of each other.) We utilize the notions of category theory to build functors between nested equivalence structures and full trees of finite height. These functors behave quite nicely, and we build them in a computable way so that the various computability-theoretic properties of the structures are preserved. We discuss computable isomorphisms and the Turing degree spectrum of a structure – defining and giving examples of each, and showing how, once our computable functors are constructed, such properties transfer readily between nested equivalence structures and trees.

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 January 30th, 2015