Лекции сайта «РазныеРазности»
Вид материала | Лекции |
- Лекции сайта «РазныеРазности», 14661.74kb.
- Лекции сайта «РазныеРазности», 3039.99kb.
- Лекции сайта «РазныеРазности», 3031.54kb.
- Лекции сайта «РазныеРазности», 6860.77kb.
- Лекции сайта «РазныеРазности», 29870.4kb.
- Лекции Общие сведения о порядке разработки сайтов, 21.86kb.
- Анализ требований к проекту сайта (см табл. 9) 18 Согласование выработанной идеи проекта, 590.25kb.
- Название лекции: 2011. 08. 16. Йога Триада. Лекция, 430.35kb.
- Название лекции: 2011. 05. 17. Йога Триада. Лекция, 335.26kb.
- Название лекции, 2025.12kb.
В своем гёделевском доказательстве (в частности, в утверждении (М)) я использовал аргумент следующего вида: «Допущение о ложности X приводит к противоречию; следовательно, утверждение X истинно». Под «X» в данном случае следует понимать утверждение: «Вычисление Ck (k) не завершается». Это рассуждение относится к типу reductio ad absurdum; что же касается доказательства Гёделя в целом, то оно и в самом деле построено именно таким образом. Направление же в математике, называемое «интуиционизмом» (у истоков которого стоял голландский математик Л. Э. Я. Брауэр; см. [222] и НРК, с. 113— 116), отрицает возможность построения обоснованного доказательства на основе reductio ad absurdum. Интуиционизм возник приблизительно в 1912 году как реакция на некоторые сформировавшиеся к концу девятнадцатого — началу двадцатого века математические тенденции, суть которых сводится к следующему: математический объект можно полагать «существующим» даже в тех случаях, когда нет никакой возможности этот объект так или иначе воплотить в действительности. А надо сказать, что слишком вольное применение крайне расплывчатой концепции математического существования и впрямь приводит порой к весьма неприятным противоречиям. Самый известный пример такого противоречия связан с парадоксальным «множеством всех множеств, не являющихся членами самих себя» Бертрана Рассела. (Если множество Рассела является членом самого себя, то оно таковым не является; если же оно членом самого себя не является, то оно им, как ни странно, является! Подробнее см. §3.4 и НРК, с. 101.) Дабы противостоять общей тенденции, в рамках которой могут считаться «существующими» весьма вольно определенные математические объекты, интуиционисты полагают необоснованным математическое рассуждение, позволяющее делать вывод о существовании того или иного математического объекта на основании одной лишь противоречивости его несуществования. Доказательство существования объекта посредством reductio ad absurdum не дает абсолютно никаких оснований полагать, что упомянутый объект действительно можно построить. Каким же образом запрет на применение reductio ad absurdum может повлиять на наше гёделевское доказательство? Вообще говоря, совсем не может, по той простой причине, что reductio ad absurdum мы применяем, если можно так выразиться, наоборот, то есть противоречие в нашем случае выводится из допущения, что нечто существует, а не из обратного допущения. С интуиционистской точки зрения все выглядит совершенно законно: мы заключаем, что объект не существует, на том основании, что противоречие возникает как раз из допущения о существовании этого самого объекта. Предложенное мною гёделевское доказательство, по сути своей, является в интуиционистском смысле абсолютно приемлемым. (См. [222], с. 492.)
Аналогичные рассуждения применимы и ко всем прочим «конструктивистским» или «финитистским» направлениям в математике, о каких мне известно. Комментарий к возражению Q8 демонстрирует, что даже та точка зрения, согласно которой последовательность натуральных чисел нельзя считать «на самом деле» бесконечной, не освобождает нас от неизбежного вывода: для установления математической истины мы таки не пользуемся познаваемо обоснованными алгоритмами.
2.7. Некоторые более глубокие математические соображения
Для того чтобы лучше разобраться в значении гёделевского доказательства, полезно будет вспомнить, с какой, собственно, целью оно было первоначально предпринято. На рубеже веков ученые, деятельность которых была связана с фундаментальными математическими принципами, столкнулись с весьма серьезными проблемами. В конце XIX века — в значительной степени благодаря глубоко оригинальным математическим трудам Георга Кантора (с «диагональным доказательством» которого мы уже познакомились) — математики получили в распоряжение эффективные методы доказательства некоторых наиболее фундаментальных своих результатов, основанные на свойствах бесконечных множеств. Однако с этими преимуществами оказались связаны и не менее фундаментальные трудности, проистекающие из чересчур вольного обращения с концепцией бесконечного множества. Особо отметим парадокс Рассела (на который я вкратце ссылался в комментарии к Q9, см. также §3.4 — Кантор о нем также упоминает), обозначивший некоторые препятствия, подстерегающие склонных к опрометчивым умозаключениям. Тем не менее, все понимали, что если вопрос о допустимости тех или иных методов рассуждения продумать с достаточной тщательностью, то можно добиться очень и очень впечатляющих математических результатов. Проблема, по всей видимости, сводилась к отысканию способа, посредством которого можно было бы в каждом конкретном случае абсолютно точно определить, была ли соблюдена при выборе метода рассуждения «достаточная тщательность».
Одной из главных фигур движения, поставившего перед собой цель достичь этой точности, был великий математик Давид Гильберт. Движение окрестили формализмом; в соответствии с его основополагающим принципом, следовало однозначно определить все допустимые методы математического рассуждения в пределах той или иной конкретной области раз и навсегда, включая и те, что связаны с понятием бесконечного множества. Такая совокупность правил и математических утверждений называется формальной системой. После того как определены правила формальной системы F, решение вопроса о корректности применения этих правил — количество которых непременно является конечным — сводится к элементарной механической проверке. Разумеется, если мы хотим, чтобы любой выводимый с помощью таких правил результат мог считаться действительно истинным, нам придется присвоить им всем статус вполне допустимых и обоснованных форм математического рассуждения. Однако некоторые из рассматриваемых правил могут подразумевать какие-либо манипуляции с бесконечными множествами, и в этом случае математическая интуиция, подсказывающая нам, какие методы рассуждения допустимы, а какие нет, может оказаться и не достойной абсолютного доверия. Сомнения в этой связи как. нельзя более уместны, учитывая несоответствия, возникающие при столь вольном обращении с бесконечными множествами, что допустимым становится даже парадоксальное «множество всех множеств, не являющихся членами самих себя» Бертрана Рассела. Правила системы F не должны допускать существования «множества» Рассела, но где же, в таком случае, следует провести границу? Вообще запретить применение бесконечных множеств было бы слишком строгим ограничением (обычное евклидово пространство, например, содержит бесконечное множество точек, да и множество натуральных чисел является бесконечным); кроме того, существуют же формальные системы, абсолютно в этом смысле удовлетворительные (поскольку в их рамках не допускается, к примеру, формулировать сущности, подобные «множеству» Рассела), применяя которые можно получить большую часть необходимых математических результатов. Откуда нам знать, каким из этих формальных систем можно верить, а каким нельзя?
Рассмотрим подробнее одну такую формальную систему F; для математических утверждений, которые можно получить с помощью правил системы F, введем обозначение ИСТИННЫЕ, а для утверждений, отрицания (т. е. утверждения, обратные рассматриваемым) которых выводятся из того же источника, — обозначение ЛОЖНЫЕ. Любое утверждение, которое можно сформулировать в рамках системы F, но которое не является в этом смысле ни истинным, ни ложным, будем полагать неразрешимым. Кто-то, возможно, сочтет, что поскольку на деле может оказаться «бессмысленным» и само понятие бесконечного множества, то, по всей видимости, нельзя абсолютно осмысленно говорить ни об истинности, ни о ложности относящихся к ним утверждений. (Это мнение применимо, по крайней мере, к некоторым разновидностям бесконечных множеств, если не ко всем.) Если придерживаться такой точки зрения, то нет особой разницы, какие именно утверждения о бесконечных множествах (некоторых разновидностей) оказываются ИСТИННЫМИ, а какие — ЛОЖНЫМИ, лишь бы не вышло так, что одно утверждение получится ИСТИННЫМ и ЛОЖНЫМ одновременно, т.е. система F должна все же быть непротиворечивой. Собственно говоря, в этом и состоит суть истинного формализма, а в отношении формальной системы F первостепенно важно знать лишь следующее: (а) является ли она непротиворечивой и (Ь) является ли она полной. Система F называется полной, если любое математическое утверждение, должным образом сформулированное в рамках F, всегда оказывается либо истинным, либо ЛОЖНЫМ (т. е. НЕРАЗРЕШИМЫХ утверждений система F не содержит).
Для строгого формалиста вопрос о том, является ли то или иное утверждение о бесконечных множествах действительно истинным в сколько угодно абсолютном смысле, не обязательно имеет смысл и, уж конечно же, не имеет никакого существенного отношения к процедурам формалистской математики. Таким образом, поиски абсолютной математической истины в отношении утверждений, связанных с упомянутыми бесконечными величинами, заменяются стремлением продемонстрировать непротиворечивость и полноту соответствующих формальных систем. Какие же математические правила допустимо использовать для такой демонстрации? Достойные доверия, прежде всего, причем формулировка этих правил никоим образом не должна основываться на сомнительных рассуждениях с привлечением слишком вольно определяемых бесконечных множеств (типа множества Рассела). Была надежда на то, что в рамках некоторых сравнительно простых и очевидно обоснованных формальных систем (например, такой достаточно элементарной системы, как арифметика Пеано) отыщутся логические процедуры, которых будет достаточно для того, чтобы доказать непротиворечивость других, более сложных, формальных систем — скажем, системы F, — непротиворечивость которых уже не столь бесспорна и в рамках которых допускаются формальные рассуждения об очень «больших» бесконечных множествах. Если принять философию формалистов, то подобное доказательство непротиворечивости для F, как минимум, даст основание для использования методов рассуждения, допустимых в рамках системы F. Затем можно доказывать математические теоремы, применяя концепцию бесконечных множеств тем или иным непротиворечивым образом, а может, удастся и вовсе избавиться от необходимости отвечать на вопрос о реальном «смысле» таких множеств. Более того, если удастся показать, что система F является еще и полной, то можно будет вполне резонно счесть, что эта система действительно содержит абсолютно все допустимые математические процедуры; т. е. представляет собой, в некотором смысле, полное описание математического аппарата рассматриваемой области.
Однако в 1930 году (публикация состоялась в 1931) Гёдель взорвал свою «бомбу», раз и навсегда показав, что мечта формалистов принципиально недостижима. Он продемонстрировал, что не может существовать формальной системы F, которая была бы одновременно и непротиворечивой (в некоем «сильном» смысле, который мы рассмотрим в следующем разделе), и полной, — при условии, что F считается достаточно мощной, чтобы сочетать в себе формулировки утверждений обычной арифметики и стандартную логику. Таким образом, теорема Гёделя справедлива для таких систем F, в рамках которых арифметические утверждения типа теоремы Лагранжа и гипотезы Гольдбаха (см. §2.3) формулируются как утверждения математические.
В дальнейшем мы будем рассматривать только те формальные системы, которые являются достаточно обширными, чтобы содержать в себе необходимые для действительной формулировки теоремы Гёделя арифметические операции (а также, в случае нужды, и операции какой угодно машины Тьюринга; см. ниже). Говоря о какой-либо формальной системе F, я обычно буду подразумевать, что она действительно достаточно обширна в этом смысле. Это допущение не отразится на наших рассуждениях сколько-нибудь существенным образом. (Тем не менее, рассматривая формальные системы в таком контексте, я, для пущей ясности, буду иногда снабжать их эпитетом «достаточно обширная» или иным подобным.)
2.8. Условие

