Computability of the set of computable indexing schemes of the class of constructible models
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.
scientific article; zbMATH DE number 797886