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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

формулы N(x) (с единственной свободной переменной x), которая «утверждает», что x
является натуральным числом. Далее, необходимо отобразить в теории T элементарные
формулы EA, т.е. формулы вида t
1
= t
2
, трактующие о значениях полиномов t
1
, t
2
с
натуральными коэффициентами.
Имея относительную интерпретацию EA в T, в теории T можно доказать любое
свойство натуральных чисел, которое доказуемо в EA. Учитывая роль системы
натуральных чисел в математике, формальную теорию, в которой относительно
интерпретируема теория EA (и которая содержит в этом смысле полноценное понятие
натурального числа), будем называть фундаментальной
теорией. Простейшей из
фундаментальных теорий является, конечно, сама теория EA.
Теорема Гёделя, оказывается, справедлива для любой фундаментальной теории.
Понятие об ω-противоречивости несколько «портит» теорему К. Гёделя о
неполноте. Однако сам Гёдель не пытался освободиться от него, впервые это удалось
только Б. Россеру в 1936 г. – в теореме Россера вместо ω-противоречивости
фигурирует
«обычная» противоречивость.
Теорема 24 (теорема Гёделя в форме Россера). В языке всякой фундаментальной
теории T найдется замкнутая формула R
T
(«выражающая» некоторое свойство
натуральных чисел), такая, что если |–
T
R
T
или |–
T
¬R
T
, то теория T противоречива.
В этой формулировке сделано еще одно усиление теоремы о неполноте, не
имеющее отношения к методу Россера. Cейчас речь идет о теории T с произвольным
языком первого порядка, которая содержит в себе элементарную арифметику. Это
освобождает нас от подозрений, что принципиальное несовершенство всякой системы
аксиом арифметики кроется
в неудачном выборе языка EA.
«Принцип несовершенства» К. Гёделя
Всякая фундаментальная теория несовершенна – она либо противоречива, либо
недостаточна для решения всех возникающих в ней проблем.
В частности, если удалось аксиоматизировать всю математику, то она была бы
несовершенной.
В качестве примера нефундаментальной теории можно назвать арифметику
Пресбургера, которая получается из EA удалением символа умножения. В 1929 г. М.
Пресбургер доказал полноту и непротиворечивость этой теории. В силу теоремы Геделя–
Россера тем самым была доказана и ее нефундаментальность.
Нестандартное расширение EA
Поскольку EA является неполной системой (формула G – неразрешима), то ее
можно пополнить (как можно дополнить абсолютную геометрию).
5
Стандартное пополнение: добавить в качестве аксиомы формулу G. (Это
соответствует расширению абсолютной геометрии в эвклидовом смысле.) Такое
добавление кажется довольно безвредным и даже желательным, поскольку G всего
навсего утверждает некоторую истину о системе натуральных чисел.
Нестандартное пополнение: (если следовать аналогии с ситуацией аксиомы
параллельности) добавить в качестве аксиомы формулу ¬G
. Но как мы можем даже
подумать о такой ужасной, отвратительной вещи? В конце концов, если перефразировать
Саккери
6
, не является ли то, что утверждает ¬G, «противным самой природе натуральных
чисел».
5
Этот пункт излагается по книге Д. Хофштадтера [27].
6
Джованни Саккери (1967–1733) – итальянский математик. Сделал попытку доказать пятый постулат
Евклида о параллельных от противного. Саккери не допускал возможности отказа от пятого постулата о
параллельных.

Страницы