Logic Seminar
Reed SolomonUniversity of Connecticut
Title: Model completeness and relative decidability of countable structures
Tuesday, October 16, 2018 - 2:55pm
Malott 206
Abstract: The definition for T to be a model complete theory is equivalent to T having quantifier elimination down to existential formulas. It follows quickly from this quantifier elimination that every computable model of a c.e. model complete theory must be decidable. We call a structure relatively decidable if it has this property more broadly: for every copy M of the structure with domain omega, the elementary diagram of M is Turing reducible to the atomic diagram of M. In this talk, we will discuss connections between model completeness and relative decidability. This work is joint with Jennifer Chubb and Russell Miller.