Geodesic
On $\Sigma^0_1$-Classification of Relations on Computable Structures
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 8 (2008) no. 4, pp. 23-32 
S. S. Goncharov; N. T. Kogabaev. On $\Sigma^0_1$-Classification of Relations on Computable Structures. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 8 (2008) no. 4, pp. 23-32. http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a2/
@article{VNGU_2008_8_4_a2,
     author = {S. S. Goncharov and N. T. Kogabaev},
     title = {On $\Sigma^0_1${-Classification} of {Relations} on {Computable} {Structures}},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {23--32},
     year = {2008},
     volume = {8},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a2/}
}
TY  - JOUR
AU  - S. S. Goncharov
AU  - N. T. Kogabaev
TI  - On $\Sigma^0_1$-Classification of Relations on Computable Structures
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2008
SP  - 23
EP  - 32
VL  - 8
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a2/
LA  - ru
ID  - VNGU_2008_8_4_a2
ER  - 
%0 Journal Article
%A S. S. Goncharov
%A N. T. Kogabaev
%T On $\Sigma^0_1$-Classification of Relations on Computable Structures
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2008
%P 23-32
%V 8
%N 4
%U http://geodesic.mathdoc.fr/item/VNGU_2008_8_4_a2/
%G ru
%F VNGU_2008_8_4_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper the example of computable structure in the language with infinite number of binary predicate symbols without $\Sigma^0_1$-classification of all unary relations, which are definable by $\Sigma^0_1$-formulas on the structure, is constructed.

[1] Goncharov S. S., Nait Dzh., “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41:6 (2002), 639–681

[2] Friedberg R. M., “Three Theorems on Recursive Enumeration”, J. Symbolic Logic, 23:3 (1958), 309–316

[3] Goncharov S. S., Sorbi A., “Obobschenno-vychislimye numeratsii i netrivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641

[4] Goncharov S. S., Lempp S., Solomon D. R., “Fridbergovy numeratsii semeistv $n$-vychislimo perechislimykh mnozhestv”, Algebra i logika, 41:2 (2002), 143–154

[5] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli, Nauchnaya kniga, Novosibirsk, 1999

[6] Yu. Ershov, S. Goncharov, A. Nerode, J. Remmel (eds.), V. Marek (ass. ed.), Handbook of Recursive Mathematics, v. 1–2, Studies in Logic and the Foundation of Mathematics, Elsever, Amsterdam–Lausanne–N. Y.–Oxford–Shanon–Singapore–Tokio, 1998