Элементы теории множеств 2 (стр. 3 из 4)
Рис. 2.2.5
2.3 Свойства операций над множествами
Пусть задан универсум U. Тогда для всех A,B,CÌUвыполняются следующие свойства (табл. 2.3.1):
Свойства операций над множествами
| Для объединения ( È ) | Для пересечения ( Ç ) |
| Идемпотентность | |
| A È A = A | A Ç A =A |
| Коммутативность | |
| A È B = B È A | A Ç B = B Ç A |
| Ассоциативность | |
| A È (BÈC) = (A È B)ÈC | A Ç (BÇC) = (A Ç B)ÇC |
| Дистрибутивность | |
| A È (BÇC) = (A È B)Ç(A È C) | A Ç (BÈC) = (A Ç B)È(A Ç C) |
| Поглощение | |
| (A Ç B)ÈA = A | (A È B)ÇA = A |
| Свойства нуля | |
| A ÈÆ = A | A ÇÆ = Æ |
| Свойства единицы | |
| A È U = U | A Ç U = U |
| Инволютивность | |
 = A | |
| Законы де Моргана | |
 |  |
| Свойства дополнения | |
 |  |
| Выражение для разности | |
 | |
| Выражение для симметрической разности | |
 | |
В справедливости перечисленных свойств можно убедиться различными способами. Например, нарисовать диаграммы Эйлера для левой и правой частей равенства и убедиться, что они совпадают, или же провести формальное рассуждение для каждого равенства. Рассмотрим для примера первое равенство: AÈA = А. Возьмем произвольный элемент х, принадлежащий левой части равенства, х ÎAÈA. По определению операции объединения È имеем хÎAÈхÎA.В любом случае хÎA. Взяв произвольный элемент из множества в левой части равенства, обнаружили, что он принадлежит множеству в правой части. Отсюда по определению включения множеств получаем, что AÈAÌ А. Пусть теперь хÎA. Тогда, очевидно, верно хÎAÈхÎA. Отсюда по определению операции объединения имеем х ÎAÈA. Таким образом, А ÌAÈA. Следовательно, по определению равенства множеств, AÈA = А. Аналогичные рассуждения нетрудно провести и для остальных равенств.
Докажем свойство дистрибутивности для операции объединения на диаграммах Эйлера-Венна (рис 2.3.1):
A È (BÇC) = (A È B)Ç(A È C)
Рис. 2.3.1
Глава 3. Аксиоматическая теория множеств
3.1 Наивная теория множеств
В начале XX векаБертран Рассел, изучая наивную теорию множеств, пришел к парадоксу (с тех пор известному как парадокс Рассела). Таким образом, была продемонстрирована несостоятельность наивной теории множеств и связанной с ней канторовской программы стандартизации математики. А именно, был обнаружен ряд теоретико-множественных антиномий: оказалось, что при использовании теоретико-множественных представлений некоторые утверждения могут быть доказаны вместе со своими отрицаниями (а тогда, согласно правилам классической логики высказываний, может быть «доказано» абсолютно любое утверждение!). Антиномии ознаменовали собой полный провал программы Кантора.
После обнаружения антиномии Рассела часть математиков (например, Л. Э. Я. Брауэр и его школа) решила полностью отказаться от использования теоретико-множественных представлений. Другая же часть математиков, возглавленная Д. Гильбертом, предприняла ряд попыток обосновать ту часть теоретико-множественных представлений, которая казалась им наименее ответственной за возникновение антиномий, на основе заведомо надёжной финитной математики. С этой целью были разработаны различные аксиоматизации теории множеств.
Особенностью аксиоматического подхода является отказ от лежащего в основе программы Кантора представления о действительном существовании множеств в некотором идеальном мире. В рамках аксиоматических теорий множества «существуют» исключительно формальным образом, и их «свойства» могут существенно зависеть от выбора аксиоматики. Этот факт всегда являлся мишенью для критики со стороны тех математиков, которые не соглашались (как на том настаивал Гильберт) признать математику лишённой всякого содержания игрой в символы. В частности, Н. Н. Лузин писал, что «мощность континуума, если только мыслить его как множество точек, есть единая некая реальность», место которой в ряду кардинальных чисел не может зависеть от того, признаётся ли в качестве аксиомы континуум-гипотеза, или же её отрицание.
В настоящее время наиболее распространённой аксиоматической теорией множеств является ZFC — теория Цермело — Френкеля с аксиомой выбора. Вопрос о непротиворечивости этой теории (а тем более — о существовании модели для неё) остаётся нерешенным.
3.2 Аксиомы теории множеств
Сейчас у нас имеются все средства, чтобы сформулировать систему аксиом теории множеств ZFC, в рамках которой можно изложить все общепринятые в современной математике способы рассуждений и не проходит ни один из известных теоретико-множественных парадоксов. Эта система позволяет строить все математические объекты исходя из пустого множества. Представим систему аксиом, Цермело — Френкеля (ZF).
1.Аксиома существования пустого множества: Существует пустое множество Æ;
2.Аксиома существования пары: Если существуют множества а и b, то существует множество {a, b};
3.Аксиома суммы: Если существует множество X, то существует множество ÈX={a|aÎb для некоторого bÎX};
4.Аксиома бесконечности: Существует множество w = { 0, 1,…,n,… }, где 0 = Æ, n + 1 = nÈ{n};
5.Аксиома множества всех подмножеств: Если существует множество А, то существует множество:
Р(А) = {B|BÍA};
6. Аксиома замены: Если P(x, у) — некоторое условие на множества x, у, такое, что для любого множества xсуществует не более одного множества у, удовлетворяющего Р(х, у), то для любого множества а существует множество {b|P(c,b) для некоторого с Î а};
7. Аксиома экстенсиональности:
Два множества, имеющие одинаковые элементы, равны, любое множество определяется своими элементами:
;8. Аксиома регулярности:
Всякое непустое множество xимеет элемент а Î х, для которого
aÇx = Æ.
Из аксиомы регулярности следует, что каждое множество получается на некотором шаге "регулярного процесса" образования множества всех подмножеств, начинающегося с Æ и подобного построению натуральных чисел из пустого множества по аксиоме бесконечности. Это означает, что любой элемент любого множества является множеством, сконструированным из пустого множества.
Покажем, как аксиоматика ZF позволяет определять теоретико-множественные операции.
1. Определим множество AÈ В, исходя из множеств А к В. По аксиоме существования пары образуется множество {А, В}. С помощью аксиомы суммы получаем множество È{A, B}, которое по определению совпадает с множеством AÈB.
2. Пересечение А Ç В множеств А и В определяется по аксиоме замены с помощью следующего свойства Р(х, у): х = у и х Î А. Имеем множество {b|P(c,b) и с Î В} = {b| с = bи с Î А и с ÎВ} = {c| с Î А и с ÎВ}.
3. Покажем, что из аксиом 5 и 6 следует существование множества А2 = {(a, b) |a, bÎ А} для любого множества А. Так как (a, b) = {{a}, {a, b}}, то А2ÍP(Р(А)). Пусть свойство Р(х, у) означает, что существуют такие a, bÎ А, что x = {{а}, {а, b}} и y = х. Тогда множество А2 равно {b|P(c,b), cÎ Р(Р(А))} и по аксиоме 6 оно существует.
Система аксиом ZFC образуется из ZF добавлением одной из следующих двух эквивалентных аксиом, которые, с одной стороны, являются наименее "очевидными", а с другой — наиболее содержательными,
1. Аксиома выбора.
Для любого непустого множества А существует такое отображение j: Р(А) \ {Æ} ®A, что j (Х) ÎX|для всех XÍ А, X¹Æ.
2. Принцип полного упорядочения. Для любого непустого множества А существует бинарное отношение £ на А, для которого {A, £} вполне упорядоченное множество.
В системе ZFC справедлив принцип трансфинитной индукции, являющийся обобщением принципа полной индукции: если {A, £} - вполне упорядоченное множество, Р(х) — некоторое свойство, то справедливость свойства Р(х) на всех элементах х Î А следует из того, что для любого zÎ А выполнимость свойства Р на элементах у, где у < z, влечет выполнимость P(z):
Глава 4. Представление множеств в ЭВМ
Термин «представление» (еще употребляют термин «реализация») применительно к программированию означает следующее. Задать представление какого-либо объекта (в данном случае множества) — значит описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции. В данной работе предполагается, что в используемой системе программирования доступны такие общеупотребительные структуры данных, как массивы, структуры (или записи) и указатели. Таким образом, применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций.