Metadata language
Անվանում:
On Some Properties of Positive and Strongly PositiveArithmetical Sets ; О некоторых свойствах позитивных и строго позитивных арифметических множеств
Հեղինակ:
Տեսակ:
Չվերահսկվող բանալի բառեր:
Positive set ; strongly positive set ; Transitive closure ; Signature
Ամփոփում:
The notions of positive and strongly positive arithmetical sets are defined as in [1]-[4] (see, for example, [2], p. 33). It is proved (Theorem 1) that any arithmetical set is positive if and only if it can be defined by an arithmetical formula containing only logical operations ∃,&,V and the elementary subformulas having the forms X = 0 or X= y + 1, where x and y are variables. Corollary: the logical description of the class of positive sets is obtained from the logical description of the class of strongly positive sets replacing the list of operations &,V by the list ∃,&,V. It is proved (Theorem 2) that for any one-dimensional recursively enumerable set M there exists 6-dimensional strongly positive set H such that X ∈ M holds if and only if (1, 2X, 0, 0, 1, 0) ∈ H+, where H+ is the transitive closure of H.
;
Определения понятий позитивного и строго позитивного арифметического множества даются так же как в [1]-[4] (см., например, [2], стр.33). Доказывается (Теорема 1), что любое арифметическое множество позитивно в том, и только в том случае, когда оно задается арифметической формулой, которая содержит только логические операции ∃,&,V и только элементарные подформулы вида �� = 0, �� = �� + 1. Следствие: Логическое описание класса позитивных арифметических формул получается из логического описания класса строго позитивных арифметических формул посредством замены списка логических операций &,V списком ∃,&,V. Доказывается (Теорема 2), что для любого одномерного рекурсивно перечислимого множества M существует строго позитивное множество H размерности , такое, что �� ∈ M имеет место в том и только в том случае, когда (1, 2��, 0, 0, 1, 0) ∈ H+, где H+ есть транзитивное замыкание множества H>
Հրատարակիչ:
"GITUTYUN" PUBLISHING HOUSE OF NAS RA ; Издательство "Гитутюн" НАН РА
Հանձնման ամսաթիվը:
Ընդունման ամսաթիվը:
DOI:
ISSN:
Լեզու:
Ամսագրի կամ հրապարակման վերնագիր:
Mathematical Problems of Computer Science ; Математические вопросы кибернетики и вычислительной техники
Հատոր:
URL:
լրացուցիչ տեղեկատվություն:
Կազմակերպության անվանում:
Institute for Informatics and Automation Problems ; Институт проблем информатики иавтоматизации