Книги по разным темам Pages:     | 1 |   ...   | 15 | 16 | 17 | 18 | 19 |   ...   | 54 |

Стало быть, задача Цермело Ц - выбрать по элементу в каждом непустом подмножестве в U Ц - принимает следующий вид: для всякого булева многочлена найти точку, в которой он обращается в нуль, или доказать, что он тождественно равен единице. Более того, мы хотим решить эту задачу за время, полиномиальное относительно числа битов в коде для f.

Г К Это приводит к NP-полной (лмаксимально трудной) задаче, если записывать булевы многочлены, пользуясь следующей версией дизъюнктивной нормальной формы. Закодируем такую форму с помощью семейства u = {m; (S1, T1), Е, (SN, TN )}, m ; Si, Ti {1, Е, m}.

Битовый размер семейства u равен mN, а соответствующий булевский многочлен есть N fu := 1 + 1 + (1 + xk) xj.

i=1 kSi jTi Такая запись позволяет быстро проверить, входит ли данный элемент в соответствующее множество нулей. За это приходится платить:

единственность представления данного многочлена f места не имеет, и более того, проверка равенства fu = fv становится вычислительно сложной задачей.

В частности, даже следующее ослабление проблемы Цермело оказывается NP-полным и тем самым, на сегодняшний день, неприемлемо сложным: проверить, отличен ли от константы данный булевский многочлен, заданный в дизъюнктивной нормальной форме.

Цермеловская аксиома выбора вызвала в свое время бурную дискуссию математиков из разных стран, опубликованную в первом номере журнала Mathematische Annalen за 905 год. Значительная часть дискуссии была сосредоточена на психологии математического воображения и на проблеме надежности его плодов. Все время возникали каверзные вопросы наподобие такого: Откуда мы знаем, что в процессе рассуждения мы все время думаем об одном и том же множестве. Если считать, что по крайней мере часть процессов, происходящих в нашем мозгу, можно адекватно промоделировать конечными автоматами, то количественные оценки требуемых ресурсов, которые дает нам теория вычислимости за полиномиальное время, могут в какой-то момент оказаться полезными для нейрофизиологии, а следовательно, и для психологии.

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

Е наши результаты дают основания надеяться, что можно будет согласовать результаты самонаблюдений различных мате 4 Ч I. М матиков, показав, что даже в такой ограниченной области, как элементарная арифметика, разные задачи представляются в мозгу разными способами. Точная арифметика делает упор на лингвистическом представлении данных; она использует левые нижние лобные доли, отвечающие также за построение ассоциаций между словами. Символическая арифметика является культурным феноменом, специфическим для человека; ее развитие зависело от постепенного совершенствования систем счисления. Е Приближенная арифметика, напротив, не проявляет никакой зависимости от языка; она основывается в первую очередь на количественном представлении, реализованном в визуально-пространственных нейронных сетях левой и правой теменных долей ([4, c. 973]).

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

Приложение: некоторые определения. Для полноты напомним читателю основные определения, связанные с P-NP проблемой. Начнем с бесконечного конструктивного мира U в смысле [8]; например, это могут быть натуральные числа. Говорят, что подмножество E U принадлежит классу P, если оно разрешимо, а его характеристическая функция E вычислима за полиномиальное время для всякого x E.

Далее, подмножество E U принадлежит к классу NP, если оно является полиномиально ограниченной проекцией некоторого множества E U U, принадлежащего к классу P, т. е. если для некоторого многочлена G имеем u E существует (u, v) E, где |v | G(|u|) (через |v | обозначен размер элемента v). В частности, P NP.

Неформально включение E NP означает, что для всякого u E существует полиномиально ограниченное доказательство этого включения (а именно, вычисление значения E(u, v) для подходящего v);

при этом нахождение такого доказательства (т. е. элемента v) наивным перебором всех v, удовлетворяющих условию |v | G(|u|), может потребовать экспоненциального времени.

Подмножество E U называется NP-полным, если для любого другого множества D V, принадлежащего классу P, существует выГ К числимая за полиномиальное время функция f : V U, для которой -D = f (E), т. е. D(v) = E( f (v)).

Использованная здесь запись булевых многочленов объясняется и мотивируется доказательством NP-полноты; см., например, [6, з 2.6].

