C&SA | Contents

Volume 59 >>> № 5 SEPTEMBER — OCTOBER 2023

-->

UDC 519.217.2

A.M. Gupal¹, O.A. Vagis²

¹ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

gupalanatol@gmail.com

² V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

valexdep135@gmail.com

INCOMPLETENESS OF ARITHMETIC FROM THE POINT OF VIEW
OF DIOPHANTINE SET THEORY

Abstract. Analysis of Diophantine sets showed that all recursively enumerated sets are Diophantine. Based on classical results in the theory of computable functions, a simple version of the theorem on the incompleteness of arithmetic can be given: there is a polynomial that does not have positive integer solutions, and for which it is impossible to prove the absence of positive roots.

Keywords: Diophantine set, recursively enumerated sets, incompleteness of arithmetic.

full text

REFERENCES

Matiyasevich Yu.V. Diophantine sets. Uspekhi matematicheskikh nauk. 1971. Vol. 22. Iss. 5. P. 185–222.

Cutland N. Computability. Introduction to the theory of recursive functions [Russian translation]. Moscow: Mir, 1983. 256 p.

Matiyasevich Yu.V. Hilbert's tenth problem [Russian translation]. Moscow: Mir, 1993. 224 p.

Mendelsohn E. Introduction to Mathematical Logic [Russian translation]. Moscow: Mir, 1971. 320 p.

UDC 519.217.2

INCOMPLETENESS OF ARITHMETIC FROM THE POINT OF VIEW OF DIOPHANTINE SET THEORY

REFERENCES

INCOMPLETENESS OF ARITHMETIC FROM THE POINT OF VIEW
OF DIOPHANTINE SET THEORY