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

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

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

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

Чтобы ликвидировать этот дефект, Расселом и Уайтхедом была построена так называемая теория типов, исключающая рассмотрение множеств, приводящих к антиномии. В силу этой теории множество М, которое рассматривается в антиномии Рассела, следует рассматривать как новое образование, которое не имеет смысла причислять ни к первому, ни ко второму классам. Множества можно образовывать только на основании точной процедуры, надстраивая их классы один над другим в порядке некоторой иерархии (иерархия типов). Иерархия типов, построен- 280 ная Расселом и Уайтхедом, приводит к чрезмерным ограничениям, в силу которых математика становится чрезвычайно сложной, Другая попытка устранения антиномий теории множеств была предпринята немецким математиком Э.

Цермело (1908), который построил теорию множеств в виде формальной аксиоматической теории. Прежде чем сформулировать систему аксиом данной аксиоматической теории, отметим два обстоятельства. Во-первых, формальная теория множеств создавалась как аксиоматическая теория для уже существовавшей содержательной (или «наивной») канторовской теории множеств. Задача состояла в том, чтобы аксиоматизировать эту теорию, т.е. зафиксировать первоначальные (неопределяемые) понятия и выбрать совокупность известных утверждений о них, которую обьявить системой аксиом. Во-вторых, формальная теория множеств должна стать элементарной теорией первого порядка, базирующейся на формализованном исчислении предикатов, т.е. прикладным исчислением первого порядка. В 1908 г., когда Цермело сформулировал свои аксиомы, аксиоматизация теории предикатов в математической логике еще не была достигнута и точная форма языка формальной теории еще не была известна.

