|
This article is cited in 38 scientific papers (total in 38 papers)
Logical theories of one-place functions on the set of natural numbers
A. L. Semenov
Abstract:
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.
Received: 29.04.1982
Citation:
A. L. Semenov, “Logical theories of one-place functions on the set of natural numbers”, Izv. Akad. Nauk SSSR Ser. Mat., 47:3 (1983), 623–658; Math. USSR-Izv., 22:3 (1984), 587–618
Linking options:
https://www.mathnet.ru/eng/im1415https://doi.org/10.1070/IM1984v022n03ABEH001456 https://www.mathnet.ru/eng/im/v47/i3/p623
|
Statistics & downloads: |
Abstract page: | 793 | Russian version PDF: | 342 | English version PDF: | 45 | References: | 60 | First page: | 1 |
|