Countably categorical theories
type: Item
instance of: scholarly article
title: Countably categorical theories
zbMATH Open document ID: 1272.03144
author: Vadim G. Puzarenko
published in: Algebra and Logic
publication date: 2013-01-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03C35
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03C30
Mathematics Subject Classification ID: 03C64
zbMATH DE Number: 6121539
zbMATH Keywords: Ershov conjecture about representability via linear orders
zbMATH Keywords: indiscernibles
zbMATH Keywords: Fraïssé limit
zbMATH Keywords: countably categorical theory
zbMATH Keywords: decidable theory
zbMATH Keywords: decidable model
MaRDI profile type: Publication
full work available at URL: s10469-012-9187-4
OpenAlex ID: W2052645577
cites work: Q4249360
cites work: Q4003410
cites work: Q4935938
cites work: Computability of Fraïssé limits
cites work: Indiscernibles and decidable models
cites work: Q4451652
cites work: Q4795523
cites work: Q4664636
DOI: 10.1007/S10469-012-9187-4
Recommended article: Q4664636
Recommended article: The complexity of isomorphism for complete theories of linear orders with unary predicates
Recommended article: COMPUTABILITY AND UNCOUNTABLE LINEAR ORDERS I: COMPUTABLE CATEGORICITY
Recommended article: \(\Sigma \)-definability of uncountable models of \(c\)-simple theories
Recommended article: On quantifier-rank equivalence between linear orders
Recommended article: A five element basis for the uncountable linear orders
Recommended article: Q4677695
Recommended article: Q3218108
Recommended article: On interpretability of almost linear orderings
Recommended article: The metamathematics of scattered linear orderings
description: scientific article; zbMATH DE number 6121539