Теорема Гёделя о неполноте и четыре дороги, ведущие к ней
Владимир Успенский
Теорема Гёделя о неполноте — едва ли не самая знаменитая теорема математики. Она утверждает, что какие бы способы доказывания ни предложить, в любом достаточно богатом языке найдутся истинные, но не доказуемые утверждения. Богатство языка есть его способность выражать факты. Оказывается, что для целей теоремы Гёделя богатство языка достаточно понимать как его способность выражать принадлежность натуральных чисел перечислимым множествам. Понятие перечислимого множества — одно из основных понятий теории алгоритмов: непустое множество называется перечислимым, если его можно расположить в вычислимую последовательность. Таким образом, теорема Гёделя имеет алгоритмические истоки. Возможны четыре принципиально различные пути, ведущие от этих истоков к теореме; эти пути были предложены, соответственно, Гёделем, Колмогоровым, Чейтином и Шенем.
Успенский Владимир Андреевич — д.ф.-м.н., профессор.
Лекции летней школы «Современная математика», г. Дубна
21-22 июля 2007 г.
#математика #основания_математики #теория_множеств #логика #теория_алгоритмов #философия #доказательство #Владимир_Успенский #Успенский_В_А #ЛШСМ