Комбинаторная природа математического доказательства*

 

В.В. Целищев

 

* В работе представлены результаты исследований, поддержанных Российским научным гуманитарным фондом (грант № 01–03–00131) и Интеграционным проектом № 125 Сибирского отделения РАН.

 

 

«Математическое» и «философское» понятия доказательства

 

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

Прекрасным введением в подобного рода обсуждение природы доказательства будет довольно пространный пассаж из замечательной работы Ф. Девиса и Р. Херша «Математический опыт», в котором описывается беседа профессора математики и студента. Эта беседа дает прекрасное представление о том, что понимают под доказательством «работающие» математики.

 

"Студент: Сэр, что такое математическое доказательство?

Профессор: Как, вы не знаете этого? На каком курсе вы учитесь?

Студент: Третий год аспирантуры.

Профессор: Невероятно! Доказательство – это то, что я делаю на доске перед вами в аудитории три раза в неделю на протяжении всех трех лет! Вот что такое доказательство.

Студент: Извините, сэр, мне следует объясниться. Я специализируюсь в философии, а не в математике, и я никогда не посещал ваших лекций.

Профессор: Ну, в любом случае у вас же был какой-то курс математики. Вы знакомы с доказательством основной теоремы анализа или основной теоремы алгебры?

Студент: Я видел некоторые аргументы в геометрии и алгебре, которые называются доказательствами. Но я спрашиваю вас не о примерах доказательства, а об определении доказательства. Иначе откуда могу я знать, что пример является верным?

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

Студент: В самом деле? Это просто поразительно! Я слушал лекции по анализу и алгебре, по топологии и никогда не видел таких доказательств.

Профессор: О, конечно, никто на самом деле не проделывает этого. Это заняло бы бесконечное время. Вы просто показываете, что могли бы сделать это, и этого вполне достаточно.

Студент: Но даже такого понимания нет в моих учебниках и лекциях. Так что же получается – математики на самом деле не приводят доказательств?

Профессор: Конечно, у математиков есть доказательства! Если теорема не доказана, ее просто нет.

Студент: Тогда что же такое доказательство? Если оно связано с формальным языком и преобразованием формул, тогда никто ничего не доказывает. И что, для того чтобы что-то доказать, нужно уже знать все о формальных языках и формальной логике?

Профессор: Конечно, нет! Чем меньше этого добра вы знаете, тем лучше для вас. Все эти вещи – абстрактная чепуха.

Студент: Тогда что же на самом деле есть доказательство?

Профессор: Ну, это аргумент, который убеждает тех, кто знает предмет.

Студент: Тех, кто знает предмет? Тогда определение доказательства субъективно, оно зависит от конкретной личности. Перед тем, как я решу, является ли нечто доказательством, мне надо решить, а кто тут эксперты. Какое это имеет отношение к доказываемой вещи?

Профессор: Нет, нет, нет. Тут нет ничего субъективного, Каждый знает, что такое доказательство. Надо просто читать определенные книги, слушать лекции компетентных математиков, и в результате вы поймете, что такое доказательство.

Студент: Вы уверены?

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

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

Профессор: Если не я, то кто же еще?" [1].

 

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

Более недавним примером является спор по поводу компьютерных доказательств (скажем, доказательство теоремы о четырех красках). Если в споре интуиционистов и формалистов разногласия касаются того, какого рода логика может использоваться в качестве орудия доказательства, то в случае компьютерных доказательств речь идет уже о том, что такого рода доказательства выводят нас за пределы собственно математики. И как раз тут перекидывается мостик между двумя аспектами понимания доказательства – математическим и философским: компьютерное доказательство не признается «настоящим» доказательством по причине того, что оно, полностью удовлетворяя формальным критериям доказательства, абсолютно выходит за пределы «человеческих» критериев доказательства – обозримости, интуитивного постижения и др. Тем самым мы получаем довольно известный лозунг: У нас есть решение проблемы четырех красок, но является ли это математикой?

