Undecidability and recursive equivalence I

J. N. Crossley, J. B. Remmel

    Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review


    Manaster and Nerode showed that the theory of order of isols and the theory of recursive equivalence types (RETs) with order is undecidable. The results of Manaster and Nerode rely on coding an arbitrary binary relation in the isols using indecomposable RETs and indecomposable covers of ω-sequences of recursive equivalence types (RETs). RETs were generalized from sets to many other structures. In the chapter, the undecidability results analogous to those of Manaster and Nerode and Nerode and Shore for five theories of constructive order types (COTs) is proved with addition and in two planned sequels to matroids, vector spaces, and algebraically closed fields. A quasi finite COT is one that has a representative with no infinite recursive ascending or descending chain and a losol is a COT with an immune representative. All losols are, therefore, quasi-finite COTs.

    Original languageEnglish
    Title of host publicationSoutheast Asian Conference on Logic
    Subtitle of host publicationProceedings of the Logic Conference Singapore, 1981
    Number of pages17
    Publication statusPublished - 1 Jan 1983

    Publication series

    NameStudies in Logic and the Foundations of Mathematics
    ISSN (Print)0049-237X

    Cite this