Some Algebraical and Logical Properties of Two-dimensional Arithmetical Sets Representable in Presburger’s System


  • Seda N. Manukian Institute for Informatics and Automation Problems of NAS RA


A classification (0)  (1)  (2)  ... H H H of arithmetical sets representable in M.Presburger’s system ([1]-[4]) and a classification (0)  (1)  (2)  ... H H H of twodimensional sets of the same kind are considered. It is proved that these classifications are strictly monotone and complete. The operations ,,  ,  , 1 on twodimensional arithmetical sets ([5]-[7]) and the algebras Θ0 and Θ1 based on these operations ([5]-[7]) are considered. The relations of these operations and algebras to the mentioned classifications are investigated.


M. Presburger, “Über die Vollstaendigkeit eines gewissen System der Arithmetik ganzer Zahlen, in welchem die Addition als einige Operation hervortritt”, Comptes Rendu du I Congres des Mathematiciens des Pays Slaves, Warszawa, pp. 92-101, 1930.

D. Hilbert und P. Bernays. Grundlagen der Mathematik. Band I. Zweite Auflage, Berlin-Heidelberg- New York, Springer Verlag, 1968.

R. Stansifer. Presburger's Article on Integer Arithmetic: Remarks and Translation. Department of Computer Science, Cornell University, Ithaca, New York, 1984.

H. Enderton. A Mathematical Introduction to Logic. 2nd ed., San Diego, Harcourt, Academic Press, 2001.

S. N. Manukian, “Algebras of Recursively Enumerable Sets and Their Applications to Fuzzy Logic”, Journal of Mathematical Sciences, vol. 130, №2, pp. 4598-4606, 2005.

S. N. Manukian, “A Classification of Arithmetical Sets Expressible in Presburger's System”, Proceedings of the International Conference «Computer Science and Information Technologies», CSIT- 05, Yerevan, Armenia, pp. 161-162, 2005.

S. N. Manukian, “On the Representation of Recursively Enumerable Sets in Weak Arithmetic. Mathematical Problems of Computer Science, vol. 27, pp. 90-110, 2006.

S. N. Manukian, “Classification of Many-dimensional Arithmetical Sets Represented in M. Presburger's System”, Reports of the National Academy of Science of Armenia, vol. 111, №2, pp. 114- 120, 2011 (in Russian).

S. C. Kleene. Introduction to Metamathematics. D. Van Nostard Comp., Inc., New York-Toronto, 1952.




How to Cite

Manukian, S. N. . (2021). Some Algebraical and Logical Properties of Two-dimensional Arithmetical Sets Representable in Presburger’s System. Mathematical Problems of Computer Science, 37, 64–74. Retrieved from