Интуитивное постижение доказательства, его обозримость и тому подобные аспекты являются скорее психологическими обстоятельствами, которые на протяжении веков размышлений над природой математического доказательства эксплицировались философскими категориями. Среди таких категорий важное место занимают тесно переплетенные между собой концептуальные различения априорного и апостериорного, необходимого и контингентного, аналитического и синтетического. Последние две пары концепций связаны с другими различениями: определенность и неопределенность, постижимость и непостижимость. Экспликация понятия доказательства является не единственным средством в попытке придать большее содержание понятию доказательства. Большое хождение имеют метафоры, что, впрочем, является обычным делом в научной практике. Данная статья посвящена описанию некоторых таких экспликаций и метафор.

 

 

Априорные утверждения и доказательство

 

Априорное познание заключается в том, что некоторые факты, касающиеся внешнего мира, становятся нам известными путем чистого размышления, без обращения к опыту. Тезис о том, что математическое знание базируется на доказательстве, принадлежит направлению, называемому математическим априоризмом. В его основе лежит отрицание важности психологических рассмотрений для понимания сути природы доказательства. Ф. Китчер анализирует в этой связи два представления о доказательстве. Первое из них он называет структуралистским [2]. Доказательство представляет собой, с этой точки зрения, лингвистическую конструкцию, некоторую последовательность предложений данного формального языка; членами последовательности являются либо аксиомы системы, либо результат преобразований аксиом или предыдущих утверждений согласно определенным правилам системы.

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

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

В такое понимание природы доказательства неявно входит несколько посылок, имеющих следующую структуру [3]:

 

(1) Имеется класс утверждений А и класс правил вывода Р, такие что:

a) каждый член А есть базисное априорное утверждение;

b) каждый член Р есть правило, сохраняющее априорность;

c) каждое утверждение стандартной математики либо является последним членом последовательности, все члены которой принадлежат А, либо получается из предыдущих членов согласно одному из правил Р.

 

Эта структура позволяет дать классификацию целого ряда философских позиций в отношении доказательства. В частности, Китчеру удалось показать неадекватность априористской концепции доказательства. Действительно, представление об априорности доказательств встречается с рядом трудностей, которые хорошо известны из математической практики. Во-первых, известно много случаев, когда в принятом математическим сообществом доказательстве обнаруживаются ошибки. Например, при доказательстве А. Уайлсом теоремы Ферма на одном из этапов, когда теорема представлялась доказанной, им же была обнаружена ошибка. Во-вторых, многие доказательства требуют довольно много времени для их получения в ясном виде. В-третьих, длинные доказательства необозримы. Хао Ван в статье «Процесс и существование в математике» приводит пример такого рода: если доказательство теоремы занимает 200 страниц, каждая из которых не представляет особых проблем для постижения аргументации, но увязывание между собой отдельных понятых аргументов являет собой непреодолимую трудность, то можно ли считать эти 200 страниц доказательством? Все эти обстоятельства вряд ли свидетельствуют в пользу априорности доказательств, если иметь в виду обычный смысл априорности (к вопросу об обычном смысле мы вернемся позднее).

Если принять во внимание, что структура (1) есть пример применения математической индукции, возражения против априорности математического доказательства приводят к следующим трем возможным вариантам: (i) индуктивный аргумент принимается наряду с возражениями против априоризма; (ii) индуктивный аргумент принимается, а возражения против априоризма отбрасываются; (iii) индуктивный аргумент отвергается. В последних двух случаях мы имеем противоположные выводы: (ii) влечет, что (1) достаточно для установления математического априоризма, а (iii) влечет, что (1) недостаточно для установления априоризма. В случае (i) отвергается полностью утверждение (1).

При отказе от индуктивного аргумента мотивом является то обстоятельство, что индукция правдоподобна при малых числах. Китчер называет такую картину доказательства «Decay Picture»: в этой схеме фигурирует специальный вид вывода, при котором доверие к истинности посылок не меньше, чем доверие к выводу. Более точно, если уровень доверия в посылках не превышает определенный порог, то доверие к заключению также не превышает этот порог. Заметим, что обсуждение возможности вывода ведется тут в эпистемологических терминах доверия к утверждениям. В данном случае это вполне оправданно. Так, Р. Нозик приводит следующий пример. Предположим, что некто по какой-то причине не принимает самого простого из логических правил вывода modus ponens. Как убедить его принять логическое правило и какие средства убеждения при этом допустимы (крайний случай – лагерь по перевоспитанию, замечает Нозик) [4]? В любом случае речь идет об эпистемологических процедурах. Если иметь в виду превышение некоторого порога доверия к выводу, то можно сказать, что такой вывод сохраняет априорность в процессе логического вывода. Но степень доверия (или порог доверия) является в значительной степени эмпирически зависимой процедурой, так что математический априоризм в данном случае неоправдан.