Гипотеза континуума и случайные переменные Мамфорд [ 0, c. 208] обсуждает следующее рассуждение Криса Фрейлинга [5], призванное убедить в том, что гипотеза континуума является лочевидно ложной.

Два игрока независимо друг от друга бросают стрелы в мишень. Если гипотеза континуума верна, то точки P на поверхности мишени можно вполне упорядочить таким образом, что для всякой P множество точек Q, удовлетворяющих условию Q < P (обозначим его SP), является счетным. Предположим, что первый и второй игроки попали в мишень в точках P1 и P2 соответственно.

Либо P1 < P2, либо P2 < P1. Предположим, что выполнено первое соотношение; тогда P1 лежит в счетном множестве SP. Поскольку два броска независимы, мы можем считать, что сначала бросал второй игрок, а затем первый. После броска второго игрока счетное множество SP зафиксировано. Однако всякое счетное множество измеримо и имеет меру нуль. То же рассуждение показывает, что вероятность того, что точка P2 попала в SP, также равна нулю. Стало быть, с вероятностью единица ни одно из этих двух событий не произошло, и это противоречит утверждению, что мишень представляет собой первый несчетный кардинал! Е Я полагаю, что это доказательство свидетельствует о том, что если построить математику на основе, включающей в себя случайные переменные, то гипотеза континуума окажется ложной и мы избавимся от одной из бессмысленных головоломок теории множеств3.

На самом деле работе Фрейлинга предшествовали работы Скотта и Соловея, в которых был переведен на язык логически случайных множеств коэновский метод форсинга, использованный для доказательства совместимости отрицания гипотезы континуума с аксиСтатья Мамфорда носит выразительное название Заря эры стохастичности. Дэвид заверил меня, что это заглавие не имеет отношения к принадлежащей Джамбаттиста Вико теории исторических циклов, которая в пересказе Гарольда Блума [ ] выглядит так. Джамбаттиста Вико в своей книге Новая наука описал исторический цикл, состоящий из трех фаз: теократической, аристократической и демократической.

Затем следует хаос, а за ним Ц - новый теократический век.

6 Ч I. М омами ЦермелоФренкеля. Эти работы показали, что случайные переменные действительно можно внести в список основных понятий и что случайные переменные можно осмысленно использовать.

Сам Поль Коэн в конце своей книги высказал предположение, что точка зрения, согласно которой гипотеза континуума лочевидно ложна, может стать общепринятой.

Однако же, если рассуждения Скотта и Соловея доказывают точную теорему про формальный язык теории множеств, то рассуждение Фрейлинга апеллирует непосредственно к нашей физической интуиции; точнее всего его было бы назвать мысленным экспериментом.

Этот эксперимент аналогичен по своей природе некоторым классическим мысленным экспериментам в физике, в которых, например, выводятся различные утверждения про динамику из невозможности создания вечного двигателя.

Сама идея использования мысленного эксперимента взамен логического вывода может рассматриваться как правополушарное соответствие левополушарным элементарным логическим операциям.

Аналогичную роль играют хорошие метафоры. Когда мы сравниваем возможности двух полушарий мозга, нас поражает то, что я в другом месте назвал врожденной слабостью метафор: метафоры противостоят попыткам построить систему на их основе. Можно только более или менее искусно сочетать разные метафоры, но полученное в итоге здание останется стоять или обрушится вне зависимости от того, истинно ли наше построение.

Физика дисциплинирует мысленные эксперименты, как поэзия дисциплинирует метафоры, но внутренняя дисциплина есть только у логики.

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

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

Я буду понимать лоснования математики несколько размыто: как общий термин для меняющегося со временем конгломерата правил и принципов, используемых при организации уже существующего Г К или заново создающегося корпуса математических знаний соответствующей эпохи. Иногда основания кодифицируются в авторитетном математическом тексте (пример: Начала Евклида); в другие эпохи интерес к основаниям проявляется в нервных вопросах к самому себе о смысле бесконечно малых, или о точном соотношении между числами и точками на действительной прямой, или, наконец, о природе алгоритмов. Как бы то ни было, основания математики в этом широком смысле Ц - это нечто, имеющее значение для работающего математика, связанное с некоторыми основными принципами его ремесла, но при этом не составляющее сути его работы.

В XX веке все основные тенденции в основаниях математики связаны с канторовскими языком и интуицией множеств.

