Microsoft Word - Seda_Manukian_32--41 Mathematical Problems of Computer Science 43, 32--41, 2015. 32 On Strongly Positive Multidimensional Arithmetical Sets 1 Seda N. Manukian Institute for Informatics and Automation Problems of NAS RA e-mail: zaslav@ipia.sci.am Abstract The notion of positive arithmetical formula in the signature ),,0( S= , where 1)( += xxS , is defined and investigated in [1] and [2]. A multidimensional arithmetical set is said to be positive if it is determined by a positive formula. Some subclass of the class of positive sets, namely, the class of strongly positive sets, is considered. It is proved that for any 3≥n there exists a n2 -dimensional strongly positive set such that its transitive closure is non-recursive. On the other side, it is noted that the transitive closure of any 2-dimensional strongly positive set is primitive recursive. Keywords: Arithmetical formula, Transitive closure, Recursive set, Signature. 1. Introduction The classes of recursive sets having in general non-recursive transitive closures have been investigated in the theory of algorithms since the first steps of this theory ([3]-[8]). The works [9]-[13] are dedicated mainly to algebraic problems, however, some examples of recursive sets having non-recursive transitive closures are actually given also in these works. In [14] it is noted that there exists a two-dimensional arithmetical set belonging to the class 4Σ and having a non- recursive transitive closure (the classes n Σ for 0≥n are defined in [14] as some classes of arithmetical sets determined by formulas in M. Presburger’s system ([4], [15], [16])). Below the class of strongly positive arithmetical sets is considered (the definition will be given in Section 2) such that the sets belonging to this class have a more simple structure than the sets noted above, and have the following properties: (1) for any 3≥n there exists a n2 -dimensional strongly positive set such that its transitive closure is non-recursive; (2) any 2-dimensional strongly positive set has a primitive recursive transitive closure (see below, Theorem 1 and Theorem 2). 1 This work was supported by State Committee of Science, MES RA, in frame of the research project №SCL 13- 1B321. S. Manukian 33 2. Main Definitions and Results By N we denote the set of all non-negative integers, ,...}2,1,0{=N . By nN we denote the set of n -tuples ),...,,( 21 nxxx , where 1≥n , Nxi ∈ for ni ≤≤1 . An n -dimensional arithmetical set, where 1≥n , is defined as any subset of nN . An n -dimensional arithmetical predicate P is defined as a predicate which is true on some set nNA ⊆ and false out of it; in this case we say that A is the set of truth for P , and P is the representing predicate for A . The notions of primitive recursive function, general recursive function, partially recursive function, primitive recursive set, recursive set are defined in a usual way ([3]-[8]). The corresponding terms will be shortly denoted below by PmRF, GRF, PtRF, PmRS, RS. We will consider arithmetical formulas in the signature ),,0( S= , where 1)( += xxS , for Nx ∈ (see [1]-[8]). Any term included in a formula of the mentioned kind has the form )...))((...( xSSS or )...))0((...( SSS , where x is a variable. Such terms we will denote correspondingly by )(xS k and )0(kS , where k is the quantity of symbols S contained in the considered term. We replace )(0 xS and )0(0S with x and 0. Any elementary subformula of a formula of this kind has the form 21 tt = , where 1t and 2t are terms. Any arithmetical formula of this kind is obtained by the logical operations ∃∀¬⊃∨ ,,,,&, from elementary formulas. We say that a formula is semi-elementary if it has the form 21 tt = or )( 21 tt =¬ , where 1t and 2t are terms. The deductive system of formal arithmetic in the signature ),,0( S= is defined as in [4], [6]; we will denote this system by DedS (cf. [1], [2]). As it is proved in [4], this system is complete. We say that formulas F and G in the signature ),,0( S= are DedS-equivalent (or simply equivalent) if the formula )(&)( FGGF ⊃⊃ is deducible in DedS. Below we consider formulas of the mentioned kind up to their DedS-equivalence. An arithmetical formula of the mentioned kind is said to be positive if it contains no other symbols of logical operations except ¬∨∃ ,,&, , and all the symbols ¬ of negation relate to elementary subformulas containing no more than one variable (see [1], [2]). An arithmetical formula of this kind is said to be strongly positive if it can be obtained by the logical operations & and ∨ from semi-elementary formulas of the following forms: ax = , where x is a variable, a is a constant, Na ∈ ; yx = , where x and y are variables; )( ySx = , where x and y are variables; )0( =¬ x , where x is a variable. An arithmetical predicate is said to be positive (correspondingly, strongly positive), if it can be expressed by a positive (correspondingly, strongly positive) formula. An arithmetical set is said to be positive (correspondingly, strongly positive) if its representing predicate is positive (correspondingly, strongly positive). The notion of one-dimensional creative set is given in a usual way ([3], [5], [7], [8]). We will slightly generalize this notion. We use a PmRF ),...,,( 21 nn xxxc , where 2≥n , establishing a one-to-one correspondence between nN and N (for example, )),)...,),,(((...(),...,,( 1321222221 nnnn xxxxxccccxxxc −= , where 1)12(2),(2 −+⋅= yyxc x ). We say that a set nNB ⊆ is an n -dimensional image of a set NA ⊆ when Axxxc nn ∈),...,,( 21 if and only if Bxxx n ∈),...,,( 21 . The set n NB ∈ is said to be creative in the generalized sense if it is an n -dimensional image of some one-dimensional creative set. Clearly, the properties of creative sets in the generalized sense are similar to the properties of one-dimensional creative sets (for example, all sets creative in the generalized sense are non-recursive). On Strongly Positive Multidimensional Arithmetical Sets 34 Transitive closure *A of an arithmetical set A having an even dimension k2 is defined in a usual way by the following generating rules (cf. [1], [2], [13]): (1) if Axxx k ∈),...,,( 221 , then * 221 ),...,,( Axxx k ∈ , (2) if * 2121 ),...,,,...,,( Ayyyxxx kk ∈ , and * 2121 ),...,,,...,,( Azzzyyy kk ∈ , then *2121 ),...,,,...,,( Azzzxxx kk ∈ . Theorem 1: For any 3≥n there exists a n2 -dimensional strongly positive set such that its transitive closure is creative in the generalized sense. Theorem 2: Transitive closure of any 2-dimensional strongly positive set is primitive recursive. The proof of Theorem 1 will be given below. The proof of Theorem 2 will be published later. 3. Auxiliary Notions and Statements We will use some class of operator algorithms ([8], [17]) having a special structure. The algorithms belonging to this class we will call Ω -algorithms. Any Ω -algorithm consists of finite number of elementary Ω -algorithms, which will be called below “ Ω -operators”. The set of all Ω -operators included in the considered Ω -algorithm we call “scheme” of this Ω -algorithm. We suppose that some non-negative integer is attached to any Ω -operator in the scheme of a given Ω -algorithm in such a way, that different integers are attached to different Ω -operators. The integer attached to some Ω -operator we call “an identifier” of this Ω -operator. In this case we say that this Ω -operator has the mentioned identifier. Any Ω -operator implements one step of the process of computation realized by the considered Ω -algorithm. The objects transformed in the process of computation are non-negative integers. The state of the mentioned computation process is defined as a pair ),( wα , where α is the identifier attached to the Ω -operator which is working on the considered step of the process, and w is the number obtained by the previous steps of the process. Ω -operators are algorithms having one of the following forms (where α is the identifier attached to the considered Ω -operator, β and γ are identifiers attached to Ω - operators which should work after the working of this Ω -operator): (1) ),( endα . This Ω -operator is called below “a final operator”; it finishes the process of computation. (2) ),2,( βα × . This Ω -operator transforms the state ),( wα to the state )2,( wβ . (3) ),3,( βα × . This Ω -operator transforms the state ),( wα to the state )3,( wβ . (4) ),,6:,( γβα . This Ω -operator transforms the state ),( wα to the state ) 6 ,( w β if the number w is divisible by 6; in the opposite case it transforms the state ),( wα to the state ),( wγ . Note that such forms of operators are considered actually in [17] (see also [8], p. 292, p. 312). We suppose that any scheme of Ω -algorithm contains only a single final Ω -operator which has the identifier 0=α . Among the operators contained in the scheme of the considered Ω - algorithm we distinguish the initial Ω -operator having the identifier 1=α ; the working of this operator begins the process of computation. The whole process of working of the given Ω - algorithm is described by the sequence of states ),( 11 wα , ),( 22 wα ,…, ),( kk wα ,…,(where S. Manukian 35 11 =α ) obtained during the working of this Ω -algorithm. The process is described by a finite sequence ),1( 1w , ),( 22 wα ,…, ),0( mw if it is finished by the working of the final Ω -operator. In this case we say that the considered Ω -algorithm transforms the state ),1( 1w to the state ),0( m w , and is applicable to the state ),1( 1w . If the final Ω -operator does not work during the process of computation, then the mentioned sequence ),1( 1w , ),( 22 wα ,… is infinite. In this case we say that the considered Ω -algorithm is not applicable to the state ),1( 1w . The following theorem is proved in [17] (see also [8], pp. 312-315) in some other terms. Theorem 3 ([17]): For any PtRF )( xf there exists an Ω -algorithm which transforms the state )2,1( 2 x to the state )2,0( )(2 xf when the value )( xf is defined, and is not applicable to the state )2,1( 2 x in the opposite case. If some Ω -algorithm has the property described in Theorem 3, then we say that this Ω - algorithm realizes the PtRF )( xf . For example, the following Ω -algorithm: ),0( end , )2,3,1( × , )3,1,6:,2( , )0,2,3( × realizes the GRF 0)( =xf . We will use also another classes of algorithms, namely, n Γ -algorithms for 1≥n . These algorithms are actually special cases of graph-schemes with memory ([18]), though they will be described below in some other terms than the descriptions in [18]. Any n Γ -algorithm consists of finite number of n Γ -operators. The set of all n Γ -operators included in the considered n Γ -algorithm we call “scheme” of this n Γ -algorithm. The index n in the notation n Γ denotes that the objects transformed by the considered n Γ -algorithm are n - tuples ),...,,( 21 nxxx , where Nxi ∈ for ni ≤≤1 . The notion of identifier attached to the considered n Γ -operator is defined similarly to the notion of “identifier attached to the considered Ω -operator” which is given above; we suppose that different n Γ -operators have different identifiers attached to them. If some identifier is attached to a n Γ -operator, we will say that this n Γ -operator has the mentioned identifier. The state of the computation process realized by a n Γ -algorithm is defined as an )1( +n - tuple ),...,,,( 132 +nxxxα , where α is the identifier attached to the nΓ -operator which is working on the considered step of the process, and ),...,,( 132 +nxxx is the n -tuple of numbers obtained by the previous steps of the process. n Γ -operators are algorithms having one of the following forms (where the notations α , β , γ have the same sense as α , β , γ in the description of Ω - operators given above): (1) ),( endα . This n Γ -operator we call “a final operator”; it finishes the process of computation. (2) ),1,( βα + i x , where 12 +≤≤ ni . This n Γ -operator transforms the state ),...,,,,...,,,( 11132 ++− niii xxxxxxα to the state ),...,,1,,...,,,( 11132 ++− + niii xxxxxxβ . On Strongly Positive Multidimensional Arithmetical36 (3) i x,(α ),1 β , where 2 +≤≤ ni yxy −= when yx ≥ , and transforms the state ,,( 32 xxα ),...,,1 11 ++ ni xx . (4) ),,0,( γβα = i x ,where 2 ≤≤ i ),...,,,( 132 +nxxxα to the state ),...,,,( 132 +nxxxγ when 0≠ix . We suppose that any scheme of n Γ -algorithm contains only the identifier 0=α . Among the n Γ -operators contained in the scheme of the considered algorithm we distinguish the initial n Γ operator begins the process of computation. This process is described by a sequence of states ),( 11 Qα , ),( 22 Qα ,…, ),( kk Qα ,… where Such a sequence is finite if the final infinite in the opposite case. If the sequence of states is finite, then we say that the considered -algorithm is applicable to the state ,1( the state ),1( 1Q to the state ),0( mQ , where the sequence of states ),1( 1Q , ,2( Q algorithm is not applicable to the state We say that a n Γ -algorithm (where transforms the state )0,...,0,0,2,1( x to the state and is not applicable to the state 1( example, the following n Γ -algorithm realizes the PtRF ),0( end , 2,1( x )1,1 . Lemma 3.1: If the initial state in the process of computation realized by some the form )3,2,1( vu , where Nu ∈ , v ∈ satisfies the condition st m w 32 ⋅= , where The proof is easily obtained from the definitions. Lemma 3.2: For any Ω -algorithm ϕ realizing the same PtRF )( xf . Proof: We will consider the process of computation realized by the state in such a process has the form ,1( state included in such a process has the form included in the scheme of Ω -algorithm 2Γ -algorithm ψ which has the following property: if t state )32,( vu ⋅α to the state )32,( st ⋅β On Strongly Positive Multidimensional Arithmetical Sets 1+ ; we denote by the symbol the PmRF such that , and x 0=y when yx < (cf. [3]-[8]). This Γ ),...,,,,..., 111 ++− niii xxxx to the state xx ,...,,,( 32β 1+≤ n . This n Γ -operator transforms the state to the state ),...,,,( 132 +nxxxβ when 0=ix , and to the state . algorithm contains only a single final n Γ -operator which has operators contained in the scheme of the considered -operator having the identifier 1=α ; the working of this operator begins the process of computation. This process is described by a sequence of states ,… where 11 =α , and any iQ is an n -tuple ,( )( 2 i xx Such a sequence is finite if the final n Γ -operator works during the mentioned process, and is infinite in the opposite case. If the sequence of states is finite, then we say that the considered )1Q ; in this case we say also that nΓ -algorithm , where ),0( m Q is the last state in the considered sequence. If )2Q ,… is infinite, then we say that the considered to the state ),1( 1Q . algorithm (where 2≥n ) realizes a PtRF )( xf , if for any to the state )0,...,0,0,2,0( )( xf when the value )( xf )0,...,0,0,2,1 x when the value )( xf is not defined. For algorithm realizes the PtRF )( xf which is nowhere defined: If the initial state in the process of computation realized by some Ω -algorithm has N∈ , then any state ),( mm wα included in this process , where Nst ∈, . The proof is easily obtained from the definitions. realizing some PtRF )( xf there exists a 2Γ -algorithm We will consider the process of computation realized by the Ω -algorithm ϕ . Any initial )2,1 2 x that is )32,1( 02 ⋅ x . As it is proved in Lemma state included in such a process has the form )32,( st m ⋅α where Nst ∈, . For any Ω algorithm ϕ we will construct some subscheme of the supposed which has the following property: if the considered Ω -operator transforms the ) then the corresponding subscheme of the supposed the PmRF such that x n Γ -operator ii xx ,,..., 1− operator transforms the state , and to the state operator which has operators contained in the scheme of the considered n Γ - ; the working of this operator begins the process of computation. This process is described by a sequence of states ),..., )( 1 )( 3 i n i x + . operator works during the mentioned process, and is infinite in the opposite case. If the sequence of states is finite, then we say that the considered n Γ algorithm transforms is the last state in the considered sequence. If ,… is infinite, then we say that the considered n Γ - , if for any Nx ∈ it is defined, is not defined. For which is nowhere defined: algorithm has included in this process algorithm ψ . Any initial . As it is proved in Lemma 3.1 any Ω -operator we will construct some subscheme of the supposed operator transforms the then the corresponding subscheme of the supposed 2Γ - algorithm ψ transforms the state consider the following cases. Case 1. The considered Ω -operator has the form of the supposed 2Γ -algorithm Case 2. The considered Ω -operator has the form of the supposed 2Γ -algorithm Case 3. The considered Ω subscheme of the supposed ),,0,( 12 δγα =x , ,0,( 31 γδ =x identifiers attached to additional 2Γ -algorithm for modeling the working of the considered identifiers should be different in different subschemes of this kind. Case 4. The considered Ω -operator has the form the states of Ω -algorithm. So, the The scheme of the supposed mentioned forms constructed for all algorithm. It is easily seen that such completes the proof. Corollary 1: For any PtRF f )( xf . The proof is based on Theorem Note: The statements established in Lemma in [18], where it is proved that any PtRF may be realized by some graph constructed on the base of the functions graph-schemes with memory corresponding to graph-schemes considered in Theorem 7.1 in [18]. Besides, the definition of realizability by n Γ -algorithm differs from the corresponding definition in [18]. Now let us define for any Γ computation process realized by this describing predicate”, or, shortly, “SD SD-predicate for a given n Γ -algorithm, then algorithm transforms the state corresponding computation process. Let us note the following property of the predicate ),...,,( 121 +nxxx is a state of the computational process realized by the considered S. Manukian transforms the state ),,( vuα of 2Γ -algorithmψ to the state operator has the form ),2,( βα × . In this case the required subscheme algorithm ψ consists of the single 2Γ -operator ,1,( 2α +x operator has the form ),3,( βα × . In this case the required subscheme algorithm ψ consists of the single 2Γ -operator ,1,( 3α +x -operator has the form ),,6:,( γβα . In this case the required subscheme of the supposed 2Γ -algorithm ψ consists of the following ), 2δγ , 22 ,( xδ ),1 3δ , 33 ,( xδ ),1 β . Here identifiers attached to additional 2Γ -operators which are included in the scheme of the supposed algorithm for modeling the working of the considered Ω -operator. Of course, these identifiers should be different in different subschemes of this kind. operator has the form ),0( end . This Ω -operator algorithm. So, the corresponding 2Γ -operator has the same form The scheme of the supposed 2Γ -algorithm is obtained as the union of subschemes of the mentioned forms constructed for all Ω -operators included in the scheme of the given algorithm. It is easily seen that such 2Γ -algorithm satisfies the conditions of Lemma )( xf and any 2≥n there exists a nΓ -algorithm realizing the PtRF The proof is based on Theorem 3 and is similar to that of Lemma 3.2. The statements established in Lemma 3.2 and in its Corollary 1 are similar to Theorem 7.1 in [18], where it is proved that any PtRF may be realized by some graph-scheme with memory constructed on the base of the functions 1+x , x 1 and of the predicate schemes with memory corresponding to n Γ -algorithms are essentially simple schemes considered in Theorem 7.1 in [18]. Besides, the definition of realizability algorithm differs from the corresponding definition in [18]. n Γ -algorithm, where 1≥n , the predicate describing one step of computation process realized by this n Γ -algorithm. Such a predicate we will call “ describing predicate”, or, shortly, “SD-predicate” for a given n Γ -algorithm. Namely, if algorithm, then ),...,,( 2221 +nxxxη is true if and only if the given algorithm transforms the state ),...,,( 121 +nxxx to the state ),...,,( 2232 +++ nnn xxx corresponding computation process. Let us note the following property of the predicate is a state of the computational process realized by the considered 37 to the state ),,( stβ . We will . In this case the required subscheme ), β . . In this case the required subscheme ), β . . In this case the required following 2Γ -operators: Here 1δ , 2δ , 3δ are operators which are included in the scheme of the supposed operator. Of course, these does not transform form ),0( end . algorithm is obtained as the union of subschemes of the s included in the scheme of the given Ω - algorithm satisfies the conditions of Lemma 3.2. This algorithm realizing the PtRF are similar to Theorem 7.1 scheme with memory 1 and of the predicate 0=x . However, algorithms are essentially simpler than the schemes considered in Theorem 7.1 in [18]. Besides, the definition of realizability of PtRf , the predicate describing one step of algorithm. Such a predicate we will call “a step algorithm. Namely, if η is the is true if and only if the given n Γ - ) by one step of the corresponding computation process. Let us note the following property of the predicate η : if is a state of the computational process realized by the considered n Γ -algorithm, On Strongly Positive Multidimensional Arithmetical38 such that x1≠ 0, then there exists a single ),...,,( 2221 +nxxxη is true. The set of truth for the mentioned predicate algorithm. Clearly, such a set π has the following property: ),...,,( 121 +nxxx is a state of computation process realized by th this n Γ -algorithm transforms the state of the computation process. Now let us define the forms of SD that some n Γ -algorithm ψ , where ≥n any n Γ -operator included in the scheme of Case 1. The considered n Γ -operator has the form state ),...,,,,...,,,( 11132 ++− niii xxxxxxα where 23 xxn =+ , 34 xxn =+ ,…, −+ = iin xx The SD-predicate for such a n Γ 1 2 3 2 4 3 1 1 2 1 2 2 1 ( ) & ( ) & ( ) & ( ) & ... & ( ) & ( ( )) & &( ) & ... & ( ). n n n n i i n i i n i i n n x x x x x x x x x S x x x x x α β + + + + − + + + + + + + = = = = = = = = Case 2. The considered n Γ -operator has the form state ),...,,,,...,,,( 11132 ++− niii xxxxxxα to the state 23 xxn =+ , 34 xxn =+ ,…, 1−+ = iin xx , inx + The SD-predicate for such a n Γ (&)0(((&)(& )(&)(&)( 1122 2321 ++++ ++ == === innn nn xxxx xxxx βα Case 3. The considered n Γ -operator has the form the state ),...,,,( 132 +nxxxα to the states 23 xxn =+ , 34 xxn =+ ,…, 122 ++ = nn xx ) in the cases, when, correspondingly, SD-predicate for such a n Γ -operator is ))).0(&)(( )(&)(&)( 2 34231 =¬= === + ++ in nn xx xxxxx γ α Case 4. The considered n Γ -operator has the form the states of n Γ -algorithm, so, an SD-predicate is not considered for such The SD-predicate for n Γ -algorithm disjunction of formulas expressing SD contained in the scheme of ψ and different from the operator algorithm ψ is obtained as the set of truth for the corresponding SD set is a )22( +n -dimensional arithmetical set. On Strongly Positive Multidimensional Arithmetical Sets there exists a single )1( +n -tuple ),...,,( 2232 +++ nnn xxx The set of truth for the mentioned predicate η we will call “SD-set” for the considered has the following property: π∈ + ),...,,( 2221 nxxx if and only if is a state of computation process realized by the considered n Γ -algorithm, and algorithm transforms the state ),...,,( 121 +nxxx to the state ),...,,( 2232 +++ nnn xxx by one step Now let us define the forms of SD-predicates and SD-sets for n Γ -algorithms. We suppose 1≥ is fixed. We will define the forms of SD-predicates for operator included in the scheme of ψ . operator has the form ),1,( βα + i x . Such n Γ -operator transforms the to the state ,,,...,,,( 2143 +++++++ inininnn xxxxxβ 1− , 11 +=++ iin xx , 12 +++ = iin xx ,…, 122 ++ = nn xx . n -operator is expressed by the following formula: 1 2 3 2 4 3 1 1( ) & ( ) & ( ) & ( ) & ... & ( ) & ( ( )) &n n n n i i n i ix x x x x x x x x S x+ + + + − + += = = = = = operator has the form i x,(α ),1 β . Such n Γ -operator transforms the to the state ,...,,,,...,,,( 22143 +++++++ inininnn xxxxxxβ i x= +1 1, 12 +++ = iin xx ,…, 122 ++ = nn xx . n -operator is expressed by the following formula: )))).((&)0(())0 (&)(&...&)(& 1 2134 ++ ++−++ ==¬∨= === iniii iniinn xSxxx xxxxx operator has the form ),,0,( γβα = i x . Such n Γ -operator transforms to the states ),...,,,( 2243 +++ nnn xxxβ or ,...,,,( 243 +++ nnn xxxγ ) in the cases, when, correspondingly, 0= i x or x operator is expressed by the following formula: (&)(((&)(&...&) 2122 === +++ innn xxxx β operator has the form ),0( end . Such n Γ -operator does not transform predicate is not considered for such n Γ -operator. algorithm ψ is expressed by the formula obtained as the disjunction of formulas expressing SD-predicates constructed above for all n Γ and different from the operator ),0( end . The SD-set for is obtained as the set of truth for the corresponding SD-predicate. Clearly, such SD dimensional arithmetical set. such that set” for the considered n Γ - if and only if algorithm, and by one step algorithms. We suppose predicates for operator transforms the ),..., 222 +nx , following formula: operator transforms the )22 +n ,where the following formula: ...&)1+ix operator transforms )2+ (where 0≠ i x . The expressed by the following formula: ))0 ∨ operator does not transform operator. is expressed by the formula obtained as the n -operators set for n Γ - predicate. Clearly, such SD- S. Manukian 39 Lemma 3.3: SD-predicate and SD-set constructed for any n Γ -algorithm, where 1≥n , are strongly positive. The proof is obtained evidently from the definitions. Lemma 3.4: (cf. [13], p.72). If A is a k2 -dimensional set, kNA 2⊆ , then k2 -tuple ),...,,,,...,,( 2121 kk yyyxxx belongs to the transitive closure * A of the set A if and only if there exists a sequence ),...,,( 21 mQQQ of k -tuples, such that 2≥m , ),...,,( 211 kxxxQ = , ),...,,( 21 km yyyQ = and any k2 -tuple ),( 1+ii QQ for 11 −≤≤ mi belongs to A . The proof is easily obtained using the definition of the transitive closure *A . 4. Proof of Theorem 1 Let M be any one-dimensional creative set ([3], [5], [7], [8]). We consider the PtRF )( xf such that 0)( =xf when Mx ∈ , and the value )( xf is indefined when Mx ∉ . For any fixed 2≥n we construct (using Corollary of Lemma 3.2) a n Γ -algorithm ψ realizing the PtRF )( xf ; clearly, ψ transforms the state )0,...,0,0,2,1( x to the state )0,...,0,0,1,0( when Mx ∈ and is not applicable to the state )0,...,0,0,2,1( x when Mx ∉ . Now, let us consider the SD-predicate η and SD-set π for ψ . Clearly, η is true for )22( +n -tuple ),...,,,,...,,( 121121 ++ nn yyyxxx (and the statement π∈ ++ ),...,,,,...,,( 121121 nn yyyxxx holds) if and only if ψ transforms the state ),...,,( 121 +nxxx to the state ),...,,( 121 +nyyy by one step of the process of computation. Let us consider the transitive closure *π of the SD-set π . Using Lemma 3.4 we conclude that *121121 ),...,,,,...,,( π∈++ nn yyyxxx if and only if there exists a sequence ),...,,( 21 mQQQ of )1( +n -tuples such that ),...,,( 1211 += nxxxQ , ),...,,( 121 += nm yyyQ , and π∈+ ),( 1ii QQ for any i such that mi <≤1 . But in this case the sequence ),...,,( 21 mQQQ is a sequence of states of the nΓ -algorithm ψ which describes some part of a process of computation implemented by the n Γ -algorithm ψ . Hence, the )22( +n -tuple )0,...,0,0,1,0,0,...,0,0,2,1( x belongs to *π if Mx ∈ . It is easily seen that the mentioned )22( +n -tuple does not belong to *π if Mx ∉ . Let us consider the set N∈ **π such that its )22( +n -dimensional image is *π . Then ** 22 )0,...,00,1,0,0,...,0,0,2,1( π∈+ x n c if and only if Mx ∈ . So the set M is m -reducible to the set **π . Using the corresponding theorem concerning m -reducibility (see, for example, [8], p. 161), we conclude that the set **π is creative, the set *π is creative in the generalized sense, and the set π is strongly positive (see Lemma 3.3). This completes the proof. Note: It is seen from Theorem 1 that the transitive closures of some strongly positive sets having the dimensions 6, 8, 10, … are creative in the generalized sense. On the other side (Theorem 2) the transitive closure of any 2-dimensional strongly positive set is primitive recursive. Similar problem concerning 4-dimensional strongly positive sets remains open. On Strongly Positive Multidimensional Arithmetical Sets 40 References [1] S. N. Manukian, “On the representation of recursively enumerable sets in weak arithmetics”, Transactions of the IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 27, pp. 90--110, 2006. [2] S. N. Manukian, “On an algebraic classification of multidimensional recursively enumerable sets expressible in formal arithmetical systems”, Transactions of the IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 41, pp. 103-113, 2014. [3] S. C. Kleene, Introduction to Metamathematics, D, Van Nostrand Comp., Inc., New York- Toronto, 1952. [4] H. B. Enderton, A Mathematical Introduction to Logic, 2nd edition, San Diego, Harcourt, Academic Press, 2001. [5] E. Mendelson, Introduction to Mathematical Logic, D, Van Nostrand Comp., Inc., Princeton-Toronto-New York-London, 1964. [6] D. Hilbert and P. Bernays, Grundlagen der Mathematik, Band1, Zweite Auflage, Berlin- Heidelberg-New York, Springer Verlag, 1968. [7] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw Hill Book Comp., New York-St. Louis-San Francisco-Toronto-London-Sydney, 1967. [8] A. I. Malcev, Algorithms and Recursive Functions, 2nd edition, (in Russian), 1986. [9] A. A. Markov, “Impossibility of some algorithms in the theory of associative systems”, Reports of the Acad. Sci. USSR, (in Russian), vol. 55, no. 7, pp. 587-590, 1947. [10] E. L. Post, “Recursive unsolvability of a problem of Thue”, Journ. of Symb. Logic, vol. 12, pp. 1-11, 1947. [11] P. S. Novikov, “On the algorithmic unsolvability of identity problem in the group theory”,Transactions of Steklov Institute of the Acad. Sci. USSR, (in Russian), vol. 44, 1955. [12] G. S. Tseytin, “Associative calculus with the unsolvable problem of equivalence”, Transactions of Steklov Institute of the Acad. Sci. USSR, (in Russian), vol. 52, pp. 172- 189, 1958. [13] G. S. Tseytin, “One method of representation for the theory of algorithms and enumerable sets”, Transactions of Steklov Institute of the Acad. Sci. USSR, (in Russian), vol. 72, pp. 69-98, 1964. [14] S. N. Manukian,. “Classification of many-dimensional arithmetical sets represented in M. Presburger’s system”, Reports of the National Acad. Sci. of Armenia, (in Russian), vol. 111, no. 2, pp. 114--120, 2011. [15] M. Presburger, “Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt”, Comptes Rendu du I Congres des Mathematiciens des Pays Slaves, Warszawa, pp. 92-101, 1930. [16] R. Stransifer, Presburger’s Article on Integer Arithmetics: Remarks and Translation, Department of Computer Science, CornellUniversity, Ithaca, New York, 1984. [17] M. L. Minsky, “Recursive unsolvability of Post’s problem of “Tag” and topics in theory of Turing machines”, Ann. Math., vol. 74, pp. 437-455, 1961. [18] I.D. Zaslavsky, “Graph-schemes with memory”, Transactions of Steklov Institute of Acad. Sci. USSR, (in Russian), vol. 72, pp. 99-192, 1964. Submitted 25.11.2014, accepted 27.01.2015. S. Manukian 41 Խիստ պոզիտիվ բազմաչափ թվաբանական բազմությունների մասին Ս. Մանուկյան Ամփոփում [1]-ում և [2]-ում սահմանվում և հետազոտվում է պոզիտիվ թվաբանական բանաձևի գաղափարը ),,0( S= սիգնատուրայում, (որտեղ 1)( += xxS ): Բազմաչափթվաբանական բազմությունը կոչվում է պոզիտիվ, եթե այն որոշվում է որևէ պոզիտիվ բանաձևի միջոցով: Դիտարկվում է պոզիտիվ բազմությունների դասի որևէ ենթադաս, այսինքն` խիստ պոզիտիվ բազմությունների դասը: Ապացուցվում է, որ ցանկացած n -ի համար, որտեղ 3≥n , գոյություն ունի n2 -չափանի խիստ պոզիտիվ բազմություն, որի տրանզիտիվ փակումը ռեկուրսիվ չէ: Մյուս կողմից նշվում է, որ ցանկացած 2-չափանի խիստ պոզիտիվ բազմություն ունի պարզագույն ռեկուրսիվ տրանզիտիվ փակում: О строго позитивных многомерных арифметических множествах С. Манукян Аннотация Понятие позитивной арифметической формулы в сигнатуре ),,0( S= , где 1)( += xxS , определено и исследовано в [1] и [2]. Многомерное арифметическое множество называем позитивным, если оно задаётся позитивной формулой. Рассматривается подкласс класса позитивных множеств, а именно, класс строго позитивных множеств. Доказывается, что для всякого 3≥n существует строго позитивное множество размерности n2 , такое, что его транзитивное замыкание нерекурсивно. С другой стороны, указывается, что транзитивное замыкание всякого строго позитивного множества размерности 2 примитивно рекурсивно.