Metadata language
Title:
On Strongly Positive Multidimensional Arithmetical Sets ; О строго позитивных многомерных арифметическихмножествах
Author:
Type:
Uncontrolled Keywords:
Arithmetical formula ; Transitive closure ; Recursive set ; Signature
Abstract:
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 примитивно рекурсивно.
Date submitted:
Date accepted:
ISSN:
Language:
Journal or Publication Title:
Mathematical Problems of Computer Science
Volume:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems