Теоремы Гёделя о неполноте
http://psilogic.livejournal.com/307089.html
Миф: Гёдель доказал, что нельзя доказать все
Миф состоит в том, что теоремы Гёделя применяют там, где их применять нельзя. Что именно доказал Гёдель (и его последователи)? Они доказали, что в аксиоматической системе, основанной на классическом исчислении предикатов и арифметике Пеано, существуют недоказуемые утверждения, и среди таких утверждений - непротиворечивость системы.
Пояснения к терминам:
"Аксиоматическая система" или коротко "аксиоматика" - система логических рассуждений, в которой есть аксиомы и правила вывода, и все утверждения выводятся строго на основе этих аксиом и правил, не прибегая к дополнительным средствам.
"Классическое исчисление предикатов" (КИП) - аксиоматическая система, описывающая основные логические операции: "и", "или", "не", а также предикаты и два квантора ("для всех" и "существует"). Это совсем не то же самое, что булева алгебра, привычная программистам, но некий ее "дальний родственник". Есть множество вариантов КИП по-разному построенных и в разной степени "навороченных". Вот, некий вариант используется в теореме Гёделя.
И сразу одна "неприятность": обычно в КИП используется та самая аксиома
A => (B => A).
"Арифметика Пеано" - это способ изложить арифметику в форме аксиоматики. Речь идет о самой обычной арифметике, которую проходят в школе, но тут попытка оформить ее как систему аксиом.
"Основанной на" - то есть, некая аксиоматика, в которой есть аксиомы КИП, аксиомы арифметики Пеано, и может быть еще какое-то количество аксиом, добавленных с некоторыми оговорками.
Что это может быть за система? Ну например, некая значительная часть математики, скажем, весь матанализ (дифференциальное и интегральное исчисление). Вот если попытаться выстроить "матан" именно как аксиоматическую систему на базе КИП и арифметики Пеано, то получится нечто (аксиоматизированный матан).
И это нечто не сможет доказать отсутствие противоречий в самом себе.
А еще что не сможет доказать? Про любую произвольную формулу нельзя сказать, можно ее доказать или нет, но вот по крайней мере отсутствие противоречий доказать нельзя.
Если хочется доказать непротиворечивость, придется создавать какую-то совсем принципиально иную систему, поскольку известно, что добавление новых аксиом не спасает.
Каково практическое применение этой теоремы вне математики? Похоже, что никакое. Вне математики строгие аксиоматические системы не используются. В естественных науках как метод доказательства применяется эксперимент, неполная индукция, разные нестрогие (по меркам математики) рассуждения, которые к аксиоматическим системам отношения не имеют.
Тем не менее, Гёделя постоянно поминают всуе. Обычно это происходит, когда кто-нибудь пытается обосновать свой "гносеологический пессимизм" (С) falcao. То бишь, заявить, что некую проблему невозможно решить или некое утверждение невозможно доказать. И дальше следует ссылка на Гёделя. Но то, что невозможно доказать согласно Гёделю, обычно не равно тому, что обсуждается. Создается впечатление, что Гёдель дал этим товарищам своего рода индульгенцию: право ставить клеймо "недоказуемо" на произвольно выбранные утверждения.
PS: У psilogic'а еще много умных мыслей в журнале - рекомендую!
.
Миф: Гёдель доказал, что нельзя доказать все
Миф состоит в том, что теоремы Гёделя применяют там, где их применять нельзя. Что именно доказал Гёдель (и его последователи)? Они доказали, что в аксиоматической системе, основанной на классическом исчислении предикатов и арифметике Пеано, существуют недоказуемые утверждения, и среди таких утверждений - непротиворечивость системы.
Пояснения к терминам:
"Аксиоматическая система" или коротко "аксиоматика" - система логических рассуждений, в которой есть аксиомы и правила вывода, и все утверждения выводятся строго на основе этих аксиом и правил, не прибегая к дополнительным средствам.
"Классическое исчисление предикатов" (КИП) - аксиоматическая система, описывающая основные логические операции: "и", "или", "не", а также предикаты и два квантора ("для всех" и "существует"). Это совсем не то же самое, что булева алгебра, привычная программистам, но некий ее "дальний родственник". Есть множество вариантов КИП по-разному построенных и в разной степени "навороченных". Вот, некий вариант используется в теореме Гёделя.
И сразу одна "неприятность": обычно в КИП используется та самая аксиома
A => (B => A).
"Арифметика Пеано" - это способ изложить арифметику в форме аксиоматики. Речь идет о самой обычной арифметике, которую проходят в школе, но тут попытка оформить ее как систему аксиом.
"Основанной на" - то есть, некая аксиоматика, в которой есть аксиомы КИП, аксиомы арифметики Пеано, и может быть еще какое-то количество аксиом, добавленных с некоторыми оговорками.
Что это может быть за система? Ну например, некая значительная часть математики, скажем, весь матанализ (дифференциальное и интегральное исчисление). Вот если попытаться выстроить "матан" именно как аксиоматическую систему на базе КИП и арифметики Пеано, то получится нечто (аксиоматизированный матан).
И это нечто не сможет доказать отсутствие противоречий в самом себе.
А еще что не сможет доказать? Про любую произвольную формулу нельзя сказать, можно ее доказать или нет, но вот по крайней мере отсутствие противоречий доказать нельзя.
Если хочется доказать непротиворечивость, придется создавать какую-то совсем принципиально иную систему, поскольку известно, что добавление новых аксиом не спасает.
Каково практическое применение этой теоремы вне математики? Похоже, что никакое. Вне математики строгие аксиоматические системы не используются. В естественных науках как метод доказательства применяется эксперимент, неполная индукция, разные нестрогие (по меркам математики) рассуждения, которые к аксиоматическим системам отношения не имеют.
Тем не менее, Гёделя постоянно поминают всуе. Обычно это происходит, когда кто-нибудь пытается обосновать свой "гносеологический пессимизм" (С) falcao. То бишь, заявить, что некую проблему невозможно решить или некое утверждение невозможно доказать. И дальше следует ссылка на Гёделя. Но то, что невозможно доказать согласно Гёделю, обычно не равно тому, что обсуждается. Создается впечатление, что Гёдель дал этим товарищам своего рода индульгенцию: право ставить клеймо "недоказуемо" на произвольно выбранные утверждения.
PS: У psilogic'а еще много умных мыслей в журнале - рекомендую!
.