No label defined (Q4249358)

An early result about recursive structures is the following, attributed to S. Tennenbaum. There is a recursive linear ordering of order type \(\omega+\omega^*\) having no infinite recursive ascending or descending sequence. There are also, of course, more obvious recursive orderings of this type, for example \(0,2,4,\dots, 5,3,1\). An ordering of the first sort, which can be constructed by a priority argument, is classically isomorphic to the second, but cannot be recursively isomorphic since it has different recursive properties. Some other examples are mentioned in work of the author and \textit{A. Nerode} [Aspects of effective algebra, Proc. Conf., Monash Univ./Aust. 1979, 26-41 (1981; Zbl 0647.03041)]: a recursive linear ordering of type \(\omega\) on which the successor relation is not recursive; a recursive vector space over any recursive infinite field having no recursive basis; a recursive algebraically closed field of any characteristic having no recursive transcendence basis. In each of these cases it is clear that within the isomorphism type of a single structure we have recursive structures which are not recursively isomorphic. In this article, we discuss general results which have been obtained concerning this and related matters. For the entire collection see [Zbl 0905.03001].