Computable structures and isomorphisms
Speaker:
Jonathan Stephenson, Valparaiso University
Date and Time:
Monday, June 4, 2018 - 3:00pm to 3:20pm
Location:
University of Waterloo - MC 5501
Abstract:
If $f\colon\mathcal{A}\to\mathcal{B}$ is an isomorphism between computable copies of a structure, then it is clear that for a computable subset $U$ of the domain of $\mathcal{A}$, $f(U)\leq_T f$. In many constructions we make use of this phenomenon by choosing $U$ for which $f(U)=_T f$. For instance, this is a common step in computing the degree of categoricity of a structure. We ask the question: under what circumstances is it possible to find such a set $U$? We focus on the linear orders $\omega$ and $\omega^2$ as examples.
This is joint work with B. Csima and M. Deveau. B. Csima was partially supported by Canadian NSERC Discovery Grant 312501. M. Deveau was partially supported by Canadian NSERC Postgraduate Scholarship PGSD1-234567-2017.