Что касается ошибки, то здесь можно отметить следующее. С эпистемологической точки зрения некоторое утверждение может считаться априорно известным, несмотря на то что оно может оказаться ошибочным. Во-первых, это может быть ошибка, которую просто просмотрели при доказательстве соответствующего предложения. Во-вторых, в некоторых случаях мы верим в математическое утверждение, хотя не имеем на то полных оснований, но на основании такой веры полагаем его априорно известным. Даже вычисления, которые следуют определенному алгоритму, могут содержать ошибки. Наконец, многие математические утверждения, известные как априорные утверждения, фактически являются ошибочными, так как формулируются исходя из априорных оснований, но без должных ограничений. Выход за пределы этих ограничений означает нарушение сохранения априорности. Аргумент от ошибки вряд ли можно отбросить, как это предполагается в возможном варианте (ii), так что и здесь математический априоризм не проходит.

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

Декарт полагал, что первые принципы, известные априори, являются исходным пунктом дедукции. В ходе длинных доказательств эти первые принципы могут выпасть из сферы внимания. Для спасения математического априоризма Декарт предлагает картину, которую Китчер называет «Storage Picture» [5]. Правило VII «Правил для руководства ума» гласит: «Чтобы придать науке полноту, надлежит все, что служит нашей цели, вместе и по отдельности обозреть в последовательном и нигде не прерывающемся движении мысли и охватить достаточной и упорядоченной энумерацией. Соблюдение того, что здесь предполагается, необходимо, чтобы отнести к числу достоверных те истины, которые… непосредственно невыводимы из первых и очевидных принципов. Ведь это иногда делается при помощи столь длинного ряда выводов, что когда мы достигаем данных истин, нам нелегко припомнить весь путь, который привел нас к этому; поэтому мы и говорим, что слабость памяти нужно возместить неким последовательным движением мысли… Это движение нигде не должно прерываться… как только пропускается нечто даже самое малое, тотчас разрывается цепь и рушится вся достоверность заключения» [6]. Избавлением от ограниченности человеческого ума и несовершенства памяти является правило XI: «После того как мы усмотрели несколько простых положений, полезно, если мы выводим из них нечто иное, обозреть их в последовательности и нигде не прерывающемся движении мысли, поразмышлять над их взаимными отношениями и отчетливо представить сразу столь многие из них, сколь это возможно: ведь таким образом и наше познание становится гораздо более достоверным…» [7]

По сути дела, Декарт предлагает применение некоторого рода запоминающего устройства, к которому можно обращаться по мере необходимости в ходе длинного доказательства. Естественно, что прежде всего «запоминаются» (лучше сказать «сохраняются», если продолжать компьютерную метафору) первые принципы, или априорные утверждения. Но если вновь обратиться к эпистемологическим критериям априорности, тогда ясно, что включение в процесс вывода запоминающего устройства усложняет элементарный процесс сохранения априорности, который лежит в основе логического вывода. У нас нет больше того эпистемологического доверия к получаемым в ходе вывода утверждениям. Но это означает возможность (i), при которой математический априоризм невозможен. Рассмотренные две картины показывают трудности, которые априористский подход к математическому доказательству должен преодолеть в случае длинных доказательств, и приведенное краткое обсуждение показывает, что эти трудности преодолеть нелегко.

