Ամփոփում:

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 примитивно рекурсивно.

Հանձնման ամսաթիվը:

25.11.2014

Ընդունման ամսաթիվը:

27.01.2015

Նույնականացուցիչ:

oai:noad.sci.am:136008

ISSN:

0131-4645

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Mathematical Problems of Computer Science

Հատոր:

43

URL:

լրացուցիչ տեղեկատվություն:

zaslav@ipia.sci.am

Կազմակերպության անվանում:

Institute for Informatics and Automation Problems

Երկիր:

Armenia

Ինդեքսավորում:

ASCI