scientific article; zbMATH DE number 1302872
\(\alpha\)-systems\(\Delta^0_\alpha\)-categoricity\(\Delta^0_\alpha\)-stabilityback-and-forth relationsintrinsically \(\Sigma^0_\alpha\) relationsintrinsically recursive relationsisomorphism typenon-recursive structuresrecursive categoricityrecursive infinite formulaerecursive similarity typerecursive stabilityrecursive structuresrecursively isomorphic
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].
- Recursive properties of isomorphism types
- scientific article; zbMATH DE number 3869317
- The relation of recursive isomorphism for countable structures
- Recursive isomorphism types of recursive Boolean algebras
- Structures for structural recursion
- On recursively enumerable structures
- Pairs of recursive structures
- Types of resemblance and of recursive isomorphism of partial recursive functions
- Recursive Structures and Ershov's Hierarchy
- Towards a theory of recursive structures
- Recursive automorphisms of recursive linear orderings
- Recursive versus recursively enumerable binary relations
- Degree spectra of relations on structures of finite computable dimension
- On bi-embeddable categoricity of algebraic structures
- On decidability of amenability in computable groups
- Recursive properties of isomorphism types
- A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
- scientific article; zbMATH DE number 749934 (Why is no real title available?)
- Computable structure theory of partial combinatory algebras
- Degrees of orderings not isomorphic to recursive linear orderings
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249358)
