Countably categorical theories (Q1928482)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Countably categorical theories |
scientific article |
Statements
Countably categorical theories (English)
0 references
3 January 2013
0 references
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.
0 references
Ershov conjecture about representability via linear orders
0 references
indiscernibles
0 references
Fraïssé limit
0 references
countably categorical theory
0 references
decidable theory
0 references
decidable model
0 references