Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Формальные теории первого порядка

Формальные теории первого порядка


Введение в формальные теории


Ранее было построено чистое формализованное исчисление предикатов первого порядка, а затем в предыдущей лекции рассмотрены его свойства (метатеория). В этом исчислении не участвуют функциональные буквы и предметные константы основного алфавита, хотя язык исчисления (т. е. его формулы) определен с учетом того, что такие символы в нем будут использоваться. Если в аксиомах и других формулах исчисления предикатов участвуют функциональные буквы и предметные константы, то говорят о прикладном исчислении предикатов, или о формальной аксиоматической теории, или об элементарной теории, или о теории первого порядка. Здесь можно отметить, что термин "теория первого порядка" означает, что в теории кванторы применяются лишь по предметным переменным и не применяются по переменным предикатным. Таким образом, каждая из теорий первого порядка является расширением формализованного исчисления предикатов. Система аксиом теории первого порядка получается в результате добавления к аксиомам формализованного исчисления предикатов, называемых в данной ситуации логическими аксиомами, собственных или нелогических аксиом теории. В записи нелогических аксиом используются символы отношений, символы операций и нелогические константы, присущие данной формальной теории. Другой важной особенностью прикладных исчислений является то, что в схемах аксиом [math](\mathsf{PA1})[/math] и [math](\mathsf{PA2})[/math] участвуют уже не предметные переменные, а произвольные термы. Более точно, эти схемы аксиом принимают следующий вид:


[math]\begin{aligned}(\mathsf{PA1}')&\colon~~ (\forall x)\bigl(F(x)\bigr)\to F(t);\\ (\mathsf{PA2}')&\colon F(t)\to (\exists x)\bigl(F(x)\bigr),\end{aligned}[/math]

где терм [math]t[/math] не содержит предметной переменной [math]x[/math], а [math]F(t)[/math] — результат подстановки терма [math]t[/math] в [math]F(x)[/math] вместо всех свободных вхождений [math]x[/math], причем все переменные t должны быть свободными в [math]F(t)[/math].


Формальные теории возникают как некие формальные конструкции для соответствующих содержательных теорий. Если для семантической (содержательной) теории удается построить непротиворечивую и полную формальную теорию, то исходную содержательную теорию называют аксиоматизируемой или формализуемой теорией. Ранее мы установили, что логика высказываний и логика предикатов формализуемы с помощью соответствующих исчислений.


В настоящей лекции будут рассмотрены формальные подходы к тем аксиоматическим теориям, которые лежат в основаниях математики и о которых речь шла ранее. Сначала кратко коснемся формальных теорий с равенством, а затем достаточно обстоятельно поговорим о формальных теориях множеств, в частности о формальной теории Цермело–Френкеля. Затем будет рассмотрена формальная арифметика и дана характеристика теоремы Гёделя о ее неполноте. Далее будут рассмотрены пути формализации теорий числовых систем, геометрии и математического анализа.




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


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


[math](\mathsf{PA3})\colon~ (\forall x(x=x))()[/math] (конкретная аксиома);

[math](\mathsf{PA4})\colon~ (\forall x,y)\bigl(x=y\to (F(x,x)\to F(x,y))\bigr)[/math] (схема аксиом),

где формула [math]F(x,y)[/math] получается из формулы [math]F(x,x)[/math] заменой некоторых (не обязательно всех) вхождений [math]x[/math] на [math]y[/math] при условии, что [math]y[/math] в этих вхождениях также остается свободным. Последняя аксиома выражает свойство равенства, часто называемое правилом замены равного равным: два равных объекта ([math]x[/math] и [math]y[/math]) обладают одинаковыми (равносильными) свойствами. Всякая формальная теория, в которой [math](\mathsf{PA3})[/math] и [math](\mathsf{PA4})[/math] являются аксиомами или теоремами, называется теорией (или исчислением) с равенством. Дело в том, что из [math](\mathsf{PA3})[/math] и [math](\mathsf{PA4})[/math] выводимы основные свойства равенства: рефлексивность, симметричность, транзитивность. (Так что такое равенство при интерпретации формальной теории мыслится не как совпадение элементов модели, а как их эквивалентность, т. е. принадлежность одному классу отношения эквивалентности.) Теорема 30.1. В любой формальной теории с равенством:


1) [math]\vdash t=t[/math] для любого терма t {рефлексивность равенства);
2) [math]\vdash x=y\to y=x[/math] (симметричность равенства);
3) [math]\vdash x=y\to (y=z\to x=z)[/math] (транзитивность равенства).

