Contact Info
Pure MathematicsUniversity of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada
N2L 3G1
Departmental office: MC 5304
Phone: 519 888 4567 x43484
Fax: 519 725 0160
Email: puremath@uwaterloo.ca
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
Departmental office: MC 5304
Phone: 519 888 4567 x43484
Fax: 519 725 0160
Email: puremath@uwaterloo.ca
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.