?

Log in

No account? Create an account

Previous Entry | Next Entry

Гедель 4

1  2  3   4   5  6  7

XI. Математические последствия

Хорошо или плохо для математики открытие Геделя? С одной стороны, надежды математиков на самообоснованность математики, на существование единственной верной математической системы, которую можно «открывать», но не «выдумывать», испарились. Можно подумать, что это плохо. С другой же стороны, оказалось, что математика не сводится к механической процедуре доказательств, что в математике всегда останется место для нового не автоматизированного творчества. Проще говоря — математика не заканчивается, как она бы завершилась с изобретением полностью механизированной математической системы. Математики без работы не останутся, и их, в отличие от рабочих на сборочном конвейере, не заменят роботы. И это как будто бы хорошо.

Диалектическую сущность открытия Геделя хорошо сформулировал К. Подниекс в [2]:

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

Итак, с философской точки зрения, теорема Геделя радикально поменяла математические воззрения на основания математики.Математика не может быть одновременно полной и непротиворечивой. Противоречие — много худший дефект теории, чем неполнота: она сводит на нет всю доказательную силу теории. Поэтому математика, какой мы ее разрабатываем, не должна быть противоречивой. Если мы придем к противоречию, нам придется отступить на несколько шагов назад, чтобы изъять из системы те положения, аксиомы, которые к этому противоречию привели. Наша непротиворечивая математика всегда будет неполной. Но каковы же практические — то есть, важные для ежедневной математической работы — последствия этой неполноты?

По всей видимости, они невелики. В некоторых областях математики, наиболее абстрактных, например, теории категорий, они более ощутимы, и на них необходимо оглядываться; в других же геделевы утверждения являются сами по себе предметом математического поиска. Они достаточно редки, и их обнаружение само по себе является достижением. Например, относительно недавно было доказано, что теорема Гудстайна является геделевым утверждением арифметики, и не может быть в ней доказана. Гудстайн описывает особую манипуляцию над числами; утверждение его состоит в том, что, с какого бы числа мы ни начали, повторяя алгоритм конечное число раз, мы в конце концов получим в результате ноль. Хоть эти действия можно проделать в ЭА для наперед взятого числа, доказательство того, что так будет для любого, лежит за пределами ЭА.

Кроме того, в математике имеется определенное число подобных «наблюдательных» предположений. В некотором смысле, это сближает математику с естественными науками: мы делаем наблюдения над поведением математических объектов, затем строим гипотезы, пытаемся построить теории, подвести солидные доказательства под эти гипотезы — и это не всегда получается. С другой стороны, это подкрепляет, в определенном смысле, платонистический-пифагорейский подход к математике. Математика, какой мы ее придумали, существует и ведет себя как объект, поведения которого мы не понимаем до конца, и открываем его свойства — хоть это сложное поведение и задано простыми правилами, которые следуют из еще более простых, установленных произвольно.

Часто бывает, что математика отставляет недоказанность некоторых утверждений в сторону, и развивается, будто они были доказаны. Так же ведут себя и естественные науки. Все, что мы знаем в физике, так же «доказано» наблюдениями и сведением их в теории. В физике нет аксиом, есть только наблюдения. Математика, разумеется, предпочитает аксиомы, но в некоторых случаях и принимает — предварительно, в силу своей строгости — недоказанные утверждения, от которых можно отталкиваться и двигаться вперед.

В число таких недоказанных утверждений входят не только «курьезы» — интересные теоремы, из утверждений которых не делается никаких дальнейших выводов, к каким, например, относится Великая теорема Ферма, доказанная всего несколько лет назад. Существуют гораздо более «серьезные» теоремы, с помощью которых математики доказывают новые теоремы. В их число входит гипотеза Римана.

Гипотеза Римана говорит о значениях нулей комплексной дзета-функции Римана. Разъяснение этой гипотезы лежит далеко за пределами нашего повествования, но нам, безусловно, интересно, что происходит в математике вокруг нее. Доказательства этой гипотезы не найдено уже 150 лет. Говорят, будто, когда у Гильберта спросили, что он сделает, если заснет и проснется через 500 лет, он ответил, что первый вопрос, который он задаст, будет о том, была ли доказана гипотеза Римана. Дело в том, что гипотеза Римана используется во многих доказательствах, как если бы это была доказанная теорема. В этом ее отличие от теоремы Ферма, которая была и остается просто интересным фактом о числах, но не используется в доказательствах так широко. Институт Клэя назначил приз в 1 миллион долларов США за доказательство Римановой гипотезы, потому что ее доказательство чрезвычайно важно для арифметики, в частности, в области факторизации чисел на простые сомножители. Выходит, что и криптостойкость современных шифров зависит от верности предположения Римана, и, таким образом, она оказывает влияние на материальный мир через ежедневные компьютерные операции в нем.

