scientific article; zbMATH DE number 2047478

MaRDI QIDQ4451633zbMATH OpenFDO

Authors S. S. Goncharov, J. F. Knight

Publication date 29 February 2004

zbMATH Keywords

classes of modelsclassificationcomputable modelindex setsinfinitary sentencesnumberingsrecursive model

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1302873
• Computability theoretic classifications for classes of structures
• Classification from a Computable Viewpoint
• Computability in special models
• Comparing Classes of Finite Structures

Cited in

(84)

• Index sets for some classes of structures
• Computable structures and the hyperarithmetical hierarchy
• Computable torsion abelian groups
• Classifications of computable structures
• Scott sentences for certain groups
• Coding and definability in computable structures
• A note on computable distinguishing colorings
• Turing computability: structural theory
• Computable topological abelian groups
• Enumerating classes of effective quasi-Polish spaces
• Computable analysis and classification problems
• The isomorphism problem for FST injection structures
• On the isomorphism problem for some classes of computable algebraic structures
• Punctual copies of algebraic structures
• Graphs are not universal for online computability
• Enumerating abelian \(p\)-groups
• A note on decidable categoricity and index sets
• Learning families of algebraic structures from informant
• Classifications of definable subsets
• Scott sentences for equivalence structures
• Categorical linearly ordered structures
• The index set of the groups autostable relative to strong constructivizations
• Degrees of autostability relative to strong constructivizations for Boolean algebras
• Degrees of autostability for linear orders and linearly ordered abelian groups
• Index set of structures with two equivalence relations that are autostable relative to strong constructivizations
• Boolean algebras, Tarski invariants, and index sets
• Degrees of autostability relative to strong constructivizations
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
• Computable axiomatizability of elementary classes
• Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations
• Decidable structures between Church-style and Curry-style
• On Σ¹ ₁ equivalence relations over the natural numbers
• scientific article; zbMATH DE number 6536307 (Why is no real title available?)
• scientific article; zbMATH DE number 4154430 (Why is no real title available?)
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• scientific article; zbMATH DE number 41858 (Why is no real title available?)
• Structural properties for feasibly computable classes of type two
• scientific article; zbMATH DE number 1984268 (Why is no real title available?)
• Computability-Theoretic Complexity of Countable Structures
• scientific article; zbMATH DE number 2063217 (Why is no real title available?)
• Torsion-free abelian groups with optimal Scott families
• A Friedberg enumeration of equivalence structures
• Computable topological groups and Pontryagin duality
• Index sets of constructive models of nontrivial signature autostable relative to strong constructivizations
• The index set of Boolean algebras autostable relative to strong constructivizations
• Degrees of categoricity of trees and the isomorphism problem
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Decompositions of decidable abelian groups
• Structure and Randomness in Computability and Set Theory
• Computability theoretic classifications for classes of structures
• Isomorphism relations on computable structures
• Isomorphism of Computable Structures and Vaught's Conjecture
• Index sets of constructive models that are autostable under strong constructivizations
• ON THE COMPLEXITY OF CLASSIFYING LEBESGUE SPACES
• Computability of Polish spaces up to homeomorphism
• Computable embeddability for algebraic structures
• Индексное множество автоустойчивых упорядоченных абелевых групп
• Tree-automatic well-founded trees
• MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY
• Computable Stone spaces
• On two types of concept lattices in the theory of numberings
• STRUCTURAL HIGHNESS NOTIONS
• COMPUTABLY COMPACT METRIC SPACES
• Model-theoretic complexity of automatic structures
• Every \(\Delta^0_2\) Polish space is computable topological
• Computably locally compact groups and their closed subgroups
• The computable embedding problem
• Comparing notions of presentability in Polish spaces and Polish groups
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• Algorithmically random series
• Ideal presentations and numberings of some classes of effective quasi-Polish spaces
• Computable classifications of continuous, transducer, and regular functions
• Computable structure theory of partial combinatory algebras
• The \(\delta_\alpha^0\)-computable enumerations of the classes of projective planes
• Complexity of the isomorphism problem for computable free projective planes of finite rank
• Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations
• PAC learning, VC dimension, and the arithmetic hierarchy
• Computable numberings of the class of Boolean algebras with distinguished endomorphisms
• Index sets of autostable relative to strong constructivizations constructive models for familiar classes
• The isomorphism problem for torsion-free abelian groups is analytic complete

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4451633)