|
Zapiski Nauchnykh Seminarov POMI, 2012, Volume 407, Pages 77–104
(Mi znsl5486)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
On a Diophantine representation of the predicate of provability
M. Carla, B. Z. Morozb a Fachbereich Mathematik und Statistik, Universität Konstanz, Konstanz, Germany
b Max-Planck-Institut für Mathematik, Bonn, Germany
Abstract:
Let $\mathcal P$ be the first order predicate calculus with a single binary predicate letter. Making use of the techniques of Diophantine coding developed in the works on Hilbert tenth problem, we construct a polynomial $F(t;x_1,\ldots,x_n)$ with integral rational coefficients such that the Diophantine equation
$$
F(t_0;x_1,\ldots,x_n)=0
$$
is soluble in integers if and only if the formula of $\mathcal P$, numbered $t_0$ in the chosen numbering of the formulae of $\mathcal P$, is provable in $\mathcal P$. As an application of that construction, we describe a class of Diophantine equations which can be proved insoluble only under some additional axioms of the axiomatic set theory, for instance, assuming existence of an inaccessible cardinal.
Key words and phrases:
Diophantine coding, Matiyasevich's theorem, Pell's equation, Gödel–Bernays set theory.
Received: 05.11.2012
Citation:
M. Carl, B. Z. Moroz, “On a Diophantine representation of the predicate of provability”, Studies in constructive mathematics and mathematical logic. Part XII, Zap. Nauchn. Sem. POMI, 407, POMI, St. Petersburg, 2012, 77–104; J. Math. Sci. (N. Y.), 199:1 (2014), 36–52
Linking options:
https://www.mathnet.ru/eng/znsl5486 https://www.mathnet.ru/eng/znsl/v407/p77
|
Statistics & downloads: |
Abstract page: | 260 | Full-text PDF : | 83 | References: | 35 |
|