Арифметические функции и отношения. Их выразимость в формальной арифметике — различия между версиями
ExileHell (обсуждение | вклад) (Новая страница: «Введем обозначение. Будем говорить, что <tex>\alpha (x_1, \dots x_n)</tex> — это формула с <tex>n</tex> своб...») |
м (rollbackEdits.php mass rollback) |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
+ | [[Лекция 7 | <<]][[Геделева нумерация. Арифметизация доказательств | >>]] | ||
+ | |||
Введем обозначение. Будем говорить, что <tex>\alpha (x_1, \dots x_n)</tex> — это формула с <tex>n</tex> свободными переменными, если переменные <tex>x_1, ... x_n</tex> входят в <tex>\alpha</tex> свободно. Запись <tex>\alpha (y_1, \dots y_n)</tex> будем трактовать, как <tex>\alpha [x_1 := y_1, ... x_n := y_n]</tex>, при этом мы подразумеваем, что <tex>y_1, \dots y_n</tex> свободны для подстановки вместо <tex>x_1, \dots x_n</tex> в <tex>\alpha</tex>. | Введем обозначение. Будем говорить, что <tex>\alpha (x_1, \dots x_n)</tex> — это формула с <tex>n</tex> свободными переменными, если переменные <tex>x_1, ... x_n</tex> входят в <tex>\alpha</tex> свободно. Запись <tex>\alpha (y_1, \dots y_n)</tex> будем трактовать, как <tex>\alpha [x_1 := y_1, ... x_n := y_n]</tex>, при этом мы подразумеваем, что <tex>y_1, \dots y_n</tex> свободны для подстановки вместо <tex>x_1, \dots x_n</tex> в <tex>\alpha</tex>. | ||
Строка 127: | Строка 129: | ||
}} | }} | ||
+ | |||
+ | [[Категория: Математическая логика]] |
Текущая версия на 19:23, 4 сентября 2022
Введем обозначение. Будем говорить, что
— это формула с свободными переменными, если переменные входят в свободно. Запись будем трактовать, как , при этом мы подразумеваем, что свободны для подстановки вместо в .Также, запись
будет означать, что мы определяем новую формулу с именем . Данная формула должна восприниматься только как сокращение записи, макроподстановка.
Определение: |
Арифметическая функция — функция | . Арифметическое отношение — -арное отношение, заданное на .
Определение: |
Арифметическое отношение
| называется выразимым (в формальной арифметике), если существует такая формула с свободными переменными, что для любых натуральных чисел ...
Например, отношение является выразимым в арифметике: Рассмотрим формулу . В самом деле, если взять некоторые числа и , такие, что , то найдется такое положительное число , что . Можно показать, что если подставить и в , то формула будет доказуема.
Наметим доказательство: Тут должно быть два доказательства по индукции, сперва по
, потом по . Рассмотрим доказательство по индукции: пусть , индукция по 2-му параметру: Разберем доказательство базы при . Тогда надо показать :(1) | Несложно показать | |
(2) | Cх. акс. для | |
(3) | M.P. 1 и 2. |
Определение: |
Введем следующее сокращение записи: пусть | означает Здесь и — некоторые переменные, не входящие в формулу свободно.
Определение: |
Арифметическая функция
Комментарии: Функция называется сильно представимой, если в свойстве 2 натуральные числа заменить на переменные: | от аргументов называется представимой в формальной арифметике, если существует такая формула с свободными пременными, что для любых натуральных чисел ...
Комментарии:
Очевидно, что сильно представимая функция также является представимой --- с помощью уже встречавшегося ранее трюка с введением квантора всеобщности, а потом с подстановкой конкретного терма вместо переменной мы можем подставить любые константы вместо переменных.
Теорема: |
Функции , , являются представимыми. |
Доказательство: |
Наметим доказательство. Для этого приведем формулы, доказательство корректности этих формул оставим в виде упражнения.
|
Теорема: |
Если функции и , ... представимы, то функция также представима. |
Доказательство: |
Поскольку функции | и представимы, то есть формулы и , их представляющие. Тогда следующая формула представит :
Определение: |
Характеристическая функция арифметического отношения | — это функция
Очевидно, что характеристическая функция представима тогда и только тогда, когда отношение выразимо.
Определение: |
-функция Геделя - это функция . Здесь операция (%) означает взятие остатка от целочисленного деления. |
Лемма: |
Функция примитивно-рекурсивна, и при этом представима в арифметике формулой |
Доказательство: |
Упражнение. |
Лемма: |
Для любой конечной последовательности чисел ... можно подобрать такие константы и , что для . |
Доказательство: |
Возьмем число . Рассмотрим числа .
|
Теорема: |
Всякая рекурсивная функция представима в арифметике. |
Доказательство: |
Представимость первых четырех примитивов уже показана. Покажем представимость примитивной рекурсии и операции минимизации. Пусть есть некоторый . Соответственно, и уже представлены как некоторые формулы и . Из определения мы знаем, что для значения должна существовать последовательность результатов применения функций f и g — значений на одно больше, чем итераций в цикле примитивной рекурсии, а это количество определяется последним параметром функции . При этом:Значит, по лемме, должны существовать такие числа и , что для .Приведенные рассуждения позволяют построить следующую формулу, представляющую :
|