Гипотеза эта доказана для некоторых частных случаев, и, кроме того, разумеется, производились масштабные компьютерные проверки ее истинности. Проверено огромное число (около 10 триллионов!) нулей дзета-функции, и все их значения соответствуют утверждению гипотезы. Общее же число этих нулей бесконечно велико, поэтому полная компьютерная их проверка невозможна. Требуется доказательство, но его нет.

Что будет с математикой, если выяснится, что гипотезу Римана нельзя доказать в существующих даже самых сильнх, самых внешних математических теориях? Конечно, можно сделать ее утверждение аксиомой, просто объявить, что, раз она недоказуема, то мы будем полагать ее истинной по положению. Но, кроме этого, возможен и другой путь. Мы могли бы объявить гипотезу ложной, и считать ее ложность аксиомой15. В принципе, это не вызвало бы в математике противоречий, но, тем не менее, такое положение шло бы вразрез с уже накопленным математическим знанием. Здесь опять проявляется некоторое сходство математики и естественных наук — сходство, возникающее от того, что думают над теориями в этих науках люди, пользуясь родственными мыслительными системами. Мы наблюдаем, что гипотеза Римана верна для огромного количества случаев, и предполагаем — очень уверенно предполагаем! — что она верна всегда в построенной нами системе математики. Поэтому, если нам случится полагать ее аксиомой, расширяющей эту систему, то естественным будет положить аксиомой ее утверждение, а не его отрицание.

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

1  2  3   4   5  6  7
__________________________________
15. Например, так: существует хотя бы один нетривиальный нуль дзета-функции, вещественная часть которого отлична от 1/2.

Tags:

Comments

( 26 comments — Leave a comment )
nataly_demina
Dec. 21st, 2009 08:47 am (UTC)
Доброе утро, а не хотите об этом статью написать для "Полит.ру" или газеты "Троицкий вариант". Мне кажется, что у Вас почти готовый текст есть.
fregimus
Dec. 24th, 2009 11:44 am (UTC)
Не думал об этом, спасибо, хорошая идея. Пока еще не дописал даже; посмотрим, как еще получится. Комментарии очень хорошие, надо будет хорошенько переработать.
gdt
Dec. 21st, 2009 10:38 am (UTC)
Может, вы не видели, у avva была серия постов про Гудстайна, вот последний: http://avva.livejournal.com/249897.html
fregimus
Dec. 21st, 2009 04:19 pm (UTC)
Нет, не видел, спасибо.
bdag_med
Dec. 21st, 2009 11:26 am (UTC)
"Что будет с математикой, если выяснится, что гипотезу Римана нельзя доказать в существующих даже самых сильнх, самых внешних математических теориях?" - непонятно. На момент этого выяснения будет известно, что список таких сильных теорий исчерпан?
fregimus
Dec. 21st, 2009 04:34 pm (UTC)
Согласен, не очень хороший пример: ведь теория, в которой она формулируется, не имеет необходимого свойства «фундаментальности» (не может выражать арифметики). Но, даже если бы речь шла и об арифметической теории, вопрос бы не снимался. Во-первых, мы не можем знать, что все теории (арифметические) уже исчерпали себя. Во-вторых, мы не знаем, противоречивы они или нет — мы только надеемся, что нет.

Но само рассуждение все-таки не неверное — я же не строю предположений о том, как именно выяснится. Просто такая математико-логическая фантазия о том, что будет, если вдруг это выяснится — пусть мы и знаем даже, что по иным причинам этого не произойдет.
bdag_med
Dec. 22nd, 2009 08:52 am (UTC)
Тогда не очень понятно, почему это фантазия :), чем это отличается от ситуации сейчас. Как я понимаю, сейчас известно, что гипотеза Римана не доказывается при помощи некоторых методов, а про другие методы это неизвестно. Более того, с ней работают как с аксимомой.
fregimus
Dec. 22nd, 2009 08:57 am (UTC)
Доказательства не найдено, но это не значит, что она не доказывается в существующих теориях. Мы же говорим о принципиальной выводимости утверждений в теории — некоторые арифметические утверждения выводимы в арифметике, другие недоказуемы в принципе (а предположение Римана не арифметическое утверждение, к тому же).
bdag_med
Dec. 22nd, 2009 09:10 am (UTC)
Да, я понимаю, я потому и писал о "методах". Но все равно мне кажется, что ситуации (1) "во всех имеющихся у нас теориях ГР формально невыводима" и (2) "у нас нет доказательства ГР" аналогичны, потому что в (1) есть компонент "у нас есть". И то и другое описывает "человеческое" положение дел.
Извините, если чушь порю, ни разу не математик :)
fregimus
Dec. 24th, 2009 11:50 am (UTC)
Нет-нет, отнюдь не чушь, хорошее наблюдение. Формальная невыводимость в (1) всегда под вопросом, потому что доказать ее можно только в метатеории. Из (2) поэтому (1) не следует.
kobak
Dec. 21st, 2009 02:09 pm (UTC)
С одной стороны, надежды математиков на самообоснованность математики, на существование единственной верной математической системы, которую можно «открывать», но не «выдумывать», испарились. [...] Математика не может быть одновременно полной и непротиворечивой.

