Теоремы Гёделя и их философия

Кодируя самореференцию в арифметику, Гёдель доказал, что любая непротиворечивая формальная система, достаточно богатая для арифметики, содержит истинные утверждения, которые она не может доказать.

Definition

Первая теорема Гёделя о неполноте утверждает, что любая непротиворечивая, эффективно аксиоматизированная формальная система, способная выражать элементарную арифметику, содержит истинное утверждение, которое она не может ни доказать, ни опровергнуть; вторая теорема утверждает, что ни одна такая система не может доказать свою собственную непротиворечивость.

Scope

Эта тема охватывает теоремы Гёделя о неполноте и их философскую интерпретацию. Она рассматривает технику арифметизации (нумерация Гёделя) и диагональную лемму, которая конструирует самореферентное утверждение «Я недоказуемо»; первую теорему (такие системы неполны) и вторую (они не могут доказать свою собственную непротиворечивость); а также спорные философские применения теорем — утверждения о пределах формализма и программы Гильберта, а также аргументы Лукаса-Пенроуза о том, что человеческий разум превосходит любой алгоритм.

Core questions

• Как нумерация Гёделя позволяет арифметике говорить о своих собственных доказательствах?
• Что именно устанавливают теоремы о неполноте и для каких систем?
• Что означали теоремы для программы Гильберта и логицизма?
• Показывают ли теоремы, что разум превосходит машины?

Key concepts

• нумерация Гёделя (арифметизация)
• диагональная лемма
• гёделевская формула
• первая и вторая теоремы о неполноте
• программа Гильберта
• непротиворечивость и омега-непротиворечивость

Key theories

Неполнота через диагонализацию

Гёдель арифметизирует синтаксис таким образом, что формула может выражать свою собственную недоказуемость; полученное утверждение истинно (если система непротиворечива), но недоказуемо, что устанавливает неполноту, а вторая теорема показывает, что сама непротиворечивость недоказуема внутри системы.

Аргумент Лукаса-Пенроуза

Лукас, исходя из теоремы Гёделя, утверждает, что поскольку человек может видеть истинность гёделевской формулы любой непротиворечивой машины, моделирующей разум, то разум не может быть такой машиной; этот аргумент широко оспаривается.

History

Гёдель доказал теоремы о неполноте в 1931 году, решительно ограничив программу Гильберта по доказательству полноты и непротиворечивости математики финитными средствами. Результаты нашли отклик в философии математики и сознания, при этом Лукас (1961), а затем Пенроуз сделали антимеханистические выводы, что вызвало обширную критическую литературу.

Debates

Опровергают ли теоремы механистический взгляд на разум?

Вопрос о том, правомерно ли аргумент Лукаса-Пенроуза выводит из неполноты, что человеческое математическое прозрение превосходит любой алгоритм, или же он заходит слишком далеко, предполагая, что мы всегда можем знать свою собственную непротиворечивость и распознавать соответствующую гёделевскую формулу.

Key figures

• Kurt Godel
• David Hilbert
• J. R. Lucas
• Roger Penrose
• Peter Smith

Seminal works

• godel1931
• smith2013

Frequently asked questions

Означает ли теорема Гёделя, что математика «сломана»?

Нет. Это означает, что ни одна непротиворечивая формальная система не может доказать каждую арифметическую истину, и ни одна не может подтвердить свою собственную непротиворечивость изнутри. Математика прекрасно функционирует; теоремы вместо этого устанавливают принципиальный предел того, что может быть достигнуто любой фиксированной аксиоматической системой, опровергая надежду на единое, полное, самоподтверждающееся основание.