?

Log in

об одной замечательной мысли (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

об одной замечательной мысли (математическое) [дек. 16, 2009|03:14 pm]
Anatoly Vorobey
Несколько дней назад поучаствовал в одной дискуссии по-английски, о теоремах о неполноте Гёделя. Всплыли некоторые старые мысли и впечатления из этой области... несколько лет об этом не думал.

В частности, зашел разговор об учебниках логики, и меня искренне поразила чья-то рекомендация учебника Манина. Учебник логики Манина - для меня в каком-то смысле анти-книга: она написана в таком стиле, и составлена в таком порядке, который вызывает у меня отвращение. Она эклектична там, где эклектичность противопоказана, прыгает беспорядочно от темы к теме, пропускает самое интересное во многих темах, а в других местах погружается в скучные и ненужные технические подробности, которых можно было бы избежать. Если бы я по ней учил логику, то в голове образовался бы полный конфуз, убежден. При этом я понимаю, конечно, что есть люди, которые ее любят и считают ее лучшим учебником. И многие из этих людей наверняка все знают и понимают лучше меня. Это можно как-то объяснить, если постараться (в смысле, я могу себе это психологически объяснить), но все равно остается ощущение того, что это очень странно.

Моя идеальная книга для изучения мат. логики - A Mathematical Introduction to Logic Эндертона. Она не очень много покрывает материала; если надо больше, то Shoenfield хорош. Конкретно по теме теорем о неполноте - Goedel's Incompleteness Theorems Smullyan'а.

Именно у Смаллиана в свое время я отметил аргумент, который регулярно с тех вспоминаю как образец блестящей мысли, задним умом совершенно, казалось бы, очевидной, но до тех пор мне нигде не встречавшейся (и сам конечно до этого не додумался).

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

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

Но - тут начинается главная мысль Смаллиана - это на самом деле совершенно нелогичная точка зрения. С какой стати нам сокрушаться о том, что теория множеств не может доказать свою непротиворечивость? Поставим вопрос так: предположим, теория множеств может доказать свою непротиворечивость. Сейчас мы знаем, что из этого по теореме Геделя следует ее противоречивость, но предположим, что теоремы Геделя бы не было, и мы доказали с помощью теории множеств ее собственную непротиворечивость. Добавляет ли это нам уверенности в непротиворечивости теории множеств? Конечно, нет! Ведь все равно остается верным тот факт, что если в ней есть противоречие, она доказывает что угодно, включая собственную непротиворечивость!

Если задуматься, то доказательство непротиворечивости системы внутри самой системы в любом случае - и в отсутствие теорем Геделя - не добавляет нам никакой уверенности в том, что система непротиворечива. Потому что в этом конкретном вопросе доверять самой системе нельзя. Она соврет - недорого возьмет.

Значит ли это, что вторая теорема о неполноте бесполезна? Разумеется, нет. Кроме применений ее собственно в математической логике, и с философской точки зрения она важна. Просто надо понять, что важен не тот факт, что теория множеств, например, не может доказать свою непротиворечивость, а то, что из этого следует, что более слабыми финитарными методами тем более нельзя доказать непротиворечивость теории множеств. Достаточно сложные системы включают в себя то, что мы понимаем под финитарными методами: грубо говоря, вся математика, которую можно сделать, манипулируя только конечными объектами. Вторая теорема о неполноте показывает, что мы никогда не сможем доказать непротиворечивость этих систем, пользуясь только такими методами (если эти системы действительно непротиворечивы), и это действительно хоронит программу Гильберта и лишает нас возможности когда-либо доказать строго и несомненно, что здание нашей математики построено не на песке.
СсылкаОтветить

Comments:
From: (Anonymous)
2009-12-16 01:29 pm
"Но если система непротиворечива, то вторая теорема о неполноте говорит, что этот факт о себе она доказать не может."
поэтому нельзя доказать отсутствие бога? ))
(Ответить) (Thread)
[User Picture]From: avva
2009-12-16 01:59 pm
нет.
(Ответить) (Parent) (Thread)
[User Picture]From: ibsorath
2009-12-16 01:41 pm
Великолепно.

