×

A solution of the Goncharov-Ash problem and the spectrum problem in the theory of computable models. (English. Russian original) Zbl 1041.03030

Dokl. Math. 61, No. 2, 178-179 (2000); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 371, No. 1, 30-31 (2000).
From the text: An important open problem in the field of computable models is the Goncharov-Ash problem about the relation between the algorithmic dimension of a model \({\mathcal B}\) and of its enrichment \(({\mathcal B},c_1,c_2,\dots, c_m)\) by a finite set of constants. Note that the inequality \[ \dim({\mathcal B})\leq \dim({\mathcal B},c_1,c_2,\dots, c_m) \] is always fulfilled.
The following theorem gives a complete solution to the Goncharov-Ash problem.
Theorem 1. For any nonzero cardinal \(n\leq\omega\), there exists an autostable model \({\mathcal B}\) such that the algorithmic dimension of the model \(({\mathcal B},c)\) equals \(n\) for an arbitrary constant \(c\in{\mathcal B}\).

MSC:

03C57 Computable structure theory, computable model theory