При разговоре о математическом априоризме следует упомянуть, что в отношении термина «априорный» в литературе существует значительная путаница, объясняемая как историческими, так и концептуальными причинами. Прежде всего, часто в работах по философии математики и логики термины «априорный», «необходимый» и «аналитический» рассматриваются как синонимы. Эта тенденция, как полагают многие исследователи, восходит к деятельности Венского кружка, и в значительной степени проникла в сознание новых поколений философов благодаря «восхитительной вульгаризации», осуществленной А.Дж. Айером в 1936 г. в книге «Язык, истина, логика» [8]. В ней Айер соединил все три термина в «хорошо перемешанный сироп», объяснив априорное в терминах аналитического [9]. С тех пор в аналитической философии эти три понятия практически взаимозаменяемы. Как замечает Я. Хакинг, такое отождествление было понятно, пока позитивистская программа пользовалась успехом [10]. Но стараниями В. Куайна различение аналитического и синтетического стало сомнительным, и, как следствие, стало сомнительным также отождествление аналитического с необходимым и априорным [11]. Далее, относительно недавние работы С. Крипке показали, что некоторые утверждения, выражающие необходимое тождество, могут быть известны апостериорно [12]. Эта ситуация привела к тому, что математический априоризм стал еще более сомнительной доктриной, и если есть какой-то исходный смысл в априоризме, который мыслился тождественным аналитичности, тогда остается рассмотреть, в каком смысле математическое доказательство является аналитическим.

 

 

Аналитический аргумент

 

Понятие аналитического суждения, как и его предполагаемые синонимы – априорное суждение и необходимое суждение, имеет долгую историю. Далее мы следуем превосходному изложению происхождения понятий, представленному Я. Хакингом [13]. Рассуждение априори до Лейбница означало рассуждение от причины к следствию, или же от первопричины к следствиям. Рассуждение апостериори означало размышление от известных следствий к причинам. Идеи анализа и синтеза использовались в античности для описания методов доказательства и исследования, и есть параллель между дихотомией априорное/апостериорное и дихотомией анализ/синтез. Анализ является априорным в том смысле, что это ход рассуждения от начала к концу; синтез является апостериорным, потому что это ход рассуждения от конца к началу. Таким образом, различения подобного рода касались не знания, а способов размышления. Впоследствии такое схоластическое понимание подверглось изменению в работах Лейбница и Канта. Уже Кант понимал априорное суждение как суждение, независимое от опыта. Возможно, что смешение априорного с аналитическим, свойственное позитивистам, ближе к схоластической интерпретации этих понятий.

Лейбниц имел теорию, согласно которой каждое необходимое утверждение может быть доказано конечным числом шагов из тождеств и определений. Современным языком можно было бы сказать, что Лейбниц использовал синтаксическое понятие доказательства, которое, согласно его замыслу, могло объяснить понятие логической необходимости. Сам Лейбниц исходил из теологических рассмотрений, в которых понятие необходимости играло традиционно важную роль. «Есть ли такие суждения, что даже Бог не мог бы создать такой мир, в котором они ложны? В отличие от Декарта Лейбниц принадлежал к большинству мыслителей, которые полагали, что есть некоторые суждения, такие что даже всемогущее существо не может фальсифицировать их. Отсюда возникает проблема примирения необходимости со всемогуществом. Теория доказательства Лейбница решила эту проблему. Каждое логически необходимое суждение есть неявное тождество…» [14]. Итак, синтаксическое доказательство должно быть аналитическим аргументом – в схоластическом смысле этого термина. И тут важно понять, что такая доказуемость за конечное число шагов совпадает со знаменитым лейбницевским понятием истинности во всех возможных мирах. В некотором смысле эта идея Лейбница реализована в доказательстве полноты для узкого исчисления предикатов. Таким образом, Лейбниц хотел показать, что все необходимые истины математики являются аналитическими, т.е. доказуемыми из тождеств путем подстановки определений.

В известном смысле точка зрения Лейбница была возрождена Г. Фреге, потому что для него аналитическими истинами являются истины, которые могут быть доказаны логическими законами и определениями. Однако понятие аналитического суждения гораздо шире. Полезно привести классификацию аналитических суждений, представленную Я. Хинтиккой [15].

 

I.        Аналитические истины являются истинными благодаря лишь значению терминов, которые содержатся в них (аналитическая истина как концептуальная истина).

