ОСНОВЫ ТЕОРИИ МНОЖЕСТВ

Понятие множества

Понятие “множество” является одним из основных понятий математики. Это понятие в явном виде не определяется, хотя на интуитивном уровне его можно описать, задать.

Объекты материального мира существуют в составе определенных совокупностей, которые и дают первые примеры множеств: стадо коров, отара овец, множество пальцев на руке и т.п. К примерам множеств, рассматриваемых в математике, относятся: множество всех целых чисел, множество решений данного уравнения, множество всех точек отрезка, множество всех треугольников и т.д.

В результате многократного использования в практической деятельности людей многочисленных примеров совокупностей сформировалось математическое понятие множества, как объединения отдельных объектов в нечто единое целое.

Интуитивно под множеством понимают совокупность определенных вполне различаемых объектов, рассматриваемых как единое целое.

Определение. Под множеством S будем понимать любое собрание определенных и различимых между собой объектов, мыслимое как единое целое. Эти объекты называются элементами множества S.

Можно говорить о множестве стульев в комнате, множестве людей, живущих в г. Таганроге, множестве студентов в группе, множестве натуральных чисел, множестве букв в алфавите, множестве состояний системы и т. п. При этом о множестве можно вести речь только тогда, когда элементы множества различимы между собой. Например, нельзя говорить о множестве капель в стакане воды, так как невозможно четко и ясно указать каждую отдельную каплю.

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

Отдельные объекты, из которых состоит множество, называются элементами множества. Так, число 3 — элемент множества натуральных чисел, а буква б — элемент множества букв русского алфавита. Множества обозначаются заглавными буквами, как правило, латинского алфавита A, S, X.... Элементы множества принято заключать в фигурные скобки, внутри которых перечисляются элементы множества. Для обозначения элементов множества в общем виде используются различные строчные буквы a, s, к... или строчные буквы с индексами а₁, а₂...

Для указания того, что некоторый элемент а является элементом множества S, используется символ принадлежности множеству. Запись означает, что элемент а принадлежит множеству S, а запись означает, что элемент х не принадлежит множеству S. Записью пользуются в качестве сокращения для записи .

Множества бывают конечными и бесконечными. Множество называется конечным, если число его элементов конечно, т. е. если существует натуральное число N, являющееся числом элементов множества.

Определение. Мощность конечного множества А – это число его элементов. Мощность множества обозначают |A|.

Пример |{1, 2, 3}|=3.

Определение. Множества называются равномощными, если их мощности совпадают.

Множество называется бесконечным, если оно содержит бесконечное число элементов.

Проблема установления конечности или бесконечности множества, на первый взгляд кажется очевидной, но с точки теории множеств очень сложная. Рассмотрим несколько примеров.

1. Число песчинок в стакане очень большое, но, тем не менее, их можно пересчитать, значит, их конечное число.

2. Множество натуральных чисел бесконечно. В этом можно легко убедиться, если понять, что к любому, пусть даже самому большому натуральному числу всегда можно прибавить, по крайней мере, число 1.

Бесконечными являются и другие основные числовые множества: рациональные числа, целые числа, действительные числа.

Для того чтобы оперировать с конкретными множествами, нужно уметь задавать эти множества. Существуют два способа задания множеств:

1) путем перечисления элементов множества;

2) путем указания свойства, которому удовлетворяют все элементы данного множества.

Задание множества способом перечисления соответствует перечислению всех элементов, составляющих множество. Так, множество отличников группы можно задать, перечислив студентов, которые учатся на отлично, например {Иванов, Петров, Сидоров}. Для сокращения записи Х_п={х₁, х₂,...,x_n} иногда пишут или вводят множество индексов I={1, 2,...,п} и пишут . Такой способ удобен при рассмотрении конечных множеств, содержащих небольшое число элементов, но иногда он может применяться и для задания бесконечных множеств, например {2, 4, 6, 8...}. Естественно, что такая запись применима, если вполне ясно, что понимается под многоточием.

Описательный способ задания множества состоит в том, что указывается характерное свойство, которым обладают все элементы множества.

Свойство, с помощью которого задано множество, называется характеристическим свойством. Этим свойством должны обладать все элементы данного множества. Если некоторый из элементов не принадлежат этому множеству, то он не обладает заданным свойством.

Запись M={x| P(x)} или M={x: P(x)} означает, что множество M состоит их всех элементов x, обладающие свойством P(x).

Например,

