Операции над множествами
Рассмотрим операции над множествами, которые позволяют из уже имеющихся множеств образовывать новые множества.
Для любых двух множеств и определены новые множества, называемые объединением, пересечением, разностью и симметрической разностью:
— объединение, — пересечение, — разность, — симметрическая разность,
т.е. объединение и есть множество всех таких , что является элементом хотя бы одного из множеств ; пересечение и — множество всех таких , что — одновременно элемент и элемент ; разность — множество всех таких , что — элемент , но не элемент ; симметрическая разность — множество всех таких , что — элемент , но не элемент или — элемент , но не элемент .
Кроме того, фиксируя универсальное множество , мы можем определить дополнение множества следующим образом: . Итак, дополнение множества — это множество всех элементов универсального множества, не принадлежащих .
Полезно разобраться в том, как операции над множествами, введенные выше, соотносятся с логическими операциями. Пусть и , т.е. множество задано посредством характеристического предиката , а множество — посредством характеристического предиката .
Легко показать, что
Следующие процедуры получения новых множеств связаны с понятием подмножества. Говорят, что есть подмножество множества , если всякий элемент есть элемент . Для обозначения используют запись: . Говорят также, что содержится в или включено в , или включает (имеет место включение ). Считают, что пустое множество есть подмножество любого множества и, если фиксировано некоторое универсальное множество, каждое рассматриваемое множество есть его подмножество. Нетрудно проверить, что если и , то тогда и только тогда, когда высказывание тождественно истинно.
Сопоставляя определение подмножества и определение равенства множеств, мы видим, что множество равно множеству тогда и только тогда, когда есть подмножество и наоборот, т.е.
(1.2)
Формула (1.2) является основой для построения доказательств о равенстве множеств. Ее применение состоит в следующем. Чтобы доказать равенство двух множеств и , т.е. что , достаточно доказать два включения и ", т.е. доказать, что из предположения (для произвольного ) следует, что , и, наоборот, из предположения следует, что . Такой метод доказательства теоретико-множественных равенств называют методом двух включений. Примеры применения этого метода мы дадим позже.
Замечание. Равенство множеств и означает, что предикаты Р(х) и Q(x) эквивалентны, т.е. предикат Р(х) О Q{x) является тождественно истинным.
Собственное подмножество и булеан множества
Если , но , то пишут и называют строгим подмножеством (или собственным подмножеством) множества , а символ — символом строгого включения.
Для всякого множества может быть образовано множество всех подмножеств множества . Его называют булеаном множества и обозначают
Для булеана используют также обозначения и .
Пример. а. Булеан множества состоит из четырех множеств
, то есть .
б. Булеан состоит из всех возможных, конечных или бесконечных, подмножеств множества . Так, и , вообще для любого множество , множество
и т.д.
Для булеана мы можем рассматривать произвольные его подмножества. Таким подмножеством, например, будет Одноэлементное множество , где — произвольное подмножество . Подчеркнем, что единственным элементом множества является, в свою очередь, некоторое множество. Вообще же образование булеана открывает путь для построения множеств, элементами которых являются множества, элементами которых, в свою очередь, являются некоторые множества, и т.д. Так можно определить множества и т.д.
Свойства операций над множествами
Введенные выше операции над множествами обладают следующими свойствами:
Каждое из написанных выше равенств, верное для любых входящих в них множеств, часто называют теоретико-множественным тождеством. Любое из них может быть доказано методом двух включений. Докажем этим методом тождество 19.
Пусть . Тогда, согласно определению симметрической разности, . Это означает, что или . Если , то и , то есть и при этом . Если же , то и , откуда и . Итак, в любом случае из следует и , то есть . Таким образом, доказано, что
Покажем обратное включение .
Пусть . Тогда и . Из следует, что или . Если , то с учетом имеем , и поэтому . Если же , то опять-таки в силу получаем, что и . Итак, или , то есть . Следовательно,
Оба включения имеют место, и тождество 19 доказано.
Метод двух включений является универсальным и наиболее часто применяемым методом доказательства теоретико-множественных тождеств. Помимо метода двух включений для доказательства теоретико-множественных тождеств могут быть использованы другие методы, например метод характеристических функций.
Кроме того, теоретико-множественные тождества можно доказывать, используя ранее доказанные тождества для преобразования левой части к правой или наоборот. Такой метод доказательства часто называют методом эквивалентных преобразований.
Докажем этим методом тождество 22, пользуясь тождествами 1-19. Преобразуем левую часть к правой:
Таким образом, тождество доказано.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|