I(a). Аналитическая истина основывается лишь на определениях терминов.

I(b). Аналитическая истина объемлет определения и их логические следствия.

I(c). Аналитические истины – это истины, которые могут быть доказаны лишь посредством логических законов и определений (Фреге).

I(d). Аналитические истины объемлют истины логики и все истины, которые могут быть сведены к ним подстановкой синонимов вместо синонимов (Куайн).

 

II.      Значимый аргументный шаг является аналитическим, если заключение есть подпредложение одной из его посылок.

II(a). Аргумент является аналитическим, если его шаги аналитичны в смысле II.

II(b). Значимое доказательство F1 из предложения F0 аналитично, если все предложения, входящие в доказательство в качестве предварительных шагов этого доказательства, являются подпредложениями либо предложения F1, либо предложения F0.

 

Перед тем как продолжить классификацию смыслов аналитического утверждения (и доказательства), предложенную Хинтиккой, целесообразно обратиться к важному понятию, которое используется многими исследователями при анализе понятия доказательства. Понять доказательство – значит сделать две альтернативные вещи. Во-первых, воспринять его психологически, – сюда входит обозримость, ощущение проникновения в суть (то, что называется более точно инсайтом, прозрением и т.д.), прямое постижение аргумента. Именно эта сторона доказательства, по заверению Я. Хакинга, является причиной того, что некоторые философы были буквально больны математикой [16]. Во-вторых, понять доказательство – это значит устанавливать последовательность его шагов таким образом, что каждый последующий шаг недвусмысленно вытекает из предыдущих. Это понятие связано с чисто комбинаторными операциями, и никак не связано с концепцией априорного утверждения. В самом очищенном виде идея комбинаторного способа мышления присутствует в понятии вычисления, на котором мы остановимся позднее.

Как видно из предыдущего изложения, комбинаторное понимание доказательства полностью соответствует синтаксическому пониманию, мотивированному теологическими соображениями. Если же обратиться к более прозаическим соображениям, то мы должны иметь при комбинаторном понимании некоторого рода единицу комбинаторных преобразований, и естественным кандидатом на эту роль выглядит понятие индивида. То есть комбинаторные преобразования делаются с отчетливо очерченными объектами, каковыми являются индивиды математического дискурса. В критериях аналитичности I комбинаторный подход отсутствует вовсе, а в критериях II он имеет место в неявном виде (подпредложение предложения подразумевает наличие некоторого элементарного образования, которое подходит на роль индивида).

Для того чтобы придать доказательству четкий комбинаторный характер, нужно, чтобы логическое исчисление, скажем первого порядка, было основано на понятии индивида. Стандартная логика первого порядка располагает универсумом рассмотрения, который является областью квантификации, но не связывает вхождение квантора с вхождением одного индивида. Я. Хинтикка предложил такое представление логики первого порядка, которая реализует, с нашей точки зрения, идею комбинаторного доказательства в логике. Это представление связано с аппаратом дистрибутивных нормальных форм в логике первого порядка [17].

Наипростейший способ объяснения понятия дистрибутивной нормальной формы в пропозициональной логике состоит в обращении к дизъюнктивной нормальной форме, которая есть дизъюнкция определенных конъюнкций – конституент. Конституента представляет собой конъюнкцию различных атомарных формул pi, каждая из которых либо утверждается, либо отрицается. Общий ее вид –

 

? i = 1k pi .

 

Ясно, что может быть 2k таких конституент. Если заменить атомарные формулы пропозиционального исчисления атомарными предикатами Px, тогда произвольный предикат представляется в виде

 

? i = 1k Pix .

 

Некоторое возможное положение дел характеризуется существованием объектов, обладающих некоторыми из таких сложных предикатов, и несуществованием объектов, обладающих остальными предикатами из перечня 2k­предикатов, т.е.

 

+- (Ех) ? i = 1k Pix .

 

Если обозначить выражения, утверждающие существование объектов, через Сi, тогда возможное положение дел в мире представляется следующей формулой:

 

(Ех) С1х & (Ex) C2x & …& (Ex) Cnx & (?x) (C1x ?C2x ?…? Cnx) .

 