Смаллиан вообще замечательный, и серьёзные работы, и более популярные, те самые, "Эта книга никак не называется" и т.д.

(Ответить) (Thread)
[User Picture]From: rednyrg721
2009-12-16 01:46 pm
Возможно, немного не в тему, но у fregimus последние посты посвящены популярному изложению теорем Гёделя:
http://fregimus.livejournal.com/80970.html
http://fregimus.livejournal.com/81395.html.
(Ответить) (Thread)
[User Picture]From: e2pii1
2009-12-29 05:17 pm
Спасибо, интересно. Там уже 5 частей написано - о доказательстве, и о применении теоремы в разных областях.
(Ответить) (Parent) (Thread)
[User Picture]From: yoksel_moksel
2009-12-16 01:48 pm
В то время, как противоречивая система может доказать всё, что угодно, от признания непротиворечивой системы невозможности доказать собственную непротиворечивость даже веет каким-то благородством.
(Ответить) (Thread)
From: komprendre
2009-12-16 01:54 pm
И в результате, в публичном диспуте, у глашатая непротиречивой системы (и прочих бла-ародных) нету никаких шансов.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: akopyan
2009-12-16 02:09 pm
Ведь все равно остается верным тот факт, что если в ней есть противоречие, она доказывает что угодно, включая собственную непротиворечивость!
Торможу, а из этого не следует ли вторая теорема Гёделя?
(Ответить) (Thread)
[User Picture]From: avva
2009-12-16 02:23 pm
Нет; если "есть противоречие" это A, а "доказывает собственную непротиворечивость" это B, то:

- процитированная вами строка это A->B, и это тривиальное утверждение

- конечно, это эквивалентно not-B -> not-A, и это тоже тривиально

- вторая теорема Геделя это not-A -> not-B, и это сложно (и требует помимо прочего всякие дополнительные условия).
(Ответить) (Parent) (Thread) (Развернуть)
From: komprendre
2009-12-16 02:15 pm
Замечательно - и одновременно так просто.
Рассуждение по сути (то-есть для математика) в одну строчку но мимо нее так легко пройти )
(Ответить) (Thread)
[User Picture]From: diana_shipilova
2009-12-16 02:35 pm
Смаллиан замечательный математик. К сожалению, насколько мне известно, на русский язык переводились только его научно-популярные работы (или я ошибаюсь?).
(Ответить) (Thread)
[User Picture]From: avva
2009-12-16 02:37 pm
По-моему, да. По крайней мере мне неизвестно о переводах серьезных трудов.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-12-16 02:42 pm
Если задуматься, то доказательство непротиворечивости системы внутри самой системы в любом случае - и в отсутствие теорем Геделя - не добавляет нам никакой уверенности в том, что система непротиворечива. Потому что в этом конкретном вопросе доверять самой системе нельзя. Она соврет - недорого возьмет.

На самом деле все даже еще веселее. Если есть хотя бы одно утверждение, назовем его Ы, которое теория Ю не может доказать, то мы спасены — она не может быть противоречивой (потому что противоречивые теории доказывают все утверждения). Дело за малым — доказать утверждение ЫЫ, говорящее, что теория Ю не может доказать Ы. Положим, мы получили доказательство ЫЫ (в рамках теории Ю или за ее пределами). Но можем ли мы верить этому доказательству? Не можем, потому что для этого нам нужна непротиворечивая система, а ее у нас пока нет...
(Ответить) (Thread)
[User Picture]From: avva
2009-12-16 02:48 pm
Да, так и есть.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2009-12-16 02:51 pm
Честно говоря, про связь между отчаянием от теоремы Геделя и тегами я не понял :)

