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}\).
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 |