Теорема Гёделя о неполноте и четыре дороги, ведущие к ней
Теорема Гёделя о неполноте — едва ли не самая знаменитая теорема математики. Она утверждает, что какие бы способы доказывания ни предложить, в любом достаточно богатом языке найдутся истинные, но не доказуемые утверждения. Богатство языка есть его способность выражать факты. Оказывается, что для целей теоремы Гёделя богатство языка достаточно понимать как его способность выражать принадлежность натуральных чисел перечислимым множествам. Понятие перечислимого множества — одно из основных понятий теории алгоритмов: непустое множество называется перечислимым, если его можно расположить в вычислимую последовательность. Таким образом, теорема Гёделя имеет алгоритмические истоки. Возможны четыре принципиально различные пути, ведущие от этих истоков к теореме; эти пути были предложены, соответственно, Гёделем, Колмогоровым, Чейтином и Шенем.
Материалы к лекциям: 1.pdf, 2.pdf.
Успенский Владимир Андреевич — доктор физико-математических наук, профессор.
Лекции летней школы «Современная математика», г. Дубна
21-22 июля 2007 г.
Похожее
-
Владимир Успенский
Знаменитая Теорема Гёделя о неполноте имеет две версии — синтаксическую (объявленную и доказанную самим Гёделем) и семантическую (чаще всего фигурирующую в популярных рассуждениях о великой Теореме). Семантическая версия утверждает, что какую бы систему формальных доказательств ни придумать, в языке найдутся истинные утверждения, не доказуемые в рамках предложенной системы. Таким образом, семантическая версия исходит из того, что некоторые выражения языка выражают осмысленные утверждения, являющиеся истинными или ложными. Синтаксическая версия не опирается на то, что какие бы то ни было выражения языка имеют какой-то смысл, она смотрит на выражения как на синтаксические конструкции, то есть как на цепочки символов, организованные по определённым правилам.
-
Алексей Сосинский
Теорема Гёделя, наряду с открытием теории относительности, квантовой механики и ДНК, обычно рассматривается как крупнейшее научное достижение ХХ века. Почему? В чем ее суть? Каково ее значение? Эти вопросы в своей лекции раскрывает Алексей Брониславович Сосинский, математик, профессор Независимого московского университета, офицер Ордена академических пальм Французской Республики, лауреат премии Правительства РФ в области образования 2012 года. В частности, были даны несколько разных ее формулировок, описаны три подхода к ее доказательству (Колмогорова, Чейтина и самого Гёделя), и объяснено ее значение для математики, физики, компьютерной науки и философии.
-
В Евклидовой геометрии любое утверждение либо ложно, либо истинно, и третьего не дано. И в начале ХХ века математики наивно полагали, что такая же ситуация должна наблюдаться в любой логически непротиворечивой системе. И тут в 1931 году какой-то венский очкарик — математик Курт Гёдель — взял и опубликовал короткую статью, попросту опрокинувшую весь мир так называемой «математической логики». Гёдель попросту доказал следующее удивительное свойство любой системы аксиом: всякая система математических аксиом начиная с определенного уровня сложности либо внутренне противоречива, либо неполна.
-
Питер Эткинз
Эта книга предназначена для широкого круга читателей, желающих узнать больше об окружающем нас мире и о самих себе. Автор, известный ученый и популяризатор науки, с необычайной ясностью и глубиной объясняет устройство Вселенной, тайны квантового мира и генетики, эволюцию жизни и показывает важность математики для познания всей природы и человеческого разума в частности.
-
Владимир Успенский
Если в качестве значений переменных разрешается брать только элементы носителя, язык называют элементарным языком, или языком первого порядка. Если же в качестве значений переменных разрешается брать также функции и отношения, язык называют языком второго порядка. Выразительные возможности языков первого порядка довольно ограничены. Например, на языке первого порядка можно сообщить, что носитель содержит ровно 17 элементов, но невозможно выразить его конечность. На языке второго порядка выразить конечность носителя возможно. Возникает совершенно естественное недоумение: а зачем тогда пользоваться языками первого порядка с их бедными выразительными средствами, не лучше ли пользоваться языками второго порядка?
-
Лев Беклемишев
Классическая логика высказываний исходит из предположения о том, что любые высказывания либо истинны, либо ложны. Логика доказуемости отражает более глубокую картину мира, осознанную после теорем Гёделя о неполноте: истинность высказывания, вообще говоря, не равносильна его доказуемости. Можно ли — и если да, то как — говорить на уровне логики о доказуемости или недоказуемости высказываний, наряду с их истинностью или ложностью? Программа: Логика высказываний и её модели. Модальная логика, модели Крипке. Логика Гёделя-Лёба GL. Теорема о полноте логики GL по Крипке на конечных деревьях. Формальная арифметика Пеано. Гёделева нумерация. Теорема о неподвижной точке. Формулы доказуемости и непротиворечивости. Теоремы Гёделя, Россера и Лёба. Доказуемость как модальность: арифметическая интерпретация логики GL. Замкнутые модальные формулы, последовательность Тьюринга, локальная рефлексия. Существование и единственность модально определимых неподвижных точек (теорема де Йонга).
-
Владимир Успенский
В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть: конструктивный обьект, алгоритм, число шагов алгоритма, вычислимая функция, перечислимое множество, разрешимое множество, сводимость нумераций, главная вычислимая нумерация, вычислимая операция.
-
Отрывок из книги книга Дэвида Дарлинга и Агниджо Банерджи «Эта странная Математика — на краю бесконечности и за ним» о том, как Гедель доказал существование Бога и почему пифагорейцы утопили математика Гиппаса.
-
Грегори Чейтин
Из идей сложности и случайности, впервые высказанных Готфридом Лейбницем в его «Рассуждении о метафизике» (1686), и их подтверждения в современной теории информации следует, что невозможно создать «самую общую теорию всего» в математике.
-
Джордана Цепелевич
Всякая надежда на создание единой математической теории, амбициозного проекта, который был предложен математиком Давидом Гильбертом в 19 веке и продолжил существовать, поддерживаемый многими, в 20 столетии, рухнула. Основы математики были далеко не столь надежными, как того хотел бы Гильберт. А Гëдель своими теоремами ясно продемонстрировал, что любая система аксиом, какой бы обширной она ни была, уязвима для возникновения невосполнимых пробелов. Попытки же восполнить их созданием более полной системы породили бы только бóльшее количество утверждений без доказательств — так что и тут возникнет необходимость в усовершенствовании системы, и так далее до бесконечности. И случилось нечто странное: математики решили не обращать на это внимания. Они посчитали, что неполнота систем не имеет непосредственного влияния на их работу.
Далее >>>
|
|
