Liam Tan of UIC : Characterizing Relative Decidability

Posted by Michael Lange , part of the Louise Hay Logic Seminar.

At

Sept. 9, 2026, 11 a.m.

In

SEO 427

Abstract

The main objective of this talk is to understand when computational properties of structures have model-theoretic explanations. I will introduce the notion of relative decidability of theories. A theory is relatively decidable if, for every model of the theory, its elementary diagram can be computed from its atomic diagram together with the theory. I will then present a theorem of Chubb, Miller, and Solomon characterizing the uniformly relatively decidable c.e. theories as exactly the model-complete c.e. theories. Finally, I will discuss joint work from my REU with Matthew Harrison-Trainor showing that, for complete theories, relative decidability is equivalent to model-completeness after a finite expansion by constants. I will sketch a proof of this result.

 I will provide background on computability theory as needed.