Mathematical Problems of Computer Science  45, 67--76, 2016. 

 
 
 

On Transitive Closures of Two-dimensional Strongly 
Positive Arithmetical Sets1 

 
Seda N. Manukian 

 
Institute for Informatics and Automation Problems of NAS RA 

e-mail: zaslav@ipia.sci.am 
 
 

Abstract 
 

The notions of positive and strongly positive arithmetical set are considered in ([1]-[3]). 
It is noted in [3] that the transitive closure of any 2-dimensional strongly positive set is 
primitive recursive. In this article a more strong statement is proved: the transitive closure of 
any 2-dimensional strongly positive set is defined by an arithmetical formula  in the signature 
(0, =, <, 𝑆𝑆), where 𝑆𝑆(𝑥𝑥) = 𝑥𝑥 + 1. Besides, it is proved that the class of two-dimensional 
strongly positive sets and the class of transitive closures of such sets do not coincide with the 
class of two-dimensional arithmetical sets expressible by the formulas in the signature (0, =
, <, 𝑆𝑆). 

Keywords: Positive, Strongly positive, Arithmetical set, Dimension, Signature. 
 
 
 
1. Introduction 
 
The notion of strongly positive arithmetical set is defined and investigated in [3]. It is proved in 
[3] that for any 𝑛𝑛 ≥ 3 there exists a 2𝑛𝑛-dimensional strongly positive set such that its transitive 
closure is not recursive. It is noted in [3] (without a proof) that the transitive closure of any 2-
dimensional strongly positive set is primitive recursive. Below a stronger statement is proved: the 
transitive closure of any 2-dimensional strongly positive set can be defined by an arithmetical 
formula in the signature (0, =, <, 𝑆𝑆), where 𝑆𝑆(𝑥𝑥) = 𝑥𝑥 + 1(see below, Theorem 1). It is proved also 
that the class of the mentioned transitive closures does not coincide with the class of sets 
expressible by arithmetical formulas in the signature (0, =, <, 𝑆𝑆). For example, it is proved that 

1 This work was supported by State Committee of Science, MESS RA in frame of the research project SCS 15T-
1B238. 

67 
 

                                                           

mailto:zaslav@ipia.sci.am


68                           On Transitive Closures of Two-dimensional Strongly Positive Arithmetical Sets 

the set {(𝑥𝑥, 𝑦𝑦)/𝑦𝑦 = 𝑥𝑥 + 2} is not strongly positive and cannot be represented as the transitive 
closure of some strongly positive set (see below, Theorem 2). 
 
 
2. Main Definitions and Results 
 
By 𝑁𝑁 we denote the set of all non-negative integers, 𝑁𝑁 = {0,1,2, … }. By 𝑁𝑁𝑛𝑛, where 𝑛𝑛 ≥ 1, we 
denote the set of 𝑛𝑛-tuples (𝑥𝑥1, 𝑥𝑥2, … 𝑥𝑥𝑛𝑛), where 𝑥𝑥𝑖𝑖 ∈ 𝑁𝑁 for 1 ≤ 𝑖𝑖 ≤ 𝑛𝑛. 
An 𝑛𝑛-dimensional arithmetical set, where 𝑛𝑛 ≥ 1, is defined as any subset of 𝑁𝑁𝑛𝑛. An 𝑛𝑛-dimensional 
arithmetical predicate is defined as a predicate 𝑃𝑃, which is true on some set 𝐴𝐴 ⊆ 𝑁𝑁𝑛𝑛 and false on 
the set 𝑁𝑁𝑛𝑛\𝐴𝐴. If the mentioned relation between 𝐴𝐴 and 𝑃𝑃 takes place, then we say that 𝑃𝑃 is the 
representing predicate for 𝐴𝐴, and 𝐴𝐴 is the set of truth for 𝑃𝑃. 

The notions of primitive recursive set and recursive set are defined in a usual way (see [4]-
[6]). 

The notion of arithmetical formula on a given signature (on the base of logical operations 
&,∨, ⊃, ¬, ∀, ∃) is defined in a usual way, ([2]-[6]). We will consider arithmetical formulas in the 
signatures (0, =, 𝑆𝑆) and (0, =, <, 𝑆𝑆), where 𝑆𝑆(𝑥𝑥) = 𝑥𝑥 + 1 for 𝑥𝑥 ∈ 𝑁𝑁. 

The deductive systems in the signatures (0, =, 𝑆𝑆) and (0, =, <, 𝑆𝑆) are defined as in [6]; we 
will denote these deductive systems correspondingly by DedS and DedL. As it is proved in [6], 
these deductive systems are complete. We say that the formulas 𝐹𝐹 and 𝐺𝐺 in the corresponding 
signatures are equivalent if the formula (𝐹𝐹 ⊃ 𝐺𝐺)&(𝐺𝐺 ⊃ 𝐹𝐹) is deducible in the corresponding 
deductive system. We will consider the formulas in the mentioned signatures up to their 
equivalence. 

The relation “𝑛𝑛-dimesional arithmetical set 𝐴𝐴 is defined by an arithmetical formula 𝐹𝐹” is 
given in a usual way (see [2]-[6]) (in [2] this relation is called as follows: “𝑘𝑘-dimensional 
arithmetical set 𝐴𝐴 is represented (or representable) by a formula 𝐹𝐹"). 

The notion of transitive closure 𝐴𝐴∗ for an arithmetical set 𝐴𝐴 having an even dimension 
2𝑘𝑘 (where 𝑘𝑘 ≥ 1) is defined in a usual way (see, for example, [3], [8]). Let us recall that the 
following statement holds (see [3], lemma 3.4, and [8], p.72): if 𝐴𝐴 is a 2𝑘𝑘-dimensional set, 𝐴𝐴 ⊆
𝑁𝑁2𝑘𝑘, where 𝑘𝑘 ≥ 1, then (𝑥𝑥1, 𝑥𝑥2, … , 𝑥𝑥𝑘𝑘, 𝑦𝑦1, 𝑦𝑦2, … , 𝑦𝑦𝑘𝑘) ∈ 𝐴𝐴∗ if and only if there exists a sequence 
(𝑄𝑄1, 𝑄𝑄2, … , 𝑄𝑄𝑚𝑚) of 𝑘𝑘-tuples such that 𝑚𝑚 ≥ 2, 𝑄𝑄1 = (𝑥𝑥1, 𝑥𝑥2, … , 𝑥𝑥𝑘𝑘), 𝑄𝑄𝑚𝑚 = (𝑦𝑦1, 𝑦𝑦2, … , 𝑦𝑦𝑘𝑘), 
(𝑄𝑄𝑖𝑖, 𝑄𝑄𝑖𝑖+1) ∈ 𝐴𝐴 for 1 ≤ 𝑖𝑖 ≤ 𝑚𝑚 − 1. Below we will say that the sequence (𝑄𝑄1, 𝑄𝑄2, … , 𝑄𝑄𝑚𝑚), having 
the mentioned properties is a sequence establishing the value (𝑄𝑄1, 𝑄𝑄𝑚𝑚) ∈ 𝐴𝐴∗ of the transitive 
closure 𝐴𝐴∗ (or, shortly, ETC-sequence). In what follows we will consider ETC-secuences only 
for the case 𝑘𝑘 = 1. 

The notion of strongly positive arithmetical set is defined as in [3]. Let us recall that an 
𝑚𝑚-dimensional arithmetical set, where 𝑚𝑚 ≥ 1, is said to be strongly positive if it is defined by 
an arithmetical formula 𝐹𝐹 which is constructed by logical operators & and ∨ from subformulas 
having the forms (𝑥𝑥 = 𝑎𝑎) (where 𝑎𝑎 is a constant, 𝑎𝑎 ∈ 𝑁𝑁), 𝑥𝑥 = 𝑦𝑦, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), ¬(𝑥𝑥 = 0), where 𝑥𝑥 
and 𝑦𝑦 are variables. 



