RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2012 Volume 407, Pages 77–104 (Mi znsl5486)

This article is cited 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.

UDC: 511.526+510.223

Received: 05.11.2012

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2014, 199:1, 36–52

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024