Logic Seminar
Matthew Harrison-Trainor
UIC
A characterization of relative decidability
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.
Tuesday January 27, 2026 at 3:00 PM in 636 SEO