Чтение онлайн

– 21 -

пустым или нет множество всех решений в целых числах уравнения x3 + y3 + z3 = 30. Без понятия пустого множества во всех подобных случаях, говоря о каком-нибудь множестве, приходилось бы добавлять оговорку «если оно существует».

3. Множество и подмножества. Множество А, все элементы которого принадлежат и множеству В, называется подмножеством (частью) множества В. Это отношение между множествами называют включением и обозначают символом , т.е. А В (А включено в В) или В А (В включает А). Например, множество конденсаторов электронной цепи является подмножеством всех ее компонентов, множество положительных чисел — это подмножество множества действительных чисел.

Отношение А В допускает и тождественность (А = В), т.е. любое множество можно рассматривать как подмножество самого себя (А А). Полагают также, что подмножеством любого множество является пустое множество т.е. А. Одновременное выполнение соотношения А В и В А возможно только при А = В. И обратно А = В, если А В и В А. Это может служить определением равенства двух множеств через отношение включения.

Наряду с А В, в литературе можно встретить и другое обозначение А В. При этом под А В понимают такое отношение включение, которое не допускает равенства А и В (строгое включение). Если допускается А = В, то пишут А В (нестрогое включение). Мы будем придерживаться принятого ранее обозначения как для строгого, так и для нестрогого включения.

4. Множество подмножеств. Любое непустое множество А имеет, по крайней мере, два различных подмножества: само А и пустое множество . Эти подмножества называются несобственными, а все другие подмножества А называют собственными(эта терминология связана со словами «собственно подмножества», а не со словом «собственность»). Конечные собственные подмножества образуются всевозможными сочетаниями по одному, два, три и т.д. элементов данного множества.

Элементы множества сами могут являться некоторыми множествами. Например, книга из множества книг в шкафу может рассматриваться как множество страниц. Здесь следует обратить внимание на то, что речь идет об элементах множества, а не о подмножествах (никакая совокупность страниц не может рассматриваться как подмножество множества книг).

Множество, элементами которого являются все подмножества множества А, называют множеством подмножеств (множеством-степенью) А и обозначают через P(А). Так, для трехэлементного множества A ={a, b, c} имеем P(А) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

– 22 -

В случае конечного множества А, состоящего из n элементов, множество подмножеств P(А) содержит 2n элементов. Доказательство основывается на сумме всех коэффициентов разложения бинома Ньютона или на представлении подмножеств n-разрядными двоичными числами, в которых 1 (или 0) соответствует элементам подмножеств.

Следует подчеркнуть различия между отношением принадлежности и отношением включения. Как уже указывалось, множество A может быть своим подмножеством (A A), но оно не может входить в состав своих элементов (A A). Даже в случае одноэлементных подмножеств следует различать множество A={a} и его единственный элемент а. Отношение включения обладает свойством транзитивности: если A B и B C, то A C. Отношение принадлежности этим свойством не обладает. Например, множество A={1, {2,3} ,4} в числе своих элементов содержит множество {2, 3}, поэтому можно записать: 2,3 {2, 3} и {2, 3} A. Но из этого вовсе не следует, что элементы 2 и 3 содержатся в A (в приведенном примере мы не находим 2 и 3 среди элементов множества A, т. е. 2, 3 A.

5. Задание множеств.

Множество A = {a1, a2, ... an} можно задать простым перечислением его элементов. Например, спецификация задает множество деталей изделия, каталог — множество книг в библиотеке. Но этот способ не пригоден для задания бесконечных множеств и даже в случае конечных множеств часто практически нереализуем.

Рассмотрим в качестве примера фасад 16-этажного дома с 38 окнами в каждом этаже. В вечернее время каждое из окон дома может быть освещено или затемнено, т. е. 2608 10183 находиться в двух состояниях. Определенные совокупности освещенных окон можно рассматривать как некоторые образы. Считая все окна (их число равно 38*16=608) различными по их расположению на фасаде, каждый такой образ можно связать с соответствующим подмножеством освещенных окон. Тогда количество всех образов равно количеству элементов множества подмножеств всех окон, т. е. . Полученное число настолько большое, что его трудно даже представить. Оно несравнимо больше числа атомов во всей видимой вселенной, которое равно примерно 1037. Если бы каждый атом превратился во вселенную, то и тогда на один атом приходилось бы 1037 образов 10183 = 1037 *1037 * 1037). Поэтому, хотя множество всех образов конечно и любой из них можно легко определить, о задании подобных множеств перечислением их элементов не может быть и речи.

