![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНесколько дней назад поучаствовал в одной дискуссии по-английски, о теоремах о неполноте Гёделя. Всплыли некоторые старые мысли и впечатления из этой области... несколько лет об этом не думал.
В частности, зашел разговор об учебниках логики, и меня искренне поразила чья-то рекомендация учебника Манина. Учебник логики Манина - для меня в каком-то смысле анти-книга: она написана в таком стиле, и составлена в таком порядке, который вызывает у меня отвращение. Она эклектична там, где эклектичность противопоказана, прыгает беспорядочно от темы к теме, пропускает самое интересное во многих темах, а в других местах погружается в скучные и ненужные технические подробности, которых можно было бы избежать. Если бы я по ней учил логику, то в голове образовался бы полный конфуз, убежден. При этом я понимаю, конечно, что есть люди, которые ее любят и считают ее лучшим учебником. И многие из этих людей наверняка все знают и понимают лучше меня. Это можно как-то объяснить, если постараться (в смысле, я могу себе это психологически объяснить), но все равно остается ощущение того, что это очень странно.
Моя идеальная книга для изучения мат. логики - A Mathematical Introduction to Logic Эндертона. Она не очень много покрывает материала; если надо больше, то Shoenfield хорош. Конкретно по теме теорем о неполноте - Goedel's Incompleteness Theorems Smullyan'а.
Именно у Смаллиана в свое время я отметил аргумент, который регулярно с тех вспоминаю как образец блестящей мысли, задним умом совершенно, казалось бы, очевидной, но до тех пор мне нигде не встречавшейся (и сам конечно до этого не додумался).
Вторая теорема о неполноте говорит, что любая достаточно сложная аксиоматическая система, если она непротиворечива, не может доказать собственную непротиворечивость. Если в системе есть противоречие, то она может доказать вообще все угодно, включая собственную непротиворечивость, только толку в этом мало. Просто противоречивая система доказывает любое утверждение, истинное или ложное, включая утверждение о своей непротиворечивости. Но если система непротиворечива, то вторая теорема о неполноте говорит, что этот факт о себе она доказать не может.
Смаллиан пишет, что его раздражает то, как эту теорему часто представляют в виде чего-то, что лишает нас возможности убедиться в непротиворечивости. Возьмем для примера теорию множеств. Согласно второй теореме Геделя теория множеств не может доказать свою непротиворечивость, и часто именно об этом сокрушаются, рассуждая о том, как результаты Геделя определили предел тому, что мы можем надеяться доказать.
Но - тут начинается главная мысль Смаллиана - это на самом деле совершенно нелогичная точка зрения. С какой стати нам сокрушаться о том, что теория множеств не может доказать свою непротиворечивость? Поставим вопрос так: предположим, теория множеств может доказать свою непротиворечивость. Сейчас мы знаем, что из этого по теореме Геделя следует ее противоречивость, но предположим, что теоремы Геделя бы не было, и мы доказали с помощью теории множеств ее собственную непротиворечивость. Добавляет ли это нам уверенности в непротиворечивости теории множеств? Конечно, нет! Ведь все равно остается верным тот факт, что если в ней есть противоречие, она доказывает что угодно, включая собственную непротиворечивость!
Если задуматься, то доказательство непротиворечивости системы внутри самой системы в любом случае - и в отсутствие теорем Геделя - не добавляет нам никакой уверенности в том, что система непротиворечива. Потому что в этом конкретном вопросе доверять самой системе нельзя. Она соврет - недорого возьмет.
Значит ли это, что вторая теорема о неполноте бесполезна? Разумеется, нет. Кроме применений ее собственно в математической логике, и с философской точки зрения она важна. Просто надо понять, что важен не тот факт, что теория множеств, например, не может доказать свою непротиворечивость, а то, что из этого следует, что более слабыми финитарными методами тем более нельзя доказать непротиворечивость теории множеств. Достаточно сложные системы включают в себя то, что мы понимаем под финитарными методами: грубо говоря, вся математика, которую можно сделать, манипулируя только конечными объектами. Вторая теорема о неполноте показывает, что мы никогда не сможем доказать непротиворечивость этих систем, пользуясь только такими методами (если эти системы действительно непротиворечивы), и это действительно хоронит программу Гильберта и лишает нас возможности когда-либо доказать строго и несомненно, что здание нашей математики построено не на песке.
В частности, зашел разговор об учебниках логики, и меня искренне поразила чья-то рекомендация учебника Манина. Учебник логики Манина - для меня в каком-то смысле анти-книга: она написана в таком стиле, и составлена в таком порядке, который вызывает у меня отвращение. Она эклектична там, где эклектичность противопоказана, прыгает беспорядочно от темы к теме, пропускает самое интересное во многих темах, а в других местах погружается в скучные и ненужные технические подробности, которых можно было бы избежать. Если бы я по ней учил логику, то в голове образовался бы полный конфуз, убежден. При этом я понимаю, конечно, что есть люди, которые ее любят и считают ее лучшим учебником. И многие из этих людей наверняка все знают и понимают лучше меня. Это можно как-то объяснить, если постараться (в смысле, я могу себе это психологически объяснить), но все равно остается ощущение того, что это очень странно.
Моя идеальная книга для изучения мат. логики - A Mathematical Introduction to Logic Эндертона. Она не очень много покрывает материала; если надо больше, то Shoenfield хорош. Конкретно по теме теорем о неполноте - Goedel's Incompleteness Theorems Smullyan'а.
Именно у Смаллиана в свое время я отметил аргумент, который регулярно с тех вспоминаю как образец блестящей мысли, задним умом совершенно, казалось бы, очевидной, но до тех пор мне нигде не встречавшейся (и сам конечно до этого не додумался).
Вторая теорема о неполноте говорит, что любая достаточно сложная аксиоматическая система, если она непротиворечива, не может доказать собственную непротиворечивость. Если в системе есть противоречие, то она может доказать вообще все угодно, включая собственную непротиворечивость, только толку в этом мало. Просто противоречивая система доказывает любое утверждение, истинное или ложное, включая утверждение о своей непротиворечивости. Но если система непротиворечива, то вторая теорема о неполноте говорит, что этот факт о себе она доказать не может.
Смаллиан пишет, что его раздражает то, как эту теорему часто представляют в виде чего-то, что лишает нас возможности убедиться в непротиворечивости. Возьмем для примера теорию множеств. Согласно второй теореме Геделя теория множеств не может доказать свою непротиворечивость, и часто именно об этом сокрушаются, рассуждая о том, как результаты Геделя определили предел тому, что мы можем надеяться доказать.
Но - тут начинается главная мысль Смаллиана - это на самом деле совершенно нелогичная точка зрения. С какой стати нам сокрушаться о том, что теория множеств не может доказать свою непротиворечивость? Поставим вопрос так: предположим, теория множеств может доказать свою непротиворечивость. Сейчас мы знаем, что из этого по теореме Геделя следует ее противоречивость, но предположим, что теоремы Геделя бы не было, и мы доказали с помощью теории множеств ее собственную непротиворечивость. Добавляет ли это нам уверенности в непротиворечивости теории множеств? Конечно, нет! Ведь все равно остается верным тот факт, что если в ней есть противоречие, она доказывает что угодно, включая собственную непротиворечивость!
Если задуматься, то доказательство непротиворечивости системы внутри самой системы в любом случае - и в отсутствие теорем Геделя - не добавляет нам никакой уверенности в том, что система непротиворечива. Потому что в этом конкретном вопросе доверять самой системе нельзя. Она соврет - недорого возьмет.
Значит ли это, что вторая теорема о неполноте бесполезна? Разумеется, нет. Кроме применений ее собственно в математической логике, и с философской точки зрения она важна. Просто надо понять, что важен не тот факт, что теория множеств, например, не может доказать свою непротиворечивость, а то, что из этого следует, что более слабыми финитарными методами тем более нельзя доказать непротиворечивость теории множеств. Достаточно сложные системы включают в себя то, что мы понимаем под финитарными методами: грубо говоря, вся математика, которую можно сделать, манипулируя только конечными объектами. Вторая теорема о неполноте показывает, что мы никогда не сможем доказать непротиворечивость этих систем, пользуясь только такими методами (если эти системы действительно непротиворечивы), и это действительно хоронит программу Гильберта и лишает нас возможности когда-либо доказать строго и несомненно, что здание нашей математики построено не на песке.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-12-16 01:29 pm (UTC)поэтому нельзя доказать отсутствие бога? ))
no subject
Date: 2009-12-16 01:41 pm (UTC)Смаллиан вообще замечательный, и серьёзные работы, и более популярные, те самые, "Эта книга никак не называется" и т.д.
no subject
Date: 2009-12-16 01:46 pm (UTC)http://fregimus.livejournal.com/80970.html
http://fregimus.livejournal.com/81395.html.
no subject
Date: 2009-12-16 01:48 pm (UTC)no subject
Date: 2009-12-16 01:54 pm (UTC)no subject
Date: 2009-12-16 01:59 pm (UTC)no subject
Date: 2009-12-16 02:09 pm (UTC)Торможу, а из этого не следует ли вторая теорема Гёделя?
no subject
Date: 2009-12-16 02:15 pm (UTC)Рассуждение по сути (то-есть для математика) в одну строчку но мимо нее так легко пройти )
no subject
Date: 2009-12-16 02:23 pm (UTC)- процитированная вами строка это A->B, и это тривиальное утверждение
- конечно, это эквивалентно not-B -> not-A, и это тоже тривиально
- вторая теорема Геделя это not-A -> not-B, и это сложно (и требует помимо прочего всякие дополнительные условия).
no subject
Date: 2009-12-16 02:32 pm (UTC)http://elementy.ru/news/430970
no subject
Date: 2009-12-16 02:35 pm (UTC)no subject
Date: 2009-12-16 02:37 pm (UTC)no subject
Date: 2009-12-16 02:40 pm (UTC)no subject
Date: 2009-12-16 02:42 pm (UTC)На самом деле все даже еще веселее. Если есть хотя бы одно утверждение, назовем его Ы, которое теория Ю не может доказать, то мы спасены — она не может быть противоречивой (потому что противоречивые теории доказывают все утверждения). Дело за малым — доказать утверждение ЫЫ, говорящее, что теория Ю не может доказать Ы. Положим, мы получили доказательство ЫЫ (в рамках теории Ю или за ее пределами). Но можем ли мы верить этому доказательству? Не можем, потому что для этого нам нужна непротиворечивая система, а ее у нас пока нет...
no subject
Date: 2009-12-16 02:48 pm (UTC)no subject
Date: 2009-12-16 02:50 pm (UTC)no subject
Date: 2009-12-16 02:51 pm (UTC)"Эх..." я написал в том смысле, что да, надо теги сделать, не хватает сил это организовать, а как подумаю, что по-хорошему надо стагировать весь архив на 8 лет в прошлое...
no subject
Date: 2009-12-16 03:05 pm (UTC)no subject
Date: 2009-12-16 03:19 pm (UTC)no subject
Date: 2009-12-16 03:48 pm (UTC)описка у вас
Date: 2009-12-16 04:30 pm (UTC)no subject
Date: 2009-12-16 04:31 pm (UTC)Re: описка у вас
Date: 2009-12-16 04:37 pm (UTC)no subject
Date: 2009-12-16 05:18 pm (UTC)no subject
Date: 2009-12-16 05:30 pm (UTC)