"Записки научных семинаров ПОМИ"
Том 407, стр. 77-104
О диофантовом представлении предиката ``доказуемость''
М. Карл, Б. З. Мороз
Fachbereich Mathematik und Statistik,
Universit\"at Konstanz, Universit\"atsstrasse 10,
D-78457 Konstanz, GERMANY
merlin.carl@uni-konstanz.de
Max-Planck-Institut f\"ur Mathematik, Vivatsgasse 7,
D-53111 Bonn, GERMANY
moroz@mpim-bonn.mpg.de
- Аннотация: Обозначим через $\mathcal P$ исчисление предикатов первого
порядка с фиксированным бинарным предикатом.
Пользуясь развитой в работах по десятой проблеме Гильберта техникой
диофантова кодирования, мы строим полином
$F(t;x_1,\ldots,x_n)$ с целыми рациональными коэффициентами
такой, что при подходящей нумерации формул теории
$\mathcal P$, формула под номером
$t_0$
доказуема в $\mathcal P$
тогда и только тогда, когда уравнение
$$
F(t_0;x_1,\ldots,x_n)=0
$$
разрешимо в целых числах. В качестве одного из приложений
этой конструкции описывается класс диофантовых уравнений,
для доказательства неразрешимости которых в целых числах
необходимо привлечь дополнительную аксиому теории иножеств,
например, аксиому о существовании недостижимых кардиналов.
Библ. -- 14 назв.
- Ключевые слова: Диофатовое кодирование, уравнение Пелля,
теорема Матиясевича, система Гёделя-Бернайса
[Diophantine coding, Matiyasevich's theorem,
Pell's equation, Godel-Bernays set theory]
Полный текст(.pdf)