Максимальное число цепи кванторов, таких что область действия внешнего из них включает все остальные объекты, область действия второго включает оставшиеся объекты и т.д., называется глубиной формулы в дистрибутивной нормальной форме. Интуитивное содержание этого параметра связано с числом индивидов, рассматриваемых в их взаимоотношениях. Предположение, что использование квантора предопределяет рассмотрение одного индивида, является стандартной частью понимания логики первого порядка. Понятия квантификации, предикации, экстенсиональности онтологии образуют единую структуру [18]. Квантификация открытого предложения предполагает в качестве области значений переменных объекты, указываемые сингулярными терминами, которые должны указывать на один и только один объект.

При переходе к двуместным и более предикатам структура конституент становится весьма сложной. Одним из следствий этой сложности является возникновение тривиальной и нетривиальной противоречивости конституент [19]. Возможность появления противоречивых конституент усматривается из следующих соображений. Дистрибутивные нормальные формы в пропозициональной логике и кванторной теории с одной переменной дают разрешающую процедуру: если формула имеет нормальную форму, она выполнима; формула логически истинна, если и только если ее нормальная форма содержит все конституенты с теми же параметрами. По теореме Черча, исчисление предикатов первого порядка неразрешимо. Из структуры дистрибутивной нормальной формы ясно, что неразрешимость обусловлена наличием противоречивых конституент.

Сама процедура разрешимости эквивалентна проблеме обнаружения противоречивых конституент. Противоречивость конституент бывает тривиальной и нетривиальной. Тривиальная противоречивость усматривается непосредственно согласно некоторым критериям. Нетривиальная противоречивость представляет собой более сложное явление. Различие между тривиальной и нетривиальной непротиворечивостью конституент является, пожалуй, наиболее важным аспектом той концептуализации, которая лежит в основе предложенной Хинтиккой новой дихотомии аналитическое / синтетическое. Дело в том, что, конституента глубины d описывает систематическую процедуру выбора некоторой последовательности из d индивидов. Кроме того, существует четкая процедура расширения конституенты с увеличением ее глубины. Каждая из этих последовательностей изображает возможный ход событий. Нетривиальная противоречивость есть скрытая противоречивость, для обнаружения которой конституента должна быть расширена до некоторой (не определенной заранее) глубины. Действительно, если было бы возможно заранее определить глубину, на которой устраняются все нетривиально противоречивые компоненты формулы, это означало бы существование процедуры разрешимости для логики первого порядка. Хинтикка показал, что для каждой противоречивой конституенты глубины d существует е, такое что на глубине e + d противоречивость конституенты будет обнаружена. Но каково это е, нам неизвестно.

Аппарат дистрибутивных нормальных форм позволяет ввести целый ряд критериев аналитичности доказательства нетривиальными следствиями. Третий смысл аналитичности связан с понятием индивида и прямо отвечает комбинаторному смыслу доказательства.

 

III. Общезначимый аргументный шаг аналитичен, если он не вводит в рассмотрение новые индивиды.

III(a). Аналитический аргумент не может вести от утверждения о существовании некоторого индивида к утверждению о существовании другого индивида.

III(b). Общезначимый аргумент аналитичен, если он не увеличивает числа индивидов, рассматриваемых в отношении друг к другу.

III(c). Общезначимый аргументный шаг аналитичен, если глубина заключения аргумента не больше глубины по крайней мере одной из посылок.

III(d). Аргумент аналитичен, если все его шаги аналитичны в смысле III(с).

III(e). Общезначимое доказательство предложения F1 из предложения F0 аналитично, если ни одно из предложений, входящих в доказательство в качестве промежуточных шагов, не имеет большей глубины, чем глубина F0 и F1.

 

Индивиды и комбинаторное доказательство

 

Рассмотрим критерий III(a). Пусть имеется некоторая логическая истина, записанная в дистрибутивной нормальной форме. Если некоторые из ее конституент противоречивы, их устранение не отражается на тавтологическом характере логических истин. Но устранение противоречивых конституент существенно связано в обсуждаемым нами смыслом аналитичности. Каждая конституента имеет вид

 

