Abstract:

The notions of positive and strongly positive arithmetical set are considered in ([1]-[3]). It is noted in [3] that the transitive closure of any 2-dimensional strongly positive set is primitive recursive. In this article a more strong statement is proved: the transitive closure of any 2-dimensional strongly positive set is defined by an arithmetical formula in the signature (0, =, <, S), where S (��) = x + 1. Besides, it is proved that the class of two-dimensional strongly positive sets and the class of transitive closures of such sets do not coincide with the class of two-dimensional arithmetical sets expressible by the formulas in the signature (0, =, <, S).
; Понятия позитивного и строго позитивного множества рассматриваются в [1]-[3]. В [3] указано, что транзитивное замыкание всякого строго позитивного множества размерности 2 примитивно рекурсивно. В этой статье доказывается более сильное утверждение: транзитивное замыкание всякого строго позитивного множества размерности 2 задается арифметической формулой в сигнатуре (0, =, <, S), где S(��) = �� + 1. Доказывается также, что класс строго позитивных множеств размерности 2 и класс транзитивных замыканий таких множеств не совпадают с классом арифметических множеств размерности 2, задаваемых посредством арифметических формул в сигнатуре (0, =, <, S).

Publisher:

"GITUTYUN" PUBLISHING HOUSE OF NAS RA ; Издательство "Гитутюн" НАН РА

Date submitted:

04.10.2015

Date accepted:

15.01.2016

Identifier:

oai:noad.sci.am:135856

ISSN:

0131-4645

Language:

English ; Английский

Journal or Publication Title:

Mathematical Problems of Computer Science ; Математические вопросы кибернетики и вычислительной техники

Volume:

45

URL:

Additional Information:

zaslav@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems ; Институт проблем информатики иавтоматизации

Country:

Armenia ; Армения

Indexing:

АИНЦ