Множества

Содержание Введение Способы задания множеств Операции над множествами Литература
Введение
Под множеством обычно понимается совокупность, или набор каких-то объектов, имеющих что-то общее, и при этом каждый из них чем-то отличается от другого. Например, множество людей, присутствующих на каком-то мероприятии, множество домов некоторого района города и т.п. Понятие множества является одним из основных понятий математики. Таким же является понятие элемента множества. Это исходные понятия, и поэтому точного определения для них нет. Принадлежность элемента а множеству М обозначается как а Î М. Если же некоторый элемент а не принадлежит множеству М, то это обозначается как а Ï М или а`Î М. Любое множество может быть элементом другого множества, которое также может быть элементом некоторого множества, и т.д. (множество множеств, множество множеств множеств и т.д.). Иногда для большего благозвучия вместо словосочетания «множество множеств» употребляют «совокупность множеств» или «семейство множеств». Множество А называется подмножеством множества В, если всякий элемент из А принадлежит множеству В. Этот факт обозначается А Í В (Í - знак включения). При этом говорят, что множество В содержит, или покрывает множество А. Множества А и В равны (А = В), если их элементы совпадают, т.е. А Í В и В Í А. Пустое множество (обозначаемое Æ), т.е. множество, не имеющее ни одного элемента, является подмножеством любого множества, т.е. Æ Í М для любого М. Пустое множество, а также само М являются несобственными подмножествами множества М. Если А Í В и А ¹ В для некоторого непустого множества А, то А является собственным подмножеством множества В, и это обозначается как А Ì В (Ì - знак строгого включения). Не следует путать знаки Ì и Î, когда рассматриваются множества множеств. Например, зрительный зал можно рассматривать как множество рядов М, каждый из которых, Мi, представляется как множество кресел. Тогда Мi Î М и для отдельного кресла тj можно записать тj Î Мi. Тот же зрительный зал можно представить как множество М¢ всех находящихся в нем кресел. Тогда для того же Мi имеет место Мi Ì М¢. Множество всех подмножеств некоторого множества М называется булеаном. Булеан обозначается символом 2М. Среди его элементов находятся само множество М, а также пустое множество Æ. Множества бывают конечными (содержащими конечное число элементов) и бесконечными. Параметром, характеризующим размер множества, является мощность множества. Для конечного множества М мощностью является число элементов, которое обозначается символом |М|. Мощность бесконечного множества – более сложное понятие. Оно выражается через соответствие. Мощность булеана множества М равна 2|М|. Действительно, 2Æ = {Æ}, т.е. число элементов булеана пустого множества есть 20 = 1. Добавление к М одного нового элемента каждый раз увеличивает мощность его булеана вдвое (прежние элементы булеана при этом сохраняются, а новые получаются из прежних добавлением к ним данного нового элемента). Если множества А и В равномощны, т.е. |А| = |В|, то между ними можно установить взаимно однозначное соответствие. Каждому элементу из А ставится в соответствие элемент из В и наоборот. Для бесконечных множеств отношение равномощности устанавливается путем нахождения взаимно однозначного соответствия между их элементами. Примерами бесконечных множеств служат: N = {1, 2, … } – множество натуральных чисел, Z = { … – 2, – 1, 0, 1, 2, … } – множество целых чисел, R – множество действительных чисел (рациональные и иррациональные числа). Множества, равномощные с множеством N, называются счетными. Для того, чтобы выяснить, является ли некоторое множество М счетным, надо найти способ установить взаимно однозначное соответствие между М и N, т.е. пронумеровать элементы множества М. Любое бесконечное подмножество N множества N счетно. Действительно, пусть N Ì N. Выберем в N наименьший элемент и обозначим его п1. Удалим из N элемент п1 и из оставшихся элементов выберем снова наименьший, который обозначим п2, и т.д. Таким образом, можно себе представить, что все элементы бесконечного множества N окажутся пронумерованными. Множество P положительных рациональных чисел счетно. Любое рациональное число можно представить в виде правильной или неправильной дроби , где а и b – натуральные числа. Образуем внутри множества P классы Р1 = {}, Р2 = {,}, Р3 = {,,}, … . Здесь в i-ом классе (i = 1, 2, …) собраны все , для которых a + b = i + 1. Выстроим последовательность из дробей, принадлежащих классам Pi, сохраняя порядок нумерации этих классов. Дроби, принадлежащие одному и тому же классу, упорядочиваются по возрастанию числителя а. В полученной последовательности любая дробь снабжается номером 1 + 2 + … + (i – 1) + a. Следовательно, множество P счетно. Примером несчетного множества является множество всех действительных чисел отрезка [0, 1]. Такое множество имеет название континуум. Булеан бесконечного счетного множества также не является счетным множеством.
Способы задания множеств Перечисление элементов. Это простейший способ задания конечного множества. Например, если множество А состоит из элементов а1, а2, … , ап, то можно записать А = {а1, а2, … , ап}. Указание свойств элементов. При таком способе задается одно или несколько свойств, по которым определяется принадлежность элементов к данному множеству. Если Р(х) означает, что х обладает свойством Р, то А = {х / Р(х)} есть множество всех тех и только тех элементов, которые обладают свойством Р. Например, М = {х / х = 2k, k Î N} – множество всех чисел, каждое из которых представляет собой число 2 в натуральной степени. Индуктивный способ. Задается некоторая порождающая процедура, которая определяет способ получения элементов множества из уже полученных элементов. Например, для бесконечного множества М = {1, 2, 4, 8, 16, …} такой определяющей процедурой является следующая: 1) 1 Î М; 2) если т Î М, то 2т Î М. Алгебраический способ. При этом способе дается формула, по которой можно получить множество из других множеств с помощью алгебраических операций над ними. Визуальное представление множеств. Множества изображаются на плоскости в виде фигур, называемых диаграммами Эйлера-Венна. Этот способ используется обычно для наглядной демонстрации операций над множествами или отношений между множествами. Пример использования данного способа будет приведен при описании операций над множествами.
Булевы векторы. При рассмотрении конечных множеств вводится универсальное множество (универсум), обозначаемое обычно U, и всякое множество, подлежащее рассмотрению, считается подмножеством U. Тогда любое множество М представляется вектором, число компонент которого |U| и компоненты соответствуют элементам множества U. Компонента вектора равна 1, если соответствующий элемент принадлежит множеству М, и 0 – в противном случае. Пусть U = {a, b, c, d, e} и М = {a, b, d}. Тогда М представится вектором 11010. Векторы 00000 и 11111 представят соответственно пустое множество Æ и универсальное множество U. Операции над множествами Как было сказано выше, множество можно представить в виде результата операций над другими множествами. Объединение множеств А и В представляет собой множество, содержащее те и только те элементы, которые принадлежат А или В:
А È В = {x / x Î A или x Î В}. Пересечением множеств А и В является множество, содержащее те и только те элементы, каждый из которых принадлежит и А и В:
А Ç В = {x / x Î A и x Î В}. Разность множеств А и В состоит из элементов множества А, которые не принадлежат множеству В:
А \ В = {x / x Î A и x Ï В}. Сумма множеств А и В (ее называют еще симметрической разностью множеств А и В) содержит все элементы из А, не принадлежащие В, и все элементы из В, не принадлежащие А:
А + В = {x / (x Î A и x Ï В) или (x Î В и x Ï А)}. Дополнение множества А состоит из элементов универсального множества U, не принадлежащих А:
`А = {x / x Î U и x Ï А}. На рис.1.1 затемненными областями на диаграммах Эйлера-Венна показаны результаты перечисленных операций.
А È В
А Ç В
А \ В