S. Manukian                                                                                69 

Theorem 1: The transitive closure of any 2-dimensional strongly positive set can be defined by 
an arithmetical formula in the signature (0, =, <, 𝑆𝑆). 
Theorem 2: The set {(𝑥𝑥, 𝑦𝑦)/ 𝑦𝑦 = 𝑆𝑆(𝑆𝑆(𝑥𝑥))} is not strongly positive and cannot be represented 
as a transitive closure of some strongly positive set. 

 
 

3. Proofs of Theorems 
 

We consider the properties of 2-dimensional strongly positive sets. Let 𝜋𝜋 be any set of such kind. 
By 𝜂𝜂 we denote the representing predicate for 𝜋𝜋. Using the definition of strongly positive set we 
conclude that the predicate 𝜂𝜂 can be expressed by an arithmetical formula 𝐹𝐹 having the form 𝐹𝐹1 ∨
𝐹𝐹2 ∨ … ∨ 𝐹𝐹𝑚𝑚, where any 𝐹𝐹𝑖𝑖 is the conjuction of subformulas having the following forms: 𝑥𝑥 = 𝑎𝑎, 
𝑦𝑦 = 𝑏𝑏, (where 𝑎𝑎 and 𝑏𝑏 are constants, 𝑎𝑎 ∈ 𝑁𝑁, 𝑏𝑏 ∈ 𝑁𝑁), 𝑥𝑥 = 𝑦𝑦, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), 𝑥𝑥 = 𝑆𝑆(𝑦𝑦), ¬(𝑥𝑥 = 0), 
¬(𝑦𝑦 = 0). The predicate expressed by the formula 𝐹𝐹𝑖𝑖 we denote by 𝜂𝜂𝑖𝑖; the set of truth for 𝜂𝜂𝑖𝑖 we 
denote by 𝜋𝜋𝑖𝑖. The following equalities hold: 

𝜂𝜂(𝑥𝑥, 𝑦𝑦) ≡ 𝜂𝜂1(𝑥𝑥, 𝑦𝑦) ∨ 𝜂𝜂2(𝑥𝑥, 𝑦𝑦) ∨ … ∨ 𝜂𝜂𝑚𝑚(𝑥𝑥, 𝑦𝑦); 
𝜋𝜋 = 𝜋𝜋1 ∪ 𝜋𝜋2 ∪ … ∪ 𝜋𝜋𝑚𝑚. 

Clearly, all the predicates 𝜂𝜂, 𝜂𝜂1, 𝜂𝜂2, … , 𝜂𝜂𝑚𝑚, and all the sets 𝜋𝜋, 𝜋𝜋1, 𝜋𝜋2, … , 𝜋𝜋𝑚𝑚 are expressible 
by arithmetical formulas in the signature (0, =, 𝑆𝑆). Let us note that if some 𝐹𝐹𝑖𝑖 includes 
simultaneously some two subformulas of the forms 𝑥𝑥 = 𝑦𝑦, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), 𝑥𝑥 = 𝑆𝑆(𝑦𝑦), then the 
corresponding predicate 𝜂𝜂𝑖𝑖 is identically false, hence, 𝐹𝐹𝑖𝑖 can be deleted from the structure of 𝐹𝐹, 
similarly, 𝐹𝐹𝑖𝑖 can be deleted from the structure of 𝐹𝐹 if it includes subformulas of the forms 𝑥𝑥 = 𝑎𝑎1 
and 𝑥𝑥 = 𝑎𝑎2 where 𝑎𝑎1 ≠ 𝑎𝑎2 or subformulas of the forms 𝑦𝑦 = 𝑏𝑏1 and 𝑦𝑦 = 𝑏𝑏2 where 𝑏𝑏1 ≠ 𝑏𝑏2. 

Let us consider possible forms of the formula 𝐹𝐹𝑖𝑖. We do not consider the cases mentioned 
above when 𝐹𝐹𝑖𝑖 can be deleted from the structure of 𝐹𝐹. 

(Case 1). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑥𝑥 = 𝑎𝑎, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0). 
In this case 𝜋𝜋𝑖𝑖 is either empty, or contains the single pair (𝑎𝑎, 𝑎𝑎 + 1) (for example, 𝜋𝜋𝑖𝑖 is empty if 
𝐹𝐹𝑖𝑖 has the form (𝑥𝑥 = 0 & 𝑦𝑦 = 𝑆𝑆(𝑥𝑥)& ¬(𝑥𝑥 = 0))). 

(Case 2). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑦𝑦 = 𝑏𝑏, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0). 
In this case 𝜋𝜋𝑖𝑖 is either empty or contains the single pair (𝑏𝑏 − 1, 𝑏𝑏), where 𝑏𝑏 > 0. 

(Case 3). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0) (we 
suppose that 𝐹𝐹𝑖𝑖 contains no subformula having one of the forms 𝑥𝑥 = 𝑎𝑎, 𝑦𝑦 = 𝑏𝑏, 𝑥𝑥 = 𝑦𝑦, 𝑥𝑥 = 𝑆𝑆(𝑦𝑦)). 
In this case all pairs of numbers having the form (𝑥𝑥, 𝑥𝑥 + 1), where 𝑥𝑥 > 0, belong to 𝜋𝜋𝑖𝑖. The 
statement (0,1) ∈ 𝜋𝜋𝑖𝑖 is true if and only if the subformula ¬(𝑥𝑥 = 0) is not included in 𝐹𝐹𝑖𝑖. 

