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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

По теореме дедукции отсюда следует |– A(x)⊃A(S(x)), а затем |– ∀x(A(x)⊃A(S(x))).
Так как A(0) уже доказано, то по схеме индукции получаем |– ∀xA(x) или |– 0+x=x.
Аналогично доказываются другие простые теоремы EA. Следует помнить, однако,
что перед тем как доказывать какую-либо теорему (например, коммутативность
умножения: х×у=у×х), полезно уже знать некоторые теоремы. Таким образом, даже
доказательство простых теорем EA содержит в себе творческий момент – он состоит в
наиболее рациональном выборе порядка, в котором эти теоремы следует доказывать.
Следующее утверждение является эмпирически установленным фактом: все
рассуждения обычной (интуитивной
) теории чисел, которые не апеллируют к
произвольным действительным числам и функциям, могут быть формально
воспроизведены в EA.
Язык теории EA (как и любой язык теории первого порядка) можно расширить,
введя новые функциональные символы и константы, которые «доказуемо выразимы» в
языке. Это просто формальный вариант «введения новых обозначений». Их добавление к
алфавиту сокращает формульные выводы и записи формул, но не увеличивают множество
выводимых формул (см. [16, стр. 75–76]).
Арифметические функции и отношения
Как можно трактовать в теории EA операцию возведения в степень, если
соответствующего символа в языке теории нет? Другой вопрос: мы пишем формулы,
заменяющие в EA интуитивно понимаемые предикаты вроде «x – простое число»:
«1<x» & ¬∃y∃z(«y<x»& «z<x» & x=y×z);
Какие требования мы должны предъявлять к
такого рода формулам? Если кто-то
предлагает формулу и утверждает, что она «выражает» то-то и то-то, как это проверить?
Для таких ситуаций вводятся понятия выразимости предикатов и представимости
функций.
Арифметическими функциями называются функции, у которых область
определения и множество значений состоят из натуральных чисел, а арифметическим
отношением является
всякое отношение, заданное на множестве натуральных чисел. Так,
например, умножение есть арифметическая функция с двумя аргументами, а выражение
x+y < z определяет некоторое арифметическое отношение с тремя аргументами.
Арифметические функции и отношения являются понятиями интуитивными, и не
связанными ни с какой формальной системой.
Выразимые отношения
Арифметическое отношение R(x
1
,…, x
n
) называется выразимым в EA, если существует
формула A(x
1
,…, x
n
) теории EA с n свободными переменными такая, что для любых
натуральных чисел k
1
,…, k
n
1) если R(k
1
,…, k
n
) истинно, то |– A(k
1
,…, k
n
),
2) если R(k
1
,…, k
n
) ложно, то |– ¬A(k
1
,…, k
n
).
Легко проверить, что формула x=y выражает в EA обычное интуитивно понимаемое
равенство натуральных чисел. В самом деле, для любых m, n: а) если m=n, то |– m=n
(термы m, n в этом случае просто совпадают), б) если m≠n, то |– ¬(m=n) (проверьте).
Интересно было бы получить
какую-то характеристику класса тех предикатов,
которые выразимы в EA. Если теория EA противоречива, то в ней доказуема любая
формула и поэтому – в смысле принятого нами определения – в EA можно выразить
любой предикат (например, формула x=y выражает любой двухместный предикат).
Многочисленные примеры выразимых отношений с доказательствами см. в [17, с.132–
135]. Любое ли арифметическое отношение является выразимым в элементарной
арифметике? Каждое одноместное отношение (свойство) натуральных чисел определяет
некоторое множество натуральных чисел, а именно, состоящее из чисел, обладающих

Страницы