правила логического рассуждения - 3 (теорема Гёделя о полноте)
ОКОНЧАНИЕ. Начало здесь и здесь
7. Теорема Гёделя о полноте (исчисления предикатов). Широко известны теоремы Гёделя о неполноте (формальных теорий), о которых я когда-то писал. Слова "полнота" и "неполнота" здесь употребляются в разных смыслах, о чём следует помнить. В данном случае речь пойдёт о полноте указанной выше системы правил в том смысле, который имелся в виду.
Для начала хотелось бы сформулировать имеющий самостоятельное значение важный факт о теориях и моделях, из которого теорема Гёделя сразу же вытекает. Но для этого нам надо дать одно определение.
Как мы видели, в нашей версии нет общелогических аксиом -- мы их "упрятали" в правила доказательства. Но при рассмотрении той или иной математической теории, излагаемой при помощи языка исчисления предикатов, могут возникать аксиомы данной конкретной теории. Этой теорией может быть элементарная геометрия, арифметика (теория чисел), теория групп, теория множеств -- список далеко не полный. Для данной теории мы прежде всего выбираем сигнатуру, то есть набор используемых "значков" -- предикатных символов. Скажем, выше уже говорилось, что для теории множеств достаточно одного двуместного предикатного символа, предназначенного для содержательного выражения той мысли, что объект x является элементом множества y (то есть x принадлежит y).
Для арифметики нам потребовался бы одноместный предикат Z(x) для выражения той мысли, что x есть ноль; двуместный предикат N(x,y), отражающий тот факт, что число y следует за x в натуральном ряду, а также трёхместные предикаты S(x,y,z) и П(x,y,z) для x+y=z и xy=z, соответственно. На этом языке можно сформулировать аксиомы формальной арифметики, они же аксиомы Пеано, о которых я также как-то писал (с той оговоркой, что в контексте логики принято начинать натуральный ряд с нуля, а не с единицы).
В каких-то теориях может потребоваться знак равенства. Поскольку у нас его нет, то нужен соответствующий бинарный предикат E(x,y). При этом не следует забывать о том, что базовые свойства равенства также придётся задавать аксиомами. Это три аксиомы, говорящие о том, что равенство обладает свойствами рефлексивности, симметричности и транзитивности, то есть условия E(x,x); E(x,y) -> E(y,x); E(x,y) & E(y,z) -> E(x,z). Здесь можно навесить кванторы по переменным, давая понять, что эти условия справедливы для всех значений переменных, но можно этого и не делать в виду наличия правила Gen.
Этих аксиом мало, потому что кроме указанных трёх условий, равенство обладает ещё свойством подстановочности. Смысл такой: если x равно у, то в любой атомарной формуле вида P(...,x,...) можно x менять на y. Скажем, если бы для арифметики мы ввели предикат равенства, то потребовались бы ещё аксиомы типа E(x,y) -> (Z(x) -> Z(y)) и по три аксиомы для каждого из предикатов S, П -- c учётом количества мест. Но этот предикат там вообще-то не нужен, да и помимо всего прочего выразим через остальные при помощи формулы (Et)(Z(t) & S(x,t,y)).
Итак, желая развить в рамках исчисления предикатов какой-то конкретный раздел математики, мы можем зафиксировать набор привлекаемых предикатных символов -- сигнатуру, а также выбрать надлежащим образом аксиомы теории. Надо заметить, что в принципе никто не запрещает выбрать набор аксиом совершенно произвольно. Максимум, чем мы при этом рискуем -- это тем, что полученная теория окажется неинтересной. Допускается даже случай, когда рассматриваемая теория противоречива, то есть в ней можно вывести противоречие. Это вообще-то означает, что в такой теории доказуема любая формула. Именно по этой причине теорию следует считать неинтересной. Но сам вопрос о том, выводимо ли в некоторой теории (или, напротив, невыводимо) противоречие может оказаться весьма содержательным и зачастую довольно трудным.
Итак, под формальной теорией мы будем понимать фиксированный набор предикатных символов (сигнатуру) и фиксированный набор формул, записываемых в данной сигнатуре (аксиом теории). Если при помощи этих аксиом можно вывести (доказать) какую-либо формулу Ф, то эта формула считается теоремой данной теории. Отметим, что, вопреки распространённому взгляду, будто аксиомы "не нуждаются в доказательстве", всякая аксиома тривиальным образом является теоремой -- доказательство состоит просто в её выписывании. При доказательствах, проводимых в рамках данной теории, все аксиомы даются нам как бы "бесплатно", и мы их можем неограниченным образом использовать в рассуждениях.
Часто вместо оборота "формальная теория" говорят "теория первого порядка", имея в виду при этом, что кванторы разрешается навешивать только на предметные переменные, но не на предикатные символы (свойства). Обычно ограничиваются теориями первого порядка ввиду того, что в рамках возникающих исчислений можно говорить почти о чём угодно. Однако можно рассмативать и "теории второго порядка" , когда кванторы можно навешивать на предикаты и говорить о "любых свойствах". Мы этой тематики здесь не касаемся.
Формальная теория называется непротиворечивой, если среди её теорем не возникает противоречия, то есть ни для какой формулы Ф нельзя одновременно доказать как Ф, так и ¬Ф. Поскольку мы сказали, что выбор аксиом в принципе ничем не ограничен, то возникает следующий естественный вопрос. Пусть мы имеем непротиворечивую теорию T. Можно ли сказать, что эта теория описывает некую реальность?
Этот вопрос явно имеет некоторый философский привкус. Можно задавать дополнительные вопросы. Например, если такая "реальность" имеется, то единственна ли она? Или теория описывает обязательно что-то одно, в предположении, что она "состоятельна"? Ответ на вопрос о существовании "реальности" -- положительный. Ответ на вопрос о её единственности, как правило, отрицательный для большинства интересных случаев. То есть мы можем прийти к выводу, что любой непротиворечивый набор положений всегда что-нибудь да описывает, это раз. И при этом он, как правило, подходит для описания многих совсем разных, отличающихся друг от друга "реальностей". Второе положение можно считать усилением первого: "реальности" не только есть -- их много. И это принципиально, потому что многие привыкли к тому, что любая теория "заточена" под описание чего-то одного, и вся задача состоит только в том, чтобы нужный кусок "реальности" описывался "правильно". Я уж тут не говорю о позиции "наивного реализма", когда теории или модели отождествляются с описываемой ими реальностью, что вообще-то является методологической нелепостью.
Итак, что имеется в виду? Пусть дана некоторая формальная теория T. Нас интересует такая её интерпретация, в которой истинными оказываются все теоремы (являющиеся замкнутыми формулами). Если теория противоречива, то такой интерпретации заведомо не существует. На самом деле достаточно потребовать того, чтобы все аксиомы теории были истинными в выбранной интерпретации, так как все теоремы выводятся из аксиом по правилам логики, а из истинных утверждений логически следуют только истинные. Если такая интерпретация имеется, то она называется моделью теории T. Следующее важное утверждение по сути является ключевым для доказательства теоремы Гёделя о полноте.
Теорема. Всякая непротиворечивая формальная теория имеет модель.
Доказательства я здесь не привожу, так как оно довольно длинное и "техническое" по своему характеру. Но несколько слов о том, из чего же строится модель, сказать стоит. В нашей теории T доказуемы некоторые формулы, утверждающие существование каких-то объектов. Для каждой такой формулы можно ввести специальный символ для обозначения соответствующего объекта, существование которого утверждает формула. Эти символы и образуют модель, а точнее -- предметную область модели. На самом деле ситуация немного сложнее. С содержательной точки зрения, появившиеся символы могут каким-то образом участвовать в других формулах. Легче всего этого эффекта достичь при помощи введения предметных констант, но можно обойтись и введением дополнительных одноместных предикатов. То есть список формул, которые выражают существование чего-либо, расширятся. Из сказанного так или иначе понятно, откуда в принципе берутся элементы будущей модели. По сути дела, это просто формулы определённого вида. Поскольку формула -- это конечная последовательность символов, то отсюда вытекает не просто наличие моделей, а наличие счётных моделей. Скажем, формальная теория множеств (в предположении её непротиворечивости) имеет счётные модели, что может показаться парадоксом ввиду наличия несчётных множеств. Однако этот парадокс легко разрешается.
Что касается множественности моделей, то при выбранном нами подходе (нет "настоящего" отношения равенства) оказывается, что любой элемент модели можно "размножить" в любом количестве экземпляров. Например, считать, что в модели арифметики имеется любое заданное количество экземпляров нуля. Так как равенства нет, этот факт никак не обнаружить. Все эти "нули" равноценны и взаимозаменяемы. Поэтому модели при таком подходе можно как "раздувать", так и "сжимать".
Принципиально здесь на самом деле то, что в большинстве интересных случаев одна и та же теория имеет много принципиально разных моделей, свойства которых не просто различаются, но выразимы посредством языка самой теории. Так происходит всегда, когда мы имеем дело с неполной теорией, то есть такой, в которой имеются замкнутые формулы, не доказуемые и не опровержимые в рамках данной теории. Теорема Гёделя о неполноте говорит как раз о том, что любая теория, если она непротиворечива и "достаточно сильна" ("содержит" арифметику), то она обязательно неполна. И по этой причине имеет принципиально разные модели. В самом деле, если Ф нельзя ни доказать, ни опровергнуть в теории T, то принятие Ф в качестве новой аксиомы приводит к непротиворечивой теории T1, имеющей модель. Принятие ¬Ф вместо Ф также приводит к непротиворечивой теории T2, и эта теория имеет свою модель. Обе модели будут моделями старой теории T, но они различаются по своим свойствам -- в одной из них Ф истинна, а в другой -- ложна.
Классический пример такого типа возникает в геометрии вокруг "аксиомы параллельных" (она же -- "Пятый Постулат" Евклида). Принятие этой аксиомы приводит к евклидовой геометрии; принятие её отрицания -- к неевклидовой (в версии Гаусса -- Бойяи -- Лобачевского).
Из теоремы, сформулированной выше, легко вытекает следующий классический результат.
Теорема Гёделя о полноте. В исчислении предикатов доказуемыми замкнутыми формулами являются все тавтологии, и только они.
Здесь речь идёт о тех пяти правилах доказательства (логического рассуждения), о которых говорилось выше. То есть это правила 1), 2P), 3), 4), 5); они же -- MP, CondP, Contr, Gen, Part. Точнее говорить о том, что полна именна эта система правил, позволяющих доказать любую тавтологию, то есть "абсолютный логический закон", верный при любой интерпретации входящих в него символов. О том, что любое содержательное доказательство можно мыслить как вывод некоторой (вообще говоря, сложной) тавтологии, уже говорилось.
Доказывается эта теорема очень просто. То, что все выводимые формулы -- это тавтологии, факт совершенно очевидный. Обратное нужно обосновать. То есть надо доказать, что любая тавтология Ф выводима (доказуема). Если это не так, то теория T, состоящая из одной аксиомы ¬Ф, должна быть непротиворечивой. Потому что вывод противоречия тем самым доказывал бы "от противного" формулу Ф. А поскольку всякая непротиворечивая теория имеет модель, то мы получили бы такую модель, в которой формула ¬Ф истинна. Это означало бы, что Ф ложна в данной модели (интерпретации). Но это противоречит тому, что Ф является тождественно истинной (тавтологией).
Заметим, что теорема Гёделя о полноте исчисления предикатов формально не является усилением теоремы о полноте исчисления высказываний -- это разные теоремы. (В исчислении предикатов имеется 5 приёмов доказательства, а не 3.)
8. Заключение Очень хотелось бы сделать ещё акцент на следующем соображении, которое было во многом для меня "вдохновляющим", и ради которого в каком-то смысле это всё и писалось. Как мы видели, тавтологии играют очень важную роль, и математические вопросы так или иначе сводимы к вопросам о тавтологиях. Если формула Ф является тавтологией, то имеется её вывод в исчислении предикатов. Этот вывод может быть явно представлен и проверен чисто "машинными" средствами -- все правила чисто формальны, и очень легко отследить, что доказательство им следует. Другое дело, что нахождение такого доказательства, как правило, требует существенных творческих усилий. В частности, большую роль играет нахождение новых полезных предикатов (задаваемых формулами), которые соответствуют каким-то новым понятиям или свойствам. Часто оказывалось, что привлечение таких понятий позволяет говорить о новых объектах и их свойствах. Скажем, прогресс в решении вопроса о разрешимости алгебраических уравнений был достигнут в результате привлечения нового для математики того времени понятия группы. Примеров такого сорта очень много. То есть даже при доказательстве тавтологий, то есть по сути дела сложных тождеств, необходим некий творческий потенциал, позволяющий решать определённые задачи.
Ещё более наглядно творческая составляющая проявляет себя, когда надо удостовериться в том, что какая-то формула тавтологией не является. Здесь вывода просто уже не существует; как в этом можно убедиться? Один из способов, который, правда, редко бывает успешным -- способ "синтаксический". Выводимые формулы обладают какими-то свойствами. Например, нетрудно заметить, что у них у всех количество использованных символов отрицания является чётным. На этом основании можно заключить, что формула, включающая в себя нечётное число таких символов, невыводима, то есть не является тавтологией.
Второй способ основан на построении подходящих моделей (интерпретаций). Чтобы убедиться в том, что формула Ф не является тавтологией, достаточно придумать такую интерпретацию, в которой она ложна. Здесь в чистом виде всплывает проблема явно творческого характера -- требуется придумать некий особый "мир", в котором что-то определённое происходит. То есть помимо доказательства тождеств, в задачу математика входит изобретение "новых миров". Именно на этой мысли я и намеревался сделать акцент. В идеале мне хотелось бы, чтобы обсуждение велось вокруг именно этого вопроса, что тесно смыкается с ранее затрагивавшимися вопросами о математическом "платонизме" и о платонизме вообще.
Хотелось бы привести один несложный пример, показывающий, как может возникнуть необходимость привлекать для рассмотрения бесконечные множества. (Я заранее вижу здесь ряд мелких спорных моментов, поэтому готов к тому, что мне на них укажут. Тем не менее, пример я всё равно привожу.)
Рассмотрим множество, на котором задано отношение строгого частичного порядка. Такое отношение описывается при помощи двуместного предиката P, с заданием двух аксиом: антирефлексивности, гласящей, что ¬P(x,x) и транзитивности, утверждающей, что P(x,y) -> (P(y,z) -> P(x,z)). Примерами таких отношений являются отношение "меньше" на множестве чисел, отношение "быть собственным делителем" на множестве целых положительных чисел, а также отношение строгого включения множеств. В некоторых случаях частично упорядоченное множество может иметь максимальные элементы, то есть такие, для которых нет "большего". Условие существования максимального элемента записывается следующей формулой: (Ex)(Ay)¬P(x,y). Это условие мы для краткости обозначим через Ф, а аксиомы антирефлексивности и транзитивности, на которые навешены кванторы -- через Ф1 и Ф2 соответственно. Тогда формула (Ф1 -> (Ф2 -> Ф)) будет замкнутой, и она отражает тот факт, что частично упорядоченное множество имеет максимальный элемент. Легко понять, что эта формула истинна во всех интерпретациях, у которых предметная область конечна. В то же время, тавтологией она не будет, так как она ложна в интерпретации со всеми натуральными числами в качестве предметной областью и отношением "меньше" для символа P. То есть факт нетавтологичности построенной формулы устанавливается путём привлечения бесконечности. Ниоткуда не следует, впрочем, отсутствие "синтаксических" доказательств, но имеются более сложные примеры, которые показывают, что привлечение понятия бесконечности оказывается так или иначе неизбежным, если мы не хотим очень сильно ограничивать свои доказательные возможности.
Я хотел бы напомнить, что проблема распознавания тавтологий для исчисления предикатов (в отличие от исчисления высказываний) неразрешима алгоритмически -- это доказал в середине 30-х годов XX века английский математик А.Чёрч. То есть вопрос о том, будет ли данная формула тавтологией, может представлять собой весьма сложную проблему.
Расширение тех средств, при помощи которых можно творить "новые миры", расширяет наши возможности в плане того, про какие формулы, не являющиеся тавтологиями, мы способны установить это. Привлечение понятия бесконечности, арсенала теории множеств -- примеры таких "прорывов". Из общих соображений представляется правдоподобным, что на этом процесс не окончился, что возможны новые "прорывы". Перспективным здесь выглядит ревизия проделываемых нами мыслительных актов на глубоком уровне. (Одним из тех, кто шёл этим путём, является А.С.Есенин-Вольпин.) Речь может также идти о расширении языкового арсенала, привлечении различных категорий модальностей и так далее. Пока что достижения в этой области представляются довольно скромными. Но ясно, что необходимы исследования в области логики в широком смысле этого слова. Классическую "формальную логику" с её "железобетонными" конструктами, на мой взгляд, следует считать безнадёжно устаревшей. Я бы очень хотел написать отдельный пост на эту тему с критикой формальной логики и обоснованием её недостаточности. (На самом деле эта недостаточность бросается в глаза даже при сравнении с достижениями в области математической логики ещё конца XIX века.)
К ОБСУЖДЕНИЮ
7. Теорема Гёделя о полноте (исчисления предикатов). Широко известны теоремы Гёделя о неполноте (формальных теорий), о которых я когда-то писал. Слова "полнота" и "неполнота" здесь употребляются в разных смыслах, о чём следует помнить. В данном случае речь пойдёт о полноте указанной выше системы правил в том смысле, который имелся в виду.
Для начала хотелось бы сформулировать имеющий самостоятельное значение важный факт о теориях и моделях, из которого теорема Гёделя сразу же вытекает. Но для этого нам надо дать одно определение.
Как мы видели, в нашей версии нет общелогических аксиом -- мы их "упрятали" в правила доказательства. Но при рассмотрении той или иной математической теории, излагаемой при помощи языка исчисления предикатов, могут возникать аксиомы данной конкретной теории. Этой теорией может быть элементарная геометрия, арифметика (теория чисел), теория групп, теория множеств -- список далеко не полный. Для данной теории мы прежде всего выбираем сигнатуру, то есть набор используемых "значков" -- предикатных символов. Скажем, выше уже говорилось, что для теории множеств достаточно одного двуместного предикатного символа, предназначенного для содержательного выражения той мысли, что объект x является элементом множества y (то есть x принадлежит y).
Для арифметики нам потребовался бы одноместный предикат Z(x) для выражения той мысли, что x есть ноль; двуместный предикат N(x,y), отражающий тот факт, что число y следует за x в натуральном ряду, а также трёхместные предикаты S(x,y,z) и П(x,y,z) для x+y=z и xy=z, соответственно. На этом языке можно сформулировать аксиомы формальной арифметики, они же аксиомы Пеано, о которых я также как-то писал (с той оговоркой, что в контексте логики принято начинать натуральный ряд с нуля, а не с единицы).
В каких-то теориях может потребоваться знак равенства. Поскольку у нас его нет, то нужен соответствующий бинарный предикат E(x,y). При этом не следует забывать о том, что базовые свойства равенства также придётся задавать аксиомами. Это три аксиомы, говорящие о том, что равенство обладает свойствами рефлексивности, симметричности и транзитивности, то есть условия E(x,x); E(x,y) -> E(y,x); E(x,y) & E(y,z) -> E(x,z). Здесь можно навесить кванторы по переменным, давая понять, что эти условия справедливы для всех значений переменных, но можно этого и не делать в виду наличия правила Gen.
Этих аксиом мало, потому что кроме указанных трёх условий, равенство обладает ещё свойством подстановочности. Смысл такой: если x равно у, то в любой атомарной формуле вида P(...,x,...) можно x менять на y. Скажем, если бы для арифметики мы ввели предикат равенства, то потребовались бы ещё аксиомы типа E(x,y) -> (Z(x) -> Z(y)) и по три аксиомы для каждого из предикатов S, П -- c учётом количества мест. Но этот предикат там вообще-то не нужен, да и помимо всего прочего выразим через остальные при помощи формулы (Et)(Z(t) & S(x,t,y)).
Итак, желая развить в рамках исчисления предикатов какой-то конкретный раздел математики, мы можем зафиксировать набор привлекаемых предикатных символов -- сигнатуру, а также выбрать надлежащим образом аксиомы теории. Надо заметить, что в принципе никто не запрещает выбрать набор аксиом совершенно произвольно. Максимум, чем мы при этом рискуем -- это тем, что полученная теория окажется неинтересной. Допускается даже случай, когда рассматриваемая теория противоречива, то есть в ней можно вывести противоречие. Это вообще-то означает, что в такой теории доказуема любая формула. Именно по этой причине теорию следует считать неинтересной. Но сам вопрос о том, выводимо ли в некоторой теории (или, напротив, невыводимо) противоречие может оказаться весьма содержательным и зачастую довольно трудным.
Итак, под формальной теорией мы будем понимать фиксированный набор предикатных символов (сигнатуру) и фиксированный набор формул, записываемых в данной сигнатуре (аксиом теории). Если при помощи этих аксиом можно вывести (доказать) какую-либо формулу Ф, то эта формула считается теоремой данной теории. Отметим, что, вопреки распространённому взгляду, будто аксиомы "не нуждаются в доказательстве", всякая аксиома тривиальным образом является теоремой -- доказательство состоит просто в её выписывании. При доказательствах, проводимых в рамках данной теории, все аксиомы даются нам как бы "бесплатно", и мы их можем неограниченным образом использовать в рассуждениях.
Часто вместо оборота "формальная теория" говорят "теория первого порядка", имея в виду при этом, что кванторы разрешается навешивать только на предметные переменные, но не на предикатные символы (свойства). Обычно ограничиваются теориями первого порядка ввиду того, что в рамках возникающих исчислений можно говорить почти о чём угодно. Однако можно рассмативать и "теории второго порядка" , когда кванторы можно навешивать на предикаты и говорить о "любых свойствах". Мы этой тематики здесь не касаемся.
Формальная теория называется непротиворечивой, если среди её теорем не возникает противоречия, то есть ни для какой формулы Ф нельзя одновременно доказать как Ф, так и ¬Ф. Поскольку мы сказали, что выбор аксиом в принципе ничем не ограничен, то возникает следующий естественный вопрос. Пусть мы имеем непротиворечивую теорию T. Можно ли сказать, что эта теория описывает некую реальность?
Этот вопрос явно имеет некоторый философский привкус. Можно задавать дополнительные вопросы. Например, если такая "реальность" имеется, то единственна ли она? Или теория описывает обязательно что-то одно, в предположении, что она "состоятельна"? Ответ на вопрос о существовании "реальности" -- положительный. Ответ на вопрос о её единственности, как правило, отрицательный для большинства интересных случаев. То есть мы можем прийти к выводу, что любой непротиворечивый набор положений всегда что-нибудь да описывает, это раз. И при этом он, как правило, подходит для описания многих совсем разных, отличающихся друг от друга "реальностей". Второе положение можно считать усилением первого: "реальности" не только есть -- их много. И это принципиально, потому что многие привыкли к тому, что любая теория "заточена" под описание чего-то одного, и вся задача состоит только в том, чтобы нужный кусок "реальности" описывался "правильно". Я уж тут не говорю о позиции "наивного реализма", когда теории или модели отождествляются с описываемой ими реальностью, что вообще-то является методологической нелепостью.
Итак, что имеется в виду? Пусть дана некоторая формальная теория T. Нас интересует такая её интерпретация, в которой истинными оказываются все теоремы (являющиеся замкнутыми формулами). Если теория противоречива, то такой интерпретации заведомо не существует. На самом деле достаточно потребовать того, чтобы все аксиомы теории были истинными в выбранной интерпретации, так как все теоремы выводятся из аксиом по правилам логики, а из истинных утверждений логически следуют только истинные. Если такая интерпретация имеется, то она называется моделью теории T. Следующее важное утверждение по сути является ключевым для доказательства теоремы Гёделя о полноте.
Теорема. Всякая непротиворечивая формальная теория имеет модель.
Доказательства я здесь не привожу, так как оно довольно длинное и "техническое" по своему характеру. Но несколько слов о том, из чего же строится модель, сказать стоит. В нашей теории T доказуемы некоторые формулы, утверждающие существование каких-то объектов. Для каждой такой формулы можно ввести специальный символ для обозначения соответствующего объекта, существование которого утверждает формула. Эти символы и образуют модель, а точнее -- предметную область модели. На самом деле ситуация немного сложнее. С содержательной точки зрения, появившиеся символы могут каким-то образом участвовать в других формулах. Легче всего этого эффекта достичь при помощи введения предметных констант, но можно обойтись и введением дополнительных одноместных предикатов. То есть список формул, которые выражают существование чего-либо, расширятся. Из сказанного так или иначе понятно, откуда в принципе берутся элементы будущей модели. По сути дела, это просто формулы определённого вида. Поскольку формула -- это конечная последовательность символов, то отсюда вытекает не просто наличие моделей, а наличие счётных моделей. Скажем, формальная теория множеств (в предположении её непротиворечивости) имеет счётные модели, что может показаться парадоксом ввиду наличия несчётных множеств. Однако этот парадокс легко разрешается.
Что касается множественности моделей, то при выбранном нами подходе (нет "настоящего" отношения равенства) оказывается, что любой элемент модели можно "размножить" в любом количестве экземпляров. Например, считать, что в модели арифметики имеется любое заданное количество экземпляров нуля. Так как равенства нет, этот факт никак не обнаружить. Все эти "нули" равноценны и взаимозаменяемы. Поэтому модели при таком подходе можно как "раздувать", так и "сжимать".
Принципиально здесь на самом деле то, что в большинстве интересных случаев одна и та же теория имеет много принципиально разных моделей, свойства которых не просто различаются, но выразимы посредством языка самой теории. Так происходит всегда, когда мы имеем дело с неполной теорией, то есть такой, в которой имеются замкнутые формулы, не доказуемые и не опровержимые в рамках данной теории. Теорема Гёделя о неполноте говорит как раз о том, что любая теория, если она непротиворечива и "достаточно сильна" ("содержит" арифметику), то она обязательно неполна. И по этой причине имеет принципиально разные модели. В самом деле, если Ф нельзя ни доказать, ни опровергнуть в теории T, то принятие Ф в качестве новой аксиомы приводит к непротиворечивой теории T1, имеющей модель. Принятие ¬Ф вместо Ф также приводит к непротиворечивой теории T2, и эта теория имеет свою модель. Обе модели будут моделями старой теории T, но они различаются по своим свойствам -- в одной из них Ф истинна, а в другой -- ложна.
Классический пример такого типа возникает в геометрии вокруг "аксиомы параллельных" (она же -- "Пятый Постулат" Евклида). Принятие этой аксиомы приводит к евклидовой геометрии; принятие её отрицания -- к неевклидовой (в версии Гаусса -- Бойяи -- Лобачевского).
Из теоремы, сформулированной выше, легко вытекает следующий классический результат.
Теорема Гёделя о полноте. В исчислении предикатов доказуемыми замкнутыми формулами являются все тавтологии, и только они.
Здесь речь идёт о тех пяти правилах доказательства (логического рассуждения), о которых говорилось выше. То есть это правила 1), 2P), 3), 4), 5); они же -- MP, CondP, Contr, Gen, Part. Точнее говорить о том, что полна именна эта система правил, позволяющих доказать любую тавтологию, то есть "абсолютный логический закон", верный при любой интерпретации входящих в него символов. О том, что любое содержательное доказательство можно мыслить как вывод некоторой (вообще говоря, сложной) тавтологии, уже говорилось.
Доказывается эта теорема очень просто. То, что все выводимые формулы -- это тавтологии, факт совершенно очевидный. Обратное нужно обосновать. То есть надо доказать, что любая тавтология Ф выводима (доказуема). Если это не так, то теория T, состоящая из одной аксиомы ¬Ф, должна быть непротиворечивой. Потому что вывод противоречия тем самым доказывал бы "от противного" формулу Ф. А поскольку всякая непротиворечивая теория имеет модель, то мы получили бы такую модель, в которой формула ¬Ф истинна. Это означало бы, что Ф ложна в данной модели (интерпретации). Но это противоречит тому, что Ф является тождественно истинной (тавтологией).
Заметим, что теорема Гёделя о полноте исчисления предикатов формально не является усилением теоремы о полноте исчисления высказываний -- это разные теоремы. (В исчислении предикатов имеется 5 приёмов доказательства, а не 3.)
8. Заключение Очень хотелось бы сделать ещё акцент на следующем соображении, которое было во многом для меня "вдохновляющим", и ради которого в каком-то смысле это всё и писалось. Как мы видели, тавтологии играют очень важную роль, и математические вопросы так или иначе сводимы к вопросам о тавтологиях. Если формула Ф является тавтологией, то имеется её вывод в исчислении предикатов. Этот вывод может быть явно представлен и проверен чисто "машинными" средствами -- все правила чисто формальны, и очень легко отследить, что доказательство им следует. Другое дело, что нахождение такого доказательства, как правило, требует существенных творческих усилий. В частности, большую роль играет нахождение новых полезных предикатов (задаваемых формулами), которые соответствуют каким-то новым понятиям или свойствам. Часто оказывалось, что привлечение таких понятий позволяет говорить о новых объектах и их свойствах. Скажем, прогресс в решении вопроса о разрешимости алгебраических уравнений был достигнут в результате привлечения нового для математики того времени понятия группы. Примеров такого сорта очень много. То есть даже при доказательстве тавтологий, то есть по сути дела сложных тождеств, необходим некий творческий потенциал, позволяющий решать определённые задачи.
Ещё более наглядно творческая составляющая проявляет себя, когда надо удостовериться в том, что какая-то формула тавтологией не является. Здесь вывода просто уже не существует; как в этом можно убедиться? Один из способов, который, правда, редко бывает успешным -- способ "синтаксический". Выводимые формулы обладают какими-то свойствами. Например, нетрудно заметить, что у них у всех количество использованных символов отрицания является чётным. На этом основании можно заключить, что формула, включающая в себя нечётное число таких символов, невыводима, то есть не является тавтологией.
Второй способ основан на построении подходящих моделей (интерпретаций). Чтобы убедиться в том, что формула Ф не является тавтологией, достаточно придумать такую интерпретацию, в которой она ложна. Здесь в чистом виде всплывает проблема явно творческого характера -- требуется придумать некий особый "мир", в котором что-то определённое происходит. То есть помимо доказательства тождеств, в задачу математика входит изобретение "новых миров". Именно на этой мысли я и намеревался сделать акцент. В идеале мне хотелось бы, чтобы обсуждение велось вокруг именно этого вопроса, что тесно смыкается с ранее затрагивавшимися вопросами о математическом "платонизме" и о платонизме вообще.
Хотелось бы привести один несложный пример, показывающий, как может возникнуть необходимость привлекать для рассмотрения бесконечные множества. (Я заранее вижу здесь ряд мелких спорных моментов, поэтому готов к тому, что мне на них укажут. Тем не менее, пример я всё равно привожу.)
Рассмотрим множество, на котором задано отношение строгого частичного порядка. Такое отношение описывается при помощи двуместного предиката P, с заданием двух аксиом: антирефлексивности, гласящей, что ¬P(x,x) и транзитивности, утверждающей, что P(x,y) -> (P(y,z) -> P(x,z)). Примерами таких отношений являются отношение "меньше" на множестве чисел, отношение "быть собственным делителем" на множестве целых положительных чисел, а также отношение строгого включения множеств. В некоторых случаях частично упорядоченное множество может иметь максимальные элементы, то есть такие, для которых нет "большего". Условие существования максимального элемента записывается следующей формулой: (Ex)(Ay)¬P(x,y). Это условие мы для краткости обозначим через Ф, а аксиомы антирефлексивности и транзитивности, на которые навешены кванторы -- через Ф1 и Ф2 соответственно. Тогда формула (Ф1 -> (Ф2 -> Ф)) будет замкнутой, и она отражает тот факт, что частично упорядоченное множество имеет максимальный элемент. Легко понять, что эта формула истинна во всех интерпретациях, у которых предметная область конечна. В то же время, тавтологией она не будет, так как она ложна в интерпретации со всеми натуральными числами в качестве предметной областью и отношением "меньше" для символа P. То есть факт нетавтологичности построенной формулы устанавливается путём привлечения бесконечности. Ниоткуда не следует, впрочем, отсутствие "синтаксических" доказательств, но имеются более сложные примеры, которые показывают, что привлечение понятия бесконечности оказывается так или иначе неизбежным, если мы не хотим очень сильно ограничивать свои доказательные возможности.
Я хотел бы напомнить, что проблема распознавания тавтологий для исчисления предикатов (в отличие от исчисления высказываний) неразрешима алгоритмически -- это доказал в середине 30-х годов XX века английский математик А.Чёрч. То есть вопрос о том, будет ли данная формула тавтологией, может представлять собой весьма сложную проблему.
Расширение тех средств, при помощи которых можно творить "новые миры", расширяет наши возможности в плане того, про какие формулы, не являющиеся тавтологиями, мы способны установить это. Привлечение понятия бесконечности, арсенала теории множеств -- примеры таких "прорывов". Из общих соображений представляется правдоподобным, что на этом процесс не окончился, что возможны новые "прорывы". Перспективным здесь выглядит ревизия проделываемых нами мыслительных актов на глубоком уровне. (Одним из тех, кто шёл этим путём, является А.С.Есенин-Вольпин.) Речь может также идти о расширении языкового арсенала, привлечении различных категорий модальностей и так далее. Пока что достижения в этой области представляются довольно скромными. Но ясно, что необходимы исследования в области логики в широком смысле этого слова. Классическую "формальную логику" с её "железобетонными" конструктами, на мой взгляд, следует считать безнадёжно устаревшей. Я бы очень хотел написать отдельный пост на эту тему с критикой формальной логики и обоснованием её недостаточности. (На самом деле эта недостаточность бросается в глаза даже при сравнении с достижениями в области математической логики ещё конца XIX века.)
К ОБСУЖДЕНИЮ