RUS  ENG
Full version
JOURNALS // Siberian Journal of Pure and Applied Mathematics // Archive

Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 2008 Volume 8, Issue 1, Pages 71–76 (Mi vngu281)

Complexity of Index Sets for Several Classes of Models

E. N. Pavlovsky

Novosibirsk State University

Abstract: When we study questions about computable characterization existence for different classes of models the approach suggested by Goncharov and Knight [1] is effective. It consists of obtaining precise estimations of index sets of such classes in corresponding hierarchy.
For the universal numeration of computable models in non-trivial computable language there were found precise estimations of the following index sets of computable models classes: models with Ehrenfeucht theory ($\Pi^1_1$), models with a theory admitting infinitely many countable models ($\Sigma^1_1$).

UDC: 510.67, 510.5+510.635

Received: 13.02.2008



© Steklov Math. Inst. of RAS, 2024