Mathematical Problems of Computer Science 41, 103--113, 2014. 103 On an Algebraic Classification of Multidimensional Recursively Enumerable Sets Expressible in Formal Arithmetical Systems1 Seda N. Manukian Institute for Informatics and Automation Problems of NAS RA e-mail: zaslav@ipia.sci.am Abstract Algebraic representations of multidimensional recursively enumerable sets which are expressible in formal arithmetical systems based on the signatures ),,,0(  S , ),,,0( S , ),,0( S , where 1)(  xxS , are introduced and investigated. The equivalence is established between the algebraic and logical representations of multidimensional recursively enumerable sets expressible in the mentioned systems. Keywords: Predicate formula, Universal algebra, Recursively enumerable set, Mathematical structure, Deductive system, Formal arithmetic. 1. Introduction In this paper algebraic representations of multidimensional recursively enumerable sets (RES) described in some subsystems of Peano’s formal arithmetic ([1], [2], [3]) are introduced and investigated. Similar problems concerning two-dimensional RESes are considered in [4], [5], [6]. But the structure of algebraic representations of multidimensional RESes differs from the structure of algebraic representations of two-dimensional ones. It was necessary to introduce essential changes in the notions used in [4], [5], [6] for the description of such algebraic representations. However, as it will be proved below, the relations between algebraic and logical representations of multidimensional RESes are similar to those described in [5]. Theorems 2.1, 2.2, 2.3 (see below) about such relations will be formulated in Sec.2 and proved in Sec.3. 2. Main Definitions and Results Let us give the definitions of notions used below (cf. [7], [8]). An n-dimensional arithmetical set, where 1n , is defined in a natural way as a set of n-tuples ),...,,( 21 nxxx , where nxxx ,...,, 21 are 1 This work was supported by State Committee of Science, MES RA, in frame of the research project № SCS 13- B321. On an Algebraic Classification of Multidimensional Recursively Enumerable Sets Expressible104 nonnegative integers 0, 1, 2, .... An n-dimensional arithmetical predicate is defined as a predicate which is true on some n-dimensional arithmetical set and false out of it. The notion of recursively enumerable set (RES) is defined as in [1]. An algebra is defined as a “universal algebra” ([9], [10]) with a fixed set of basic elements. Thus, any algebra is described by a main set M , by a set of operations ,..., 21 ff on M (in general not everywhere defined), and a set of basic elements ,..., 21 aa in M ([5]). We say that an element Ma is inductively representable in a given algebra ,...),,...;,;( 2121 aaffM if it can be obtained by the operations ,..., 21 ff from the basic elements ,..., 21 aa . The notions of a subalgebra and a proper subalgebra of a given algebra are defined in a natural way (for example, as in [5]). We will consider the following operations on multidimensional RESes (cf [14]). 1) The operations of union  and intersection  of RESes are defined in a usual way (note that these operations are applied only to RESes having equal dimensions). 2) The operation i of projection for n-dimensional RES A concerning i-th co-ordinate, where ni 1 , is defined by the following generating rule (g.r.): if Axxx n ),...,,( 21 , then )(),...,,,...,,( 1121 Axxxxx inii  . 3) The operation  of Cartesian product for n-dimensional RES A and m-dimensional RES B is defined by the following g.r.: if Axxx n ),...,,( 21 , and Byyy m ),...,,( 21 , then BAyyyxxx mn ),...,,,,...,,( 2121 . 4) The operation ijT of transposition of i-th and j-th co-ordinates in n-dimensional RES A , where nji  ,1 , is defined by the following g.r.: if Axxx n ),...,,( 21 , then )(),...,,,...,,,,...,,( 111121 ATxxxxxxxxx ijnjijiji  . 5) The operation  of transitive closure for a RES A having an even dimension 2n is defined by the following generating rules: (a) if Axxx n ),...,,( 221 , then Axxx n ),...,,( 221 ; (b) if Ayyyxxx nn ),...,,,,...,,( 2121 and Azzzyyy nn ),...,,,,...,,( 2121 , then Azzzxxx nn ),...,,,,...,,( 2121 . The following RESes are used as basic elements for the considered algebras (cf. [7]): }0|{0  xxZ ; }1|),{(  xyyxR ; }|),,{( yxzzyxAdd  ; }|),{( yxyxQ  ; }|),{( yxyxJ  . Examples: RQ  ; )())(( 11 AddAdd  . Let us define the algebras 0 , 1 , 2 , 3 . The main set for these algebras is the set of all multidimensional RESes having the dimensions 1n . The list of operations for all these algebras is ),,,,( ijT . The lists of basic elements are as follows (cf. [7]): ),,( 0 AddRZ for 0 , ),,( 0 QRZ for 1 , ),,( 0 JRZ for 2 , ),( 0 RZ for 3 . Note: The introduced algebras are different from the algebras denoted by 0 , 1 , 2 , 3 in [5]. The algebras having these notations in [5] we will denote below by 0 ~  , 1 ~  , 2 ~  , 3 ~  . The relations between the algebras 0 , 1 , 2 , 3 and 0 ~  , 1 ~  , 2 ~  , 3 ~  will be considered in Sec.3. S. Manukian 105 The notion of a predicate formula based on the logical operations  ,,,,&, (as other notions connected with it, for example, the notion of a term) is defined in a usual way ([1], [3], [11], see also [5]). A signature is defined in a usual way as any set of constants symbols, functional symbols, predicate symbols. We say that a formula F (respectively, a term t ) belongs to a given signature  (or is a formula (respectively, a term) in the signature  ) if all the constants symbols, functional symbols, predicate symbols contained in F (respectively, all the constants symbols and functional symbols contained in t ) belong to  . We will consider the signatures ),,,0( S , ),,,0( S , ),,0( S , where S is an one-dimensional functional symbol; these signatures will be denoted below respectively by HN , LN , SN (cf. [7]). Note that similar notations are used in [7] as the notations of the corresponding mathematical structures (however, the structure corresponding to the signature ),,,0( S is denoted in [7] (and in [3]) by AN ). The arithmetical interpretation of a predicate formula belonging to one of these signatures and containing no other free variables except nxxx ,...,, 21 is defined in a natural way as an n- dimensional arithmetical predicate; the functional symbol S is interpreted as the function 1)(  xxS , and other symbols in the mentioned signatures are interpreted in a natural way. The deductive systems of formal arithmetic in the signatures HN , LN , SN are defined as in ([1], [3], [11]-[13]; see also [6]); we will denote these deductive arithmetical systems respectively by HDed , LDed , SDed (cf. [6]). For example, the system HDed is equivalent to M. Presburger’s system described in [11]-[13]. We say that formulas F and G (respectively terms t and s ) are equivalent in the framework of the corresponding deductive system if the formula )(&)( FGGF  (respectively, the formula st  ) is deducible in this system. If the formulas F and G or the terms t and s are equivalent in HDed (respectively, LDed or SDed ), we will say that they are HDed -equivalent (respectively, LDed -equivalent or SDed -equivalent). All mentioned systems of formal arithmetic are complete ([3], [11]-[13]). We say that a set  of predicate formulas belonging to one of the mentioned signatures admits the elimination of quantifiers (in the framework of the corresponding deductive system) if for any predicate formula F belonging to  a formula G belonging to Г can be constructed so that G does not contain quantifiers and is equivalent to F in the framework of the corresponding deductive system. The sets of all predicate formulas belonging to the signatures HN , LN , SN admit the elimination of quantifiers in the framework of the corresponding deductive systems HDed , LDed , SDed ([3], [11]-[13]). By )(tS n , where 0n , and t is a term, we denote the term )...))((...( tSSS , where the symbol S is repeated n times ( )(0 tS is t ). By n we denote the term )0(nS . We say that a k-dimensional arithmetical set A is represented (or representable) by a formula F belonging to one of the mentioned signatures and containing free variables kxxx ,...,, 21 , if the following condition holds: the arithmetical interpretation of the formula obtained by the substitution of the terms knnn ,...,, 21 for the variables kxxx ,...,, 21 in F is true if and only if Annn k ),...,,( 21 . We say that a k-dimensional arithmetical set A is represented (or representable) in HDed (respectively, LDed , SDed ) by a formula F in HN (respectively LN , SN ) if it is represented by some formula F  equivalent to F in HDed (respectively, LDed , SDed ). For example, the (n+1)-dimensional RES }...|),,...,,{( 2121 yxxxyxxx nn  is represented in HDed by the formula ))0(...( 21 ySzxxxz n  in HN . On an Algebraic Classification of Multidimensional Recursively Enumerable Sets Expressible106 A formula F in the signature SN is said to be positive if it contains no other logical symbols except  ,,&, and all the symbols  of negation contained in it relate to elementary subformulas containing no more than one variable (cf. [5], [7]). Theorem 2.1: A multidimensional RES is inductively representable in the algebra 0 (respectively 1 , 2 ) if and only if it is represented in HDed (respectively, LDed , SDed ) by a formula in HN (respectively, LN , SN ). Theorem 2.2: A multidimensional RES is inductively representable in the algebra 3 if and only if it is represented in SDed by a positive formula in SN . Theorem 2.3: Every next algebra in the sequence 0 , 1 , 2 , 3 is a proper subalgebra of the preceding one. Theorems 2.1 and 2.2 are formulated (without proofs and in some other terms) in [7]. 3. Proofs of Theorems In this section the proofs of Theorems 2.1, 2.2, 2.3 will be given. We will consider the following sets. By V we denote the set of all non-negative integers 0,1,2,..., by kV we denote the set of all k-tuples ),...,,( 21 kxxx where 1k , and all ix are non- negative integers. By O we denote the 1-dimensional empty set, by kO we denote the k- dimensional empty set. By E and 1Q we denote the sets }|),{( yxyxE  and }|),{(1 yxyxQ  . Obviously, all these sets are represented in the following deductive systems: V in DedS by the formula xx  , kV in DedS by the formula )&...&&( 2211 kk xxxxxx  , O in DedS by the formula )(xSx  , kO in DedS by the formula ))(&...&)(&)(( 2211 kk xSxxSxxSx  , E in DedS by the formula yx  , 1Q in DedL by the formula )()( yxyx  . Lemma 3.1: The sets V , kV , O , kO , E , 1Q , Q , J are inductively representable in the following algebras: the sets V , kV , O , kO , E in all algebras 0 , 1 , 2 , 3 , the sets 1Q , Q - in the algebras 0 and 1 , the set J - in the algebras 0 , 1 , 2 . The proof is given by the following equalities: )(2 RV  ; VVVV k  ... , where the symbol V is repeated k times; ))(( 121 RTRO  ; OOOO k  ... , where the symbol O is repeated k times; )))(()(( 122 RTVVRE  ; EQQ 1 ; )(11 AddQ  ; ))()(( 12 RVVQQ  ; )(12 QTQJ  . Corollary: Every next algebra in the sequence 0 , 1 , 2 , 3 is a subalgebra of the preceding one. S. Manukian 107 Lemma 3.2: Any RES inductively representable in 0 (respectively, 1 , 2 ) can be represented in HDed (respectively, LDed , SDed ) by a formula in HN (respectively, LN , SN ). Proof: The basic sets for 0 are represented by the formulas 0x , )(xSy  , yxz  ; similarly, the basic sets for 1 are represented by the formulas 0x , )(xSy  , yx  ; for 2 - by the formulas 0x , )( xSy  , )( yx  . If arithmetical sets A and B having equal dimensions are represented by formulas F and G , then the sets BA and BA are represented by the formulas )( GF  and )&( GF . If an n-dimensional arithmetical set A is represented by a formula F containing free variables nxxx ,...,, 21 , then the set )( Ai , where ni 1 , is represented by the formula )(Fxi . If an n-dimensional arithmetical set A is represented by a formula F containing only free variables nxxx ,...,, 21 , and an m-dimensional arithmetical set B is represented by a formula G containing only free variables myyy ,...,, 21 , then the set BA is represented by the formula GF & , where the formula G is obtained from G by the substitution of variables mnnn xxx  ,...,, 21 for myyy ,...,, 21 in G . If an n-dimensional arithmetical set A is represented by a formula F containing free variables nxxx ,...,, 21 , then the formula )( ATij , where nji  ,1 , is represented by a formula F obtained from F by a corresponding replacement of free variables. This completes the proof. Now we will give the proof of the statement opposite to the statement of Lemma 3.2. In what follows any term in HN having the form )...( xxx  , where the variable x is repeated k times, will be shortly denoted by kx . The notation kx will denote the term 0 when 0k ; it will denote the term x when 1k . We will consider below the following sets. (1) The set kZ , where k is a constant, 0k ; it is a one-dimensional set containing only the number k . (2) The set kW , where k is a constant, 0k ; it is a one-dimensional set containing all the numbers x such that kx  . (3) The set kR , where k is a constant, 1k ; it is a two-dimensional set )}(|),{( xSyyx k . (4) The set kEAdd , where k is a constant, 0k ; it is a two-dimensional set }|),{( kxyyx  . (5) The set ),,...,,( 21 qkkkLin nexp , where 1n , and qkkk n ,,...,, 21 are constants, 01 k , 02 k , ..., 0nk , 0q ; it is an (n+1)-dimensional set }...|),,...,,{( 221121 yqxkxkxkyxxx nnn  . (6) The set ),( yxCongrk , where k is a constant, 2k ; it is a two-dimensional set )})(mod(|),{( kyxyx  . Clearly, all these sets are represented by formulas in the following deductive systems: kZ is represented by the formula )( kx  in DedH, DedL, DedS; kW is represented by the formula ))(( 1 zSxz k in DedH, DedL, DedS; kR is represented by the formula )(xSy k in DedH, On an Algebraic Classification of Multidimensional Recursively Enumerable Sets Expressible108 DedL, DedS; kEAdd is represented by the formula kxy  in DedH; q),k,...,k,Linexp(k n21 is represented in DedH by the formula yqxkxkxk nn  ...2211 ; ),( yxCongrk , where 2k is represented in DedH by the formula ))()(( xkzyykzxz  . Lemma 3.3: The sets kZ , where 0k , the sets kW , where 0k , the sets kR , where 1k , the sets kEAdd , where 0k , the sets q),k,...,k,Linexp(k n21 , where 1n , 0ik for ni 1 , 0q , the sets ),( yxCongrk , where 2k are inductively representable in the following algebras: kZ , kW and kR in 0 , 1 , 2 , 3 ; kEAdd , q),k,...,k,Linexp(k n21 and ),( yxCongrk in 0 . The proof is given by the following equalities (note that the sets 0Z and R are included as basic elements in all the algebras 0 , 1 , 2 , 3 ): ))((11 RVZZ kk  ; )(10 RW  ; ))((11 RVWW kk  ; RR 1 ; ))()((21 RVVRR kk  ; 00 ZVEAdd  ; )))()()((( 223 2 111 VETAddVVEAddEAdd kk  ; )))()()(((),( 2222 AddVVZVVEAddqkexpLin qk  ; )))()()),,...,((((),,,...,,( 123213,12221 AddVVEAddVVqkkkLinTqlkkkLin n l n nnnnnn    expexp ; ))))()(((()))()((( 21112 2 11 AddVVEaddTAddVVEAddCongr kkk  . Lemma 3.4: Any term in HN is HDed -equivalent to a term having the form qxkxkxk nn  ...2211 , where q is a nonnegative integer constant. Any formula in HN is HDed -equivalent to a formula which can be obtained by & and  from subformulas having the form st  or ))(mod( kst  , where t and s are terms, and k is an integer constant, 2k . This Lemma is proved (in other terms) in [3], [4], [11] (cf. [6], Lemma 4.1). Lemma 3.5: Any RES represented in HDed by a formula in HN is inductively representable in the algebra 0 . Proof: Let F be a formula in HN . Let us denote by nxxx ,...,, 21 the list of all free variables contained in F . Using Lemma 3.4 we conclude that there exists a formula F which is HDed - equivalent to F and can be obtained by & and  from subformulas having the form st  or ))(mod( kst  , where t and s have the form described in Lemma 3.4. Without loss of generality we can suppose that the list of variables in all mentioned terms t and s coincides with the list nxxx ,...,, 21 (indeed, if some variable ix is missing in a corresponding sum, then we can add to this sum the summand ix0 ; the order of summands in all considered sums can be unified using the operation ijT ). We see that the formula F is HDed -equivalent to some formula which can be obtained by & and  from the formulas having the form st  or ))(mod( kst  in which all the terms t and s have the form qxkxkxk nn  ...2211 , where 0ik for ni 1 , and 0q . n-dimensional sets represented by the formulas of such kind can be described in 0 by the following expressions: the set represented by the formula having the S. Manukian 109 form st  - by the expression of the form )))()),,...,,(()),,...,,(((( ""2 " 12,1 '' 2 ' 121 QVVqkkkexpLinTVqkkkexpLin n nnnnnn   ; the set represented by the formula having the form ))(mod( kst  - by the expression of the form )))()),,...,,(()),,...,,(((( 212,12121 k n nnnnnn CongrVVqkkkexpLinTVqkkkexpLin    . Thus, any n-dimensional set represented by the formula F can be described in 0 applying the operations  and  to the expressions having the forms mentioned above. This completes the proof. Lemma 3.6: Any term in LN has the form )(xS k or )0(kS , where x is a variable. Any formula in LN is LDed -equivalent to a formula which can be obtained by & and  from subformulas having the form )( st  , where t and s are terms. This Lemma is proved (in other terms) in [3], [5], [11] (cf. [6], Lemma 4.2). Lemma 3.7: Any RES represented in LDed by some formula in LN is inductively representable in the algebra 1 . Proof: Let F be a formula in LN . Let us denote by nxxx ,...,, 21 the list of all free variables in F . We suppose that 2n (the case 2n is considered in a similar way). Using Lemma 3.6 we conclude that F is LDed -equivalent to some formula F  which can be obtained by & and  from subformulas of the form )( st  , where t and s are terms. Let us consider the case when t and s contain only the variables 1x and 2x (the general case is reduced to the mentioned one using the operation ijT ). We will denote the variables 1x and 2x by x and y . Using Lemma 3.6 we see that in the subformula )( st  the term t has one of the forms )(xS k , )( yS k , )0(kS , where 0k ; the term s has one of the forms )(xS l , )( yS l , )0(lS , where 0l . Thus, there are 9 possible forms of the subformula )( st  . If )( st  has the form )()( ySxS lk  , then the n- dimensional set represented by this formula is 21 ))()((    n lk VQVVR when lk  ; it is 2 233 ))()((    n kl VRVTVQ , when lk  , and 2 nVQ when lk  . If )( st  has the form )()( xSxS lk  , then the n-dimensional set represented by this formula is nO when lk  , and is nV when lk  . If )( st  has the form )0()( lk SxS  , then the n-dimensional set represented by this formula is nO when lk  , and is 1110 )...(    n kl VZZZ when lk  . The remaining forms of the formula )( st  are considered in a similar way. Thus, the n- dimensional RES represented by the formula F in LDed is obtained by  and  from sets inductively representable in 1 . This completes the proof. Lemma 3.8: Any term in SN has the form )(xS k or )0(kS , where x is a variable. Any formula in SN is SDed -equivalent to a formula which can be obtained by & and  from subformulas having the form )( st  or )( st  , where t and s are terms. This Lemma is actually proved (in other terms) in [3], [11] (cf. [5], Lemma 3.8). On an Algebraic Classification of Multidimensional Recursively Enumerable Sets Expressible110 Lemma 3.9: Any RES represented in SDed by formula in SN is inductively representable in the algebra 2 . Proof: The proof is similar to that of Lemma 3.7. Let F be a formula in SN . Let us denote by nxxx ,...,, 21 the list of all free variables contained in F . We suppose (as in the proof of Lemma 3.7) that 2n . Using Lemma 3.8 we conclude that F is SDed -equivalent to some formula F which can be obtained by & and  from subformulas having the forms )( st  and )( st  . As in the proof of Lemma 3.7 we consider the case when t and s contain only variables 1x and 2x ; we will denote these variables by x and y . Using Lemma 3.8 we see that in the subformulas )( st  and )( st  the term t has one of the forms )(xS k , )( yS k , )0(kS , where 0k ; the term s has one of the forms )(xS l , )( yS l , )0(lS , where 0l . Thus, there are 9 possible forms of the subformula )( st  and 9 possible forms of the subformula )( st  . If )( st  has the form )()( ySxS lk  , then the n-dimensional set represented by this formula is 2   n lk VR when lk  ; it is 2 12 )(    n kl VRT when lk  , and 2 nVE when lk  . The n-dimensional set represented by the formula ))()(( ySxS lk  is ))()((2 JVVR lk   when lk  , it is )))()((( 212 JVVRT kl   when lk  , and 2 nVJ when lk  . The n-dimensional set represented by the formula )()( xSxS lk  is nO when lk  ; it is nV when lk  . The n-dimensional set represented by the formula ))()(( xSxS lk  is nV when lk  ; it is nO when lk  . The n-dimensional set represented by the formula )0()( lk SxS  is nO when lk  ; it is 1   n kl VZ when lk  . The n-dimensional set represented by the formula ))0()(( lk SxS  is nV when lk  ; it is 1 110 )...(    n klkl VWZZZ when lk  ; and 1 0  nVW when lk  . The remaining forms of the formulas )( st  and )( st  are considered in a similar way. Thus, the n-dimensional RES represented by the formula F is obtained by  and  from sets inductively representable in 2 . This completes the proof. The proof of Theorem 2.1 is obtained now using Lemmas 3.2, 3.5, 3.7, 3.9. Lemma 3.10: The set of positive formulas in SN admits the elimination of quantifiers in the framework of SDed . The proof follows from the considerations in [3], because it is easily seen that the method of elimination of quantifiers in SN described in [3] gives for any positive formula F in SN some positive formula G such that G does not contain quantifiers and is SDed -equivalent to F . Lemma 3.11: Any positive formula in SN is SDed -equivalent to a formula which can be obtained by & and  from subformulas having the form )( st  or )( st  , where t and s S. Manukian 111 are terms of the form )(xS k or )0(kS , and any subformula of the form )( st  contains no more than one variable. The proof is easily obtained using Lemmas 3.8 and 3.10. Lemma 3.12: Any RES inductively representable in 3 can be represented in SDed by a positive formula in SN . Proof: The basic sets in 3 are represented in SN by the positive formulas 0x and )(xSy  . It is easily seen that the transformation of formulas generated in the proof of Lemma 3.2 by the operations iji T,,,,  gives positive formula being applied to positive formulas. This completes the proof. Lemma 3.13: Any RES represented in SDed by a positive formula in SN is inductively representable in the algebra 3 . Proof: Let F be a positive formula in SN . Let us denote by nxxx ,...,, 21 the list of all free variables in F . Similarly to the proof of Lemmas 3.7 and 3.9 we suppose that 1n . Using Lemma 3.11 we conclude that F is SDed -equivalent to a positive formula which can be obtained by & and  from positive subformulas of the form )( st  or )( st  , where t and s are terms in SN . It is easily seen that any n-dimensional set represented by a formula of the form )( st  is described by the expressions considered in the proof of Lemma 3.9. Now let us consider the sets represented by subformulas of the form )( st  . Let us recall that any positive formula of the form )( st  contains no more than one variable. The single variable contained in )( st  we denote by x and suppose that it coincides with the variable 1x in the list nxxx ,...,, 21 (the general case is considered similarly). Then the formula )( st  has the form ))0()(( lk SxS  , where 0k , 0l . But the inductive representations of the set represented by this formula in 2 are described in the proof of Lemma 3.9; it is easily seen that these representations are also representations in 3 . Thus, the n-dimensional RES represented by the formula F is obtained by  and  from sets inductively representable in 3 . This completes the proof. The proof of Theorem 2.2 is obtained now using Lemmas 3.12 and 3.13. Lemma 3.14: Any multidimensional RES is inductively representable in 0 ~  (respectively, 1 ~  , 2 ~  , 3 ~  ) if and only if it is two-dimensional and is inductively representable in 0 (respectively, 1 , 2 , 3 ). Proof: Let us recall that we denote by 0 ~  , 1 ~  , 2 ~  , 3 ~  the algebras denoted in [5] by 0 , 1 , 2 , 3 . As it is proved in [5], (in other terms) a two-dimensional RES is inductively representable in 0 ~  (respectively, 1 ~  , 2 ~  ) if and only if it is represented in HDed On an Algebraic Classification of Multidimensional Recursively Enumerable Sets Expressible112 (respectively, LDed , SDed ) by a formula in HN (respectively, LN , SN ); a two-dimensional RES is inductively representable in 3 ~  if and only if it is represented in SDed by a positive formula in SN . Now the statement of Lemma 3.14 is obtained using Theorems 2.1 and 2.2 proved above. Proof of Theorem 2.3: As it is proved in [5], there exists a two-dimensional RES 1A (respectively, 2A , 3A ) which is inductively representable in 1 ~  (respectively, 2 ~  , 3 ~  ) but not in 0 ~  (respectively, 1 ~  , 2 ~  ). The statement of Theorem 2.3 is now obtained using Lemma 3.14. Let us note that the list of operations in the algebras 0 , 1 , 2 , 3 is similar to that considered in [14]. Let us note that if we add the operation of transitive closure to this list then any multidimensional RES will be inductively representable in the extended algebra 3 . Such statement is proved in [15] (see [15], Lemma 1). Acknowledgement The author is grateful to Professor Patrick Cegielski for setting the problem considered in this paper, for his attention to this work, for valuable advice and notes. References [1] S. C. Kleene, Introduction to Metamathematics, D. Van Nostrand Comp., Inc., New York-Toronto, 1952. [2] E. Mendelson, Introduction to Mathematical Logic, D. Van Nostrand Comp., Inc., Princeton-Toronto-New York-London, 1964. [3] H. Enderton, A Mathematical Introduction to Logic, 2nd ed., San Diego, Harcourt, Academic Press, 2001. [4] S. N. Manukian, “Algebras of recursively enumerable sets and their applications to fuzzy logic”, Journal of Mathematical Sciences, vol. 130, no. 2, pp. 4598-4606, 2005. [5] S. N. Manukian. “On the representation of recursively enumerable sets in weak arithmetics”, Transactions of the IIAP of NAS RA, Mathematical Probelms of Computer Science, vol. 27, pp. 90--110, 2006. [6] S. N. Manukian, “Some algebraical and logical properties of two-dimensional arithmetical sets representable in Presburger’s System”, Transactions of the IIAP of NAS RA, Mathematical Probelms of Computer Science, vol. 37, pp. 64--74, 2012. [7] S. Manukian, “On the inductive representation of many-dimensional recursively enumerable sets definable in some arithmetical structures”, Proceedings of the International Conference “Computer Science and Information Technologies”, CSIT-09, Yerevan, Armenia, pp. 51--53, 2009. [8] S. N. Manukian. “Classification of many-dimensional arithmetical sets represented in M. Presburger’s system”, Reports of the National Academy of Science of Armenia, (in Russian), vol. 111, no. 2, pp. 114--120, 2011. [9] G. Graetzer, Universal Algebra, 2nd Edition, New-York-Heidelberg-Berlin, 1979. [10] A. I. Malcev, Algebraic Systems, Springer Verlag, 1973. [11] D. Hilbert and P. Bernays, Grundlagen der Mathematik, Band I.Zweite Auflage, Berlin- Heidelberg-New York, Springer Verlag, 1968. S. Manukian 113 [12] M. Presburger, “Über die Vollständigkeit eines gewissen System der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt”, Comptes Rendu de I Congres der Mathematiciens des Pays Slaves, Warszawa, pp. 92--101, 1930. [13] R. Stansifer, Presburger’s Article on Integer Arithmetic: Remarks and Translation, Department of Computer Science, Cornell University, Ithaca, New York, 1984. [14] G. S. Tseytin, “One method of representation for the theory of algorithms and enumerable sets”, Transactions of Steklov Institute of the Russian Academy of Sciences, (in Russian), vol. 72, pp. 69--98, 1964. [15] S. N. Manukian. “On the structure of recursively enumerable fuzzy sets”, Transactions of the IIAP of NAS RA and YSU, Mathematical Probelms of Computer Science, (in Russian), vol. 17, pp. 86--91, 1997. Submitted 14.12.2013, accepted 24. 02. 2014. Ձևայնացված թվաբանական համակարգերում արտահայտելի բազմաչափ անդրադարձ թվարկելի բազմությունների որոշ հանրահաշվական դասակարգման մասին Ս. Մանուկյան Ամփոփում Սահմանվում և հետազոտվում են ),,,0(  S , ),,,0( S , ),,0( S (որտեղ 1)(  xxS ) սիգնատուրաների վրա հիմնված ձևայնացված թվաբանության համակարգերի մեջ արտահայտելի բազմաչափ անդրադարձ թվարկելի բազմությունների հանրահաշվական ներկայացումները: Հաստատվում է համարժեքություն նշված տիպի անդրադարձ թվարկելի բազմությունների հանրահաշվական և տրամաբանական ներկայացումների միջև: Об алгебраической классификации многомерных рекурсивно перечислимых множеств, выразимых в формальных арифметических системах С. Манукян Аннотация Вводятся и исследуются алгебраические представления многомерных рекурсивно перечислимых множеств, которые выразимы в системах формальной арифметики, основанных на сигнатурах ),,,0(  S , ),,,0( S , ),,0( S , где 1)(  xxS . Устанавливается эквивалентность между алгебраическими и логическими представлениями многомерных рекурсивно перечислимых множеств, выразимых в указанных системах.