Open AccessOn Some Properties of Positive and Strongly Positive Arithmetical Sets
Author(s) -
Seda N. Manukian
Publication year - 2018
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0019
Subject(s) - arithmetic function , mathematics , transitive closure , corollary , closure (psychology) , recursively enumerable language , class (philosophy) , transitive relation , discrete mathematics , set (abstract data type) , combinatorics , recursively enumerable set , computer science , artificial intelligence , economics , market economy , programming language
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 ∃, &,∨ and the elementary subformulas having the forms =0 or =+1, where and 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 &,∨ by the list ∃, &,∨. It is proved (Theorem 2) that for any one-dimensional recursively enumerable set there exists 6- dimensional strongly positive set such that ∈ holds if and only if (1, 2, 0, 0, 1, 0)∈+, where + is the transitive closure of .