scientific article; zbMATH DE number 3896923
[For the entire collection see Zbl 0547.00036.] From the introduction. Various theories of recursive equivalence types (RETs) have been proved undecidable by \textit{A. Nerode} and \textit{A. B. Manaster} [J. Symb. Logic 35, 51-59 (1970; Zbl 0198.02504); The degree of the theory of addition of isols (abstract), Am. Math. Soc., Notices 18, 68-OZ-3, 86 (1971)], \textit{A. Nerode} and \textit{R. A. Shore} [The Kleene Symp., Proc. Madison/Wis. 1978, Stud. Logic Found. Math., Vol. 101, 181- 200 (1980; Zbl 0465.03024)] and the authors [Part I of the present paper in: Logic, Proc. Southeast Asian Conf., Singapore 1981, Stud. Logic Found. Math. 111, 37-53 (1983; Zbl 0553.03030)]. In the papers noted above it has been shown that these theories are all recursively isomorphic to second order arithmetic. We continue this work here and the present paper consists of four parts. In the first few sections ({\S} 2- 4) we extend the results of Crossley and Remmel to theories of constructive order types with \(\leq\) and \(\leq^*\) as the only non-logical constants. The second part ({\S} 5-7) treats the theory of RETs of matroids and acquaintance with Crossley and Nerode would be useful. In the third ({\S} 8-10) we deal with the theory of RETs of vector spaces over a recursive field. Finally, in {\S} 11 we turn to the theory of co- simple COTs. Here we show that the theories with \(+\) or \(\leq\) and \(\leq^*\) as the only non-logical constants are undecidable. In the co- simple case, however, we have been unable to establish the strength of the undecidability for we cannot use the techniques of Manaster, Nerode and Shore.
- scientific article; zbMATH DE number 3880676 (Why is no real title available?)
- THE AMBIGUOUS TYPE THEORY IS HEREDITARILY UNDECIDABLE
- scientific article; zbMATH DE number 749915 (Why is no real title available?)
- scientific article; zbMATH DE number 5497805 (Why is no real title available?)
- scientific article; zbMATH DE number 2236644 (Why is no real title available?)
- Sound, totally sound, and unsound recursive equivalence types
- Manifolds allowing RET arithmetic
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 Q3676136)