Conditions of effective infinity for the set of computable indexings of a class of constructive models (Q1897964): Difference between revisions

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 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\). Let \(M^t\) denote the part of a model \(M\) which is constructed in \(t\) steps of its construction. We say that a class \(K\) has the effective embeddability property if it contains a model \(M\) such that for every model \(N\) in \(K\) and every \(t\) some model \(L\) can be effectively determined which is not effectively isomorphic to \(N\) and contains an isomorphic copy of \(M^t\) as a submodel. A class \(K\) is said to have the joint constructive embeddability property if, given two arbitrary models \(M\) and \(N\) in \(K\) and a natural \(t\), we can effectively construct a model which contains isomorphic copies of both \(M^t\) and \(N^t\) as submodels and is not effectively isomorphic to \(N\). The main result of the paper is that classes of indexings of a computable class with any of these properties 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. This is also true for any computable class of constructive abelian groups whose torsion-free rank belongs to a fixed cofinite set.