Computability of the set of computable indexing schemes of the class of constructible models
type: Item
instance of: scholarly article
title: Computability of the set of computable indexing schemes of the class of constructible models
zbMATH Open document ID: 0830.03014
DOI: 10.1007/BF02110373
author: V. P. Dobritsa
published in: Mathematical Notes
publication date: 1995-09-25T00:00:00Z
review text: Informally, any algorithmic procedure \(\gamma\) which, given a natural number \(n\), yields an effective way to construct the model \(\gamma (n)\), is called an indexing scheme (or indexation) of the class \(K\) of constructive models if this class consists of all models \(\gamma (n)\), \(n< \omega\), up to effective isomorphism. A class \(K\) is called computable if it has an indexing. We say that an indexing \(\gamma_0\) reduces to \(\gamma_1\) \((\gamma_0\leq \gamma_1)\) if there exists a recursive function \(f\) such that for all \(n\) the models \(\gamma_0 (n)\) and \(\gamma_1 (f(n))\) are effectively isomorphic. Indexings \(\gamma_0\) and \(\gamma_1\) are called equivalent if \(\gamma_0\leq \gamma_1\) and \(\gamma_1\leq \gamma_0\). The author proves that the set of all computable indexings of a class containing all abelian groups of torsion-free rank 0 and \(i\neq 0\) is effectively infinite, i.e., given any effective enumeration of its indexings, we can produce an indexing which is not equivalent to an indexing from this family. The second result is that if there exist greatest and least indexings of a class, then the family of all computable indexings of this class is computable.
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 797886
zbMATH Keywords: constructive abelian groups
zbMATH Keywords: indexing
zbMATH Keywords: constructive models
reviewed by: Andrei S. Morozov
MaRDI profile type: Publication
cites work: Q3775536
cites work: Q3322080
cites work: Q4133972
full work available at URL: https://doi.org/10.1007/bf02110373
OpenAlex ID: W2079297409
description: scientific article; zbMATH DE number 797886