zbMATH — the first resource for mathematics

Computable structure and non-structure theorems. (Russian, English) Zbl 1034.03044
Algebra Logika 41, No. 6, 639-681 (2002); translation in Algebra Logic 41, No. 6, 351-373 (2002).
A new methodological approach to the study of classes of models is discussed.
Assume \(K\) is an abstract class of models. The authors consider two main general methodological notions for classes of models, namely: a characterization of \(K\) is anything that distinguishes elements of \(K\) and its non-elements; a classification (or structure theorem) for \(K\) is a system of invariants that defines each element of \(K\) up to isomorphism.
Intuitively, some classes of models have characterization and classification we consider as good and suitable, while for some other classes the situation is different. Why is this so? Trying to answer this question, the authors concretize these two basic notions in three ways: basing upon infinitary sentences, index sets, and numberings respectively. Basic properties of these concepts and their relationship are studied. These concepts and ideas are applied to some classes of models usually brought to mathematicians’ notice. The authors consider the results of this study to answer to the intuition.

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures