Luke MacLean, Department of Pure Mathematics, University of Waterloo
"Relations enumerable from positive information"
This talk will look at computable structures from the perspective of enumeration reducibility. We look at the class of relations such that the relation interpreted in a structure is enumerable using only positive information from the structure and show that they are exactly those that are definable by computable $\Sigma_1$ formulas that use only positive information. We define a new notion of the jump of a structure by adding the complements of all these relations to our language. This increases the degree of the structure relative to enumeration reducibility in a way that agrees more with the traditional enumeration jump of sets than any other attempt at defining the enumeration jump of a structure.
Time permitting, we will see how a notion of bi-interpretability between structures using these new positive computable $\Sigma_1$ formulas is equivalent to there being an adjoint equivalence between the isomorphism classes of the structures which is witnessed by enumeration operators. These positive enumerable functors were studied by Barbara Csima, Dino Rossegger, and Daniel Yu.
All of this is joint work with Barbara Csima and Dino Rossegger.
MC 5403