Some algebras of recursively enumerable sets and their applications to the fuzzy logic

S. N. Manukian

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VIII, Tome 304 (2003), pp. 75-98

Résumé

Algebras of operations defined on recursive enumerable sets of different kinds are considered. Every such algebra is given by the list of operations taking part in it; besides, in every considered algebra some list of basic elements is fixed. An element of algebra is said to be inductively representable in this algebra if it can be obtained from the basic elements by use of operations contained in the algebra. Two kinds of recursively enumerable sets are considered: recursively enumerable sets in the usual sense and fuzzy recursively enumerable sets. Some algebras of operations are introduced on two-dimensional recursively enumerable sets of the mentioned kinds. An algebra $\theta$ is constructed, where all two-dimensional recursively enumerable sets are inductively representable. A subalgebra $\theta^0$ of the algebra $\theta$ is constructed, where all two-dimensional recursively enumerable sets described by formulas of M. Presburger's arithmetical system (and only such sets) are inductively representable. An algebra $\Omega$ is constructed where all two-dimensional recursively enumerable fuzzy sets are inductively representable. A subalgebra $\Omega^0$ of the algebra $\Omega$ is constructed such that fuzzy recursively enumerable sets inductively representable in it can be considered as fuzzy analogues of sets described by the formulas of M. Presburger's arithmetical system.

Bibliographie

[1] I. D. Zaslavskii, “O konstruktivnoi istinnosti suzhdenii i nekotorykh netraditsionnykh sistemakh konstruktivnoi logiki”, Matematicheskie voprosy kibernetiki i vychislitelnoi tekhniki, Trudy VTs AN Arm. SSR i EGU, 8, 1975, 99–153 | MR | Zbl

[2] B. A. Kushner, Lektsii po konstruktivnomu matematicheskomu analizu, Nauka, M., 1973 | MR | Zbl

[3] A. I. Maltsev, Algebraicheskie sistemy, Nauka, M., 1970 | MR

[4] A. I. Maltsev, Algoritmy i rekursivnye funktsii, 2-e izd., Nauka, M., 1986 | MR

[5] S. N. Manukyan, “O perechislimykh predikatakh i sekventsialnykh ischisleniyakh nechetkoi logiki”, 9-ya Vsesoyuznaya konferentsiya po matematicheskoi logike, Tezisy dokladov, Leningrad, 1988, 5

[6] S. N. Manukyan, “O predstavlenii nechetkikh rekursivno perechislimykh mnozhestv”, 11-ya Mezhrespublikanskaya konferentsiya po matematicheskoi logike, Tezisy dokladov, Kazan, 1992, 94

[7] S. N. Manukyan, “O strukture nechetkikh rekursivno perechislimykh mnozhestv”, Matematicheskie voprosy kibernetiki i vychislitelnoi tekhniki, Trudy Instituta problem informatiki i avtomatizatsii NAN RA i EGU, 17, 1997, 86–91

[8] G. S. Tseitin, “Odin sposob izlozheniya teorii algorifmov i perechislimykh mnozhestv”, Trudy Matem. inst. im. V. A. Steklova, 72, 1964, 69–98

[9] N. A. Shanin, “Konstruktivnye veschestvennye chisla i konstruktivnye funktsionalnye prostranstva”, Trudy Matem. inst. im. V. A. Steklova, 67, 1962, 15–294 | Zbl

[10] H. Enderton, A Mathematical Introduction to Logic, 2nd ed., Academic Press, San Diego, Harcourt, 2001 | MR | Zbl

[11] G. Graetzer, Universal Algebra, 2 ed., New York–Heideberg–Berlin, 1979

[12] P. Hajek, Metamathematics of Fuzzy Logik, Kluwer, 1998 | Zbl

[13] D. Hilbert, P. Bernays, Grundlagen der Mathematik, Band I. Zweite Auflage, Springer-Verlag, Berlin–Heideberg–New York, 1968 ; D. Gilbert, P. Bernais, Osnovaniya matematiki, t. I: Logicheskie ischisleniya i formalizatsiya arifmetiki, Nauka, M., 1979 | MR | MR

[14] S. C. Kleene, Introduction to Metamathematics, D. van Nostrand Comp., Inc., New York–Toronto, 1952 ; S. K. Klini, Vvedenie v metamatematiku, IIL, M., 1957 | MR

[15] H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, Upper Saddle River, New Jersey, 1998

[16] S. N. Manukian, “On some properties of recursively enumerable fuzzy sets”, Computer Science and Information Technologies, CSIT-99, Proceedings of the Conference (August, 1999, Yerevan), Armenia, 1999, 5–6

[17] S. N. Manukian, “Algorithmic operators on recursively enumerable fuzzy sets”, Computer Science and Information Technologies, CSIT-01, Proceedings of the Conference (September 2001, Yerevan), Armenia, 2001, 125–126

[18] S. N. Manukian, “On binary recursively enumerable fuzzy sets”, 21st Days of Weak Arithmetics, International Conference, Abstracts (St. Petersburg, Russia, June 2002), St. Petersburg, 2002, 13–15

[19] E. Mendelson, Introduction to Mathematical Logic., D. van Nostrand Comp., Inc., Princeton–Toronto–New York–London, 1963 ; E. Mendelson, Vvedenie v matematicheskuyu logiku, Nauka, M., 1971 | MR | MR

[20] V. Novak, Fuzzy sets and their applications, Adam Hilger, Bristol, 1989 | MR | Zbl

[21] M. Presburger, “Über die Vollstaendigkeit eines gewissen System der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervotritt”, C. R. Congres Math. Pays slaves, 1930, 92–101 | Zbl

[22] R. M. Smullyan, Theory of formal systems, Princeton University Press, Princeton, NY, 1963 ; R. Smalyan, Teoriya formalnykh sistem, Nauka, M., 1981 | MR | MR

[23] E. Specker, “Nicht konstruktiv beweisbare Saetze der Analysis”, J. of Symb. Logic, 14:3 (1949), 145–158 | DOI | MR | Zbl

[24] L. Zadeh, “Fuzzy sets”, Information and Control, 8 (1965), 338–353 | DOI | MR | Zbl