Countably categorical theories

DOI10.1007/S10469-012-9187-4MaRDI QIDQ1928482zbMATH OpenOpenAlexFDO

Authors Vadim G. Puzarenko

Publication date 3 January 2013

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10469-012-9187-4

zbMATH Keywords

countably categorical theorydecidable modeldecidable theoryErshov conjecture about representability via linear ordersFraïssé limitindiscernibles

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Other model constructions (03C30) Categoricity and completeness of theories (03C35) Model theory of ordered structures; o-minimality (03C64)

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.

Recommendations

• scientific article; zbMATH DE number 2154089
• The complexity of isomorphism for complete theories of linear orders with unary predicates
• Computability and uncountable linear orders. I: Computable categoricity.
• \(\Sigma \)-definability of uncountable models of \(c\)-simple theories
• On quantifier-rank equivalence between linear orders
• A five element basis for the uncountable linear orders
• scientific article; zbMATH DE number 2167511
• scientific article; zbMATH DE number 3884139
• On interpretability of almost linear orderings
• The metamathematics of scattered linear orderings

Cites work

• Computability of Fraïssé limits
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 1302874 (Why is no real title available?)
• scientific article; zbMATH DE number 2047495 (Why is no real title available?)
• scientific article; zbMATH DE number 2154089 (Why is no real title available?)
• scientific article; zbMATH DE number 1873434 (Why is no real title available?)
• scientific article; zbMATH DE number 1390542 (Why is no real title available?)
• Indiscernibles and decidable models

Cited in

(14)

• Strongly minimal countably categorical theories. II
• Strongly minimal countably categorical theories. III
• Once more on countably categorical sentences
• Theories categorical in power \(n+2\)
• A decidable countably categorical model without nontrivial recursive automorphisms
• On the ``heap problem
• scientific article; zbMATH DE number 4004164 (Why is no real title available?)
• The index set of uncountably categorical theories
• scientific article; zbMATH DE number 175638 (Why is no real title available?)
• Constructive models of uncountably categorical theories
• scientific article; zbMATH DE number 4121975 (Why is no real title available?)
• Combinations related to classes of finite and countably categorical structures and their theories
• STACS 2005
• Countable categoricity

This page was built for publication: Countably categorical theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1928482)