Теоремы Гёделя о неполноте

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

Definition

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

Scope

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

Core questions

• Как синтаксис теории кодируется в самой арифметике?
• Как диагональная лемма порождает предложение, утверждающее свою собственную недоказуемость?
• Почему достаточно сильная непротиворечивая теория должна быть неполной?
• Почему такая теория не может доказать свою собственную непротиворечивость?

Key theories

Диагональная лемма

Для любой формулы с одной свободной переменной существует предложение, которое теория доказывает как эквивалентное этой формуле, применённой к собственному коду предложения, что обеспечивает контролируемую самореференцию.

Первая теорема о неполноте

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

Вторая теорема о неполноте

Формализация доказательства первой теоремы внутри теории показывает, что теория доказывает свою собственную непротиворечивость только в том случае, если она сама является противоречивой, поэтому непротиворечивая теория не может установить свою собственную непротиворечивость.

Clinical relevance

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

History

Гёдель объявил о теоремах о неполноте в 1930 году и опубликовал их в 1931 году, опровергнув ожидание того, что арифметика может быть полностью и самодостаточно аксиоматизирована. Россер усилил гипотезы в 1936 году, а одновременная теорема Тарского о неопределимости истины дала тесно связанный ограничительный результат.

Key figures

• Kurt Goedel
• Alfred Tarski
• J. Barkley Rosser
• David Hilbert

Seminal works

• smith2013
• godel1931
• boolos2007

Frequently asked questions

Означают ли теоремы о неполноте, что математика противоречива?

Нет. Они говорят, что любая отдельная непротиворечивая и достаточно сильная формальная система является неполной и не может подтвердить свою собственную непротиворечивость. Они не ставят под сомнение истинность математики, а лишь ограничивают охват любой одной аксиоматической системы.

Означает ли неполнота, что некоторые истины непознаваемы?

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