Оглавление
Диагональная лемма
-
Диагональная лемма Геделя
- Лемма утверждает, что в любой теории первого порядка, способной представлять все примитивно-рекурсивные функции, существует предложение, эквивалентное самому себе.
- Предложение, эквивалентное самому себе, называется фиксированной точкой операции, присваивающей классу эквивалентности предложения класс эквивалентности его доказуемого эквивалента.
- Доказательство леммы основано на функции, представляющей вычислимые функции, и замене формул в теории на формулы, эквивалентные их доказуемым эквивалентам.
-
История и связь с другими работами
- Лемма названа “диагональной” из-за сходства с диагональным аргументом Кантора.
- Рудольф Карнап первым доказал общую лемму о самореференции, предшествующую диагональной лемме Геделя.
- Диагональная лемма тесно связана с теоремой Клини о рекурсии и имеет схожие доказательства.
-
Важность и приложения
- Диагональная лемма является ключевым инструментом в теории доказательств и играет важную роль в понимании неполноты формальных систем.
- Она используется для доказательства теорем о неполноте Геделя и в других областях логики и математики.