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 ; Издательство "Гитутюн" НАН РА
oai:noad.sci.am:135890
Mathematical Problems of Computer Science ; Математические вопросы кибернетики и вычислительной техники
Institute for Informatics and Automation Problems ; Институт проблем информатики иавтоматизации
Mar 31, 2021
Jul 23, 2020
28
https://noad.sci.am/publication/149465
Edition name | Date |
---|---|
С. Манукян, О некоторых свойствах позитивных и строго позитивных арифметических множеств | Mar 31, 2021 |
Manukian Seda