Доказательство. 7) непосредственно следует из аксиом [math](\mathsf{PA3})[/math] и [math](\mathsf{PA1}')[/math] (где [math]F(x)[/math] имеет вид [math]x=x[/math]) по правилу заключения MP;


2) запишем аксиому [math](\mathsf{PA4})[/math] для случая, когда [math]F(x,y)[/math] есть [math]y=x\colon\, (x=y)\to (x=x\to y=x)[/math]. Используя эту аксиому и дважды применяя правило MP, нетрудно показать, что [math]x=y,~ x=x\vdash y=x[/math]. Поскольку формула [math]x=x[/math] является аксиомой теории, поэтому из числа гипотез ее можно исключить, так что [math]x=y\vdash y=x[/math]. Наконец, из этой выводимости по теореме о дедукции для ФИП заключаем, что [math]\vdash x=y\to y=x[/math];


3) заменим в [math](\mathsf{PA4})[/math] [math]x[/math] на [math]y[/math], а [math]y[/math] на [math]x[/math], в качестве [math]F(y,y)[/math] возьмем [math]y=z[/math], в качестве [math]F(y,x)[/math] возьмем [math]x=z[/math]. Получим: [math]y=x\to (y=z\to x=z)[/math]. В силу правила MP отсюда заключаем, что [math]y=x\vdash y=z\to x=z[/math]. На основании предыдущего свойства равенства имеем [math]x=y\vdash y=x[/math]. Из этих двух выводимостей заключаем, что [math]x=y\vdash y=z\to x=z[/math]. Отсюда по теореме о дедукции следует, что [math]\vdash x=y\to (y=z\to x=z)[/math].




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


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




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


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


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


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


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


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


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


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




Поиск путей выхода из кризиса


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


Чтобы кратко охарактеризовать первую позицию (к числу ее сторонников относятся Рассел и Уайтхед), вернемся к парадоксу Рассела. Попытаемся понять, в чем заключается дефект в рассуждениях, который привел к этому парадоксу. По мнению некоторых математиков, недопустимо определять объект (множество [math]M[/math]) с помощью некоторой совокупности (множество [math]M[/math] определено с помощью совокупности всех множеств и множеств второго класса), а затем причислять его к этой совокупности (множество [math]M[/math] причислялось к первому, а затем ко второму классу), так как при этом оказывается, что он в известной степени участвует в своем собственном определении. Чтобы ликвидировать этот дефект, Расселом и Уайтхедом была построена так называемая теория типов, исключающая рассмотрение множеств, приводящих к антиномии. В силу этой теории множество [math]M[/math], которое рассматривается в антиномии Рассела, следует рассматривать как новое образование, которое не имеет смысла причислять ни к первому, ни ко второму классам. Множества можно образовывать только на основании точной процедуры, надстраивая их классы один над другим в порядке некоторой иерархии (иерархия типов). Иерархия типов, построенная Расселом и Уайтхедом, приводит к чрезмерным ограничениям, в силу которых математика становится чрезвычайно сложной.


Другая попытка устранения антиномий теории множеств была предпринята немецким математиком Э.Цермело (1908), который построил теорию множеств в виде формальной аксиоматической теории.


Прежде чем сформулировать систему аксиом данной аксиоматической теории, отметим два обстоятельства. Во-первых, формальная теория множеств создавалась как аксиоматическая теория для уже существовавшей содержательной (или "наивной") канторовской теории множеств. Задача состояла в том, чтобы аксиоматизировать эту теорию, т. е. зафиксировать первоначальные (неопределяемые) понятия и выбрать совокупность известных утверждений о них, которую объявить системой аксиом. Во-вторых, формальная теория множеств должна стать элементарной теорией первого порядка, базирующейся на формализованном исчислении предикатов, т.е. прикладным исчислением первого порядка. В 1908 г., когда Цермело сформулировал свои аксиомы, аксиоматизация теории предикатов в математической логике еще не была достигнута и точная форма языка формальной теории еще не была известна. (Важнейшие шаги в этом направлении были сделаны Расселом и Уайтхедом в их монографии Principia Mathematica (1913), польским математиком К. Куратовским, который в 1921 г. свел понятие упорядоченной пары к понятию неупорядоченной пары и тем самым к отношению принадлежности, математиками школы Гильберта. Итоги этих исследований были изложены в завершенном виде в первом томе книги Гильберта и Бернайса "Основания математики", вышедшей в 1934 г.) Но когда формализация языка теории множеств была закончена, оказалось, что система аксиом Цермело прекрасно выражается на нем и почти полностью удовлетворяет потребностям математики. В 1922 г: немецкий математик А. Френкель добавил к этой системе лишь аксиому подстановки. Полученная система аксиом стала называться системой аксиом Цермело — Френкеля и обозначаться [math]\mathsf{ZF}[/math].