Наиболее известная форма теоремы Гёделя гласит, что формальная система F (достаточно обширная) не может быть одновременно полной и непротиворечивой. Это не совсем та знаменитая «теорема о неполноте», которую Гёдель первоначально представил на конференции в Кенигсберге (см. §§2.1 и 2.7), а ее несколько более сильный вариант, который был позднее получен американским логиком Дж. Баркли Россером(1936). По своей сути, первоначальный вариант теоремы Гёделя оказывается эквивалентен утверждению, что система F не может быть одновременно полной и



выражает отрицание того, что высказывание Р (п) справедливо для всех натуральных чисел п.
Условие же


Р(0),Р(1),Р(2),Р(3),Р(4), ....
Отсюда следует, что если формальная система F не является


В дальнейшем утверждения «формальная система F является непротиворечивой» и «формальная система F является

В большей части предлагаемых рассуждений я не стану проводить четкую границу между непротиворечивостью и

2.9. Формальные системы и алгоритмическое доказательство
В предложенной мною формулировке доказательства Гёделя—Тьюринга (см. §2.5) говорится только о «вычислениях» и ни словом не упоминается о «формальных системах». Тем не менее, между этими двумя концепциями существует очень тесная связь. Одним из существенных свойств формальной системы является непременная необходимость существования алгоритмической (т. е. «вычислительной») процедуры F, предназначенной для проверки правильности применения правил этой системы. Если, в соответствии с правилами системы F, некое высказывание является ИСТИННЫМ, то вычисление F этот факт установит. (Для достижения этого результата вычисление F, возможно, «просмотрит» все возможные последовательности строк символов, принадлежащих «алфавиту» системы F, и успешно завершится, обнаружив заключительной строкой искомое высказывание Р; при этом любые сочетания строк символов являются, согласно правилам системы F, допустимыми.)
Напротив, располагая некоторой заданной вычислительной процедурой Е, предназначенной для установления истинности определенных математических утверждений, мы можем построить формальную систему Е, которая эффективно выражает как ИСТИННЫЕ все те истины, что можно получить с помощью процедуры Е. Имеется, впрочем, и небольшая оговорка: как правило, формальная система должна содержать стандартные логические операции, однако заданная процедура Е может оказаться недостаточно обширной, чтобы непосредственно включить и их. Если сама заданная процедура Е не содержит этих элементарных логических операций, то при построении системы Е уместно будет присоединить их к Е с тем, чтобы ИСТИННЫМИ положениями системы Е оказались не только утверждения, получаемые непосредственно из процедуры Е, но и утверждения, являющиеся элементарными логическими следствиями утверждений, получаемых непосредственно из Е. При таком построении система Е не будет строго эквивалентна процедуре Е, но вместо этого приобретет несколько большую мощность.
(Среди таких логических операций могут, к примеру, оказаться следующие: «если Р&Q, то Р»; «если Р и Р => Q, то Q»; «если





Поставив перед собой задачу построить на основе процедуры Е формальную систему Е, мы можем начать с некоторой в высшей степени фундаментальной (и, со всей очевидностью, непротиворечивой) формальной системы L, в рамках которой выражаются лишь вышеупомянутые простейшие правила логического вывода, — например, с так называемого исчисления предикатов (см. [222]), которое только на это и способно, — и построить систему Е посредством присоединения к системе L процедуры Е в виде дополнительных аксиом и правил процедуры для L, переведя тем самым всякое высказывание Р, получаемое из процедуры Е, в разряд ИСТИННЫХ. Это, впрочем, вовсе не обязательно окажется легко достижимым на практике. Если процедура Е задается всего лишь в виде спецификации машины Тьюринга, то нам, возможно, придется присоединить к системе L (как часть ее алфавита и правил процедуры) все необходимые обозначения и операции машины Тьюринга, прежде чем мы сможем присоединить саму процедуру Е в качестве, по сути, дополнительной аксиомы. (См. окончание §2.8; подробности в [222].)
Собственно говоря, в нашем случае не имеет большого значения, содержит ли система Е, которую мы таким образом строим, ИСТИННЫЕ предположения, отличные от тех, что можно получить непосредственно из процедуры Е (да и примитивные логические правила системы L вовсе не обязательно должны являться частью заданной процедуры Е). В § 2.5 мы рассматривали гипотетический алгоритм А, который по определению включал в себя все процедуры (известные или познаваемые), которыми располагают математики для установления факта незавершаемости вычислений. Любому подобному алгоритму неизбежно придется, помимо всего прочего, включать в себя и все основные операции простого логического вывода. Поэтому в дальнейшем я буду подразумевать, что все эти вещи в алгоритме А изначально присутствуют.
Следовательно, как процедуры для установления математических истин, алгоритмы (т. е. вычислительные процессы) и формальные системы для нужд моего доказательства, в сущности, эквивалентны. Таким образом, несмотря на то, что представленное в §2.5 доказательство было сформулировано исключительно для вычислений, оно сгодится и для общих формальных систем. В том доказательстве, если помните, речь шла о совокупности всех вычислениях (действий машины Тьюринга) Cq (п). Следовательно, для того чтобы оно оказалось во всех отношениях применимо к формальной системе F, эта система должна быть достаточно обширной для того, чтобы включать в себя действия всех машин Тьюринга. Алгоритмическую процедуру А, предназначенную для установления факта незавершаемости некоторых вычислений, мы можем теперь добавить к правилам системы F с тем, чтобы вычисления, предположения о незавершающемся характере которых устанавливаются в рамках F как ИСТИННЫЕ, были бы тождественны всем тем вычислениям, незавершаемость которых определяется с помощью процедуры А.
Как же первоначальное кенигсбергское доказательство Гёде-ля связано с тем, что я представил в § 2.5? Не будем углубляться в детали, укажем лишь на наиболее существенные моменты. В роли формальной системы F из исходной теоремы Гёделя выступает наша алгоритмическая процедура А:
алгоритм А <—> правила системы F.
Роль же представленного Гёделем в Кенигсберге предположения G (F), которое в действительности утверждает непротиворечивость системы F, играет полученное в §2.5 конкретное предположение «вычисление Ck (k) не завершается», недоказуемое посредством процедуры А, но интуитивно представляющееся истинным, коль скоро процедуру A мы полагаем обоснованной:
утверждение «вычисление Ck (k) не завершается» <—> утверждение «система F непротиворечива».
Возможно, такая замена позволит лучше понять, каким образом убежденность в обоснованности процедуры — такой, например, как А — может привести к другой процедуре, с исходной никак не связанной, но в обоснованности которой мы также должны быть убеждены. Поскольку если мы полагаем процедуры некоторой формальной системы F обоснованными — т. е. процедурами, с помощью которых мы получаем одни лишь действительные математические истины, полностью исключив ложные утверждения; иными словами, если некое предположение Р выводится из такой процедуры как ИСТИННОЕ, то это значит, что оно и в самом деле должно быть истинным, — то мы должны также уверовать и в -непротиворечивость системы F. Если под «ИСТИННЫМ» понимать «истинное», а под «ЛОЖНЫМ» — «ложное» (как оно, собственно, и есть в рамках любой обоснованной формальной системы F), то безусловно истинно следующее утверждение:
не все предположения Р (0), Р (1), Р (2), Р(3), Р (4), ... могут быть ИСТИННЫМИ, если утверждение «предположение Р (п) справедливо для всех натуральных чисел п» ЛОЖНО, что в точности совпадает с условием