(Case 4). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑦𝑦 = 𝑏𝑏, 𝑥𝑥 = 𝑆𝑆(𝑦𝑦), and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0). 
In this case 𝜋𝜋𝑖𝑖 is either empty, or contains the single pair (𝑏𝑏 + 1, 𝑏𝑏). 

(Case 5). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑥𝑥 = 𝑎𝑎, 𝑥𝑥 = 𝑆𝑆(𝑦𝑦), and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0). 
In this case 𝜋𝜋𝑖𝑖 is either empty, or contains the single pair (𝑎𝑎, 𝑎𝑎 − 1), where 𝑎𝑎 > 0. 

(Case 6). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑥𝑥 = 𝑆𝑆(𝑦𝑦), and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0) (we 
suppose that 𝐹𝐹𝑖𝑖 contains no subformulas having one of the forms 𝑥𝑥 = 𝑎𝑎, 𝑦𝑦 = 𝑏𝑏, 𝑥𝑥 = 𝑦𝑦, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥)). 



70                           On Transitive Closures of Two-dimensional Strongly Positive Arithmetical Sets 

In this case all pairs of numbers having the form (𝑥𝑥 + 1, 𝑥𝑥), where 𝑥𝑥 > 0, belong to 𝜋𝜋𝑖𝑖. The 
statement  (1,0) ∈ 𝜋𝜋𝑖𝑖 is true if and only if the subformula ¬(𝑦𝑦 = 0) is not included in 𝐹𝐹𝑖𝑖. 

(Case 7). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑥𝑥 = 𝑎𝑎, 𝑦𝑦 = 𝑏𝑏, and, possibly, 𝑥𝑥 = 𝑦𝑦 ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 =
0). In this case 𝜋𝜋𝑖𝑖 is either empty, or contains the single pair (𝑎𝑎, 𝑏𝑏). 

(Case 8). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑥𝑥 = 𝑎𝑎, 𝑥𝑥 = 𝑦𝑦, and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0). In 
this case 𝜋𝜋𝑖𝑖 is either empty, or contains the single pair (𝑎𝑎, 𝑎𝑎). 

(Case 9). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑦𝑦 = 𝑏𝑏, 𝑥𝑥 = 𝑦𝑦, and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0). In 
this case 𝜋𝜋𝑖𝑖 is either empty, or contains the single pair (𝑏𝑏, 𝑏𝑏). 

(Case 10). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑥𝑥 = 𝑎𝑎, and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0) (we 
suppose that 𝐹𝐹𝑖𝑖 contains no subformulas having one of the forms, 𝑦𝑦 = 𝑏𝑏, 𝑥𝑥 = 𝑦𝑦, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), 𝑥𝑥 =
𝑆𝑆(𝑦𝑦)). In this case 𝜋𝜋𝑖𝑖 is empty when 𝑎𝑎 = 0 and the subformula ¬(𝑥𝑥 = 0) is included in 𝐹𝐹𝑖𝑖. In the 
opposite case 𝜋𝜋𝑖𝑖 contains all pairs (𝑎𝑎, 𝑦𝑦), where y> 0. The statement (𝑎𝑎, 0) ∈ 𝜋𝜋𝑖𝑖  is true (for 𝑎𝑎 >
0) if and only if the subformula ¬(𝑦𝑦 = 0) is not included in 𝐹𝐹𝑖𝑖. 

(Case 11). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑦𝑦 = 𝑏𝑏, and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0) (we 
suppose that 𝐹𝐹𝑖𝑖 contains no subformulas having one of the forms, x= 𝑎𝑎, 𝑥𝑥 = 𝑦𝑦, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), 𝑥𝑥 =
𝑆𝑆(𝑦𝑦)). In this case 𝜋𝜋𝑖𝑖 is empty when 𝑏𝑏 = 0, and the subformula ¬(𝑦𝑦 = 0) is included in 𝐹𝐹𝑖𝑖. In the 
opposite case 𝜋𝜋𝑖𝑖 contains all pairs (𝑥𝑥, 𝑏𝑏), where x> 0. The statement (0, 𝑏𝑏) ∈ 𝜋𝜋𝑖𝑖 is true (for 𝑏𝑏 ≠
0) if and only if the subformula ¬(𝑥𝑥 = 0) is not included in 𝐹𝐹𝑖𝑖. 

(Case 12). 𝐹𝐹𝑖𝑖 contains the subformulas 𝑥𝑥 = 𝑦𝑦, and, possibly, ¬(𝑥𝑥 = 0), ¬(𝑦𝑦 = 0) (we 
suppose that 𝐹𝐹𝑖𝑖 contains no subformulas having one of the forms, x= 𝑎𝑎, y = 𝑏𝑏, 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), 𝑥𝑥 =
𝑆𝑆(𝑦𝑦)). In this case 𝜋𝜋𝑖𝑖 contains all the pairs having the form (𝑥𝑥, 𝑥𝑥), where x > 0. The statement 
(0,0) ∈ 𝜋𝜋𝑖𝑖 is true if and only if the subformulas ¬(𝑥𝑥 = 0) and ¬(𝑦𝑦 = 0) are not included in 𝐹𝐹𝑖𝑖. 