Система аксиом Цермело–Френкеля и некоторые следствия из неё


Прежде — о первоначальных (неопределяемых) понятиях. Первым нелогическим конкретным неопределяемым предикатным символом является двухместный предикатный символ отношения принадлежности "[math]\in[/math]", так что атомарные формулы имеют вид "[math]x\in y[/math]" (читается: "[math]x[/math] принадлежит [math]y[/math]"), "[math]x[/math] есть член (элемент) [math]y[/math]", "[math]x[/math] содержится в [math]y[/math]", "[math]y[/math] содержит [math]x[/math] в качестве члена (элемента)". Вместо "[math]\lnot(x\in y)[/math]" условимся писать "[math]x\notin y[/math]". Вторым предикатным символом является двухместный предикатный символ отношения равенства "=", так что второй вид атомарных формул такой: "[math]x=y[/math]". Первая аксиома характеризует отношение равенства.


[math](\mathsf{ZF1})\colon[/math] Аксиома объемности или аксиома экстенсиональности (восходит к Лейбницу, введена Г.Фреге в 1893 г.):
[math](\forall x,y) \bigl[(\forall z)(z\in x \leftrightarrow z\in y) \leftrightarrow x=y\bigr][/math]

утверждает, что множества совпадают в том и только в том случае, если они состоят из одних и тех же элементов. Множества [math]x[/math] и [math]y[/math] называются различными, если существует такой [math]z[/math], что [math]z\in x[/math] и [math]z\notin y[/math], или же существует [math]z[/math], что [math]z\notin x[/math] и [math]z\in y[/math]. Запись: [math]x\ne y[/math].


С помощью следующих определений вводится отношение включения:


[math]x\subseteq y~ \Leftrightarrow~ (\forall z)(z\in x\to z\in y)[/math]

(запись "[math]x\subseteq y[/math]" читается: "[math]x[/math] включается в [math]y[/math]" или "[math]y[/math] включает [math]x[/math]") и отношение строгого включения:


[math]x\subset y~ \Leftrightarrow~ x\subseteq y\land x\ne y.[/math]

Между отношениями [math]\in[/math] и [math]\subseteq[/math] имеется весьма глубокое различие, которое необходимо понимать. Первое в нашем изложении является первоначальным, а второе вводится по определению. Но самое главное, что каждое множество включает себя само и свои подмножества, но, вообще говоря, не содержит (в качестве элементов) ни себя, ни своих подмножеств.


[math](\mathsf{ZF2})\colon[/math] Аксиома пустого множества:


[math](\exists x)(\forall y)\bigl(\lnot (y\in x)\bigr).[/math]

В этой аксиоме утверждается существование множества, не имеющего ни одного элемента. Такое множество называется пустым (или нулевым) и обозначается [math]\varnothing[/math].


[math](\mathsf{ZF3})\colon[/math] Аксиома неупорядоченных пар:


[math](\forall x,y)(\exists z)(\forall t)\bigl(t\in z \leftrightarrow (t=x\lor t=y)\bigr).[/math]

Множество [math]z[/math], существование которого для [math]x,\,y[/math] утверждается этой аксиомой, будем обозначать [math]\{x,y\}[/math]. Кроме того, через [math]\{x\}[/math] будем обозначать [math]\{x,x\}[/math]. Множество [math]\{x\}[/math] называется единичным, или одноэлементным.


