Теории первого порядка с равенством

 

Во многих теориях, которые могут быть формализованы как теории первого порядка, участвует понятие равенства. Формализация этого понятия осуществляется следующим образом. В число предикатных символов теории вводится символ "=" двухместного предиката равенства. В определение формулы добавляется пункт: "если — предметные переменные, то — формула". (Следует отметить, что если в нашей формальной теории кроме предиката равенства имеются еще какие-то и функциональные символы, то данный пункт определения будет звучать так: "если — термы, то — формула".) Наконец, в список аксиом вводятся две нелогические аксиомы, описывающие свойства равенства:

 

(конкретная аксиома);

 

(схема аксиом),

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

Теорема. В любой формальной теории с равенством:

 

1) для любого терма t {рефлексивность равенства);
2) (симметричность равенства);
3) (транзитивность равенства).

 

Доказательство. 7) непосредственно следует из аксиом и (где имеет вид ) по правилу заключения MP;

 

2) запишем аксиому для случая, когда есть . Используя эту аксиому и дважды применяя правило MP, нетрудно показать, что . Поскольку формула является аксиомой теории, поэтому из числа гипотез ее можно исключить, так что . Наконец, из этой выводимости по теореме о дедукции для ФИП заключаем, что ;

 

3) заменим в на , а на , в качестве возьмем , в качестве возьмем . Получим: . В силу правила MP отсюда заключаем, что . На основании предыдущего свойства равенства имеем . Из этих двух выводимостей заключаем, что . Отсюда по теореме о дедукции следует, что .

 

Формальные теории множеств

Ранее в примере 26.7 были рассмотрены различные аксиоматики содержательной ("наивной", канторовской) теории множеств. Одной из важнейших ролей теории множеств является та, которую она играет в вопросах доказательства в тех или иных математических теориях, т. е. фактически в самых основах математики. Мы говорили, что одним из основных методов доказательства непротиворечивости математической теории является метод моделей (или интерпретаций). В качестве основных понятий и отношений выбираются элементы какого-либо конкретного множества и отношения между ними, а затем проверяется, будут ли выполняться для выбранных понятий и отношений аксиомы данной теории. Строя модель исследуемой теории, мы сводим вопрос о ее непротиворечивости к вопросу о непротиворечивости другой математической теории. Интерпретации для многих математических теорий строятся с использованием теории множеств, поэтому непротиворечивость всей математики в значительной мере упирается в непротиворечивость теории множеств.

 

Парадоксы "наивной" теории множеств

 

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

 

Первый такой парадокс обнаружил сам Кантор в 1895 г. и сообщил об этом Гильберту. В 1897 г. его переоткрыл и впервые опубликовал Бурали-Форти. Хотя ни Кантор, ни Бурали-Форти не были способны в то время предложить разрешение антиномии, ситуация не казалась слишком серьезной: эта первая антиномия возникла в довольно специальной области теории вполне упорядоченных множеств, и, вероятно, казалось, что легкий пересмотр доказательств теорем, входящих в эту область, мог бы спасти положение и все здание теории множеств затронуто не будет. Но в 1902 г. английский философ, логик и математик Бертран Рассел обнаруживает антиномию, относящуюся к самым началам теории множеств и показывающую, что в основаниях этой дисциплины что-то неблагополучно. Антиномия Рассела потрясла основы не только теории множеств, но и логики: требовалось лишь легкое изменение в формулировке, чтобы перевести антиномию Рассела в противоречие, которое можно сформулировать в терминах самых основных понятий логики. Антиномия Рассела сильнейшим образом затронула самые фундаментальные понятия двух самых "точных" наук — логики и математики.

 

Суть парадокса (антиномии) Рассела состоит в следующем. Распределим все множества по двум классам: в первый класс включим все те множества, которые содержат себя в качестве своего элемента, во второй класс — все те множества, которые не содержат себя в качестве своего элемента. (Например, множество всех планет не является планетой и поэтому не есть собственный элемент. Напротив, множество всех множеств является своим собственным элементом.) Рассмотрим множество , элементами которого являются все множества второго класса. Спрашивается, к какому из двух вышеназванных классов принадлежит множество ? Допустим, что оно принадлежит к первому классу. Тогда множество содержит себя как элемент. Но элементами множества являются множества второго класса, а значит, множество принадлежит ко второму классу. Мы пришли к противоречию. Допустим теперь, что множество принадлежит ко второму классу. Так как все множества второго класса являются элементами множества , то содержит себя как элемент и поэтому принадлежит первому классу. Мы вновь пришли к противоречию.

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

Противоречию относительно можно придать и следующий (логический) вид, если задаться вопросом, какое утверждение для имеет место: или . Ответ будет обескураживающим. В самом деле, если , то принадлежит второму классу и, значит, . Если же предположить, что , то по определению второго класса принадлежит ему. Но все элементы второго класса являются элементами множества . Следовательно, . Итак, мы доказали, что — явное противоречие.

Парадоксу Рассела были приданы различные словесные формулировки. Одна из них выглядит так. Житель некой деревни, называемый брадобреем, должен брить тех и только тех жителей деревни, которые не умеют бриться сами. Задавшись вопросом, как брадобрей должен поступить в отношении себя, мы аналогичными рассуждениями придем к парадоксальному выводу: брадобрей должен брить себя в том и только в том случае, когда он не должен брить себя.

Парадоксы теории множеств показали, что наивная концепция множества, фигурирующая в канторовском "определении" множества и в получающихся из него общеизвестных следствиях, не может служить удовлетворительной основой теории множеств, не говоря уже о математике в целом. Роль антиномий как фактора, контролирующего и ставящего ограничения на дедуктивные системы логики и математики, можно сравнить с ролью эксперимента, проверяющего правильность полудедуктивных систем таких наук, как физика и астрономия, и вносящего в них видоизменения. И хотя в 1899 г. в своей книге "Основания геометрии" Гильберт сказал, что "никто не может изгнать нас из рая, который создал нам Кантор", открытие парадоксов предрешило уход математиков из этого канторовского "рая".

 

Рекомендуемые страницы: