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:

20.07.2018

Date accepted:

02.12.2018

Identifier:

oai:noad.sci.am:135890

DOI:

10.51408/1963-0019

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

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

Volume:

50

URL:

Additional Information:

zaslav@ipia.sci.am

Affiliation:

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

Country:

Armenia

Indexing:

ASCI