С помощью понятия неупорядоченной пары можно ввести понятие упорядоченной пары (это сделал К. Куратовский в 1921 г.). Двухэлементное множество [math]\bigl\{\{x\}, \{x,y\}\bigr\}[/math] называется упорядоченной парой, составленной из [math]x,\,y[/math], и обозначается [math](x,y)[/math]. Докажем следующее важнейшее свойство упорядоченной пары: если [math](x,y)= (u,v)[/math], то [math]x=u[/math] и [math]y=v[/math]. В самом деле, рассмотрим следующие два случая: [math]x=y[/math] и [math]x\ne y[/math]. При [math]x=y[/math] каждый элемент множества [math](u,v)[/math], то есть [math]\{u\}[/math] и [math]\{u,v\}[/math] совпадает с [math]\{x\}[/math], откуда следует, что [math]x=u=v[/math]. При [math]x\ne y[/math] множество [math]\{x\}[/math] является элементом множества [math](u,v)= \bigl\{\{u\},\{u,v\}\bigr\}[/math], т.е. одним из множеств [math]\{u\},\,\{u,v\}[/math]. Случай [math]\{x\}=\{u,v\}[/math] исключается, так как это равенство влечет [math]x=u=v[/math], откуда [math]\{u\}= \{u,v\}[/math] и [math]\{x,y\}=\{u\}= \{u,v\}[/math] [math]x=y=u[/math], что противоречит допущению [math]x\ne y[/math]. Следовательно, [math]\{x\}=\{u\}[/math], а значит, [math]x=u[/math]. Кроме того, в этом случае второй элемент [math]\{x,y\}[/math] множества [math](x,y)[/math] должен совпадать с [math]\{u\}[/math] или с [math]\{u,v\}[/math]. Совпадение [math]\{x,y\}=\{u\}[/math] влечет [math]x=y=u[/math], что противоречит допущению [math]x\ne y[/math]. Поэтому [math]\{x,y\}= \{u,v\}[/math], откуда [math]y=u[/math] или [math]y=v[/math]. Поскольку [math]x\ne y[/math] и [math]x=u[/math], то случай [math]y=u[/math] невозможен. Остается [math]y=v[/math].


После того как определено понятие упорядоченной пары, представляется возможным определить понятие функции. Функция (или отображение) — это такое множество [math]f[/math] упорядоченных пар [math](x,y)[/math], что если [math](x,y)\in f[/math] и [math](x,z)\in f[/math], то [math]y=z[/math]. При этом множество всех таких [math]x[/math], что [math](x,y)\in f[/math] (для некоторого [math]y[/math]), называется областью определения [math]f[/math]. Множество всех таких [math]y[/math], что [math](x,y)\in f[/math] (хотя бы для одного [math]x[/math]), называется областью значений [math]f[/math].


[math](\mathsf{ZF4})\colon[/math] Аксиома суммы, или некоторого объединения (введена Г. Кантором в 1899 г. и Цермело в 1908 г.):


[math](\forall x)(\exists y)(\forall z) \bigl[z\in y \leftrightarrow (\exists t)(z\in t\land t\in x)\bigr][/math]

утверждает, что существует множество [math]y[/math], являющееся объединением всех множеств из [math]x[/math]. Оно обозначается [math]\cup x[/math]. В частности, если мы имеем два множества [math]{u}[/math] и [math]{v}[/math], то на основании аксиомы [math](\mathsf{ZF3})[/math] образуем двухэлементное множество [math]w=\{u,v\}[/math], а по аксиоме [math](\mathsf{ZF4})[/math] получаем существование такого множества [math]y[/math], что [math]z\in y \leftrightarrow (z\in u\lor z\in v)[/math]. Такое множество [math]z[/math] называется объединением множеств [math]{u}[/math] и [math]{v}[/math] и обозначается [math]z=u\cup v[/math].


[math](\mathsf{ZF5})\colon[/math] Аксиома множества подмножеств, или аксиома степени (сформулирована Цермело в 1908 г.):


[math](\forall x)(\exists y)(\forall z)(z\in y \leftrightarrow z\subseteq x)[/math]

утверждает, что для каждого [math]x[/math] существует множество [math]y[/math] всех подмножеств этого [math]x[/math]. Оно обозначается [math]P(x)[/math] и называется множеством всех подмножеств [math]x[/math], или множеством-степенью [math]x[/math].


[math](\mathsf{ZF6})\colon[/math] Аксиома подстановки (сформулирована А. Френкелем в 1922 г. и Т. Скулемом в 1923 г.):


[math](\forall x)(\exists!y)\bigl(F(x,y)\bigr)\to (\forall u)(\exists v) \bigl[(\forall t) \bigl(t\in v \leftrightarrow (\exists s)(s\in u\land F(s,t))\bigr)\bigr],[/math]

где [math]F[/math] — формула, не содержащая свободных вхождений [math]{u}[/math].


Таким образом, эта аксиома есть схема аксиом. Она утверждает, что образ при произвольном взаимно-однозначном отображении произвольного множества есть множество. В самом деле, условие данной аксиомы фактически означает, что формула [math]F(x,y)[/math] определяет [math]y[/math] однозначно как функцию от [math]x[/math], то есть [math]y=f(x)[/math]. Тогда заключение утверждает, что совокупность всех таких элементов [math]t[/math], которые являются образами при отображении [math]f[/math] элементов из множества [math]{u}[/math] (то есть [math]t=f(s),~ s\in u[/math]), образует множество [math]{v}[/math].


