zbMATH — the first resource for mathematics

Computably categorical structures and expansions by constants. (English) Zbl 0928.03040
It is an easy consequence of the Ryll-Nardzewski theorem that if the theory of an arbitrary structure \({\mathcal{A}}\) is countably categorical then so is the theory of any expansion of \({\mathcal{A}}\) by finitely many constants. The problem is to consider the situation for effective model theory. {T. Millar} [J. Symb. Log. 51, No. 2, 430-434 (1986; Zbl 0631.03018)] proved the analogous result (with an additional assumption on \({\mathcal{A}}\)) for the notion of computable (=recursive) categoricity, i.e. computable categoricity is preserved under the above mentioned expansions in case the existential theory of a computable (=recursive) structure \({\mathcal{A}}\) is decidable. Here, the authors solve the general problem negatively. More precisely, it is proved that for each \(k\in\omega\) there is a computably categorical structure \({\mathcal{A}}\) whose expansion obtained by adding a constant naming any element of \({\mathcal{A}}\) has dimension \(k\), where the dimension of a structure \({\mathcal{A}}\) is the number of computable isomorphism types of computable structures (classically) isomorphic to \({\mathcal{A}}\).

03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] Philosophical Transactions of the Royal Society of London 248 pp 407–432– (1956)
[2] Algebra i Logika 19 pp 621–639– (1980)
[3] Aspects of effective algebra (1979)
[4] Logical methods pp 1–91– (1993)
[5] Transactions of the American Mathematical Society 95 pp 341–360– (1960)
[6] Recursive categoricity and persistence 51 pp 430–434– (1986)
[7] Handbook of recursion theory
[8] Uspekhi Matemematischeskoe Nauk 16 pp 3–60– (1961)
[9] Comptes Rendus de l’AcadĂ©mic des Sciences, Paris 240 pp 151–153– (1955)
[10] Izvestiya kademiya Nauk Kazakhstan SSR 1 pp 83–94– (1974)
[11] Annals of Pure and Applied Logic
[12] Recursively presentable prime models 39 pp 305–309– (1974)
[13] Annals of Pure and Applies Logic 60 pp 1–30– (1993)
[14] Handbook of recursive mathematics · Zbl 0930.03037
[15] Fundamenta Mathematicae 44 pp 61–71– (1957)
[16] Logic notebook: problems in mathematical logic (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.