(Ех) С1х & (Ex) C2x & …& (Ex) Cnx & (?x) (C1x ?C2x ?…? Cnx) .

 

Противоречивость этой конституенты позволяет перейти к отрицанию данного утверждения:

 

[(Ех) С1х & (Ex) С2х & …& (Ex) Cnx] ? (?x) (?С1х & ? С2х &…& ?Cnx) .

 

То есть если существуют индивиды вида С1, С2, …, Cn, то существует индивид, не принадлежащий ни к одному из этих индивидов, обладающий отличными от них свойствами как результат логической необходимости. Таким образом, если определенная логическая истина содержит противоречивые конституенты, значит, при ее доказательстве в рассуждение вводились утверждения о существовании индивидов, не содержащиеся в посылках.

Пусть имеется доказательство предложения q из предложения p. Если противоречивость конституенты нетривиальна, тогда увеличение числа рассматриваемых индивидов происходит в середине доказательства, в его промежуточных шагах. Осознание этого обстоятельства приводит нас к наиболее интересному уточнению аналитичности дедуктивного шага. Доказательство предложения q из предложения p аналитично, если на каждом промежуточном шаге рассматривается не больше индивидов, чем в предложениях p или q. Поскольку увеличение числа индивидов нарушает аналитичность доказательства, вполне естественно предположить, что доказательство при этом является синтетическим. Интересно в этой связи то обстоятельство, что большая часть логических истин получается в результате аналитических доказательств [20]. Только некоторые истины логики, существенно выражающие противоречивость конституент, синтетичны.

Для иллюстрации аналитичности математического доказательства прибегнем к логическому аналогу математической теоремы. Это полезно, поскольку, говоря об аналитичности, мы все время имели в виду логические истины, в то время как исходной темой была аналитичность доказательства математических утверждений. В качестве математического утверждения возьмем числовую формулу, содержащую сложение и умножение, скажем 2 + 2 = 4. Для того чтобы найти соответствующую этому утверждению теорему логической теории первого порядка, введем вспомогательное понятие – нумерически определенный квантор. Пусть имеется некоторое свойство F. Утверждение, что не существует объектов со свойством F, равносильно утверждению о пустоте класса, определяемого свойством F, т.е. ~ (Ех) Fx. Запишем это выражение в виде (E0x) Fx. Далее, можно определить выражение (E1x) Fx – «имеется точно один объект х, такой что х обладает свойством F» как сокращение выражения

 

(Ex) [Fx & (E0y) (Fy & y ? x)] ,

 

т.е. «существует объект х, такой что х обладает свойством F, и не существует объекта у, отличного от х, обладающего свойством F». Подобным же образом определяется выражение (E2x) Fx – «имеется точно два объекта, обладающих свойством F», определяемое через

 

(Ex) [Fx & (E1y) (Fy & y ? x)] .

 

и т.д. Суть определений подобного рода состоит в следующем: чтобы некоторое свойство было присуще n + 1 объектам, оно должно быть присуще объекту, отличному от тех n объектов, которым оно уже присуще, т.е. (En+1x) Fx есть сокращение для

 

(Ex) [Fx & (En) (Fy & y ? x)].

 

Таким образом, выражение (E2x) Fx, записанное только с помощью логических символов, соответствует арифметическому объекту, а именно, числу 2. Тогда математическому утверждению 2 + 2 = 4 соответствует логическое выражение – логическая истина –

 

[(E2x) Fx & (E2x) Gx & (?x) ? (Fx & Gx)] ? (E4x) (Fx ? Gx).

 

Доказывается это так. Распишем сначала выражение (E2x) Fx в виде

 

(Ex) (Ey) [Fx & Fy & x ? y & (?u) (Fu & (u = x) ? (u = y)].

 

Соответственно, выражение (E4x) (Fx ? Gx) можно представить в виде

 

               (Ex) (Ey) (Ez) (Ew) [(Fx ? Gx) & (Fy ? Gy) & (Fz ? Gz) & (Fw ? Gw) &

(S4)        & (x ? y) & x ? z) & (x ? w) & (y ? z) & (y ? w) & (z ? w)]

               (?u) [(Fu ? Gu) ? ((u = x) ? (u =y) ? y = z) ? (u = w))].

 

