Conditions of effective infinity for the set of computable indexings of a class of constructive models

DOI10.1007/BF02104943MaRDI QIDQ1897964zbMATH OpenOpenAlexFDO

Publication date 18 September 1995

Published in Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02104943

computable class constructive abelian groups constructive models effective embeddability property indexing joint constructive embeddability property

Mathematics Subject Classification ID

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

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 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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Conditions of effective infinity for the set of computable indexings of a class of constructive models

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