· M={x|3x² - 2x =0}. Множеству M принадлежат корни уравнения 3x² - 2x =0. Это числа 0 и 1,5. M= {0; 1,5}.

· Если М — множество студентов группы, то множество А отличников этой группы запишется в виде

,

что читается следующим образом: множество А состоит из элементов х множества М, обладающих тем свойством, что х является отличником группы.

Здесь и далее при задании множества символ | – вертикальная разделительная черта, используется вместо слов “таких, что”.

В тех случаях, когда не вызывает сомнений, из какого множества берутся элементы х, указание о принадлежности х множеству М можно не делать. При этом множество А запишется в виде

.

Примеры задания множеств методом описания:

1) – множество четных чисел;

2) .

3) Пусть Z – множество целых чисел. Тогда есть множество {1, 2, 3, 4, 5, 6, 7}.

Важным понятием теории множеств является понятие пустого множества. Пустым множеством называется множество, не содержащее ни одного элемента. Пустое множество может встретиться в реальных задачах. Так, например, может оказаться, что множество студентов группы, получивших в течении сессии две неудовлетворительные оценки, пусто. Это значит, что таковых студентов нет. Пустым множеством может оказать множество вещественных корней квадратного уравнения. В программировании понятие пустого множества встречается очень часто.

Понятие пустого множества играет очень важную роль при задании множеств с помощью описания. Так, без понятия пустого множества мы не могли бы говорить о множестве отличников группы или о множестве вещественных корней квадратного уравнения, не убедившись предварительно, есть ли вообще в данной группе отличники или имеет ли данное уравнение вещественные корни. Введение пустого множества позволяет совершенно спокойно оперировать с множеством отличников группы, не заботясь о том, есть или нет в рассматриваемой группе отличники. Пустое множество условно относится к конечным множествам.

Пустое множество обозначается символом Ø. Например,

Ø.

Мощность пустого множества. |Ø|=0.

Рассмотрим теперь вопрос о равенстве множеств. Два множества называются равными, если они состоят из одних и тех же элементов, т. е. представляют собой одно и то же множество (пишут А=В). Множества X и У не равны (Х≠У), если либо во множестве X есть элементы, не принадлежащие У, либо во множестве У есть элементы, не принадлежащие X.

Необходимость в проверке равенства множеств может возникнуть тогда, когда множество описано через различные свойства, и необходимо убедиться, что этим свойствам соответствует одно и тоже множество. В общем случае задача проверки равенства множеств является достаточно сложной задачей, требующей больших вычислительных затрат.

Символ равенства множеств обладает свойствами рефлексивности, симметричности и транзитивности:

· X=X — рефлексивность;

· если X=Y, то Y=X — симметричность;

· если X=Y и Y=Z, то X=Z — транзитивность.

Из определения равенства множеств вытекает, что порядок элементов в множестве несуществен. Так, например, множества {3, 4, 5, 6} и {4, 5, 6, 3} представляют собой одно и то же множество.

Из определения множества следует, что в нем не должно быть неразличимых элементов. Поэтому в множестве не может быть одинаковых элементов. Запись {2, 2, 3, 5} следует рассматривать как некорректную и заменить ее на {2, 3, 5}. Так, множество простых делителей числа 60 равно {2, 3, 5}.

Понятие подмножества

Множество X является подмножеством множества У, если любой элемент множества X принадлежит и множеству У. Пусть У — множество студентов группы, а X — множество отличников той же группы. Так как каждый отличник группы является в то же время студентом этой группы, то множество X является подмножеством множества У.

Многие определения теории множеств удобно давать в виде математических выражений, содержащих некоторые логические символы. Для определения подмножества используем два таких символа:

— символ, называемый квантором общности и означающий «любой», «каков бы ни был», «для всех»;

— символ следствия (импликации), означающий «влечет за собой».

Например, утверждение для любого х «х принадлежит X» влечет за собой утверждение «х принадлежит У», запишется так:

.

Более краткой записью выражения «X является подмножеством У» будет запись

,

что читается как «У содержит X». Используемый здесь символ означает включение.

Если множество X является подмножеством множества Y и множество Y не является подмножеством множества X, то говорят, что множество X является строгим (собственным) подмножеством множества Y, и используют символ строгого включения :

.

Связь между символами и дается выражением

и X≠Y.

Здесь использован символ ↔, означающий эквивалентность (в смысле «то же самое, что»).

