Conditions of effective infinity for the set of computable indexings of a class of constructive models
type: Item
instance of: scholarly article
title: Conditions of effective infinity for the set of computable indexings of a class of constructive models
zbMATH Open document ID: 0830.03015
DOI: 10.1007/BF02104943
author: V. P. Dobritsa
published in: Siberian Mathematical Journal
publication date: 1995-09-18T00: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 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.
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 794615
zbMATH Keywords: indexing
zbMATH Keywords: constructive models
zbMATH Keywords: effective embeddability property
zbMATH Keywords: joint constructive embeddability property
zbMATH Keywords: computable class
zbMATH Keywords: constructive abelian groups
reviewed by: Andrei S. Morozov
MaRDI profile type: Publication
cites work: Q3825006
cites work: Q5719719
cites work: Q4711784
cites work: Reduction of nonholonomic variation problems to isoperimetric ones and connections in principal bundles
cites work: On a constrained variational problem and the space of horizontal paths
full work available at URL: https://doi.org/10.1007/bf02104943
OpenAlex ID: W2046838141
description: scientific article; zbMATH DE number 794615