Из анализа выражений (E2x) Fx и (E2x) Gx ясно, что существуют объекты x, y, z и w такие, что

 

(S1) (Fx & Fy & x ? y) & (?u) (Fy ? ((u = x) ? (u = y))

 

и

 

(S2) (Gz & Gw & z ? w) & (?u) (Gy ? ((u = z) ? (u = w)).

 

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

 

(S3) (?x) ? (Fx & Gx),

 

которое гарантирует, что эти объекты различны. В целом содержание (S1), (S2) и (S3) равносильно содержанию (S4).

Таким образом, структура доказательства может быть представлена в виде

 

[(S1) & (S2) & (S3)] ? (S4).

 

Если это предложение доказано, это означает, что (S4) является логическим следствием посылок (S1), (S2) и (S3). Глубина предложений (S1) и (S2) в расписанном виде равна 3, глубина предложения (S3) равна 1, а глубина предложения (S4) равна 5. Поскольку глубина заключения больше глубины любой из посылок, доказательство 2 + 2 = 4 является не аналитическим и, значит, если принимать дихотомию аналитическое / синтетическое, синтетическим в приведенном выше смысле аналитического (и синтетического). Посылки (S1) и (S2), будучи представлены в дистрибутивной нормальной форме, являются цепью кванторов. Процесс доказательства (S4) состоит главным образом в соединении (S1), (S2) и (S3) в более длинную цепь кванторов, представляющую собой (S4).

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

 

Примечания

1. Davis Ph., Hersh R. The mathematical experience. – Penguin Press, 1981. – P. 39, 40.

2. См.: Kitcher Ph. The nature of mathematical knowledge. – Oxford Univ. Press, 1984. – P. 36.

3. Ibid. – P. 39.

4. См.: Nozick R. Philosophical explanations. – Harvard Univ. Press, 1984.

5. См.: Kitcher Ph. The nature of mathematical knowledge. – P. 44.

6. Декарт Р. Сочинения. – М.: Мысль, 1989. – Т. 1. – С. 97.

7. Там же. – С. 110.

8.

9. Эти оценки вклада А. Айера приведены в работе Hacking I. What mathematics has done to some and only some philosophers // Mathematics and Necessity / Ed. by T. Smiley. – Oxford Univ. Press, 2000. – P. 114.

10. См.: Hacking I. What mathematics has done... – Р. 118.

11. См.: Quine W.V.O. Two dogmas of empiricism.

12. См.: Kripke S. Naming and necessity.

13. См.: Hacking I. What mathematics has done… – P. 107 et al.

14. Ibid. – P. 104.

15. См.: Hintikka Ja. Logic, language games and information. – Clarendon Press, 1973. – P. 148, 149.

16. См.: Hacking I. What mathematics has done... – Р. 98.

17. См.: Хинтикка Я. Дистрибутивные нормальные формы в первопорядковой логике // Хинтикка Я. Логико-эпистемологические исследования. – М.: Прогресс, 1980. – С. 105–157.

18. Эта точка зрения убедительно представлена в работе Wallace J. On the frame of reference // Synthese. – 1970. – V. 22. – P. 117–150.

19. Подробнее см.: Целищев В.В. Философские вопросы семантики возможных миров. – Новосибирск: Наука, 1977.

20. См.: Hintikka Ja. Kant vindicated // Hintikka Ja. Logic, language games and information. – P. 174–198.

 

Институт философии и права

СО РАН, г. Новосибирск

 

Tselishchev, V.V. Combinatoric nature of mathematical proof.

The notion of mathematical proof is considered from several points of view. First of all, common sense of proof is compared with working mathematician’s conviction. Futher, more philosophical position, called mathematical apriorism, is presented and rejected. The combinatorial notion of mathematical proof is considered in connection with operation on individuals. The logical apparatus used in discussion is related to distributive normal forms. The basic conclusion consists in presenting some sense of analyticity that conforms intuitive view of proof as combinatorial activity.