Я думаю, что это неверно. Теорема Геделя нисколько не противоречит математическому платонизму. Книжку Подниекса я когда-то читал, его философские взгляды не разделяю, также как не разделяет их и (насколько я понимаю) большинство работающих математиков. Спорить об этом сейчас не хочется -- всё уже давно на эту тему сказано и написано, в том числе и в жж, где математик и убежденный платонист sowa много и подробно писал о логике и теореме Геделя. Эти разговоры несложно найти. Мне кажется, Вы пропагандируете неправильный (хотя и возможный) взгляд на эту тему.
fregimus
Dec. 21st, 2009 04:41 pm (UTC)
Да, спасибо, хорошо, что заметили. Я очень старался эту тему не затрагивать, а вот наступил, не углядел. Тут лучше мне было сказать о теориях, не о самой математике.
kobak
Dec. 21st, 2009 04:50 pm (UTC)
Да. На всякий случай, буквально в двух словах (чтобы не было разночтений): как мне кажется, "правильный" платонический взгляд на математику состоит в том, что математические объекты существуют независимо от людей, и что люди именно "открывают", а не "изобретают" математику. Теорема о неполноте, а также другие смежные результаты (в т.ч. и более простые: например, теорема Левингейма-Сколема -- привожу этот пример вслед за sowa) показывают главным образом, что аксиоматические системы неадекватны нашему математическому мышлению. Я когда-то придумал такую аналогию, которая мне кажется удачной: теорема Геделя сродни теореме о невозможности трисекции угла циркулем и линейкой. Они обе доказывают невозможность достичь какого-то результата определенными ограниченными средствами. Но это проблема не трисекции угла, это проблема циркуля и линейки.

Подниекс (если я правильно помню) пространно пишет о том, что теорема Геделя опровергает платонизм, но ведь это ерунда.
fregimus
Dec. 21st, 2009 05:08 pm (UTC)
Подниекс не пытается опровергнуть платонизм, насколько я понимаю. Об основаниях математики и своих взглядах на на них (далеких от мат. реализма) он пишет только во введении, а дальше во всех рассуждениях он говорит только, что мы не знаем, как «на самом деле». Не «никак», а «не знаем». Опровергать платонизм столь же продуктивно, как опровергать материализм, идеализм, христианство, атеизм или дзен, и Подниекс, мне кажется, это понимает.

Edited at 2009-12-21 05:10 pm (UTC)
palmas1
Dec. 21st, 2009 07:19 pm (UTC)
Спасибо большое.
fregimus
Dec. 21st, 2009 08:38 pm (UTC)
Пожалуйста. А покритиковать?
palmas1
Dec. 21st, 2009 11:50 pm (UTC)
Знаний не хватает покритиковать, я же не математик, в лучшем случае матфизик. Но теперь зато в общих чертах понятно, о чём теорема Гёделя.
fregimus
Dec. 22nd, 2009 12:06 am (UTC)
У меня не очень хорошо получилось очертить область ее применения. Пожалуй, напишу-ка я следующий кусочек о том, о чем ТГ не говорит.
auraz
Dec. 21st, 2009 11:53 pm (UTC)
очень хорошо!
(Deleted comment)
fregimus
Jan. 25th, 2010 01:09 am (UTC)
Спасибо, не знал. Мне казалось, что проверка Миллера как раз проста. (Через 30 лет после Рабина — это 2010, кстати, в этом году?)

Значит, вот это все уже больше неверно: “The extended Riemann hypothesis is far too complicated for us to explain here--but should it be proven, then we would have a very simple primality test. Until it is proven, we can at least expect that if n is composite, we should be able to find an a that shows it is composite (a witness) without searching "too long."”? Надо же, как жизнь убегает от учебников!
(Deleted comment)
fregimus
Jan. 25th, 2010 01:28 am (UTC)
Благодарю.
fregimus
Jan. 25th, 2010 07:10 am (UTC)
Нет, не понимаю. Критерий Миллера O(log^4(n)), но зависит от гипотезы Римана. В модификации Рабина O(log^3(n)), не зависит от гипотезы Римана, но вероятностный. AKS в лучшей модификации O(log^6(n)), то есть все-таки самый медленный алгоритм, но зато корректный. Если доказать г.Р., то критерий Миллера будет таким же корректным, как АКС, но быстрее. Чего я все-таки не понимаю?
(Deleted comment)
fregimus
Jan. 25th, 2010 08:19 pm (UTC)
Ага, теперь все, кажется, сходится.
( 26 comments — Leave a comment )