А + В
`А
Рис.1.1. Операции над множествами Таким образом, формула, в которой присутствуют символы операций над множествами, есть способ задания множества. Две формулы равносильны, если они представляют одно и то же множество. Некоторые операции можно выразить через другие. Так, например, имеем А + В = (А Ç`В) È (`А Ç В) = (А È В) \ (А Ç В); `А = U \ А; A \ B = A Ç`B. Три из перечисленных операций, дополнение, пересечение и объединение, составляют булеву алгебру множеств. Перечислим основные законы этой алгебры, используя общепринятое правило, что если в формуле отсутствуют скобки, устанавливающие порядок выполнения операций, то сначала выполняется дополнение, потом пересечение и затем объединение. Для повышения компактности формулы знак пересечения множеств, подобно знаку арифметического умножения, будем опускать. Коммутативность: А È В = В È А; А В = В А. Ассоциативность: А È (В È С) = (А È В) È С; А (В С) = (А В) С. Дистрибутивность: А (В È С) = А В È А С; А È В С = (А È В) (А È С). Идемпотентность: А È А = А; А А = А. Законы де Моргана: =`А`В; =`А È`В. Законы операций с константами (пустым и универсальным множествами): А È Æ = А; А U = А; А Æ = Æ; А È U = U; А È`А = U; А`А = Æ. Закон двойного дополнения: = А. Заметим, что для каждой пары формул, представляющих тот или иной закон, справедливо следующее: одна из формул получается из другой взаимной заменой всех операций пересечения на операции объединения и всех символов Æ на символы U. При этом должен быть сохранен порядок действий. Этот факт известен под названием принципа двойственности. Заметим также, что для операции пересечения пустое множество имеет свойство нуля, т.е. эта константа ведет себя как нуль при арифметическом умножении: результатом этой операции с нулем всегда является нуль. Универсальное множество имеет свойство единицы, т.е. ведет себя как единица при арифметическом умножении. Для операции объединения универсальное множество имеет свойство нуля, а пустое множество – свойство единицы. Любое равенство из булевой алгебры множеств можно вывести путем равносильных преобразований, используя формулы из приведенного списка. Например, закон поглощения А È А В = А, которого нет в приведенном списке, выводится следующим образом: А È А В = А U È А В = А (U È В) = А. Используя принцип двойственности, получим: А (А È В) = А. Список формул, приведенный выше, является достаточным, но для вывода любого равенства из данной алгебры можно воспользоваться меньшим списком, т.е. некоторые формулы этого списка можно вывести из других. Например, формулу А È В С = (А È В) (А È С) (дистрибутивность объединения относительно пересечения) можно получить следующим образом. Ее правую часть, используя дистрибутивность пересечения, представим как (А È В) (А È С) = (А È В) А È (А È В) С. Раскрыв скобки (по закону ассоциативности), получим (А È В) А È (А È В) С = А А È В А È А С È В С. Применим закон идемпотентности и используем константу U (А А = А = А U), в результате чего после применения закона коммутативности пересечения правая часть примет вид А U È А В È А С È В С. После вынесения за скобки А получим А (U È В È С) È В С, что равно левой части исходного выражения согласно свойству константы U. Выведем теперь закон простого склеивания А В È`А В = В: А В È`А В = В (А È`А) = В U = В.
Формулу А В È`А С = А В È`А С È В С (обобщенное склеивание) выведем следующим образом: А В È`А С È В С = А В È`А С È В С (А È`А) = А В (U ÈС) È`А С (U ÈВ) = = А В È`А С. Используя только что выведенную формулу и закон поглощения, докажем, что А È`А В = А È В:
А È`А В = А U È`А В = А U È`А В È U В = А È`А В È В = А È В.
Литература 1. М.Б. Балк, Г.Д. Балк. Математика после уроков. М, «Просвещение», 71. 2. А.А. Бухштаб. Теория чисел. М, «Просвещение», 96. 3. Алгебра и теория чисел. Под редакцией Н.Я. Виленкина, М, «Просвещение», 84. 4. И.М. Виноградов. Основы теории чисел. М, «Наука», 72. 5. А.А. Кочева. Задачник-практикум по алгебре и теории чисел. М, «Просвещение», 84. 6. Л.Я. Куликов, А.И. Москаленко, А.А. Фомин. Сборник задач по алгебре и теории чисел. М, «Просвещение», 93. 7. Е.С. Ляпин, А.Е. Евсеев. Алгебра и теория чисел. М, «Просвещение», 74. 8. Математическая энциклопедия, том V, М, «Советская энциклопедия», 85. 9. Ш.Х. Михелович. Теория чисел. М, «Высшая школа», 67.