Теория алгоритмов. Зюзысов В.М. - 41 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

данным свойством. Нетрудно проверить, что множество различных формул в теории
первого порядка является счетным множеством. С другой стороны множество всех
подмножеств, составленных из натуральных чисел, имеет мощность больше счетного
(теорема Кантора), отсюда следует, что существуют свойства натуральных чисел,
невыразимые в EA.
Представимые функции
Арифметическая функция f(x
1
,…, x
n
) называется представимой в EA, если существует
формула A(x
1
,…, x
n
, y) формальной арифметики со свободными переменными x
1
,…, x
n
, y
такая, что для любых натуральных чисел k
1
,…, k
n
, k
n+1
таких, что f(k
1
,…, k
n
) = k
n+1
1) |– A(k
1
,…, k
n
, k
n+1
),
2) |– ∀y (¬(k
n+1
= y) ⊃ ¬A(k
1
,…, k
n
, y)).
Все функции, которые мы в интуитивном смысле считаем вычислимыми (т. е.
значения которых вычисляются с помощью алгоритмов), оказываются представимыми в
EA. Если теория EA противоречива, то в ней представима любая функция.
Теорема 19. [17, с. 158] Всякая функция, представимая в EA, является частично-
рекурсивной и наоборот.
Оказывается, что класс выразимых отношений в EA
также оказывается очень
широк. Но сначала нам потребуется определение.
Характеристической функцией данного отношения R(x) (в данном случае x
сокращенная запись для <x
1
, …, x
n
>) называется функция C
R
(x), задаваемая условиями:
1, если R(x) истинно,
C
R
(x) =
0, если R(x) ложно.
Теорема 20. [17, стр. 134] Отношение R(x) выразимо в теории EA тогда и только
тогда, когда характеристическая функция C
R
(x) представима в EA.
Отношение R называется разрешимым, если его характеристическая функция C
R
является частично-рекурсивной.
Теорема 21. Всякое отношение, выразимое в EA, является разрешимым и наоборот.
Справедливость этой теоремы следует из теорем 19 и 20.
4.2 Неполнота элементарной арифметики
Геделева нумерация
Пусть дана некоторая формальная система. Предложение, утверждающее, что
некоторая последовательность формул образует (или не образует) вывод некоей формулы,
уже не является доказательством в самой этой формальной системе. Это утверждение о
системе; такие утверждения обычно называют метаматематическими. Необходимо
тщательно различать математические и метаматематические рассуждения. Нарушение
этого условия приводит к парадоксам. Пример см
. в разделе 3.1.
У Курта Гёделя возникла великая идея арифметизации метаматематики, т.е.
замены утверждений о формальной системе эквивалентными высказываниями о
натуральных числах с последующим выражением этих высказываний в формальной
системе. Идея арифметизации стала ключом к решению многих важных проблем
математической логики. Арифметизацией данной теории первого порядка мы называем
всякую функцию
g, отображающую инъективно множество всех символов, выражений и
конечных последовательностей выражений во множество целых положительных чисел.

Страницы