Graduate Student Seminar
Fri, 31 March, 2017
7:00pm
Title: Priority Argument Constructions for Graphs and Trees
Speaker:Hakim Walker, GWU
Abstract: In computable model theory, we study the algorithmic content and properties of classical mathematical structures, such as groups, vector spaces, linear orders, etc. In particular, one area that we examine is the computational complexity of additional relations on the structures, as well as isomorphisms between structures. It is usually the case that while a structure itself is computable, additional relations on the structure are not computable. Also, we often have two computable structures that are isomorphic to each other but have no computable isomorphism between them. One of the most common ways to demonstrate these non-computable properties is to use a priority argument, which is a generalization of Cantor's diagonal argument.
In this talk, we will demonstrate both priority and non-priority arguments on a type of directed graph called a (2,1):1 structure, which consists of a countable set A together with a function f: A --> A such that every element has exactly one or exactly two pre-images under f. Both types of argument will allow us to build structures with various non-computable properties, but we will see that priority arguments are much more powerful and are often necessary to build more interesting examples and generalize results.