Эта аксиома является исключительно сильной. Из нее может быть выведено следующее более слабое утверждение.


[math](\mathsf{ZF6}')\colon[/math] Аксиома выделения:


[math](\forall x)(\exists y)(\forall z)\bigl(z\in y \leftrightarrow (z\in x\land S(z))\bigr),[/math]

где [math]S(z)[/math] — формула, содержащая свободную переменную [math]z[/math] и не содержащая свободной переменной [math]y[/math].


Аксиома утверждает, что для каждого [math]x[/math] существует некоторое множество [math]y[/math], состоящее из всех тех [math]z[/math] из [math]x[/math], которые обладают свойством [math]S[/math]. В связи с аксиомой выделения имеет смысл еще раз вернуться к парадоксу Рассела и проанализировать причину появления этого парадокса и ему подобных в "наивной" теории множеств. Это в значительной мере обусловлено тем, что в "наивной" теории множеств мы наивно полагаем будто каждое свойство определяет некоторое множество. Парадокс Рассела как раз и демонстрирует нам, что это не так. Рассматривая свойство "[math]x\notin x[/math]" и множество [math]R[/math] объектов, обладающих им: [math]R=\{x\colon x\notin x\}[/math], приходим к следующему противоречию: по определению [math]R(\forall x)(x\in R \leftrightarrow x\notin x)[/math], тогда после подстановки [math]R[/math] вместо [math]x[/math] сразу получаем [math]R\in R \leftrightarrow R\notin R[/math] — противоречие. Таким образом, при построении формальной теории множеств надо стараться избегать таких свойств, которые могут привести к "абсурдным" множествам типа только что рассмотренного множества [math]R[/math] Рассела. Это и достигается с помощью аксиомы выделения: она допускает рассматривать не безграничные совокупности объектов, удовлетворяющие тому или иному свойству, а лишь те объекты, удовлетворяющие данному свойству, которые находятся внутри наперед заданного множества. Аксиома выделения является, пожалуй, самой характерной особенностью системы Цер-мело, отличая ее как от доаксиоматического подхода к теории множеств, так и от других аксиоматических систем.


Аксиома выделения позволяет доказать следующие две теоремы, предоставляющие в наше распоряжение две важные теоретико-множественные конструкции.




Теорема 30.2 (о пересечении множеств). Для любых двух множеств [math]a[/math] и [math]b[/math] существует вполне определенное множество членов, содержащихся как в [math]a[/math], так и в [math]b\colon[/math]


[math](\forall a,b)(\exists c)(\forall x)\bigl(x\in c \leftrightarrow (x\in a\land x\in b)\bigr).[/math]

(Более общо, для каждого непустого множества [math]{u}[/math] существует вполне определенное множество [math]{v}[/math] членов, содержащихся во всех членах из [math]u\colon[/math]


[math](\forall u)\bigl[u\ne \varnothing\to (\exists v)(\forall x) \bigl(x\in v \leftrightarrow (\forall t) (t\in u\to x\in t)\bigr)\bigr].[/math]

Множество [math]c[/math] называется пересечением множеств [math]a[/math] и [math]b[/math] и обозначается [math]a\cap b[/math]. Множество v называется пересечением множеств из [math]{u}[/math] и обозначается [math]\cap u[/math].)


Доказательство. Множество [math]a\cap b[/math] может быть определено как подмножество множества [math]a[/math], соответствующее условию [math]x\in b[/math] в аксиоме [math](\mathsf{ZF6}')[/math]. Что касается [math]\cap u[/math], то по аксиоме [math](\mathsf{ZF4})[/math] существует множество [math]s=\cap u\colon[/math] каждый элемент из [math]s[/math] содержится по крайней мере в одном члене из [math]{u}[/math]. Возьмем в качестве [math]S(z)[/math] условие: "[math]z[/math] содержится в каждом члене из [math]{u}[/math]". Тогда по аксиоме [math](\mathsf{ZF6}')[/math] существует подмножество [math]{v}[/math] множества [math]s[/math], членами которого будут в точности те, что содержатся во всех членах [math]{u}[/math], то есть [math]v=\cap u[/math]. (Если ни одного [math]z[/math], общего для всех членов [math]{u}[/math], нет, то имеем [math]\cap u=\varnothing[/math]).


Множество [math]t[/math] называется дизъюнктным (или расчлененным), если никакие два члена из [math]t[/math] не пересекаются, т. е.


[math](\forall x,y) \bigl(x\in t\land y\in t\land x\ne y\to x\cap y=\varnothing\bigr).[/math]



Теорема 30.3 (о декартовом произведении множеств). Для каждого дизъюнктного множества [math]t[/math] существует вполне определенное множество, членами которого являются в точности все те множества, которые содержат по единственному члену из каждого члена [math]t[/math].


(Это множество называется декартовым или прямым произведением членов [math]t[/math] и обозначается [math]\times t[/math]; пишут также [math]\times t=t'\times t''\times\ldots[/math], где [math]t',t'',\ldots[/math] — суть члены [math]t[/math].)


Если [math]t[/math] содержит член [math]\varnothing[/math], то [math]\times t= \varnothing[/math].


Доказательство. Поскольку члены искомого множества суть некоторые подмножества [math]\cup t[/math], мы будем исходить из множества-степени множества [math]\cup t[/math], т.е. из [math]P(\cup t)=U[/math], существующего согласно аксиомам [math](\mathsf{ZF4})[/math] и [math](\mathsf{ZF5})[/math]. В качестве условия [math]S(z)[/math] выберем следующее: "[math]z\in U[/math] и для каждого [math]\tau\in t[/math] пересечение [math]\tau\cap z[/math] есть одноэлементное множество". Тогда по аксиоме [math](\mathsf{ZF6}')[/math] существует множество [math]U_S\subset U[/math], членами которого являются те подмножества множества [math]\cup t[/math], которые содержат в точности по одному члену из каждого члена [math]t[/math].


Утверждение теоремы в случае [math]\varnothing\in t[/math] очевидно: поскольку [math]\varnothing[/math] не содержит членов, никакое множество не имеет с [math]\varnothing[/math] общих членов. Теорема доказана.


Таким образом, из трех операций над множествами, известными из "наивной" теории множеств, — объединения, пересечения и прямого произведения — выполнимость первой в системе [math]\mathsf{ZF}[/math] постулирована аксиомой [math](\mathsf{ZF4})[/math], а выполнимость двух других доказана при помощи аксиом [math](\mathsf{ZF4}),\, (\mathsf{ZF5})[/math] и [math](\mathsf{ZF6}')[/math].


[math](\mathsf{ZF7})\colon[/math] Аксиома бесконечности (введена Цермело в 1908 г.):


[math](\exists x)\bigl[\varnothing\in x\land (\forall y)(y\in x\to y\cup\{y\}\in x)\bigr][/math]

постулирует существование бесконечного множества. Ясно, что "первые" члены любого множества, удовлетворяющего этой аксиоме, суть следующие: [math]\varnothing,\,\{\varnothing\},\, \{\varnothing, \{\varnothing\}\},[/math] [math]\{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}[/math] и т. д.


Если опустить эту аксиому, то в качестве модели для оставшейся системы аксиом можно взять совокупность всех конечных множеств, которые можно построить, отправляясь от пустого множества [math]\varnothing[/math]. Ясно, что эта совокупность действительно будет моделью для всех остальных аксиом системы [math]\mathsf{ZF}[/math], так как ни одна из них не выводит за пределы класса конечных множеств, т.е., будучи применена к конечному множеству, утверждает существование такого множества, которое также должно быть конечным. Ясно, что никакое конечное множество не удовлетворяет аксиоме [math](\mathsf{ZF7})[/math], а значит, на рассматриваемой модели из конечных множеств эта аксиома не выполняется. Это означает, что аксиома бесконечности [math](\mathsf{ZF7})[/math] не зависит от остальных аксиом системы [math]\mathsf{ZF}[/math].


[math](\mathsf{ZF8})\colon[/math] Аксиома фундирования, или аксиома регулярности (предложена Дж. фон Нейманом в 1925 г.):


[math](\forall x)\bigl[x\ne \varnothing\to (\exists x)\bigl(y\in x\land (\forall z)(z\notin x\lor x\notin y)\bigr)\bigr][/math]

утверждает, что всякое непустое множество [math]x[/math] содержит такой элемент [math]y[/math], что [math]x[/math] и [math]y[/math] не имеют общих элементов. Из нее следует, что каждое непустое множество [math]x[/math] содержит элемент, минимальный по отношению [math]\kappa\in[/math] (но не [math]\kappa\subseteq[/math]). Следовательно, не может существовать такого множества [math]s[/math], что [math]s\in s[/math]. В противном случае мы могли бы рассмотреть одноэлементное (и, значит, непустое) множество [math]\{s\}[/math], для которого аксиома фундирования не выполнялась бы: [math]s\in\{s\}[/math] и множества [math]s[/math] и [math]\{s\}[/math] имеют общий элемент [math]s[/math]. Исключается существование таких множеств [math]s,\,t,\,u[/math], для которых [math]s\in t[/math] и [math]t\in s[/math], или [math]s\in t,~t\in u,~ u\in s[/math] и т. д. Наконец, исключается существование бесконечных цепей, убывающих по отношению [math]\kappa\in[/math], т. е. таких множеств [math]s[/math], которые имеют бесконечную убывающую последовательность своих членов: [math]\ldots\in s_{k+1}\in s_{k}\in \ldots\in s_2\in s_{1}\in s[/math]. Правда, при нарушении аксиомы фундирования такие убывающие цепи строятся лишь с помощью аксиомы выбора.


[math](\mathsf{ZF9})\colon[/math] Аксиома выбора (введена Цермело в 1908 г.): если [math]x[/math] — дизъюнктное множество непустых множеств, то существует такое множество [math]y[/math], которое из каждого множества из [math]x[/math] содержит точно по одному элементу (или: прямое произведение [math]\times x[/math] не пусто).


Иначе говоря, среди подмножеств множества [math]\cup x[/math] имеется по крайней мере одно, пересечение которого с каждым членом из [math]x[/math] есть одноэлементное множество. Каждое такое подмножество и множества [math]\cup x[/math] называется множеством представителей множества [math]x[/math]; множество представителей, вообще говоря, не единственно.


Эту аксиому формулируют также в терминах понятия функции: для любого дизъюнктного множества [math]S[/math] непустых множеств существует хотя бы одна такая функция [math]f(s)[/math], областью определения которой служит [math]S[/math], что [math]f(s)\in s[/math]. Каждая такая функция определяет множество представителей множества [math]S[/math] и называется функцией выбора.


Аксиома выбора предоставляет наряду с аксиомой выделения еще один способ для получения подмножеств каких-либо множеств. Эта аксиома, пожалуй, одна из самых интересных и наиболее активно обсуждавшихся (несмотря на свое сравнительно позднее происхождение) аксиом математики. В этом отношении она уступает только евклидовой аксиоме о параллельных, имеющей более чем двухтысячелетнюю историю. Основные и важнейшие теоремы и методы теории множеств, алгебры, анализа, геометрии, топологии опираются на аксиому выбора. Поразительно большое количество теорем оказывается в точности эквивалентными аксиоме выбора. Фундаментальнейшая теорема Цермело о том, что всякое непустое множество можно вполне упорядочить, т.е. задать на нем такое линейное отношение порядка, что всякое непустое подмножество будет иметь наименьший элемент, — из числа важнейших эквивалентов аксиомы выбора. Хотя эта аксиома была осознана и явно сформулирована лишь в начале XX в., анализ показал, что применялась она в неявном виде задолго до этого времени. К аксиоме выбора математики пришли точно так же, как и к другим математическим принципам, — путем последующей проверки и логического анализа понятий, методов и доказательств, уже содержавшихся фактически в математике. Так, греческие математики догадались включить в число основных геометрических принципов аксиому о параллельных — утверждение, бытовавшее в математике задолго до Евклида. Гениальность этого достижения была полностью оценена лишь более двух тысячелетий спустя.


Итак, мы завершили перечисление аксиом теории множеств системы [math]\mathsf{ZF}[/math] Цермело–Френкеля. В настоящее время это наиболее употребительная в основаниях математики система аксиом, которой охватывается вся традиционная математика.




О других аксиоматиках формальной теории множеств


Кроме рассмотренной системы аксиом Цермело–Френкеля [math](\mathsf{ZF})[/math] имеются и другие аксиоматические системы теории множеств, позволяющие формализовать обычные математические доказательства, но в то же время избежать известных парадоксов "наивной" теории множеств. Их можно разделить на следующие три группы.


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


Вторая группа аксиоматических систем включает модификации систем первой группы и системы [math]\mathsf{ZF}[/math], преследующие определенные логические или математические цели. Сюда относятся, прежде всего, система аксиом [math]\mathsf{NBG}[/math] фон Неймана–Бернайса–Гёделя и система аксиом Куайна. Построение системы аксиом [math]\mathsf{NBG}[/math] вызвано желанием исключить из системы [math]\mathsf{ZF}[/math] схемы аксиом, т. е. иметь не бесконечный список аксиом, а конечный. В системе Куайна реализуется стремление преодолеть расслоение понятий, имеющее место в теории типов.


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


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




Знаменитые проблемы теории множеств


Методы аксиоматической теории множеств позволили отчетливо сформулировать и решить ряд трудных проблем, имевших свое происхождение в классических разделах математики.


Важнейшей из таких проблем является проблема континуума. Именно ее поставил на первое место Д.Гильберт в своей знаменитой речи на II Международном математическом конгрессе, проходившем в Париже с 6 по 12 августа 1900 г., в которой им были сформулированы 23 актуальные математические проблемы. Еще Г. Кантор в 1878 г. сформулировал гипотезу, получившую название континуум-гипотезы: всякое бесконечное подмножество континуума [math]R[/math] равномощно либо множеству натуральных чисел [math]\mathbb{N}[/math], либо [math]R[/math], т.е. не существует множества промежуточной мощности между счетной мощностью и мощностью континуума. Кантору не удалось ни доказать, ни опровергнуть эту гипотезу. Среди математиков росло убеждение в принципиальной неразрешимости проблемы континуума. Но только после того как вся проблемная среда, связанная с континуум-гипотезой, была формализована, т.е. приобрела характер формальной аксиоматической теории, стало возможным математически точно поставить, а затем и решить вопрос о формальной неразрешимости континуум-гипотезы.


В 1939 г. К. Гёдель показал, что если система Цермело–Френкеля [math]\mathsf{ZF}[/math] непротиворечива, то она остается непротиворечивой и после добавления к ней континуум-гипотезы. Это означает, что в системе [math]\mathsf{ZF}[/math] в предположении ее непротиворечивости невозможно доказать (вывести) отрицание континуум-гипотезы, т. е. отрицание континуум-гипотезы не зависит от остальных аксиом теории множеств, т.е. континуум-гипотеза не может быть опровергнута. В 1963 г. американский математик П. Коэн доказал аналогичное утверждение относительно континуум-гипотезы, т. е. континуум-гипотеза не может быть доказана, тем самым полностью закрыв проблему континуума. Таким образом, ни континуум-гипотеза, ни ее отрицание не зависят от остальных аксиом теории множеств. Это означает, что возможна теория множеств с континуум-гипотезой и возможна теория множеств с отрицанием континуум-гипотезы. Ситуация здесь оказалась сходной с той, которая возникла в начале XIX в. с пятым постулатом Евклида, когда была открыта геометрия Лобачевского.


Основным методом установления невыводимости формулы [math]A[/math] в [math]\mathsf{ZF}[/math] является построение такой модели [math]\mathsf{ZF}[/math], в которой выполняется отрицание [math]\lnot A[/math]. Разработанный Коэном, а затем усовершенствованный другими авторами метод вынуждения сильно расширил возможности построения моделей теории множеств и в настоящее время лежит в основе почти всех дальнейших результатов о невыводимости.


Совершенно аналогичной оказалась ситуация и с аксиомой выбора [math](\mathsf{ZF9})[/math]. Гёдель в 1939 г. доказал, что если система [math]\mathsf{ZF}\setminus(\mathsf{ZF9})[/math] непротиворечива, то непротиворечива и система [math]\mathsf{ZF}[/math], т.е. отрицание аксиомы выбора невыводимо из остальных аксиом системы [math]\mathsf{ZF}[/math]. Невыводимость самой аксиомы выбора [math](\mathsf{ZF9})[/math] из системы [math]\mathsf{ZF}\setminus(\mathsf{ZF9})[/math] тоже установил Коэн в 1962 г.


С 1920 г. начинается история еще одной знаменитой математической проблемы XX в. — проблемы М.Я. Суслина. Мы расскажем о ней ниже в пункте "О формальных теориях числовых систем".


Установлено, что в системе [math]\mathsf{ZF}\setminus(\mathsf{ZF9})[/math] не может быть ни доказано, ни опровергнуто (т.е. является неразрешимым) следующее утверждение: всякое подмножество множества действительных чисел измеримо по Лебегу. Выяснено взаимоотношение с системой [math]\mathsf{ZF}[/math] многих важных проблем так называемой дескриптивной теории множеств, значительный вклад в которую внесли математики Московской математической школы, созданной академиком Н.Н.Лузиным (одним из ярких представителей которой является М.Я. Суслин). Получены многочисленные результаты об отсутствии эффективно определенных объектов в этой теории. Наконец, формализация теории множеств позволила обнаружить неизвестные ранее связи между проблемами "наивной" теории множеств.


Еще раз подчеркнем, что все эти проблемы удалось четко поставить и успешно разрешить только после формализации содержательной ("наивной") канторовской теории множеств.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved