Skip to main content
SpringerLink
Log in

The recursive sets in certain monadic second order fragments of arithmetic

  • Published:
Archiv für mathematische Logik und Grundlagenforschung Aims and scope Submit manuscript

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  1. Büchi, J.R.: On a decision method in restricted second-order arithmetic. In: Logic Meth. Phil. Sc., Proc. 1960 Stanford Inter. Congr. Stanford 1962, 1–11.

  2. Büchi, J.R., Landweber, L.H.: Definability in the monadic second-order theory of successor. J. Symb. Logic34 (1969), 166–170.

    Google Scholar 

  3. Büchi, J.R., Siefkes, D.: Decidable theories II: The monadic second order theory of all countable ordinals. Lect. Notes Math. 328. Springer-Verlag, Berlin-Heidelberg-New York 1973.

    Google Scholar 

  4. Hanf, W.: Model theoretic methods in the study of elementary logic. In: The theory of models, Proc. 1963 Int. Symp. Berkeley (Ed. Addison, Henkin, Tarski). Amsterdam 1965, 132–145.

  5. McNaughton, R.: Testing and generating infinite sequences by a finite automaton. Information and Control9 (1966), 521–530.

    Google Scholar 

  6. Myhill, J.: Creative sets. Z. Math. Logik Grundl. Math.1 (1955), 97–108.

    Google Scholar 

  7. Rabin, M.O.: A simple method for undecidability proofs and some applications. In: Logic Meth. Phil. Sc., Proc. 1964 Jerusalem Inter. Congr. Amsterdam 1965, 58–68.

  8. Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Transactions AMS141 (1969), 1–35.

    Google Scholar 

  9. Rabin, M.O.: Automata on infinite objects and Church's problem. Conference Board Math. Sc., Regional Conf. Series in Math., No. 13, AMS, Providence, 1972.

  10. Robinson, J.: Definability and decision problems in arithmetic. J. Symb. Logic14 (1949), 98–114.

    Google Scholar 

  11. Robinson, R.M.: Restricted set-theoretical definitions in arithmetic. Proc. AMS9, (1958), 238–242.

    Google Scholar 

  12. Siefkes, D.: Decidable monadic second order theories of arithmetic. Ph.D. thesis Heidelberg 1969.

  13. Siefkes, D.: Decidable theories I: Büchi's monadic second order successor arithmetic. Lect. Notes Math. 120, Springer-Verlag, Berlin-Heidelberg-New York 1970.

    Google Scholar 

  14. Specker, E.: Eine Verschärfung des Unvollständigkeitssatzes des Zahlentheorie. Bull. Acad. Pol. Sci., Cl. III, Vol.5 (1957), 1041–1045.

    Google Scholar 

  15. Tarski, A., Mostowski, A., Robinson, R.M.: Undecidable theories. Amsterdam 1953.

Download references

Author information

Authors and Affiliations

  1. Heidelberg

    Dirk Siefkes

Authors
  1. Dirk Siefkes
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Siefkes, D. The recursive sets in certain monadic second order fragments of arithmetic. Arch math Logik 17, 71–80 (1975). https://doi.org/10.1007/BF02280817

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02280817

Keywords

Search

Navigation