Jonny Stephenson, Department of Pure Mathematics, University of Waterloo
"Effective Bi-interpretability with Graphs"
We will complete our study of effective bi-interpretability by showing that every structure is effectively bi-interpretable with a graph. The result will be proved using a two-step process. We will first show that each structure is effectively bi-interpretable with a structure over a language $\{U,E\}$, in which $U$ is a unary relation used to represent the domain of the interpreted structure, and $E$ is a binary relation used to code the relations in the interpretation. We will then show that structures over this two-element signature are effectively bi-interpretable with graphs. Thus by composition, every structure is effectively bi-interpretable with a graph. The universality of graphs in this context is not unique: there are a number of similar results for other well-known classes of structure.
MC 5403