Следует различать элемент х и одноэлементное множество {х}. Например, Так, если Х={x, y, {x, y}}, то {{x,y}} – подмножество множества Х, содержащее один элемент {x, y}, а в свою очередь этот элемент {x, y} – подмножество, содержащее два элемента x и y . Ясно, что {{x ,y}} {x, y}.

Не надо смешивать отношения принадлежности и включения. Хотя но т.к. единственным элементом множества {{1}} является множество {1}.

Приведем диаграммы всевозможных связей между множествами A и В по отношению к включению.

В этом случае A=B

2.

A есть собственное подмножество B

3.

B есть собственное подмножество A

4.

но множества A и B имеют

общие элементы

5. и

и нет общих элементов

Свойства подмножества, вытекающие из его определения:

· (рефлексивность);

· (транзитивность).

Добавляя к любому множеству пустое множество, мы фактически ничего не добавляем, поэтому всегда можно считать, что любое множество М содержит в себе пустое множество в качестве подмножества:

Ø М.

Если некоторое множество содержит n элементов, то оно имеет 2ⁿ подмножеств. Например, множество М={1, 9, 5, 7, 3} имеет 32 подмножества (2⁵=32), среди которых одно пустое множество, пять одноэлементных, десять двухэлементных, пять четырехэлементных множеств и еще одно – само множество.

Для некоторых широко используемых в математике числовых множеств вводятся стандартные обозначения: N – множество натуральных чисел (целые положительные числа. Отрицательные и нецелые числа — к натуральным не относятся), Z – множество целых чисел (к натуральным числам прибавляем 0 и отрицательные целые числа), Q – множество рациональных чисел (это числа вида m/n где m и n целые и отличные от нуля), R – множество действительных чисел (множество десятичных дробей).

Приведем еще множества, являющиеся числовыми промежутками. Пусть a<b. Отрезок . Интервал Полуинтервал [а, b), замкнутый слева: . Полуинтервал (а, b] замкнутый справа: Замкнутый луч: Открытый луч:

1.2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Предварительные замечания

Операции над множествами рассматриваются для получения новых множеств из уже существующих. Результатом выполнения той или иной операции над множествами является множество.

Объединение множеств

Рассмотрим два множества: X – множество всех четных чисел и Y – множество всех чисел, кратных трем, т.е. Х= {xÎN|x делится на 2} и Y={xÎN|x делится на 3}. Образуем из множеств X и Y новое множество, в которое входили бы все элементы множества X, все элементы множества Y и только они. Это множество естественно назвать объединением множеств X и Y. Внашем примере это будет множество всех чисел, кратных двум или трем, т.е. {xÎN| x делится на 2или делится на 3}.

Определение. Объединением множеств X и У называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X, У, т. е. принадлежат X или принадлежат У. Объединение X и Y обозначается через X У. Формальное определение

.

Здесь союз "или" употреблен в неразделительном смысле, т.е. элементы, содержащиеся одновременно в X и Y, входят в их объединение. Согласно общему принципу образования множества, эти элементы входят в ХÈY только один раз.

Пример 1.1. Если Х={1, 2, 3, 4, 5} и Y={2, 4, 6, 7}, то Х У={1,2,3,4,5,6,7}.

Пример 1.2. Если X—множество отличников в группе, а У — множество студентов, проживающих в общежитии, то X Y — множество студентов, которые или учатся на отлично или проживают в общежитии.

Пример 1.3. Рассмотрим два круга, приведенных на рис. 1.1. Если Х — множество точек левого круга, а У — множество точек правого круга, то X Y представляет собой заштрихованную область, ограниченную обоими кругами.

Рис. 1.1. Объединение множеств

Понятие объединения можно распространить и на большее число множеств. Обозначим через ={X₁, ,Xn} совокупность п множеств Х₁,..., Х_п, называемую иногда системой множеств. Объединение этих множеств

представляет собой множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств системы .

Свойства операции объединения:

· XÈX=X; (идемпотентность объединения)

· ; (коммутативный закон)

· ассоциативный закон

· X Ø=X.

Последнее свойство очевидно, так как пустое множество не содержит элементов, а значит, X и X Ø состоят из одних и тех же элементов. Из (1.11) видно, что пустое множество Ø играет роль нуля в алгебре множеств – имеет место аналогия с выражением а+0= а в обычной алгебре.

Пересечение множеств

Определение. Пересечением множеств X и У называется множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству У. Пересечение множеств X и У обозначается через X Y. Формальное определение

.

Пример 1.4. Для множеств X и У в примере 1.1X Y={2, 4}.