Metadata language
Title:
On Some Properties of Positive and Strongly PositiveArithmetical Sets ; О некоторых свойствах позитивных и строго позитивных арифметических множеств
Author:
Type:
Uncontrolled Keywords:
Positive set ; strongly positive set ; Transitive closure ; Signature
Abstract:
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>
Publisher:
"GITUTYUN" PUBLISHING HOUSE OF NAS RA ; Издательство "Гитутюн" НАН РА
Date submitted:
Date accepted:
DOI:
ISSN:
Language:
Journal or Publication Title:
Mathematical Problems of Computer Science ; Математические вопросы кибернетики и вычислительной техники
Volume:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems ; Институт проблем информатики иавтоматизации