Элементы теории множеств

1.1. Основные понятия и определения теории множеств

Любое понятие дискретной математики можно определить с помощью понятия множества, которое является одним из фундаментальных понятий и было сформулировано впервые немецким математиком Г. Кантором.

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

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

Отдельные объекты, из которых состоит множество, называют элементами множества. Так, число 3 – элемент множества натуральных чисел, а буква б – элемент мно­жества букв русского алфавита.

Общим обозначением множества служит пара фигур­ных скобок { }, внутри которых перечисляются элементы множества. Для обозначения конкретных множеств исполь­зуют различные прописные буквы A, S, X... или пропис­ные буквы с индексами А ₁, А ₂. Для обозначения элементов множества в общем виде используют различные строчные буквы а, s, x... или строчные буквы с индексами а ₁, а ₂...

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

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

Будем использовать следующие обозначения для числовых множеств:

– множество натуральных чисел, т.е.

– множество целых чисел, т.е. = {0, ±1, ±2, …};

– множество рациональных чисел, ={ / \ , Î ; ¹ 0};

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

– множество комплексных чисел.

Множества бывают конечными и бесконечными. Мно­жество называют конечным, если число его элементов ко­нечно, т. е. если существует натуральное число n, являю­щееся числом элементов множества. Множество называют бесконечным, если оно содержит бесконечное число эле­ментов. Количество элементов конечного множества называется мощностью и обозначается = n, если множество X содержит n элементов.

Важным понятием теории множеств является понятие пустого множества. Пустым множеством называют мно­жество, не содержащее ни одного элемента. Пустое множествообозначают символом Например:

{ x Î R | x ²- x +1=0}=

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

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

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

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

X ={ x | x обладает свойством Q (x)}.

Выражение в скобках читается: множество всех элементов х, которые обладают свойством Q (x). Так, если М — множество сту­дентов группы, то множество A отличников этой группы запишется в виде А ={ х Î М | х – отличник группы},

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

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

А={ х | х – отличник группы}.

Приведем несколько примеров задания множеств мето­дом описания: { x | x – четное} – множество четных чисел;

{ х | х ²–1=0} – множество {+1, –1}.

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

Множество нечетных чисел можно определить как { x | x =2 k +1 для некоторого k Î Z }.

Способ задания множества с помощью свойств таит некоторые опасности, поскольку «неправильное» заданные свойства могут привести к противоречию. Приведем один из наиболее типичных парадоксов – парадокс Рассела. Рассмотрим множество всех множеств, которые не являются своими собственными элементами: . Спросим теперь, является ли множества К своим элементом? Если К Î К, то должно выполняться свойство, задающее множество К, т.е. К Ï К, что приводит к противоречию. Если К Ï К, то, поскольку выполняется свойство, задающее К, приходим к тому, что К Î К, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмысленному заданию множества.

Кроме того, множество можно задать с помощью характеристической функции, значения которой указывают является ли (да или нет) х элементом множества Х:

Заметим, что для любых элементов = 0; = 1.

Пример. Пусть на универсуме U ={ a,b,c,d,e } определено множество X ={ a,c,d }, тогда

Для произвольных множеств X и Y можно определить два типа отношений – отношение равенства и отношение включения.

Два множества считаются равными, если они состоят из одних и тех же элементов. Принято обозначение X = Y, если X и Y равны, и X Y – иначе.

Легко видеть, что для любых множеств X, Y, Z справедливы соотношения

,

,

( и ) .

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

Если каждый элемент множества X является элементом множества Y, то говорят, что X включено в Y и обозначают :

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

,

( и .

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

( и .

Невключение подмножества X в множество Y обозначается

Пример. Пусть Y — множество студентов группы, а Х – множество отличников той же группы. Так как каждый отличник группы является в то же время студентом этой группы, то множество X является подмножеством множе­ства Y.

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

Пример. Справедливы следующие включения: N Ì Z, Z Ì Q, Q Ì R, R Ì C.

Заметим, что если X является подмножеством Y и наоборот, то X и Y состоят из одних и тех же элементов, поэтому

и

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

Пример. Покажем, что множества М₁ ={ x | sin x = 1} и M₂ ={ x | x = , } совпадают.

Если x М₁, то x является решением уравнения sin x =1. Но это значит, что x можно представить в виде x = и поэтому x М₂. Таким образом, . Если x М_{2 ,} т.е. x = , то sin x =1, т.е. . Следовательно, М₁ = М₂.

Для каждого множества X существует множество, элементами которого являются различные подмножества множества X. Такое множество называется семейством множества или булеаном множества X и обозначается P (X) Так как включено в любое множество, то .

Пример. Пусть . Тогда

Дата добавления: 2014-12-27