On binary recursively enumerable fuzzy sets(supported by Intas 2000-447)
by
S.N. Manukian
Institute for Informatics and Automation Problems, National Academy of Sciences of Armenia

On binary recursively enumerable fuzzy sets S.N. Manukian Institute of Informatics and Automation Problems of ANAS and YSU EXTENDED ABSTRACT Binary recursively enumerable fuzzy set (BREFS) is defined as a recursively enumerable set of triplets (x, y, ), where x and y are non-negative integers and is a binary rational number, m/2n, 0 <= <= 1. This notion is a partial case of the notion of multi-dimensional recursively enumerable fuzzy set, investigated in [1], [2], [3]. We shall consider also binary recursively enumerable strict sets (BRESS), which are defined as recursively enumerable sets (in the usual sense) of pairs (x, y) where x and y are non-negative integers. BREFS A and B are said to be equivalent if for every (x, y, ) in A there exists >= such that (x, y, ) in B, and for every (x, y, ) in B there exists >= such that (x, y, ) in A. This notion corresponds to the notion of equivalence used in [1]. Fuzzy image of a given BRESS A is defined as the BREFS B such that (x, y, 1) in B if and only if (x, y) in A and, besides, (x, y, 0) in B for all non-negative integers x, y. BREFS [R] and [Q] are defined as follows: [R] is the set of pairs (x, x+1) for all non-negative integers x; [Q] is the set of pairs (x, y) for all non-negative integers x, y such that x < y. BREFS R and Q are defined as fuzzy images of [R] and [Q]. BREFS H is defined as the set of triplets (x, y, 1/2) and, besides, (x, y, 0), for all non-negative integers x, y. The operations , , o , * , , -1, on BRESS are defined by the following generating rules: (1) If (x, y) in A then (x, y) in A B; if (x, y) in B then (x, y) in A B. (2) If (x, y) in A and (x, y) in B then (x, y) in A B. (3) If (x, y) in A and (y, z) in B then (x, z) in A o B. (4) If (x, y) in A then (x, y) in * A; if (x, y) in * A and (y, z) in * A then (x, z) in * A. (For example, [R]= * [Q]). If (x, y) in A and (x, z) in B then (x, y +z) in A. (5) If (x, y) in A then (y, x) in A-1. The operations , , o , * , -1 concerning binary recursive enumerable sets of strings in a given alphabet were considered by G.S. Tseytin in [4]. Let us note that G.S.Tseytin uses the reverse order of operands for the operation o . The operations +, , o , , , , -1 on BREFS are defined by the following generating rules: (1) If (x, y, ) in A and (x, y, ) in B, then (x, y, min(1, +)) in A+B. (2) If (x, y, ) in A and (x, y, ) in B, then (x, y, •) in A. (3) If (x, y, ) in A and (y, z, ) in B, then (x, z, •) in A o B. (4) If (x, y, ) in A, then (x, y, ) in ; if (x, y, ) in and (y, z, ) in , then (x, z, min(1, +)) in . (5) If (x, y, ) in A, then (x, y, ) in A; if (x, y, ) in A and (y, z, ) in A, then (x, z, •) in A. (For example, Q= R). (6) If (x, y, ) in A and (x, z, ) in B, then (x, y + z, •) in A. (7) If (x, y, ) in A, then (y, x, ) in A-1. Similar operations +, , , concerning multi-dimensional recursively enumerable fuzzy sets were defined in [1]. We consider below algebras on BRESS'es and BREFS'es; every such algebra is given by its operations and basic elements. We say that a BRESS or a BREFS is expressible in the algebra if it is can be constructed from its basic elements using the operations of this algebra. The algebra on BRESS'es is defined by the basic element [R] and by the operations , , o , * , , -1. The algebra on BREFS'es is defined by the basic elements R, H and by the operations +, , o , , , , -1. The algebra o is obtained from by dropping the operation * and by adding [Q] to the set of its basic elements. The algebra o is obtained from by dropping the operations , and by adding Q to the set of its basic elements. Let be a system of formal arithmetic [5] based on the predicate calculus; we suppose that the signature of this system contains the constant 0 and the functional symbol ' for the function x' = x + 1. By [ #61536;n] we denote the term 0'' ... ', where the symbol ' is repeated n times. We say that the BRESS A is strongly representable in if there exists a formula B(x, y) in with free variables x and y such that B([ #61536;n], [ #61536;m]) is deducible in when (n, m) in A and not B([ #61536;n], [ #61536;m]) is deducible in when (n, m) not in A. Lemma. Every BRESS is expressible in . An analogous fact was proved by G.S. Tseytin in [4] (using another list of operations and another basic elements) for binary recursively enumerable sets of strings in a given alphabet. Theorem 1. Every BREFS is expressible (up to the equivalence) in . An analogous fact was proved in [1] for multi-dimensional recursively enumerable fuzzy sets; however the list of operations used in [1] differs from the list used here, because many operations considered in [1] are not applicable to BREFS. Theorem 2. A BRESS A is expressible in o if and only if it is strongly representable in the arithmetical system of M. Presburger ([5], [6]). If A is a BREFS then the set of -level in A for some fixed , 0 <= <= 1, is defined as the BRESS B such that (x, y) in B if and only if (x, y, ) in A. Theorem 3. A BREFS A is expressible in o if and only if there exists a natural number N > 0 such that for all (x, y, ) in A the number has the form m/2N for some m, 0 <= m <= 2N, and all the sets of -level in A are strongly representable in M. Presburger's system. So o can be considered as "fuzzy analogue" of M. Presburger's system. References 1. S.N. Manukian. On the structure of recursively enumerable fuzzy sets. Transactions of the Institute for Informatics and Automation Problems of ANAS and YSU, "Mathematical Problems of Computer Science", vol. 17, pp. 86-91 (1997) (in Russian). 2. S.N. Manukian. On some properties of recursively enumerable fuzzy sets. Proceedings of the Conference "Computer Science and Information Technologies", CSIT-99, Yerevan, Armenia, August 1999, pp.5-6 (1999). 3. S.N. Manukian. Algorithmic operators on recursively enumerable fuzzy sets. Proceedings of the Conference "Computer Science and Information Technologies", CSIT-01, Yerevan, Armenia, September 2001, pp.125-126 (2001). 4. G.S. Tseytin. One method for the representation of Algorithms and Recursively Enumerable Sets Theory. Trudy Matem. Inst. im. V.A. Steklova, vol. 72, pp. 69-98 (1964) (in Russian). 5. S.C. Kleene. Introduction to Metamthematics. D. van Nostrand Comp., Inc. (1952). 6. M.Presburger. Ueber die Vollstaendigkeit eines gewissen System der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. Sprawozdanie z I Kongresu Matematikow Krajow Slowianskich (Comptes rendudu I Congres des Mathematiciens des Pays Slaves), Warszawa, pp.92-101 (1930).

Footnotes: This research is supported by INTAS grant "Weak Arithmetics" 2000-447.

Date received: April 16, 2002