Countably categorical theories (Q1928482)

The author refutes the following conjecture of Ershov about representability via linear orders: If a theory \(T\) has an uncountable model that is \(\Sigma\)-definable in \({\mathbf H}{\mathbf F}({\mathfrak M})\) for an algebraic structure \({\mathfrak M}\) with a simple theory, then the theory \(T\) also has an uncountable model that is \(\Sigma\)-definable in \({\mathbf H}{\mathbf F}(L)\) for some dense linear order \(L\) (see [\textit{Yu. L. Ershov}, in: Handbook of recursive mathematics. Vol. 1. Recursive model theory. Amsterdam: Elsevier. 235--260 (1998; Zbl 0940.03043), p. 256, bottom]). Here, \({\mathbf H}{\mathbf F}({\mathfrak M})\) is the hereditarily finite super-structure over \({\mathfrak M}\), and `simple' has its own long definition. By Ershov's work and the author's improvement, the task boils down to constructing a decidable countably categorical theory of finite signature which has no decidable model with an infinite computable set of order indiscernibles. The construction is carried out using the Fraïssé limit and the convolution of theories -- tools that expand domains, signatures, and theories gradually to achieve the desired result.