Выразить в арифметике принадлежность к множеству чисел вида $$n^n$$

задан 9 Май '17 2:47

10|600 символов нужно символов осталось
0

Достаточно выразить трёхместный предикат $%P(x,y,z)\leftrightharpoons x^y=z$%. Тогда требуемое свойство числа $%z$% иметь вид $%n^n$% запишется как $%(\exists n)P(n,n,z)$%.

Показательный предикат строится с помощью кодирования конечных последовательностей по Гёделю. Условие $%x^y=z$% выполняется тогда и только тогда, когда существует конечная последовательность $%a_0$%, $%a_1$%, ... , $%a_y$% такая, что $%a_0=1$%, $%a_y=z$%, и для любого $%i < y$% верно $%a_{i+1}=xa_i$%. Конечные последовательности кодируются двумя параметрами при помощи бета-функции Гёделя; см. учебник Мендельсона, глава 3, параграф 3, стр. 145. См. там же Предложение 3.22 на следующей странице.

Бета-функция выразима в арифметике Пеано, и равенство $%\beta(b,c,i)=k_i$% означает, что $%i$%-й член последовательности с "кодом" $%(b,c)$% равен $%k_i$%. Отсюда предикат $%P(x,y,z)$% выражается так:

$%(\exists b)(\exists c)(\beta(b,c,0)=1\&\beta(b,c,y)=z\&(\forall i)(i < y\to\beta(b,c,i)\cdot x=\beta(b,c,i+1)))$%.

ссылка

отвечен 9 Май '17 4:16

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,781
×928
×430
×251

задан
9 Май '17 2:47

показан
623 раза

обновлен
9 Май '17 4:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru