Игошин Математическая логика и теория алгоритмов (1019110), страница 69

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 69)

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

Другой важной особенностью прикладных исчислений является то, что в схемах аксиом (РА1) и (РА2) участвуют уже не предметные переменные, а произвольные термы. Более точно, эти схемы аксиом принимают следующий вид: (РА1'): (Чх)(Г(х)) -+ Г(г); (РА2'): Г(г) -+ (Зх)(Г(х)), где терм г не содержит предметной переменной х, а Г(г) — результат подстановки терма г в Г(х) вместо всех свободных вхождений х, причем все переменные г должны быть свободными в Г(г). Формальные теории возникают как некие формальные конструкции для соответствующих содержательных теорий. Если для семантической (содержательной) теории удается построить не- 276 противоречивую и полную формальную теорию, то исходную содержательную теорию называют аксиоматизируемой или формализуемой теорией.

Ранее мы установили, что логика высказываний и логика предикатов формализуемы с помощью соответствующих исчислений, В настоящем параграфе будут рассмотрены формальные подходы к тем аксиоматическим теориям, которые лежат в основаниях математики и о которых речь шла в 5 26. Сначала кратко коснемся формальных теорий с равенством, а затем достаточно обстоятельно поговорим о формальных теориях множеств, в частности о формальной теории Цермело — Френкеля.

Затем будет рассмотрена формальная арифметика и дана характеристика теоремы Геделя о ее неполноте. Далее будут рассмотрены луги формализации теорий числовых систем, геометрии и математического анализа. Теории первого порядка с равенством. Во многих теориях, которые могут быть формализованы как теории первого порядка, участвует понятие равенства. Формализация этого понятия осуществляется следующим образом. В число предикатных символов теории вводится символ « = » двухместного предиката равенства.

В определение формулы добавляется пункт: «если х, у — предметные переменные, то (х = у) — формула». (Следует отметить, что если в нашей формальной теории кроме предиката равенства имеются еще какие-то и функциональные символы, то данный пункт определения будет звучать так: «если гь г2 — термы, то (б = г~)— формула».) Наконец, в список аксиом вводятся две нелогические аксиомы, описывающие свойства равенства: (РАЗ): (1гх)(х = х) (конкретная аксиома); (РА4): (Чх, у)(х = у -+ (г(х, х) -+ г(х, у))) (схема аксиом), где формула г(х, у) получается из формулы г(х, х) заменой некоторых (не обязательно всех) вхождений х на у при условии, что у в этих вхождениях также остается свободным.

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

(Так что такое равенство при интерпретации формальной теории мыслится не как совпадение элементов модели, а как их эквивалентность, т.е. принадлежность одному классу отношения эквивалентности.) Теорема 30.1. В любой формальной теории с равенством: 1) ь- г = г для любого терма г (рефлексивность равенства); 2) ь- х = у » у= х (симметричность равенства); 3) ~- х = у » (у = г -+ х = г) (транзитивность равенства), 277 до казател ьств о. 1) непосрелственно следует из аксиом (РА3) и (РА!') (где Г(х) имеет вид х = х) по правилу заключения МР; 2) запишем аксиому (РА4) для случая, когда Г(х, у) есть у = х; (х=у) -» (х=х-+у=х). Используя эту аксиому и дважды применяя правило МР, нетрудно показать, что х = у, х = х ~- у = х. Поскольку формула х= х является аксиомой теории, поэтому из числа гипотез ее можно исключить, так что х = у ~ — у= х. Наконец, из этой выводимости по теореме о дедукции для ФИП заключаем, что ~- х = у -» у = х; 3) заменим в (РА4) х на у, а у на х, в качестве Г(у, у) возьмем у=г, в качестве Г(у,х) возьмемх=г.

Получим:у=х-»(у=г — »х=г). В силу правила МР отсюда заключаем, что у = х ~- у = г — » х = г. На основании предыдущего свойства равенства имеем х = у >- у= х. Из этих двух выводимостей заключаем, что х = у ~- у= г » х= г. Отсюда по теореме о дедукции следует, что ~- х=у — > (у = г-» х=г). П О формальных теориях множеств. В 8 2б (пример 26.7) были рассмотрены различные аксиоматики содержательной («наивной», канторовской) теории множеств. Одной из важнейших ролей теории множеств является та, которую она играет в вопросах доказательства в тех или иных математических теориях, т.е. фактически в самых основах математики. Мы говорили, что одним из основных методов доказательства непротиворечивости математической теории является метод моделей (или интерпретаций). В качестве основных понятий и отношений выбираются элементы какого-либо конкретного множества и отношения между ними, а затем проверяется, будут ли выполняться для выбранных понятий и отношений аксиомы данной теории.

Строя модель исследуемой теории, мы сводим вопрос о ее непротиворечивости к вопросу о непротиворечивости другой математической теории. Интерпретации для многих математических теорий строятся с использованием теории множеств, поэтому непротиворечивость всей математики в значительной мере упирается в непротиворечивость теории множеств. Парадоксы «наивной» теории множеств. Смомента создания теории множеств Кантором в начале 1870-х гг.

и до конца Х1Х в. математики считали ее незыблемой основой всего математического здания. Но в конце Х1Х в. в самой теории множеств были обнаружены противоречия, получившие название аитиномий (парадоксов) теории множеств. Причем в рассуждениях, приводящих к этим противоречиям, не содержалось никаких логических ошибок. Это обстоятельство поколебало веру в безусловную надежность математических доказательств. Первый такой парадокс обнаружил сам Кантор в 1895 г. и сообщил об этом Гильберту. В 1897 г. его переоткрыл и впервые опубликовал Бурали-Форти.

Хотя ни Кантор, ни Бурали-Форти не были 278 Файл взят с сайта и и и.ко~фея.ги, на котором есть аде много интересной литературы способны в то время предложить разрешение антиномии, ситуация не казалась слишком серьезной: эта первая антиномия возникла в довольно специальной области теории вполне упорядоченных множеств, и, вероятно, казалось, что легкий пересмотр доказательств теорем, входящих в эту область, мог бы спасти положение и все здание теории множеств затронуто не будет. Но в !902 г.

английский философ, логик и математик Бертран Рассел обнаруживает антиномию, относящуюся к самым началам теории множеств и показывающую, что в основаниях этой дисциплины что-то неблагополучно. Антиномия Рассела потрясла основы не только теории множеств, но и логики: требовалось лишь легкое изменение в формулировке, чтобы перевести антиномию Рассела в противоречие, которое можно сформулировать в терминах самых основных понятий логики. Антиномия Рассела сильнейшим образом затронула самые фундаментальные понятия двух самых «точных» наук — логики и математики. Суть парадокса (ангпиномии) Рассела состоит в следующем.

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

Мы пришли к противоречию. Допустим теперь, что множество М принадлежит ко второму классу. Так как все множества второго класса являются элементами множества М, то М содержит себя как элемент и поэтому принадлежит первому классу. Мы вновь пришли к противоречию. Таким образом, множество М не принадлежит ни к первому, ни ко второму классу, что противоречит тому, что все множества распределены по этим двум классам.

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

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

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

Характеристики

Список файлов книги