It is easily seen that all the variants of the structure of 𝜋𝜋𝑖𝑖 are exhausted in the cases 1-12. 
Now we will consider the variants of the structure of 𝜋𝜋∗. As it is proved in [3] (see [3], 

Lemma 3.4) the statement (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋∗is true if and only if there exists an ETC-sequence 
(𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑞𝑞1 = 𝑥𝑥, 𝑞𝑞𝑟𝑟 = 𝑦𝑦, (𝑞𝑞𝑖𝑖, 𝑞𝑞𝑖𝑖+1) ∈ 𝜋𝜋 for 1 ≤ 𝑖𝑖 < 𝑟𝑟. Without loss of generality 
we may suppose that any considered ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) where 𝑟𝑟 ≥ 3, satisfies the 
condition 𝑞𝑞𝑖𝑖 ≠ 𝑞𝑞𝑗𝑗 when 𝑖𝑖 ≠ 𝑗𝑗 (otherwise the given ETC-sequence may be replaced by a shorter 
sequence having the same properties). 

Let us consider the number 𝑑𝑑 such that 𝑑𝑑 = 𝑑𝑑1 + 1, where 𝑑𝑑1 is the maximum of the 
numbers 𝑎𝑎 and 𝑏𝑏 in the formulas 𝑥𝑥 = 𝑎𝑎 and 𝑦𝑦 = 𝑏𝑏 included in 𝐹𝐹. If no formula of such forms is 
included in 𝐹𝐹, then we admit 𝑑𝑑 = 3. 

We will use below some classification of pairs (𝑥𝑥, 𝑦𝑦) such that 𝑥𝑥 ∈ 𝑁𝑁, 𝑦𝑦 ∈ 𝑁𝑁. We say that 
(𝑥𝑥, 𝑦𝑦) belongs to the subset 𝑆𝑆1 if 𝑥𝑥 ≤ 𝑑𝑑, 𝑦𝑦 ≤ 𝑑𝑑. In a similar way we define the subsets 𝑆𝑆2, 𝑆𝑆3, 𝑆𝑆4 
as sets of pairs (𝑥𝑥, 𝑦𝑦) such that (𝑥𝑥, 𝑦𝑦) ∈ 𝑆𝑆2 if 𝑥𝑥 > 𝑑𝑑, 𝑦𝑦 ≤ 𝑑𝑑; (𝑥𝑥, 𝑦𝑦) ∈ 𝑆𝑆3 if 𝑥𝑥 ≤ 𝑑𝑑, 𝑦𝑦 > 𝑑𝑑; (𝑥𝑥, 𝑦𝑦) ∈
𝑆𝑆4 if 𝑥𝑥 > 𝑑𝑑, 𝑦𝑦 > 𝑑𝑑. 

The sets 𝑆𝑆1∗, 𝑆𝑆2∗, 𝑆𝑆3∗, 𝑆𝑆4∗ are defined coorrespondingly as 𝑆𝑆1 ∩ 𝜋𝜋∗, 𝑆𝑆2 ∩ 𝜋𝜋∗, 𝑆𝑆3 ∩
𝜋𝜋∗, 𝑆𝑆4 ∩ 𝜋𝜋∗. 

A pair (𝑥𝑥, 𝑦𝑦) is said to be increasing if 𝑥𝑥 < 𝑦𝑦 and decreasing if 𝑥𝑥 > 𝑦𝑦. 
Lemma 3.1:  If the number ℎ satisfies the condition ℎ ≥ 𝑑𝑑, and the pair (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋∗ satisfies the 
conditions 𝑥𝑥 ≤ ℎ, 𝑦𝑦 ≤ ℎ, then there exists an ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) for the value (𝑥𝑥, 𝑦𝑦) ∈
𝜋𝜋∗ such that  𝑞𝑞1 = 𝑥𝑥, 𝑞𝑞𝑟𝑟 = 𝑦𝑦, (𝑞𝑞𝑖𝑖, 𝑞𝑞𝑖𝑖+1) ∈ 𝜋𝜋 for 1 ≤ 𝑖𝑖 < 𝑟𝑟, 𝑞𝑞𝑖𝑖 ≤ ℎ for 1 ≤ 𝑖𝑖 ≤ 𝑟𝑟. 



S. Manukian                                                                                71 

Proof: As it follows from the condition (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋∗, there exists an ETC- sequence 
(𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that  𝑞𝑞1 = 𝑥𝑥, 𝑞𝑞𝑟𝑟 = 𝑦𝑦, (𝑞𝑞𝑖𝑖, 𝑞𝑞𝑖𝑖+1) ∈ 𝜋𝜋 for 1 ≤ 𝑖𝑖 < 𝑟𝑟. If 𝑞𝑞𝑖𝑖 ≤ ℎ for 1 ≤ 𝑖𝑖 ≤ 𝑟𝑟, 
then the statement of Lemma is satisfied. In the opposite case let 𝑘𝑘 be the minimal index in the 
sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑘𝑘 > 1, 𝑞𝑞𝑘𝑘 > ℎ. Let 𝑙𝑙 be the minimal index such that 𝑙𝑙 ≥ 𝑘𝑘, 
𝑞𝑞𝑙𝑙+1 ≤ ℎ. Clearly, any number 𝑞𝑞𝑗𝑗, where 𝑘𝑘 ≤ 𝑗𝑗 ≤ 𝑙𝑙 satisfies the condition 𝑞𝑞𝑗𝑗 > ℎ(note that the 
case 𝑘𝑘 = 𝑙𝑙 is not excluded). The following statements hold: 𝑞𝑞𝑘𝑘−1 ≤ ℎ, 𝑞𝑞𝑙𝑙+1 ≤ ℎ, the pair 
(𝑞𝑞𝑘𝑘−1, 𝑞𝑞𝑘𝑘) is increasing, the pair (𝑞𝑞𝑙𝑙, 𝑞𝑞𝑙𝑙+1) is decreasing. But any increasing pair (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋 such 
that 𝑥𝑥 ≥ ℎ, 𝑦𝑦 ≥ ℎ, 𝑥𝑥 < 𝑦𝑦 should satisfy the conditions of (Case 3) or (Case 10) mentioned above. 
Therefore, either 𝑞𝑞𝑘𝑘−1 = ℎ, 𝑞𝑞𝑘𝑘 = ℎ + 1 (Case 3) or 𝑞𝑞𝑘𝑘−1 = 𝑎𝑎, where 𝑎𝑎 is the number contained in 
a formula 𝑥𝑥 = 𝑎𝑎 included in 𝐹𝐹. Similarly, any decreasing pair (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋 such that 𝑥𝑥 ≥ ℎ, 𝑦𝑦 ≥ ℎ, 
𝑥𝑥 > 𝑦𝑦, satisfies the conditions of (Case 6) or (Case 11) mentioned above. Therefore either 𝑞𝑞𝑙𝑙 =
ℎ + 1, 𝑞𝑞𝑙𝑙+1 = ℎ (Case 6) or 𝑞𝑞𝑙𝑙+1 = 𝑏𝑏, where 𝑏𝑏 is the number contained in a formula 𝑦𝑦 = 𝑏𝑏 
included in 𝐹𝐹 (Case 11). Now if 𝑞𝑞𝑘𝑘−1 = 𝑞𝑞𝑙𝑙+1 = ℎ, 𝑞𝑞𝑘𝑘 = 𝑞𝑞𝑙𝑙 = ℎ + 1, (Case 3, Case 6) then the 
segment (𝑞𝑞𝑘𝑘−1, 𝑞𝑞𝑘𝑘, 𝑞𝑞𝑘𝑘+1, … , 𝑞𝑞𝑙𝑙, 𝑞𝑞𝑙𝑙+1) of the ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) can be replaced by the 
single number 𝑞𝑞𝑘𝑘−1 = 𝑞𝑞𝑙𝑙+1 = ℎ. If 𝑞𝑞𝑘𝑘−1 = 𝑎𝑎, then the mentioned segment can be replaced by the 
segment (𝑎𝑎, 𝑞𝑞𝑙𝑙+1) (Case 10). If 𝑞𝑞𝑙𝑙+1 = 𝑏𝑏, then the mentioned segment can be replaced by the 
segment (𝑞𝑞𝑘𝑘−1, 𝑏𝑏) (Case 11). Clearly the sequence obtained by these replacements is an ETC-
sequence for the value (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋∗. 

Transforming in this way any segment of the sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) containing members 
greater than ℎ, we obtain the ETC-sequence satisfying the conditions of Lemma. This completes 
the proof. 
Corollary 1: There is only finite number of ETC-sequences obtained by the transformations 
described in Lemma 3.1. Indeed, the length of such sequence (without repetitions of members) is 
≤ ℎ + 1, and any member of such sequence is ≤ ℎ. 
Corollary 2: The set 𝑆𝑆1∗ can be defined by arithmetical formula in the signature (0, =, <, 𝑆𝑆) (even 
in (0, =, 𝑆𝑆)). Indeed, applying Corollary 1 to the case when ℎ = 𝑑𝑑, we conclude that the set of 
pairs (𝑥𝑥, 𝑦𝑦) such that 𝑥𝑥 ≤ 𝑑𝑑, 𝑦𝑦 ≤ 𝑑𝑑, (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋∗ is finite, hence, it can be defined by a formula 
having the form 

�(𝑥𝑥 = 𝑥𝑥1)&(𝑦𝑦 = 𝑦𝑦1)� ∨ �(𝑥𝑥 = 𝑥𝑥2)&(𝑦𝑦 = 𝑦𝑦2)� ∨ … ∨ �(𝑥𝑥 = 𝑥𝑥𝑚𝑚)&(𝑦𝑦 = 𝑦𝑦𝑚𝑚)�, 
where all 𝑥𝑥𝑖𝑖 and 𝑦𝑦𝑖𝑖 are constants. If this set is empty, then it can be defined by the formula 
(𝑥𝑥 = 𝑦𝑦)&(𝑥𝑥 = 𝑆𝑆(𝑦𝑦)). 
Note. If 𝑥𝑥 ≤ 𝑑𝑑, 𝑦𝑦 ≤ 𝑑𝑑, then the statement (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋∗ may be tested constructively. The method 
of testing is actually given in Corollary 1. 
Lemma 3.2: If some pair (𝑥𝑥0, 𝑦𝑦0), where 𝑥𝑥0 > 𝑑𝑑, 𝑦𝑦0 ≤ 𝑑𝑑 belongs to 𝜋𝜋∗, then any pair (𝑥𝑥, 𝑦𝑦0), 
where 𝑥𝑥 > 𝑑𝑑, belongs to 𝜋𝜋∗. 
Proof: If some pair (𝑥𝑥0, 𝑦𝑦0) satisfies the conditions of Lemma, then there exists an ETC-sequence 
(𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑞𝑞1 = 𝑥𝑥0, 𝑞𝑞𝑟𝑟 = 𝑦𝑦0, (𝑞𝑞𝑖𝑖, 𝑞𝑞𝑖𝑖+1) ∈ 𝜋𝜋 for 1 ≤ 𝑖𝑖 < 𝑟𝑟. Let 𝑘𝑘 be the minimal 
index in the sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑘𝑘 < 𝑟𝑟, 𝑞𝑞𝑘𝑘+1 ≤ 𝑑𝑑 (the case 𝑘𝑘 = 1 is not excluded). 
Without loss of generality we may suprose that 𝑞𝑞𝑖𝑖 ≤ 𝑑𝑑 for 𝑘𝑘 + 1 ≤ 𝑖𝑖 ≤ 𝑟𝑟 (indeed, in the opposite 
case the segment (𝑞𝑞𝑘𝑘+1, 𝑞𝑞𝑘𝑘+2, … , 𝑞𝑞𝑟𝑟) can be transformed by the method described in the proof of 
Lemma 3.1). 



72                           On Transitive Closures of Two-dimensional Strongly Positive Arithmetical Sets 

The pair (𝑞𝑞𝑘𝑘, 𝑞𝑞𝑘𝑘+1) is decreasing, hence, either 𝑞𝑞𝑘𝑘+1 = 𝑏𝑏, where 𝑏𝑏 is the number in a formula 
𝑦𝑦 = 𝑏𝑏 included in 𝐹𝐹, (Case 11 considered above), or 𝑞𝑞𝑘𝑘+1 = 𝑞𝑞𝑘𝑘 − 1 (Case 6 considered above). 
Now the ETC-sequence for the pair (𝑥𝑥, 𝑦𝑦0) where 𝑥𝑥 > 𝑑𝑑 is obtained from the sequence 
(𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) as follows: if 𝑞𝑞𝑘𝑘+1 = 𝑏𝑏, then the segment (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑘𝑘+1) is replaced by the 
segment (𝑥𝑥, 𝑞𝑞𝑘𝑘+1) (see Case 11); if 𝑞𝑞𝑘𝑘 = 𝑞𝑞𝑘𝑘+1 + 1, then any pair (𝑥𝑥 + 1, 𝑥𝑥), where 𝑥𝑥 > 0, belongs 
to 𝜋𝜋 (see Case 6) hence, we can obtain the required ETC-sequence replacing in the sequence 
(𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) the segment (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑘𝑘+1) by the segment (x, x – 1, … , 𝑞𝑞𝑘𝑘+1 + 1, 𝑞𝑞𝑘𝑘+1). It is 
easily seen that the sequence obtained by the mentioned replacements is an ETC-sequence for the 
value (𝑥𝑥, 𝑦𝑦0) ∈ 𝜋𝜋∗. This complets the proof. 
Corollary: The set 𝑆𝑆2∗ can be defined by an arithmetical formula in the signature (0, =, <, 𝑆𝑆). 
Indeed, applying Lemma 3.1 and its corollaries to the case when ℎ = 𝑑𝑑 + 1, we obtain the 
complete list of pairs (𝑥𝑥, 𝑦𝑦) ∈ 𝜋𝜋∗ such that 𝑥𝑥 ≤ 𝑑𝑑 + 1, 𝑦𝑦 ≤ 𝑑𝑑 + 1. In particular we obtain the 
complete list of pairs having the property (𝑑𝑑 + 1, 𝑦𝑦0) ∈ 𝑆𝑆2∗, where 𝑦𝑦0 ≤ 𝑑𝑑. Using Lemma 3.2 we 
conclude that any pair (𝑑𝑑 + 1, 𝑦𝑦0) ∈ 𝑆𝑆2∗ where 𝑦𝑦0 ≤ 𝑑𝑑 generates the set {(𝑥𝑥, 𝑦𝑦)/(𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 =
𝑦𝑦0)}, contained in 𝑆𝑆2∗, so the set 𝑆𝑆2∗ is the union of sets having this form for all 𝑦𝑦0 ≤ 𝑑𝑑 such that 
(𝑑𝑑 + 1, 𝑦𝑦0) ∈ 𝑆𝑆2∗. But any set {(𝑥𝑥, 𝑦𝑦)/(𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 = 𝑦𝑦0)} is defined by the formula (𝑥𝑥 >
𝑑𝑑)&(𝑦𝑦 = 𝑦𝑦0), so the set 𝑆𝑆2∗ is defined by the disjunction of these formulas. This completes the 
proof. 
Lemma 3.3: If some pair (𝑥𝑥0, 𝑦𝑦0), where 𝑥𝑥0 ≤ 𝑑𝑑, 𝑦𝑦0 > 𝑑𝑑, belongs to 𝜋𝜋∗, then any pair (𝑥𝑥0, 𝑦𝑦), 
where 𝑦𝑦 > 𝑑𝑑 belongs to 𝜋𝜋∗. 

The proof is similar to that of Lemma 3.2. We use the ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such 
that 𝑞𝑞1 = 𝑥𝑥0, 𝑞𝑞𝑟𝑟 = 𝑦𝑦0, (𝑞𝑞𝑖𝑖, 𝑞𝑞𝑖𝑖+1) ∈ 𝜋𝜋 for 1 ≤ 𝑖𝑖 < 𝑟𝑟. Let 𝑙𝑙 be the maximal index in the sequence 
(𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑞𝑞𝑙𝑙 ≤ 𝑑𝑑. Without loss of generality we may suppose that 𝑞𝑞𝑖𝑖 ≤ 𝑑𝑑 when 1 ≤
𝑖𝑖 ≤ 𝑙𝑙 (otherwise the segment (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑙𝑙) may be transformed by the method used in the proof 
of Lemma 3.1). 

The pair (𝑞𝑞𝑙𝑙, 𝑞𝑞𝑙𝑙+1) is increasing, therefore either 𝑞𝑞𝑙𝑙 = 𝑎𝑎, where 𝑎𝑎 is the number in a formula 
𝑥𝑥 = 𝑎𝑎 included in 𝐹𝐹 (Case 10) or 𝑞𝑞𝑙𝑙+1 = 𝑞𝑞𝑙𝑙 + 1 (Case 3). The ETC-sequence for establishing the 
statement (𝑥𝑥0, 𝑦𝑦) ∈ 𝜋𝜋∗ (where 𝑦𝑦 > 𝑑𝑑) is obtained from the sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) by the 
following replasements: either the segment (𝑞𝑞𝑙𝑙, 𝑞𝑞𝑙𝑙+1, … , 𝑞𝑞𝑟𝑟) is replaced by the segment (𝑎𝑎, 𝑦𝑦) 
(Case 10), or this segment is replased by the segment (𝑞𝑞𝑙𝑙, 𝑞𝑞𝑙𝑙 + 1, … , 𝑦𝑦 − 1, 𝑦𝑦) (Case 3). This 
completes the proof. 
Corollary: The set 𝑆𝑆3∗ can be defined by an arithmetical formula in the signature (0, =, <, 𝑆𝑆).  

The proof is similar to the proof of corollary of Lemma 3.2. 
In what follows we will say that a formula having the form 𝑦𝑦 = 𝑆𝑆(𝑥𝑥), 𝑥𝑥 = 𝑆𝑆(𝑦𝑦), or 𝑥𝑥 = 𝑦𝑦 is 

contained in a special way in some 𝐹𝐹𝑖𝑖 if this formula is contained in 𝐹𝐹𝑖𝑖 and the conditions 
described correspondingly in (Case 3), (Case 6) or (Case 12) mentioned above are satisfied. 
Lemma 3.4: If the formula 𝑦𝑦 = 𝑆𝑆(𝑥𝑥) is contained in a special way in some 𝐹𝐹𝑖𝑖 then any pair (𝑥𝑥, 𝑦𝑦) 
such that 𝑥𝑥 < 𝑦𝑦, 𝑥𝑥 > 0, belongs to 𝜋𝜋∗. 

Indeed, for establishing this statement it is sufficient to consider the ETC-sequence (𝑥𝑥, 𝑥𝑥 +
1, … , 𝑦𝑦 − 1, 𝑦𝑦). 
Lemma 3.5: If the formula 𝑥𝑥 = 𝑆𝑆(𝑦𝑦) is contained in a special way in some 𝐹𝐹𝑖𝑖, then any pair (𝑥𝑥, 𝑦𝑦) 
such that 𝑥𝑥 > 𝑦𝑦, 𝑦𝑦 > 0 belongs to 𝜋𝜋∗. 



S. Manukian                                                                                73 

For establishing this statement it is sufficient to consider the ETC-sequence (𝑥𝑥, 𝑥𝑥 −
1, … , 𝑦𝑦 − 1, 𝑦𝑦). 
Lemma 3.6: If the formula 𝑦𝑦 = 𝑆𝑆(𝑥𝑥) is contained in a special way in some 𝐹𝐹𝑖𝑖, and the formula 
𝑥𝑥 = 𝑆𝑆(𝑦𝑦) is contained in a special way in some 𝐹𝐹𝑗𝑗, where 𝑖𝑖 ≠ 𝑗𝑗, then any pair (𝑥𝑥, 𝑦𝑦), where 𝑥𝑥 >
0, 𝑦𝑦 > 0 belongs to 𝜋𝜋∗. 

For establishing this statement it is sufficient to consider the ETC-sequence (𝑥𝑥, 𝑥𝑥 +
1, … , 𝑧𝑧, … , 𝑦𝑦 − 1, 𝑦𝑦), where 𝑧𝑧 = max

 
(𝑥𝑥, 𝑦𝑦) + 1. 

Lemma 3.7: The set 𝑆𝑆4∗ can be defined by an arithmetical formula in the signature (0, =, <, 𝑆𝑆). 
Proof: If the set 𝑆𝑆4∗is empty, then it is defined, for example, by the formula (𝑥𝑥 = 𝑦𝑦)&(𝑦𝑦 = 𝑆𝑆(𝑥𝑥)). 
Otherwise, there exists a pair (𝑥𝑥0, 𝑦𝑦0) ∈ 𝑆𝑆4∗, that is 𝑥𝑥0 > 𝑑𝑑, 𝑦𝑦0 > 𝑑𝑑, (𝑥𝑥0, 𝑦𝑦0) ∈ 𝜋𝜋∗. Hence, there 
exists an ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑞𝑞1 = 𝑥𝑥0, 𝑞𝑞𝑟𝑟 = 𝑦𝑦0, (𝑞𝑞𝑖𝑖, 𝑞𝑞𝑖𝑖+1) ∈ 𝜋𝜋 for 1 ≤ 𝑖𝑖 < 𝑟𝑟. 
We will distinguish two cases: 

(𝛼𝛼) There exists such 𝑖𝑖 that 1 ≤ 𝑖𝑖 ≤ 𝑟𝑟, 𝑞𝑞𝑖𝑖 ≤ 𝑑𝑑. 
(𝛽𝛽) 𝑞𝑞𝑖𝑖 > 𝑑𝑑 for any 𝑖𝑖, where 1 ≤ 𝑖𝑖 ≤ 𝑟𝑟. 
Let us consider the case (𝛼𝛼).We denote the number 𝑞𝑞𝑖𝑖 such that 𝑞𝑞𝑖𝑖 ≤ 𝑑𝑑 by 𝑧𝑧. The pair (𝑥𝑥0, 𝑧𝑧), 

where 𝑥𝑥0 > 𝑑𝑑 belongs to 𝜋𝜋∗, therefore, using Lemma 3.2 we conclude that any pair (𝑥𝑥, 𝑧𝑧), where 
𝑥𝑥 > 𝑑𝑑, belongs to 𝜋𝜋∗. The pair (𝑧𝑧, 𝑦𝑦0), where 𝑦𝑦0 > 𝑑𝑑, belongs to 𝜋𝜋∗, therefore, using Lemma 3.3 
we conclude that any pair (𝑧𝑧, 𝑦𝑦), where 𝑦𝑦 > 𝑑𝑑 belongs to 𝜋𝜋∗. Hence, any pair (𝑥𝑥, 𝑦𝑦), where 𝑥𝑥 > 𝑑𝑑, 
𝑦𝑦 > 𝑑𝑑, belongs to 𝜋𝜋∗. 

So in the case (𝛼𝛼) the set 𝑆𝑆4∗ is defined by the formula (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑). 
Let us note that similar conclusion concerning the set 𝑆𝑆4∗ can be made if there exists any 

ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑞𝑞1 > 𝑑𝑑, 𝑞𝑞𝑟𝑟 > 𝑑𝑑 and 𝑞𝑞𝑖𝑖 ≤ 𝑑𝑑 for some 𝑖𝑖, 1 < 𝑖𝑖 < 𝑟𝑟. 
Now let us consider the case (𝛽𝛽). We will investigate the properties of all ETC-sequences 

(𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) such that 𝑞𝑞𝑖𝑖 > 𝑑𝑑 for 1 ≤ 𝑖𝑖 ≤ 𝑟𝑟, and (𝑞𝑞𝑖𝑖, 𝑞𝑞𝑖𝑖+1) ∈ 𝜋𝜋 for 1 ≤ 𝑖𝑖 < 𝑟𝑟. We distingmish 
the following subcases: (𝛽𝛽1), (𝛽𝛽2), (𝛽𝛽3), (𝛽𝛽4). 

(𝛽𝛽1) In some ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) of the mentioned kind there exists an index 𝑖𝑖 
such that 1 ≤ 𝑖𝑖 < 𝑟𝑟, 𝑞𝑞𝑖𝑖+1 = 𝑞𝑞𝑖𝑖 + 1, but there is no ETC-sequence of the mentioned kind 
containing an index 𝑗𝑗 such that 𝑞𝑞𝑗𝑗+1 = 𝑞𝑞𝑗𝑗 − 1. 

(𝛽𝛽2) In some ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) of the mentioned kind there exists an index 𝑖𝑖 
such that 1 ≤ 𝑖𝑖 < 𝑟𝑟, 𝑞𝑞𝑖𝑖+1 = 𝑞𝑞𝑖𝑖 − 1, but there is no ETC-sequence of the mentioned kind 
containing an index 𝑗𝑗 such that 𝑞𝑞𝑗𝑗+1 = 𝑞𝑞𝑗𝑗 + 1. 

(𝛽𝛽3) In some ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑟𝑟) of the mentioned kind there exists an index 𝑖𝑖 
such that 1 ≤ 𝑖𝑖 < 𝑟𝑟, 𝑞𝑞𝑖𝑖+1 = 𝑞𝑞𝑖𝑖 + 1; besides, in some ETC-sequence (𝑞𝑞1, 𝑞𝑞2, … , 𝑞𝑞𝑡𝑡) of the 
mentioned kind there exists an index 𝑗𝑗 such that 1 ≤ 𝑗𝑗 < 𝑡𝑡, 𝑞𝑞𝑗𝑗+1 = 𝑞𝑞𝑗𝑗 − 1. 

(𝛽𝛽4) There is no ETC-sequence of the mentioned kind satisfying the conditions described in 
the subcases (𝛽𝛽1)-( 𝛽𝛽3). 

Clearly, the subcase (𝛽𝛽1) takes place if some 𝐹𝐹𝑖𝑖 in the structure of 𝐹𝐹 has the form (𝑦𝑦 = 𝑆𝑆(𝑥𝑥)), 
but there is no 𝐹𝐹𝑗𝑗 having the form (𝑥𝑥 = 𝑆𝑆(𝑦𝑦)). Similarly, the subcase (𝛽𝛽2) takes place if some 𝐹𝐹𝑖𝑖 in 
the structure of 𝐹𝐹 has the form (𝑥𝑥 = 𝑆𝑆(𝑦𝑦)), but there is no 𝐹𝐹𝑗𝑗 having the form (𝑦𝑦 = 𝑆𝑆(𝑥𝑥)). The 
subcase (𝛽𝛽3) takes place if some 𝐹𝐹𝑖𝑖 and 𝐹𝐹𝑗𝑗 in the structure of 𝐹𝐹 have the forms, correspondingly 



74                           On Transitive Closures of Two-dimensional Strongly Positive Arithmetical Sets 

(𝑦𝑦 = 𝑆𝑆(𝑥𝑥)) and (𝑥𝑥 = 𝑆𝑆(𝑦𝑦)). The subcase (𝛽𝛽4) takes place if the formula 𝐹𝐹 contains no 𝐹𝐹𝑖𝑖 having 
one of the mentioned forms. 

It is easily seen that in the subcase (𝛽𝛽1) the set 𝑆𝑆4∗ is defined by the formula 
(𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 < 𝑦𝑦) or by the formula (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 ≤ 𝑦𝑦) (see Lemma 3.4). In 
the subcase (𝛽𝛽2) the set 𝑆𝑆4∗ is defined by the formula (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 > 𝑦𝑦) or by the 
formula (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 ≥ 𝑦𝑦) (see Lemma 3.5). Let us note that the inequalities 𝑥𝑥 ≤ 𝑦𝑦 and 
𝑥𝑥 ≥ 𝑦𝑦 are obtained in the subcases (𝛽𝛽1) and (𝛽𝛽2) if some 𝐹𝐹𝑖𝑖 in the structure of 𝐹𝐹 has the form 𝑥𝑥 =
𝑦𝑦 (see Case 12 mentioned above). In the subcase (𝛽𝛽3) the set 𝑆𝑆4∗ is defined by the formula 
(𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑) (see Lemma 3.6). In the subcase (𝛽𝛽4) the set 𝑆𝑆4∗ is either empty or is defined 
by the formula (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 = 𝑦𝑦). This completes the proof. 

Proof of Theorem 1. 
As it is established in Lemmas 3.1-3.7, the sets  𝑆𝑆1∗,  𝑆𝑆2∗,  𝑆𝑆3∗,  𝑆𝑆4∗, are defined by formulas 

in the signature {0, =, <, 𝑆𝑆}. Hence, the set 𝜋𝜋∗ = 𝑆𝑆1∗ ∪ 𝑆𝑆2∗ ∪ 𝑆𝑆3∗ ∪ 𝑆𝑆4∗ is defined by the 
disjunction of the mentioned formulas. This completes the proof. 

Proof of Theorem 2. 
Let 𝐴𝐴 be the set {(𝑥𝑥, 𝑦𝑦)/𝑦𝑦 = 𝑆𝑆(𝑆𝑆(𝑥𝑥))}, let 𝐵𝐵 be any 2-dimensional strongly positive set, let 

𝐵𝐵∗ be the transitive closure of 𝐵𝐵. We define the number 𝑑𝑑 for the set 𝐵𝐵 by the method given above. 
By 𝐷𝐷 we denote the set {(𝑥𝑥, 𝑦𝑦)/(𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)}. Using Lemma 3.7 we conclude that the set 
𝐵𝐵∗ ∩ 𝐷𝐷 either is empty or is defined by one of the following formulas: (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 >
𝑦𝑦), (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 < 𝑦𝑦), (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 = 𝑦𝑦), or by the disjunction of some of 
these formulas. Similarly, using Lemmas 3.4-3.6 we conclude that the set 𝐵𝐵 ∩ 𝐷𝐷 either is empty 
or is defined by one of the following formulas: (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑦𝑦 = 𝑆𝑆(𝑥𝑥)), (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 >
𝑑𝑑)&(𝑥𝑥 = 𝑆𝑆(𝑦𝑦)), (𝑥𝑥 > 𝑑𝑑)&(𝑦𝑦 > 𝑑𝑑)&(𝑥𝑥 = 𝑦𝑦), or by the disjuction of some of these formulas. 
Therefore, in all the cases the set 𝐴𝐴 ∩ 𝐷𝐷 is different form 𝐵𝐵 ∩ 𝐷𝐷 and 𝐵𝐵∗ ∩ 𝐷𝐷. Hence, 𝐴𝐴 ≠ 𝐵𝐵 and 
𝐴𝐴 ≠ 𝐵𝐵∗. This completes the proof. 

Note 1. The statement of Theorem 2 is true also for any set defined by the formula 𝑦𝑦 =
𝑆𝑆(𝑆𝑆 … 𝑆𝑆(𝑥𝑥) … ), where the symbol 𝑆𝑆 is repeated 𝑛𝑛 ≥ 2 times. The proof is similar to that of 
Theorem 2. 

Note 2. Obviously, any set defined by a formula in the signature (0, =, <, 𝑆𝑆) is primitive 
recursive, however, the reverse is not true (for example, the set of even numbers is primitive 
recurcive, but it cannot be defined by arithmetical formula in the signature (0, =, <, 𝑆𝑆) (see [6])). 
So the statement of Theorem 1 is stronger than the statement of Theorem 2 in [3]. 
 
 
References 
 

[1] S. N. Manukian, “On the representation of recursively enumerable sets in weak 
arithmetics”, Transactions of the IIAP of NAS of 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 of RA, Mathematical Problems of Computer Science, vol. 41, pp. 103-113, 20014. 



S. Manukian                                                                                75 

[3] S. N.Manukian, “On strongly positive multidimensional arithmetical sets”, Transactions 
of the IIAP of NAS of RA, Mathematical Problems of Computer Science, vol. 43, pp. 32-
41, 2015. 

[4] S. C. Kleene,  Introduction to Metamathematics,  D.Van Nostrand Comp., Inc., New York 
– Toronto, 1952. 

[5] E. Mendelson, Introduction to Mathematical Logic, D.Van Nostrand Comp., Inc., 
Princeton – Toronto – New York – London, 1964. 

[6] H. B. Enderton, A Mathematical Introduction to Logic, 2nd edition, San Diego, Harcourt, 
Academic Press, 2001. 

[7] 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. 

[8] A. I. Maltsev,  Algorithms and Recursive Functions, 2nd edition (in Russian), M.,”Nauka”, 
1986. 

 

Submitted 04.10.2015, accepted 15.01.2016 

 
Խիստ պոզիտիվ երկչափ թվաբանական բազմությունների 

տրանզիտիվ փակումների մասին 
 

Ս. Մանուկյան 
 

Ամփոփում 
 

Պոզիտիվ և խիստ պոզիտիվ թվաբանական բազմությունների գաղափարները 
սահմանված են [1]-[3] հոդվածներում: [3] հոդվածում նշված է, որ ցանկացած երկչափ 
խիստ պոզիտիվ բազմության տրանզիտիվ փակումը պարզագույն անդրադարձ է: Այս 
հոդվածում ապացուցվում է ավելի ուժեղ պնդում, այսինքն՝ ցանկացած երկչափ խիստ 
պոզիտիվ բազմության տրանզիտիվ փակումը նկարագրվում է թվաբանական 
բանաձևի միջոցով (0, =, <, 𝑆𝑆) սիգնատուրայում (որտեղ 𝑆𝑆(𝑥𝑥) = 𝑥𝑥 + 1): Բացի դրանից 
ապացուցվում է, որ երկչափ խիստ պոզիտիվ բազմությունների դասը և այդ 
բազմությունների տրանզիտիվ փակումների դասը չեն համընկնում (0, =, <, 𝑆𝑆) 
սիգնատուրայում արտահայտվող թվաբանական բազմությունների դասի հետ: 

 
 



76                           On Transitive Closures of Two-dimensional Strongly Positive Arithmetical Sets 

О транзитивных замыканиях строго позитивных арифметических 
множеств размерности 2 

 
С. Манукян 

 
Аннотация 

 
Понятия позитивного и строго позитивного множества рассматриваются в [1]-[3]. В 

[3] указано, что транзитивное замыкание всякого строго позитивного множества 
размерности 2 примитивно рекурсивно. В этой статье доказывается более сильное 
утверждение: транзитивное замыкание всякого строго позитивного множества 
размерности 2 задается арифметической формулой в сигнатуре (0, =, <, 𝑆𝑆), где 𝑆𝑆(𝑥𝑥) =
𝑥𝑥 + 1. Доказывается также, что класс строго позитивных множеств размерности 2 и класс 
транзитивных замыканий таких множеств не совпадают с классом арифметических 
множеств размерности 2, задаваемых посредством арифметических формул в сигнатуре 
(0, =, <, 𝑆𝑆).