No label defined (Q3676136)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3896923
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3896923

      Statements

      0 references
      0 references
      1984
      0 references
      recursive equivalence types
      0 references
      theories of constructive order types
      0 references
      matroids
      0 references
      vector spaces over a recursive field
      0 references
      [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.''
      0 references

      Identifiers