Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
This seminar will discuss some of the ideas of computable structure theory, which aims to apply computability-theoretic ideas to structures from other areas of mathematics.
A structure of first order logic is said to be computable if there is an algorithmic procedure which specifies the domain of the structure, as well as the relations and functions of the structure. The usual approach to structures of of first order logic is to regard any two isomorphic structures as being completely interchangeable. However, from a computability-theoretic perspective, it is quite natural to restrict ourselves to only considering structures which are computable, and to regard two computable copies of a given structure as being equivalent only when they are isomorphic via a computable map. Having made this distinction, we say the computable dimension of a structure is the number of computable copies it has, up to computable isomorphism. The computable dimension of a structure can be finite or infinite. In the case that the computable dimension is larger than 1, there are computable copies of the structure between which there are only noncomputable isomorphisms. In that case we may be interested in the Turing degrees of those isomorphisms.
In joint work with Barbara Csima, I have recently been working with structures of finite com- putable dimension. I will discuss some of our results regarding the degrees of isomorphisms between computable presentations of such structures.
Some basic familiarity with computability theory is desirable, but I will try to be fairly accessible.
MC 5413