(Важнейшие шаги в этом направлении были сделаны Расселом и Уайтхедом в их монографии Рппс1р(а Маг(зетаг(са (1913), польским математиком К. Куратовским, который в 1921 г. свел понятие упорядоченной пары к понятию неупорядоченной пары и тем самым к отношению принадлежности, математиками школы Гиль- берта.

Итоги этих исследований были изложены в завершенном виде в первом томе книги Гильберта и Бернайса «Основания математики», вышедшей в !934 г.) Но когда формализация языка теории множеств была закончена, оказалось, что система аксиом Цермело прекрасно выражается на нем и почти полностью удовлетворяет потребностям математики. В 1922 г: немецкий математик А. Френкель добавил к этой системе лишь аксиому подстановки. Полученная система аксиом стала называться сисглемой аксиом Цермело — Френкеля и обозначаться ХР.

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

Вместо «(хи у)» условимся писать «х в у». Вторым предикатным символом является двухместный предикатный символ отношения равенства « = », так что второй вид атомарных формул такой: «х = у». Первая аксиома характеризует отношение равенства. (УР1): Аксиома обаемности или аксиома зкстенсиональности (восходит к Лейбнипу, введена Г. Фреге в 1893 г.): (~х, у)НчгНг а х с-» г а у) <-> х = у) утверждает, что множества совпадают в том и только в том случае, если они состоят из одних и тех же элементов.

Множества х и у называются различными, если существует такой г, что г е х и г я у, или же существует г, что г в х и г в у. Запись: х ~ у. С помощью следующих определений вводится отношение включения: х ~ у «» (Уг)(г е х -» г е у) (запись «х а у» читается; «х включается в у» или «у включает х») и отношение строгого включения: х~у<=>х~улх~у. Между отношениями а и ~ имеется весьма глубокое различие, которое необходимо понимать. Первое в нашем изложении является первоначальным, а второе вводится по определению.

Но самое главное, что каждое множество включает себя само и свои подмножества, но, вообще говоря, не содержит (в качестве элементов) ни себя, ни своих подмножеств. (УЕ2): Аксиома пустого множества: (Зх)(чу)(-~(у е х)). В этой аксиоме утверждается существование множества, не имеющего ни одного элемента. Такое множество называется пустым (или нулевым) и обозначается И. (ХРЗ): Аксиома неупорядоченных пар: (чх, у)(Э7)(чг)(г е 7 е-+ (г = х ч г = у)). Множество г, существование которого для х, у утверждается этой аксиомой, будем обозначать (х, у). Кроме того, через (х) будем обозначать (х, х). Множество (х) называется единичным, или однозлементным. С помощью понятия неупорядоченной пары можно ввести понятие упорядоченной пары (это сделал К.

Куратовский в 1921 г.). Двухэлементное множество ((х), (х, уЦ называется упорядоченной парой, составленной из х, у, и обозначается (х, у). Докажем следующее важнейшее свойство упорядоченной пары: если (х, у) = (и, о), то х = и и у = о. В самом деле, рассмотрим следующие два случая: х=у и к~у. При х=у каждый элемент множества (и, о), т.е. (и) и (и, о) совпадает с (х), откуда следует, что х = и = о. При х в у множество (х) является элементом множества (и, о) = ((и)„(и, о)), т.е. одним из множеств (и), (и, о). Случай (х) = (и, о) исключается, 282 так как это равенство влечет х = и = о, откуда (и) = [и, о) и (х, у) = = (и) = (и, о], х = у = и, что противоречит допущению х в у. Следовательно, (х) = (и], а значит, х = и.

Кроме того, в этом случае второй элемент (х, у) множества (х, у) должен совпадать с (и) или с (и, о). Совпадение (х, у) = (и) влечет х = у= и, что противоречит допущению х в у. Поэтому (х, у) = (и, о], откуда у= и или у= о. Поскольку х ~ у и х = и, то случай у= и невозможен. Остается у = о. После того как определено понятие упорядоченной пары, представляется возможным определить понятие функции.

Функция (или отображение) — это такое множество ! упорядоченных пар (х, у), что если (х, у) е г" и (х, г) а г, то у = г. При этом множество всех таких х, что (х, у) в г" (для некоторого у), называется областью определения Я Множество всех таких у, что (х, у) а /'(хотя бы для одного х), называется областью значенийЯ.

(Хг4): Аксиома суммы, или некоторого объединения (введена Г. Кантором в 1899 г. и Цермело в 1908 г.): (чх)(зу)(гг)[г е у <-~ (Л!)(г е ! л ! е х)] утверждает, что существует множество у, являющееся объединением всех множеств из х. Оно обозначается ()х В частности, если мы имеем два множества и и о, то на основании аксиомы (Хг3) образуем двухэлементное множество и = (и, о), а по аксиоме (Хг4) получаем существование такого множества у, что г а у с-> (г а и ~ м г а о).

Такое множество г называется обьединением множеств и и о и обозначается г = и 0 о. (г.г5): Аксиома множества подмножеств, или аксиома степени (сформулирована Цермело в 1908 г.): ('Фх)(Бу)(чг)(г в у <-ь г ~ х) утверждает, что для каждого х существует множество у всех подмножеств этого х. Оно обозначается Р(х) и называется множеством всех подмножеств х, или множеством-степенью х. (г.Гб): Аксиома подстановки (сформулирована А. Френкелем в 1922 г. и Т.

Скулемом в 1923 г.): (ох)(3!у)(Р(х, у)) -+ (Фи)(ЛО) [(ч!)(! е о <-> (лг)(г е и л Р(х, г)))], гле Р— формула, не содержащая свободных вхождений и. Таким образом, эта аксиома есть схема аксиом. Она утверждает, что образ при произвольном взаимно-однозначном отображении произвольного множества есть множество. В самом деле, условие данной аксиомы фактически означает, что формула Р(х, у) определяет у однозначно как функцию от х, т.е.

у = г(х). Тогда заключение утверждает, что совокупность всех таких элементов г, которые являются образами при отображении~элементов из множества и (т.е. ! = г(г), г в и), образует множество о. 283 Эта аксиома является исключительно сильной. Из нее может быть выведено следующее более слабое утверждение. (Ерб'): Аксиома выделения: (Чх)(Зу)(ч?)(? е у <-Ф (? е х п о(?))), где о(?) — формула, содержащая свободную переменную ? и не содержащая свободной переменной у. Аксиома утверждает, что для каждого х существует некоторое множество у, состоящее из всех тех ? из х, которые обладают свойством Х В связи с аксиомой выделения имеет смысл еще раз вернуться к парадоксу Рассела и проанализировать причину появления этого парадокса и ему подобных в «наивной» теории множеств.

Это в значительной мере обусловлено тем, что в «наивной» теории множеств мы наивно полагаем будто каждое свойство определяет некоторое множество. Парадокс Рассела как раз и демонстрирует нам, что это не так. Рассматривая свойство «х я х» и множество Я объектов, обладающих им: Я = (х: х я х), приходим к следующему противоречию: по определению Я (чх)(х а Я <-> х в х), тогда после подстановки Я вместо хоразу получаем Яа Я»» Яя Я— противоречие. Таким образом, при построении формальной теории множеств надо стараться избегать таких свойств, которые могут привести к «абсурдным» множествам типа только что рассмотренного множества Я Рассела.

Это и достигается с помощью аксиомы вьщеления: она допускает рассматривать не безграничные совокупности объектов, удовлетворяющие тому или иному свойству, а лишь те объекты, удовлетворяющие данному свойству, которые находятся внутри наперед заданного множества. Аксиома вьщеления является, пожалуй, самой характерной особенностью системы Цермело, отличая ее как от доаксиоматического подхода к теории множеств, так и от других аксиоматических систем. Аксиома вьщеления позволяет доказать следующие две теоремы, предоставляющие в наше распоряжение две важные теоретико-множественные конструкции. Теорема 30.2 (о пересечении множеств).

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

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