"Эх..." я написал в том смысле, что да, надо теги сделать, не хватает сил это организовать, а как подумаю, что по-хорошему надо стагировать весь архив на 8 лет в прошлое...
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: nechaman
2009-12-16 02:50 pm
Здорово!
(Ответить) (Thread)
From: misha2
2009-12-16 03:19 pm
Учебник Манина, на мой взгляд, это не совсем учебник. Скорее, он объясняет логику математикам-неспециалиcтам, которые учебник и так читали, но не поняли в чем состоят идеи.
(Ответить) (Thread)
[User Picture]From: make4um
2009-12-16 03:48 pm
я бы только добавил - что именно факт невозможности доказательства непротиворечимости и вселяет в нас определённый оптимизм в отношении теории множеств... а от понятия "оптимизм" уже осталось полшага всего до понятия fuzzy logic ;о)
(Ответить) (Thread)
[User Picture]From: freedom_of_sea
2009-12-16 04:30 pm

описка у вас

Просто надо понять, что важен не тот факт, что теория множеств, например, не может доказать свою (НЕ)противоречивость,
(Ответить) (Thread)
[User Picture]From: avva
2009-12-16 04:37 pm

Re: описка у вас

Спасибо! исправляю.
(Ответить) (Parent) (Thread)
[User Picture]From: cousin_it
2009-12-16 04:31 pm
Очень красивая мысль, и новая для меня. Спасибо.
(Ответить) (Thread)
[User Picture]From: angerona
2009-12-16 05:30 pm
+1
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-12-16 05:18 pm
еще можно пофантазировать на тему — что будет, если работать с теориями, в которых противоречие запрятано слишком глубоко. например, формула (1=2) выводима, но длина кратчайшего вывода не меньше 22010.
(Ответить) (Thread)
From: ext_72902
2009-12-16 10:27 pm
Я как-то попробовал расписать полностью доказательство Бурбаки того факта, что x=x. В общем, на втором листе A4 мелким почерком мне надоело и я это бросил.
(Ответить) (Parent) (Thread)
[User Picture]From: mini_max
2009-12-16 06:09 pm
А мне, та тоненькая книга Юрия Ивановича нравилась, она как раз в его духе: легкая и призывающуюся к уже существующим знаниям и аналогиям.
(Ответить) (Thread)
[User Picture]From: pollak
2009-12-16 06:49 pm
А вы Манина другие книжки читали? Если да, то как они Вам? Многие ведь считают его чуть ли не эталоном вкуса и стиля в гм, скажем "математическом письме" (да и вообще в науке) .
(Ответить) (Thread)
[User Picture]From: avva
2009-12-19 11:07 pm
Нет, не читал.
(Ответить) (Parent) (Thread)
[User Picture]From: santfil
2009-12-17 02:36 pm

теорема Гёделя

Мысль Смаллиана (в другой транскрипциии - Шмульяна) интересна и, как и теорема Гёделя, и две первые "Критики" Канта, подтверждает необходимость веры там, где доказательства невозможны. Дайте, avva, ссылки на "учебник логики" Манина (вы ведь не имели в виду популярные книги "Доказуемое и недоказуемое" и "Вычислимое и невычислимое"?) и, что важнее, на работу Смаллиана, где высказана эта мысль.
(Ответить) (Thread)
[User Picture]From: avva
2009-12-17 05:47 pm

Re: теорема Гёделя

Лекции по математической логике Манина (еще есть английский перевод).
Godel's Incompleteness Theorems Smullyan'а.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: sowa
2009-12-18 02:14 am
А книга Манина не для Вас написана. У нее даже подзаголовок был "для математиков".
(Ответить) (Thread)
[User Picture]From: alexeybobkov
2009-12-18 06:25 pm
противоречивая система доказывает любое утверждение, истинное или ложное, включая утверждение о своей непротиворечивости
А как это доказывается?
(Ответить) (Thread)
[User Picture]From: avva
2009-12-19 11:07 pm
(A & not-A)=>B - тавтология.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-12-23 12:48 pm
А давайте предположим еще, что если теория множеств может доказать свою непротиворечивость, то если она непротиворечива, в ней нет противоречий и всего, что угодно, она доказать не может.
(Ответить) (Thread)
From: (Anonymous)
2009-12-23 01:00 pm
fix что хотел сказать
А давайте предположим еще, что если теория множеств может доказать свою непротиворечивость, то в ней нет противоречий и всего, что угодно, она доказать не может.
(Ответить) (Parent) (Thread)