Matthew Harrison-Trainor : A characterization of relative decidability

Posted by Matthew Harrison-Trainor , part of the Logic Seminar.

At

Jan. 27, 2026, 3 p.m.

In

636 SEO

Abstract

Let T be a recursively axiomatizable first-order theory. We say that T is relatively decidable if, for any model of T, the atomic diagram of that model can compute the full elementary diagram. For example, if T is model complete, then there is a uniform decision procedure which works for any model of T. We characterize the complete relatively decidable theories by showing that they have a sort of conservative extension which is model complete. The proof combines a standard theorem from computable structure theory with an intricate but elementary model-theoretic argument.