The notion of positive arithmetical formula in the signature (0,=, S) , where S(x) =x +1, is defined and investigated in [1] and [2]. A multidimensional arithmetical set is said to be positive if it is determined by a positive formula. Some subclass of the class of positive sets, namely, the class of strongly positive sets, is considered. It is proved that for any n ≥ 3 there exists a 2n -dimensional strongly positive set such that its transitive closure is non-recursive. On the other side, it is noted that the transitive closure of any 2-dimensional strongly positive set is primitive recursive.
;
Понятие позитивной арифметической формулы в сигнатуре (0,=, S) , где S(x) = x +1 , определено и исследовано в [1] и [2]. Многомерное арифметическое множество называем позитивным, если оно задаётся позитивной формулой. Рассматривается подкласс класса позитивных множеств, а именно, класс строго позитивных множеств. Доказывается, что для всякого n ≥ 3 существует строго позитивное множество размерности 2n , такое, что его транзитивное замыкание нерекурсивно. С другой стороны, указывается, что транзитивное замыкание всякого строго позитивного множества размерности 2 примитивно рекурсивно.
oai:noad.sci.am:136008
Mathematical Problems of Computer Science
Institute for Informatics and Automation Problems
Mar 4, 2021
Jul 29, 2020
6
https://noad.sci.am/publication/149622
Edition name | Date |
---|---|
Seda Manukian, On Strongly Positive Multidimensional Arithmetical Sets | Mar 4, 2021 |
Manukian Seda