On Strongly Positive Multidimensional Arithmetical Sets
Keywords:
Arithmetical formula, Transitive closure, Recursive set, SignatureAbstract
The notion of positive arithmetical formula in the signature (S,=,0), where S(x)=x+1, is defined and investigated in [1] and [2]. A multidimensional arithmetical set is said to be positive if it is determined by a positive formula. Some subclass of the class of positive sets, namely, the class of strongly positive sets, is considered. It is proved that for any n ≥ 3 there exists a 2n -dimensional strongly positive set such that its transitive closure is non-recursive. On the other side, it is noted that the transitive closure of any 2-dimensional strongly positive set is primitive recursive.
References
S. N. Manukian, “On the representation of recursively enumerable sets in weak arithmetics”, Transactions of the IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 27, pp. 90--110, 2006.
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.
S. C. Kleene, Introduction to Metamathematics, D, Van Nostrand Comp., Inc., New York Toronto, 1952.
H. B. Enderton, A Mathematical Introduction to Logic, 2nd edition, San Diego, Harcourt, Academic Press, 2001.
E. Mendelson, Introduction to Mathematical Logic, D, Van Nostrand Comp., Inc., Princeton-Toronto-New York-London, 1964.
D. Hilbert and P. Bernays, Grundlagen der Mathematik, Band1, Zweite Auflage, BerlinHeidelberg-New York, Springer Verlag, 1968.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw Hill Book Comp., New York-St. Louis-San Francisco-Toronto-London-Sydney, 1967.
A. I. Malcev, Algorithms and Recursive Functions, 2nd edition, (in Russian), 1986.
A. A. Markov, “Impossibility of some algorithms in the theory of associative systems”, Reports of the Acad. Sci. USSR, (in Russian), vol. 55, no. 7, pp. 587-590, 1947.
E. L. Post, “Recursive unsolvability of a problem of Thue”, Journ. of Symb. Logic, vol. 12, pp. 1-11, 1947.
P. S. Novikov, “On the algorithmic unsolvability of identity problem in the group theory”,Transactions of Steklov Institute of the Acad. Sci. USSR, (in Russian), vol. 44, 1955.
G. S. Tseytin, “Associative calculus with the unsolvable problem of equivalence”, Transactions of Steklov Institute of the Acad. Sci. USSR, (in Russian), vol. 52, pp. 172- 189, 1958.
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.
S. N. Manukian,. “Classification of many-dimensional arithmetical sets represented in M. Presburger’s system”, Reports of the National Acad. Sci. of Armenia, (in Russian), vol. 111, no. 2, pp. 114--120, 2011.
M. Presburger, “Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt”, Comptes Rendu du I Congres des Mathematiciens des Pays Slaves, Warszawa, pp. 92-101, 1930.
R. Stransifer, Presburger’s Article on Integer Arithmetics: Remarks and Translation, Department of Computer Science, CornellUniversity, Ithaca, New York, 1984.
M. L. Minsky, “Recursive unsolvability of Post’s problem of “Tag” and topics in theory of Turing machines”, Ann. Math., vol. 74, pp. 437-455, 1961.
I.D. Zaslavsky, “Graph-schemes with memory”, Transactions of Steklov Institute of Acad. Sci. USSR, (in Russian), vol. 72, pp. 99-192, 1964.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