Определяющее свойство. Другой способ задания множества состоит в описании элементов определяющим свойством Р(х) (формой от х), общим для всех элементов. Обычно Р(х) — это высказывание, в котором что-то утверждается об х, или некоторая функция

– 23 -

переменной х. Если при замене х на а высказывание Р(а) становится истинным или функция в заданной области определения удовлетворяется, то а есть элемент данного множества. Множество, заданное с помощью формы Р(х), обозначается как Х={х | Р(х)}, или Х={х :Р(х)}, причем а {х | Р(х)}, если Р(а) истинно. Например {х | х2 = 2} - множество чисел, квадрат которых равен двум, {х | х есть животное с хоботом} - множество слонов.

Обычно уже в самом определении конкретного множества явно или неявно ограничивается совокупность допустимых объектов. Так, множество слонов следует искать среди млекопитающих, а не среди рыб и тем более не среди планет. Если речь идет о множестве чисел, делящихся на 3, то ясно, что оно является подмножеством целых чисел. Удобно совокупность допустимых объектов зафиксировать явным образом и считать, что рассматриваемые множества являются подмножествами этой совокупности. Ее называют основным множеством (универсумом) и обычно обозначают через U. Так, универсумом арифметики служат числа, зоологии - мир животных, лингвистики - слова и т.п.

Если множество выделяется из множества A с помощью формы Р(х), то запись {х | х А, Р(х)} часто упрощается: {х А | Р(х)}. Запись {f(х) | Р(х)} означает множество всех таких у=f(х), для которых имеется х, обладающий свойством Р(х). Например, {х2 | х - простое число} означает множество квадратов простых чисел.

7. Операции над множествами. Множества можно определять также при помощи операций над некоторыми другими множествами. Пусть имеются два множества A и B.

Объединение (сумма) А В есть множество всех элементов, принадлежащих A или В. Например, {1, 2, 3} (2, 3, 4} = {1, 2, 3, 4}.

Пересечение (произведение) А В есть множество всех элементов, принадлежащих одновременно как A, так и В. Например, {1, 2, 3} {2, 3, 4} = {2, 3}. Множества, не имеющие общих элементов (A В = ), называют непересекающимися (расчлененными).

Разность А \ В (или A - В) есть множество, состоящее из всех элементов A, не входящих в В, например, {1, 2, 3} \ {2, 3, 4} = {1}. Ее можно рассматривать как относительное дополнение В до A. Если A U, то множество U \ A называется абсолютным дополнением (или просто дополнением) множества A и обозначается через A. Оно содержит все элементы универсума U, кроме элементов множества A. Дополнение A определяется отрицанием свойства Р(х), с помощью которого определяется A. Очевидно, А \ В = A В.

– 24 -

Дизъюнктивная сумма (симметрическая разность) А + В (или A В) есть множество всех элементов, принадлежащих или A, или В (но не обоим вместе). Например, {1, 2, 3} + {2, 3, 4} = {1, 4}. Дизъюнктивная сумма получается объединением элементов множеств за исключением тех, которые встречаются дважды.

8. Круги Эйлера. Для наглядного изображения соотношений между подмножествами какого-либо универсума и используют круги Эйлера (рис. 2). Обычно универсум представляется множеством точек прямоугольника, а его подмножества изображаются в виде кругов или других простых областей внутри этого прямоугольника.