Metadata language
Title:
On Transitive Closures of Two-dimensional StronglyPositive Arithmetical Sets1 ; О транзитивных замыканиях строго позитивных арифметическихмножеств размерности 2
Author:
Type:
Uncontrolled Keywords:
Positive set ; Strongly positive ; arithmetical set ; Dimension ; Signature
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:
Date accepted:
ISSN:
Language:
Journal or Publication Title:
Mathematical Problems of Computer Science ; Математические вопросы кибернетики и вычислительной техники
Volume:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems ; Институт проблем информатики иавтоматизации