Computability Theory Learning Seminar

Luke MacLean, Department of Pure Mathematics, University of Waterloo

"Coding isomorphisms without using relations"

Computable structure theory is concerned with the complexity of mathematical structures. A very natural question in this vein is "how difficult are isomorphisms between copies of a structure to compute?". To show that a structure has isomorphisms of a given complexity, it is often easiest to start with a standard presentation of the structure and construct a copy, ensuring that knowledge of the isomorphism is enough to compute a known set of the given complexity. Moreover, the most common way to ensure the isomorphism is computationally powerful enough is to construct in tandem a computable unary relation whose image can tell us the whole isomorphism. This begs the question of whether or not it is possible for a structure to have a complex isomorphism between copies, but no computable unary relation whose image can compute the isomorphism.

For simple enough structures, this question is answerable, but it quickly becomes very difficult as the structure admits copies with harder isomorphisms. For very complicated constructions we turn to machinery known as metatheorems. These give certain conditions that, if met, produce a computable copy with the desired properties, without having to handle all of the complicated combinatorial components of the construction.

To tackle the question for the linear order $$\omega^2$$, a new game-style metatheorem by Antonio Montalban is employed to show that it has a computable copy $$\mathcal{A}$$ such that the isomorphism $$f$$ from $$\mathcal{A}$$ into the standard copy can compute $$\emptyset'''$$, and yet, there is no computable unary relation $$U$$ on $$\mathcal{A}$$ such that $$f(U) \geq_T f$$.

This will be a series of three talks in which no knowledge of computability theory is necessary.

MC 5403