Игошин Математическая логика и теория алгоритмов (1019110), страница 71
Текст из файла (страница 71)
Для любых двух множеств а и Ь существует вполне определенное множество членов, содержащихся как в а, так и в Ь: ('ча, ЬКЗсК'чх)(ха с <-+ (ха а л хе Ь)). (Более общо, для каждого непустого множества и существует вполне определенное множество о членов, содержащихся во всех членах из и: (чи)(и 1«И — » (Ло)(Чх) (х в о «-» (ут)(г и и -+ х в ?))]. Множество с называется пересечением множеств а и Ь и обозначается а П Ь.
Множество и называется пересечением множеств из и и обозначается Пи.) 284 Доказательство. Множество а П Ь может быть определено как подмножество множества а, соответствующее условию х в Ь в аксиоме (ЕР6'). Что касается Пи, то по аксиоме (ТР4) существует множество г = 0и: каждый элемент из г содержится по крайней мере в одном члене из и. Возьмем в качестве 5(г) условие: «г содержится в каждом члене из и». Тогда по аксиоме (г.Р6') сушествует подмножество о множества г, членами которого будут в точности те, что содержатся во всех членах и, т.е. о = П и.
(Если ни одного г, общего для всех членов и, нет, то имеем П и = И ). П Множество г называется дизьюнктньии (или расчлененным), если никакие два члена из г не пересекаются, т.е. (чх,у)(хе гнув глхеу-+хПу=И). Теорема 30.3 (о декартовом произведении множеств). Для каждого дизьюнктного множества г существует вполне определенное множество, членами которого являются в точности все те множества, которые содержат по единственному члену из каждого члена д (Это множество называется декартовьии или прямым произведением членов г и обозначается х П пишут также х 1= Р х г" х ..., где г', р', ... — суть члены ь) Если г содержит член И, то х г= И.
Доказательство. Посколькучленыискомогомножествасуть некоторые подмножества 06 мы будем исходить из множества- степени множества 0г, т.е. из Р(0г) = (7, существующего согласно аксиомам (УР4) и (ХР5). В качестве условия Е(г) выберем следующее: «г е (7и для каждого т в г пересечение т П г есть одноэлементное множество».
Тогда по аксиоме (г.Р6') существует множество 1(г ~ (7, членами которого являются те подмножества множества 06 которые содержат в точности по одному члену из каждого члена г. Утверждение теоремы в случае И е г очевидно: поскольку И не содержит членов, никакое множество не имеет с И общих членов. Теоремадоказана. П Таким образом, из трех операций над множествами, известными из «наивной» теории множеств, — объединения, пересечения и прямого произведения — выполнимость первой в системе ХР постулирована аксиомой (г.Р4), а выполнимость двух других доказана при помощи аксиом (ХР4), (г.Р5) и (ХР6'). (ЕР7): Аксиома бесконечности (введена Цермело в !908 г.): (Эх)(И в ха (чу)(у е х — » у0 (у)в х)] постулирует существование бесконечного множества.
Ясно, что «первые» члены любого множества, удовлетворяющего этой аксиоме, суть следующие: И, (И), (И, (ИЦ, (И, (И), (И, (И Ц) и т. д. Если опустить эту аксиому, то в качестве модели для оставшейся системы аксиом можно взять совокупность всех конечных множеств, которые можно построить, отправляясь от пустого 285 множества О. Ясно, что эта совокупность действительно будет моделью для всех остальных аксиом системы УЕ, так как ни одна из них не выводит за прелелы класса конечных множеств, т.е., будучи применена к конечному множеству, утверждает существование такого множества, которое также должно быть конечным.
Ясно, что никакое конечное множество не удовлетворяет аксиоме (ХР7), а значит, на рассматриваемой модели из конечных множеств эта аксиома не выполняется. Это означает, что аксиома бесконечности (УЕ7) не зависит от остальных аксиом системы ЕГ. (ЕР8): Аксиома фундирования, или аксиома регулярности (предложена Дж. фон Нейманом в 1925 г.): (Фх)(х Ф 0 — > (эу)(у е х н (чг)(г 6 х '4 г я у))] утверждает, что всякое непустое множество х содержит такой элемент у, что х и у не имеют общих элементов. Из нее следует, что каждое непустое множество х содержит элемент, минимальный по отношению к а (но не к ~ ).
Следовательно, не может существовать такого множества в, что в а к В противном случае мы могли бы рассмотреть одноэлементное (и, значит, непустое) множество (в), для которого аксиома фундирования не выполнялась бы: в а (в] и множества в и (в] имеют общий элемент к Исключается существование таких множеств в, г, и, для которых в а г и г а в, или в а г, г а и, и а в и т.
д. Наконец, исключается существование бесконечных цепей, убывающих по отношению к а, т.е. таких множеств в, которые имеют бесконечную убывающую последовательность своих членов: ... а ве,, в ве я ... в вз я в, а к Правда, при нарушении аксиомы фундирования такие убывающие цепи строятся лишь с помощью аксиомы выбора. (УЕ9): Аксиома выбора (введена Цермело в 1908 г.): если х— дизъюнктное множество непустых множеств, то существует такое множество у, которое из каждого множества из х содержит точно по одному элементу (или: прямое произведение хх не пусто). Иначе говоря, среди подмножеств множества ()х имеется по крайней мере одно, пересечение которого с каждым членом из х есть одноэлементное множество.
Каждое такое подмножество и множества ()х называется множеством представителей множества х; множество представителей, вообще говоря, не единственно. Эту аксиому формулируют также в терминах понятия функции: для любого дизъюнктного множества Ю непустых множеств существует хотя бы одна такая функция г(в), областью определения которой служит о, что 7"(в) а к Каждая такая функция определяет множество представителей множества 5 и называется функцией выбора. Аксиома выбора предоставляет наряду с аксиомой выделения еще один способ для получения подмножеств каких-либо множеств. Эта аксиома, пожалуй, одна из самых интересных и наибо- 286 лее активно обсуждавшихся (несмотря на свое сравнительно позднее происхождение) аксиом математики. В этом отношении она уступает только евклидовой аксиоме о параллельных, имеющей более чем двухтысячелетнюю историю.
Основные и важнейшие теоремы и методы теории множеств, алгебры, анализа, геометрии, топологии опираются на аксиому выбора. Поразительно большое количество теорем оказывается в точности эквивалентными аксиоме выбора. Фундаментальнейшая теорема Цермело о том, что всякое непустое множество можно вполне упорядочить, т.е.
задать на нем такое линейное отношение порядка, что всякое непустое подмножество будет иметь наименьший элемент, — из числа важнейших эквивалентов аксиомы выбора. Хотя эта аксиома была осознана и явно сформулирована лишь в начале ХХ в., анализ показал, что применялась она в неявном виде задолго до этого времени. К аксиоме выбора математики пришли точно так же, как и к другим математическим принципам, — путем последующей проверки и логического анализа понятий, методов и доказательств, уже содержавшихся фактически в математике. Так, греческие математики догадались включить в число основных геометрических принципов аксиому о параллельных — утверждение, бытовавшее в математике задолго до Евклида. Гениальность этого достижения была полностью оценена лишь более двух тысячелетий спустя.
Итак, мы завершили перечисление аксиом теории множеств системы УР Цермело — Френкеля. В настоящее время это наиболее употребительная в основаниях математики система аксиом, которой охватывается вся традиционная математика. О других аксиоматиках формальной теории множеств. Кроме рассмотренной системы аксиом Цермело— Френкеля (г.Р) имеются и другие аксиоматические системы теории множеств, позволяющие формализовать обычные математические доказательства, но в то же время избежать известных парадоксов наивной» теории множеств.
Их можно разделить на следующие три группы. Первую группу составляют системы, аксиомы которых выбраны в связи с каким-либо объяснением парадоксов. Согласно одному из взглядов на парадоксы возникающее противоречие обусловлено так называемым непредикативным определением объекта, т.е. таким определением его, в котором участвует он сам. Для устранения этой причины парадоксов Б. Расселом разработана так называемая теория типов, в которой множество и его элементы разнесены по различным слоям (уровням).
Имеются и другие теории типов, в которых производится дальнейшее расчленение предметных областей вплоть до доведения их до бесконечного числа. Так возникают разветвленная теория типов Рассела, простая теория типов, теория типов с трансфинитными индексами. 287 Вторая группа аксиоматических систем включает модификации систем первой группы и системы УР, преследующие определенные логические или математические цели. Сюда относятся, прежле всего, система аксиом ХВС фон Неймана — Бернайса— Геделя и система аксиом Куайна. Построение системы аксиом ХВО вызвано желанием исключить из системы УР схемы аксиом, т.е.
иметь не бесконечный список аксиом, а конечный. В системе Куайна реализуется стремление преодолеть расслоение понятий, имеющее место в теории типов. Сторонники перечисленных направлений стремятся устранить антиномии путем ограничения понятия множества или употребления этого понятия в математике — ограничения до такого объема, который соответствует этой цели. При этом структура математической теории не подвергается коренным изменениям. Третья группа систем образует так называемое логическое направление в преодолении антиномий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