Хорошо разработанный проект Бурбаки отшлифовал идею, согласно которой всякий математический объект (будь то группа, топологическое пространство, интеграл, формальный язык...) можно рассматривать как множество X с дополнительной структурой x. Эта идея появлялась во многих специализированных исследовательских проектах, от гильбертовских Оснований геометрии до колмогоровского отождествления теории вероятности с теорией меры.

Дополнительная структура x в паре = (X, x) Ц - это элемент другого множества Y, принадлежащего шкале, построенной из X с помощью стандартных операций и удовлетворяющей условиям (аксиомам), также формулируемым исключительно на языке теории множеств. Более того, природа элементов множества X несущественна:

биекция X X, отображающая x в x, порождает изоморфный объ ект = (X, x). Эта идея сыграла важнейшую роль в консолидации и прояснении математики; она привела к замечательным достижениям далеко за пределами группы Бурбаки. Поскольку она принята в тысячах математических статей, постольку можно попросту сказать, что язык математики Ц - это язык теории множеств.

Поскольку теория множеств очень легко формализуется, это позволило логикам выдвинуть и отстаивать тот тезис, что их нормативные принципы надлежит применять ко всей математике, а также переоценивать роль парадоксов бесконечного и теорем Гёделя о неполноте.

Тем не менее, этот факт сделал также возможным такие аутореферентные акты, как включение метаматематики в математику, в форме теории моделей. Теория моделей изучает специальные математические структуры Ц - формальные языки, Ц - рассматриваемые как математические объекты (множества со структурой: с законами композиции, выделенными элементами и т. п.), а также их интерпретации 8 Ч I. М в множествах. Такие поразительные открытия, как гёделевская теорема о неполноте арифметики, немного теряют в таинственности, как только приходит понимание, что это просто утверждения о том, что некоторая алгебраическая структура не является конечно порожденной относительно данных законов композиции.

Когда на следующем этапе исторического развития множества уступили место категориям, то сначала это выразилось лишь в том, что большее внимание стало уделяться морфизмам структур (в частности, изоморфизмам), нежели структурам как таковым. Да и категорию (малую) тоже, в конце концов, можно рассматривать как множество со структурой. Тем не менее, благодаря в первую очередь работам Гротендика и его школы по основаниям алгебраической геометрии, категории выдвинулись на передний план. Вот неполный список изменений в нашем понимании математических объектов, вызванных к жизни языком категорий. Напомним, что обычно объекты категории C множествами не являются, и их природа никак не уточняется: множество образуют только морфизмы HomC(X, Y ).

А. Объект X категории C можно отождествить с представляемым им функтором Y HomC(Y, X). Тем самым, если C Ц - малая категория, то первоначально бесструктурное X становится множеством со структурой. Эта внешняя, социологическая, характеризация математического объекта через взаимодействие с другими объектами той же категории, а не через его внутреннюю структуру, оказалась чрезвычайно полезной, например, во всех задачах, связанных с пространствами модулей в алгебраической геометрии.

Б. Коль скоро два изоморфных математических объекта обладают совершенно одинаковыми свойствами, не имеет значения, сколько именно попарно изоморфных объектов содержится в данной категории C. Неформально говоря, если у категорий C и D те же самые классы изоморфных объектов и морфизмы между их представителями, то эти категории следует рассматривать как эквивалентные.

Например, категория всех конечных множеств эквивалентна всякой категории конечных множеств, содержащей в точности по одному множеству каждой мощности 0, 1, 2, 3, Е Такая лоткрытость категории, рассматриваемой с точностью до эквивалентности, является существенной, например, для абстрактной теории вычислимости. Тезис Ч лучше всего понимать как ерча постулат, согласно которому существует открытая категория конструктивных миров Ц - конечных или счетных множеств со структурой и вычислимых морфизмов между ними, Ц - в которой всякий бесконечный объект изоморфен миру натуральных чисел, а морфизмы Г К соответствуют рекурсивным функциям (см. подробности в [8]). Существует очень много других интересных бесконечных конструктивных миров, задаваемых с помощью самых разнообразных внутренних структур: слова над данным алфавитом, конечные графы, машины Тьюринга и т. д. Все они, однако, изоморфны ввиду существования вычислимых нумераций.

Pages:     | 1 |   ...   | 15 | 16 | 17 | 18 | 19 |   ...   | 54 |    Книги по разным темам