scientific article; zbMATH DE number 3896923

From MaRDI portal
Publication:3676136





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











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)