Connecticut CT Logic Seminar

Model completeness and relative decidability of countable structures

Reed Solomon (University of Connecticut)

Monday, October 8, 2018 4:45 pm
MONT 214 (Storrs)

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.