Logical theories of one-place functions on the set of natural numbers

A. L. Semenov

Izvestiya. Mathematics , Tome 22 (1984) no. 3, pp. 587-618.

Résumé

In this paper the author studies the decision problem for logical languages intended to describe the properties of one-place functions $f$ on the set $\mathbf N$ of natural numbers. For functions $f$ taking a finite number of values a criterion for decidability of the monadic theory of the structure $\langle\mathbf N;\leqslant,f\rangle$ is obtained. For a large class of monotone functions $f$, conditions are found under which the elementary theory of the structure $\langle\mathbf N;\leqslant,f\rangle$ is decidable; corresponding conditions are also found for structures of the form $\langle\mathbf N;+,f\rangle$. Bibliography: 20 titles.

Bibliographie

[1] Büchi J. R., “On a decision method in restricted second order arithmetic”, Proc. 1960 Intern. Congr. for Logic, Methodol. and Philos. of Sci., Stanford, 1962 ; Kibern. sb., no. 8, IL, M., 1964, 42–72 | MR

[2] Siefkes D., Decidable theories I: Büchi's monadic second order theories of arithmetic, Lecture Notes Math., 120, Springer, Berlin etc., 1970 | MR

[3] Thomas W., “A note on undecidable extensions of monadic second order successor arithmetic”, Arch. Math. Logik, 17:1,2 (1975), 43–44 | DOI | MR | Zbl

[4] Elgot C. C., Rabin M. O., “Decidability and undecidability of second (first) order theories of (generalized) successor”, J. Symbolic Logic, 31:2 (1966), 169–181 | DOI | Zbl

[5] Siefkes D., “Decidable extensions of monadic second order successor arithmetic”, Automatentheorie und Formale Sprachen., Mannheim Bibl. Inst., 1969, 441–472 | MR

[6] Siefkes D., “Undecidable extensions of monadic second order successor arithmetic”, Z. Math. Logik und Grundlagen der Math., 17:5 (1971), 383–394 | MR

[7] Büchi J. R., “Weak second order arithmetic and finite automata”, Z. Math. Logik und Grundl. der Math., 6:1 (1960), 66–92 | DOI | MR

[8] Semenov A. L., “O nekotorykh rasshireniyakh arifmetiki slozheniya naturalnykh chisel”, Izv. AN SSSR. Ser. matem., 43:5 (1979), 1175–1195 | MR | Zbl

[9] Adyan S. I., Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975 | MR | Zbl

[10] Büchi J. R., Landweber L. H., “Definability in the monadic second order theory of successor”, J. Symb. Logic, 34:2 (1969), 166–170 | DOI | MR | Zbl

[11] Semenov A. L., “O razreshimosti nekotorykh neelementarnykh teorii”, Pyataya Vsesoyuzn. konf. po matematicheskoi logike, Tez. dokl., Novosibirsk, 1979, 138

[12] Thomas W., “The theory of successor with extra predicate”, Math. Annalen, 237:2 (1978), 121–132 | DOI | MR | Zbl

[13] Thomas W., “On the bounded monadic theory of well-ordered structures”, J. Symb. Logic, 45:2 (1980), 334–338 | DOI | MR | Zbl

[14] Church A., “Logic, arithmetic, and automata”, Proc. Internat. Congr. Math. (Stockholm, 1962), Inst. Mittag–Leffler, Djursholm, 1963, 23–35 | MR

[15] Landweber L., “Synthesis algorithms of sequential machines”, Information Processing, 68, North Holland, Amsterdam, 1969, 300–304

[16] Rabin M. O., Automata on infinite objects and Church's problem, Amer. Math. Soc., Providence, 1972 | MR | Zbl

[17] Siefkes D., “The recursive sets in certain monadic second order fragments of arithmetic”, Arch. Math. Logik, 17:1,2 (1975), 71–80 | DOI | MR | Zbl

[18] Büchi J. R., Landweber L. H., “Soiving-sequential conditions by finite-state strategies”, Trans. Amer. Math. Soc., 138 (1969), 295–311 | DOI | MR

[19] Jacobs K., “Turing-Maschinen und zufällige $0-1$-Folgen”, Selecta Mathemat, II, Springer, Berlin etc., 1970, 141–167 ; Mashiny Tyuringa i rekursivnye funktsii, Mir, M., 1972 | MR | MR

[20] McNaughton R., “Testing and generating infinite sequences by a finite automaton”, Inform. and Contr., 9:5 (1966), 521–530 | DOI | MR | Zbl