Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 50, 52--55, 2018. On Some Properties of Positive and Strongly Positive Arithmetical Sets 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 sets are defined as in [1]-[4] (see, for example, [2], p. 33). It is proved (Theorem 1) that any arithmetical set is positive if and only if it can be defined by an arithmetical formula containing only logical operations ∃, &,∨ and the elementary subformulas having the forms 𝑥𝑥 = 0 or 𝑥𝑥 = 𝑦𝑦 + 1, where 𝑥𝑥 and 𝑦𝑦 are variables. Corollary: the logical description of the class of positive sets is obtained from the logical description of the class of strongly positive sets replacing the list of operations &,∨ by the list ∃, &,∨. It is proved (Theorem 2) that for any one-dimensional recursively enumerable set 𝑀𝑀 there exists 6-dimensional strongly positive set 𝐻𝐻 such that 𝑥𝑥 ∈ 𝑀𝑀 holds if and only if (1, 2𝑥𝑥, 0, 0, 1, 0) ∈ 𝐻𝐻+, where 𝐻𝐻+ is the transitive closure of 𝐻𝐻. Keywords: Positive set, Strongly positive set, Transitive closure, Signature. 1. Introduction In this article some simplified forms are considered for the representation of any positive arithmetical set (see below, Theorem 1). The method used in [2] for the construction of a creative set on the base of the transitive closure of some strongly positive set is generalized below, and it is shown that similar method gives the possibility for obtaining any one-dimensional recursively enumerable set on the base of the transitive closure of some strongly positive set (Theorem 2). The formulations of Theorem 1 and its corollary are given (without proof) in [4]. 52 mailto:zaslav@ipia.sci.am S. Manukian 53 2. Main Notions and Definitions By 𝑁𝑁 we denote the set of all non-negative integers {0,1,2, … }. By 𝑁𝑁𝑛𝑛, where 𝑛𝑛 ≥ 1, we denote the set of all 𝑛𝑛-tuples (𝑥𝑥1, 𝑥𝑥2, … , 𝑥𝑥𝑛𝑛), where 𝑥𝑥𝑖𝑖 ∈ 𝑁𝑁 for 1 ≤ 𝑖𝑖 ≤ 𝑛𝑛. The 𝑛𝑛-dimensional arithmetical set, where 𝑛𝑛 ≥ 1 is defined as any subset of 𝑁𝑁𝑛𝑛. The 𝑛𝑛-dimensional arithmetical predicate is defined in the usual way as a predicate, which is true on some set 𝐴𝐴 ⊆ 𝑁𝑁𝑛𝑛 and false on the set 𝑁𝑁𝑛𝑛|𝐴𝐴 (cf. [5]-[6]). The notions of general recursive function, partial recursive function and all the notions connected with them are defined as in ([5]-[6]). Signature is defined as usual, as any set of predicate symbols, functional symbols and symbols of constants. The notion of arithmetical formula in a given signature is defined in the usual way (see, for example, [2]); we will consider predicate formulas in the signature (0, =, 𝑆𝑆), where 𝑆𝑆(𝑥𝑥) = 𝑥𝑥 + 1 for 𝑥𝑥 ∈ 𝑁𝑁. The expressions 𝑆𝑆(𝑆𝑆(… 𝑆𝑆(𝑥𝑥) … )) and 𝑆𝑆(𝑆𝑆(… 𝑆𝑆(0) … )), where the symbol 𝑆𝑆 is repeated 𝑛𝑛 times, we will shortly denote as 𝑆𝑆𝑛𝑛(𝑥𝑥) and 𝑆𝑆𝑛𝑛(0) (cf.[2]). The deductive arithmetical system in the signature (0, =, 𝑆𝑆) is defined as in [7]; it is proved in [7] that this system is complete. All auxiliary notions connected with the notions mentioned above are defined as in [2]. For the convenience of the reader, let us recall the definitions of positive and strongly arithmetical set. An arithmetical set is said to be positive if it can be defined by an arithmetical formula in the signature (0, =, 𝑆𝑆) such that it contains no other symbols of logical operations besides ∃, &,∨, ¬ and has the following property: all the symbols ¬ relate to the elementary subformulas containing no more than one variable. An arithmetical set is said to be strongly positive if it can be defined by an arithmetical formula in the signature (0, =, 𝑆𝑆) such that it contains no other logical operations besides & and ∨ relating to the formulas having one of the forms 𝑥𝑥 = 𝑎𝑎, 𝑥𝑥 = 𝑦𝑦, 𝑥𝑥 = 𝑆𝑆(𝑦𝑦), ¬ (𝑥𝑥 = 0), where 𝑥𝑥 and 𝑦𝑦 are variables and 𝑎𝑎 is a constant. The transitive closure of a set having an even dimension is defined in the usual way (see, for example, [2], p.34). 3. Main Theorems Theorem 1: Any arithmetical set is positive if and only if it can be defined by an arithmetical formula, which contains only logical operations ∃, &,∨ and such that all elementary subformulas in it have the form 𝑥𝑥 = 0 or 𝑥𝑥 = 𝑆𝑆(𝑦𝑦). Proof. Let 𝐹𝐹 be any arithmetical formula defining a positive arithmetical set. Any subformula of 𝐹𝐹 containing the negation ¬ may be reduced to the form ¬ (𝑥𝑥 = 𝑆𝑆𝑛𝑛(0)) or ¬ (𝑆𝑆𝑛𝑛(𝑥𝑥) = 0). However, the formula ¬ (𝑥𝑥 = 0) is equivalent to ∃𝑧𝑧(𝑥𝑥 = 𝑆𝑆(𝑧𝑧)) and the formula ¬ (𝑥𝑥 = 𝑆𝑆𝑛𝑛(0)) when 𝑛𝑛 > 0 is equivalent to the formula (𝑥𝑥 = 0) ∨ �𝑥𝑥 = 𝑆𝑆(0)� ∨ … ∨ (𝑥𝑥 = 𝑆𝑆𝑛𝑛−1(0)) ∨ ∃𝑧𝑧(𝑥𝑥 = 𝑆𝑆𝑛𝑛+1(𝑧𝑧)). The formula ¬ (𝑆𝑆𝑛𝑛(𝑥𝑥) = 0) is equivalent to ∃𝑧𝑧(𝑥𝑥 = 𝑆𝑆(𝑧𝑧)) when 𝑛𝑛 = 0 and is equivalent to 𝑥𝑥 = 𝑥𝑥 when 𝑛𝑛 > 0. So, in all cases there exists a formula 𝐹𝐹1, which is equivalent to 𝐹𝐹 and does not contain the symbol ¬ . Any elementary subformula of 𝐹𝐹1 may be reduced to the form (𝑥𝑥 = 𝑆𝑆𝑛𝑛(𝑦𝑦)), where 𝑥𝑥 and 𝑦𝑦 are variables (or, may be, constants). But any formula having the form (𝑥𝑥 = 𝑆𝑆𝑛𝑛+1(𝑦𝑦)) may be transformed into ∃𝑧𝑧(𝑥𝑥 = 𝑆𝑆𝑛𝑛(𝑧𝑧)&(𝑧𝑧 = 𝑆𝑆(𝑦𝑦))). Using a similar transformation, we may reduce the On Some Properties of Positive and Strongly Positive Arithmetical Sets 54 formula 𝑥𝑥 = 𝑆𝑆𝑛𝑛(𝑦𝑦) to the form in which all the elementary subformulas have the form 𝑢𝑢 = 0 or 𝑣𝑣 = 𝑆𝑆(𝑤𝑤), where 𝑢𝑢, 𝑣𝑣, 𝑤𝑤 are variables. This completes the proof. Corollary 1: The definition of a positive set is obtained when we replace the list of operations &,∨ with the list ∃, &,∨ in the definition of a strongly positive set. The proof is easily obtained from the considerations given in the proof of Theorem 1. Theorem 2: For any one-dimensional recursively enumerable set 𝑀𝑀 there exists a 6-dimensional strongly positive set 𝐻𝐻 such that 𝑥𝑥 ∈ 𝑀𝑀 takes place if and only if (1, 2𝑥𝑥, 0, 0, 1, 0) ∈ 𝐻𝐻+, where 𝐻𝐻+ is the transitive closure of 𝐻𝐻. Proof. Let 𝑀𝑀 be any one-dimensional recursively enumerable set. Clearly, there exists a partial recursive function 𝑓𝑓(𝑥𝑥) such that 𝑓𝑓(𝑥𝑥) = 0 when 𝑥𝑥 ∈ 𝑀𝑀 and 𝑓𝑓(𝑥𝑥) is undefined when 𝑥𝑥 ∉ 𝑀𝑀. We will use the notions of Ω-algorithm (see [2], pp. 34-35) and Γ2-algorithm (see [2], pp. 35-36) defined in [2]. Below we will use the notion of Γ𝑛𝑛-algorithm only in the case when 𝑛𝑛 = 2. Using Theorem 3 in [2] (see [2], p. 35 and also [6], pp. 312-315) and [8], we conclude that there exists an Ω-algorithm 𝜃𝜃 such that it transforms the state (1, 22 𝑥𝑥 ) into the state (0, 2), when 𝑥𝑥 ∈ 𝑀𝑀, and is not applicable to the state (1, 22 𝑥𝑥 ) when 𝑥𝑥 ∉ 𝑀𝑀. Now, using Lemma 3.1, Lemma 3.2 in [2] (see [2], pp. 36-37) we obtain that there exists a Γ2-algorithm 𝜓𝜓 such that it transforms the state (1, 2𝑥𝑥, 0) into the state (0, 1, 0) when 𝑥𝑥 ∈ 𝑀𝑀 and is not applicable to the state (1, 2𝑥𝑥, 0) when 𝑥𝑥 ∉ 𝑀𝑀. Let us consider the “step-describing set” (shortly, “SD-set”) 𝐻𝐻 for the Γ2-algorithm 𝜓𝜓 (the notion of SD-set for Γ2-algorithm is given in [2], p. 38). As it is proved in [2], the set 𝐻𝐻 is strongly positive (the proof is actually given in [2], pp. 37-38; see also [2], Lemma 3.3, p. 39). Now, if we denote the transitive closure of 𝐻𝐻 by 𝐻𝐻+, then it is easily seen that 𝑥𝑥 ∈ 𝑀𝑀 takes place if and only if (1, 2𝑥𝑥, 0, 0, 1, 0) ∈ 𝐻𝐻+. This completes the proof. References [1] 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. [2] S. N. Manukian, “On strongly positive multidimensional arithmetical sets”, Transactions of the IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 43, pp. 32-41, 2015. [3] S. N. Manukian, “On transitive closures of two-dimensional strongly positive arithmetical sets”, Transactions of the IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 45, pp. 67-76, 2016. [4] S. N. Manukian, “On the structure of positive and strongly positive arithmetical sets”, Proceedings of the International Conference and Information Technologies, CSIT-17, Yerevan, Armenia, p. 33, 2017. [5] S. C. Kleene, Introduction to Metamathematics, D. van Nostrand comp., Inc. New York- Toronto, 1952. [6] A. I. Malcev, Algorithms and Recursive Functions, 2nd edition (in Russian), M., “Nauka”, 1986. [7] H. B. Enderton, A Mathematical Introduction to Logic, 2nd edition, San Diego, Harcourt, Academic Press, 2001. [8] M. L. Minsky, “Recursive Unsolvability of Post’s Problem of “Tag and Other Topics in Theory of Turing Machines”, Ann. Math., vol. 74, pp. 437-455, 1961. S. Manukian 55 Submitted 20.07.2018, accepted 02.12.2018. Պոզիտիվ և խիստ պոզիտիվ թվաբանական բազմությունների որոշ հատկությունների մասին Ս. Մանուկյան Ամփոփում Պոզիտիվ և խիստ պոզիտիվ թվաբանական բազմությունների գաղափարները սահմանվում են նույն ձևով, ինչպես [1]-[4]-ում (օրինակ, ինչպես [2]-ում, էջ 33): Ապացուցվում է (Թեորեմ 1), որ ցանկացած թվաբանական բազմություն պոզիտիվ է այն և միայն այն դեպքում, երբ այն սահմանվում է այնպիսի թվաբանական բանաձևի միջոցով, որը պարունակում է միայն ∃, &,∨ տրամաբանական գործողություններ և 𝑥𝑥 = 0, 𝑥𝑥 = 𝑦𝑦 + 1𝑦𝑦 տեսք ունեցող տարրական ենթաբանաձևեր: Հետևանք՝ պոզիտիվ բազմությունների դասի տրամաբանական նկարագրությունը ստացվում է խիստ պոզիտիվ բազմությունների դասի տրամաբանական նկարագրությունից, երբ &,∨ տրամաբանական գործողությունների ցուցակը փոխարինվում է ∃, &,∨ ցուցակով: Ապացուցվում է (Թեորեմ 2), որ մեկ չափանի ցանկացած 𝑀𝑀 անդրադարձ թվարկելի բազմության համար գոյություն ունի 6 չափանի խիստ պոզիտիվ ինչ որ 𝐻𝐻 բազմություն, որի համար տեղի ունի հետևյալ առնչությունը՝ 𝑥𝑥 ∈ 𝑀𝑀 այն և միայն այն դեպքում, եթե (1, 2𝑥𝑥, 0, 0, 1, 0) ∈ 𝐻𝐻+, որտեղ 𝐻𝐻+ իրենից ներկայացնում է 𝐻𝐻 բազմության տրանզիտիվ փակումը: О некоторых свойствах позитивных и строго позитивных арифметических множеств С. Манукян Аннотация Определения понятий позитивного и строго позитивного арифметического множества даются так же как в [1]-[4] (см., например, [2], стр.33). Доказывается (Теорема 1), что любое арифметическое множество позитивно в том, и только в том случае, когда оно задается арифметической формулой, которая содержит только логические операции ∃, &,∨ и только элементарные подформулы вида 𝑥𝑥 = 0, 𝑥𝑥 = 𝑦𝑦 + 1. Следствие: Логическое описание класса позитивных арифметических формул получается из логического описания класса строго позитивных арифметических формул посредством замены списка логических операций &,∨ списком ∃, &,∨. Доказывается (Теорема 2), что для любого одномерного рекурсивно перечислимого множества 𝑀𝑀 существует строго позитивное множество 𝐻𝐻 размерности 6, такое, что 𝑥𝑥 ∈ 𝑀𝑀 имеет место в том и только в том случае, когда (1, 2𝑥𝑥, 0, 0, 1, 0) ∈ 𝐻𝐻+, где 𝐻𝐻+ есть транзитивное замыкание множества 𝐻𝐻.