Множества и операции над ними

 

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

Множество состоит из элементов и полностью определяется ими. Принадлежность элемента a множеству A обозначают ; запись  означает, что a – не элемент A.

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

Примеры. 1) Запись вида означает, что множество   A состоит из трех элементов a, b и c.

2) {человек│человек является студентом СПбГЭУ}. Множество A – множество студентов СПбГЭУ.

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

 

Числовые множества

 

Перечислим общепринятые обозначения числовых множеств.

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

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

Q – множество рациональных чисел.  Рациональным числом называется число, которое может быть представлено в виде отношения  , где , .

  R – множество действительных чисел.

 

    Два множества называются равными, если они состоят из одних и тех же элементов. Равенство множеств A и B обозначают: .

    Множество A называется подмножеством множества B если каждый элемент множества A является элементом множества B. В этом случае также говорят, что имеет место включение множества A в множество B и обозначают  (или ).

    Для любого множества A верно, что  и .

    Очевидно, что  тогда и только тогда, когда  и .

 

Операции над множествами

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

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

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

Следующие свойства операций объединения и пересечения множеств следуют непосредственно из определений:

1) Коммутативность объединения и пересечения множеств

(переместительный закон):

; .

2) Ассоциативность объединения и пересечения множеств

(сочетательный закон):

; .

3) ; .

4) ; .

Следующие два свойства называются дистрибутивностью объединения

и пересечения множеств (распределительным законом):

5) .

6) .

Замечание. Для обозначения объединения множеств  

используют обозначение . Аналогичное обозначение используют для пересечения множеств: .

Разностью множеств A и B (или дополнением множества B в

множестве A) называется множество, обозначаемое A \ B, состоящее из элементов множества A, не входящих в множество B.

Пример. Пусть и . Тогда A \ B , B \ A .

Операции с множествами – объединение, пересечение и разность (дополнение) – связаны между собой так называемыми соотношениями двойственности: дополнение к объединению множеств равно пересечению их дополнений, а дополнение к пересечению – объединению дополнений. Действительно, пусть A, B и C – три множества. Докажем, что:

\ \ A) \ B).                        

Пусть . Это означает, что

Второе соотношение двойственности:  доказывается аналогично.

Будем считать, что все множества в рассматриваемой задаче содержатся в одном и том же множестве U (универсальном множестве). Тогда дополнение множества A в множестве U будем обозначать . В этих обозначениях соотношения двойственности принимают вид:

 и ,

и известны как формулы де Моргана.

    Прямым (декартовым) произведением двух множеств A и B называется множество, обозначаемое , элементами которого являются упорядоченные пары , где .

Пример. , . Тогда и .

 

Отображения и функции

 

Определение 2.1. Рассмотрим два непустых множества X  и Y. Если каждому элементу множества X соответствует один элемент множества Y, то говорят, что задано отображение f множества X в множество Y.

Этот факт обычно записывают в виде:

                       .    

Определение 2.2. Элемент из множества Y, соответствующий элементу , обозначают  и называют образом элемента x относительно отображения f.  При этом элемент x называется прообразом элемента  относительно отображения f.  Множество X называется областью определения отображения f.

Определение 2.3. Пусть f – отображение множества X в множество Y, а множество A является подмножеством множества X. Множество  называется образом множества X при отображении f  и обозначается . В этом случае множество A называется прообразом множества .

Пример. Пусть X – множество студентов потока, находящихся в аудитории на лекции, а Y – множество стульев, находящихся в этой аудитории. Рассмотрим отображение f, сопоставляющее каждому студенту стул, на котором он сидит (при условии, что все студенты на лекции сидят). Тогда стул, занимаемый студентом является образом данного студента при отображении f. Рассмотрим множество , A – множество студентов из одной определенной группы потока. Тогда  – множество стульев, занимаемых студентами из данной группы.

Определение 2.4. Отображение f множества X в множество Y называется функцией, если множество Y – числовое множество.

Определение 2.5. Отображение f множества X в множество Y называется сюръективным, или “ отображением на ”, если образом области определения X является все множество Y.

Отображение f множества X в множество Y называется инъективным, если для любых из условия  следует .

Отображение f множества X в множество Y называется биективным, если оно сюръективно и инъективно. Биективное отображение также называют взаимно однозначным соответствием.

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

2) Пусть , . Отображение  задается формулой:

. Тогда отображение f является функцией. При этом оно не сюръективно (). Оно также и не инъективно, так как разным значениям x могут соответствовать равные образы, например, .

3) Пусть , . Отображение  задается формулой:

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

4) Пусть , . Отображение  задается формулой:

. В этом случае отображение f  сюръективно, так как , но не инъективно.

5) Пусть , , Отображение  задается формулой:

. В этом случае отображение f  , очевидно, сюръективно и инъективно, следовательно, биективно.

 

Сравнение множеств

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

    Определение 3.1. Говорят, что два множества имеют одинаковую мощность (равномощны), если между элементами этих множеств можно установить взаимно однозначное соответствие.

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

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

    Определение 3.2. Бесконечное множество называется счетным, если оно имеет одинаковую мощность с множеством натуральных чисел N.

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

Примеры. 1) Множество целых чисел Z счетно. Действительно, составим таблицу, в первой строке которой записаны целые числа, а во второй – их натуральные номера:

Z	0	-1	1	-2	2	-3	3	-4	…
N	1	2	3	4	5	6	7	8	…

 

2) Пусть множества A и B счетны. Тогда их прямое произведение  тоже счетно. Для доказательства этого составим бесконечную (вправо и вниз) таблицу, в которой каждой строке соответствует элемент множества A, а каждому столбцу – элемент множества B. В клетках таблицы поставим натуральные числа – номера элементов множества  так, как показано стрелками. Очевидно, что таким образом каждому элементу  будет соответствовать свой определенный номер, причем разным элементам будут соответствовать разные номера. Это и доказывает счетность множества .

 

					…
	1	4	5	16
	2	3	6	15
	9	8	7	14
	10	11	12	13

 

3) Множество рациональных чисел Q счетно. Для доказательства этого рассмотрим прямое произведение двух счетных множеств: , оно, как было доказано в примере 2, счетно. Это значит, что каждой упорядоченной паре чисел , где , можно присвоить натуральный номер. Тогда и каждой обыкновенной дроби , можно присвоить натуральный номер, следовательно, множество обыкновенных дробей также счетно. Поскольку каждое рациональное число может быть представлено в виде различных обыкновенных дробей (например, рациональное число  можно представить также в виде дробей ,  и т. д.), множество рациональных чисел Q можно отождествить с некоторым подмножеством множества обыкновенных дробей. А так как множество Q бесконечно, то оно, очевидно, счетно.

    Рассмотрим теперь пример множества, которое не является счетным. Докажем, что интервал не является счетным.

    Предположим, что интервал  – счетное множество. Это значит, что все числа из  удалось каким-то образом занумеровать:  . Каждое такое число можно записать в виде бесконечной десятичной дроби:

               ,

     ,

     …………………………….

     …………………………….

      ,

где , .

    Напишем теперь десятичную дробь , цифры которой удовлетворяют условию: . Понятно, что тогда  ни при каком . Но с другой стороны . Следовательно, нам не удалось занумеровать все числа из интервала  вопреки предположению.

    Этот пример показывает, что имеются множества, не являющиеся счетными.

Определение 3.3. Будем говорить, что множество действительных чисел, составляющих интервал имеет мощность континуум, и все множества равномощные с интервалом  также имеют мощность континуум.

    Примеры. 1) Множество всех действительных чисел R имеет мощность континуум. Действительно, взаимно однозначное соответствие между интервалом  и множеством R можно установить, например, с помощью функции , которая каждому числу  ставит в соответствие число y по формуле . Из свойств этой функции следует, что она является взаимно однозначным соответствием, значит множества  и R равномощны, а это и означает, что R имеет мощность континуум.

2) Очевидно, что любой интервал  также имеет мощность континуум. Привести пример взаимно однозначного соответствия интервалов  и  предоставляется читателю.

3) Полуинтервал также имеет мощность континуум. Для доказательства этого построим биективное отображение полуинтервала  на интервал следующим образом. В интервале выделим какое-нибудь счетное подмножество, например, . Если мы объединим это множество с множеством , то полученное множество также, очевидно, будет счетным. Это значит, что существует биективное отображение f  множества A на множество B. Распространим отображение f на точки множества \ A следующим образом: . Таким образом мы получили, что существует биективное отображение f интервала  на полуинтервал , что и доказывает равномощность этих множеств.

Можно доказать, что мощность континуум имеет и множество всех

точек плоскости, и множество точек пространства, и множество  при всех .

 

Бинарные отношения

 

Определение 4.1. Пусть A – некоторое множество. Рассмотрим декартово произведение   и некоторое его подмножество . Тогда называется бинарным отношением на множестве A.

Говорят, что элемент находится в отношении  с элементом , если упорядоченная пара . Этот факт также записывают в виде .

Примеры. 1) Пусть . Определим бинарное отношение  на множестве R следующим образом: , .

2) Пусть A – множество студентов потока, тогда  – множество упорядоченных пар студентов. Рассмотрим , определяемое следующим образом: студенты x и y учатся в одной группе.

     Рассмотрим ряд определений, связанных с понятием бинарного отношения.

    Определение 4.2. Пусть , , т. е. отношение не выполняется ни для одной пары элементов множества A. Тогда отношение называется пустым.

Пример. Пусть , тогда . Рассмотрим отношение . Очевидно, что .

    Определение 4.3. Пусть . Тогда отношение называется полным.

    Определение 4.4. Пусть . Рассмотрим бинарное отношение . Бинарное отношение называется дополнительным к бинарному отношению .

Пример. Рассмотрим предыдущий пример, где A – множество студентов потока и бинарное отношение определяется так: студенты x и y учатся в одной группе. Тогда  студенты x и y учатся в разных группах.

    Определение 4.5. Пусть . Рассмотрим бинарное отношение , определяемое следующим образом: .  Бинарное отношение называется противоположным бинарному отношению .

Примеры. 1) Пусть . Пусть , . Тогда .

2) Пусть A – множество студентов потока и бинарное отношение определяется так: студенты x и y учатся в одной группе. Тогда, очевидно, .

 

Свойства бинарных отношений

 

    Рассмотрим бинарное отношение на множестве A.

1. Рефлексивность. Бинарное отношение называется рефлексивным, если

выполняется , для всех .

2. Симметричность. Бинарное отношение называется симметричным,

если , для всех .

3. Транзитивность.Бинарное отношение называется транзитивным,

если , для всех .

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

2) Пусть A – множество всех людей на Земле. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: человек x является братом или сестрой человека y (т. е. x и y имеют хотя бы одного общего родителя). Тогда , очевидно, рефлексивно, симметрично, но не транзитивно.

    Определение 4.6. Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности называется отношением эквивалентности.

Примеры. 1) Пусть . Рассмотрим бинарное отношение  на множестве R, определяемое следующим образом: . Тогда является отношением эквивалентности. Действительно, рефлексивно, поскольку  для всех . Бинарное отношение , очевидно, также симметрично и транзитивно.

2) Пусть A – множество студентов потока. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: студенты x и y учатся в одной группе. Тогда  является отношением эквивалентности. Действительно, рефлексивность означает, что каждый студент учится сам с собой в одной группе. Симметричность  означает, что если студент x учится в одной группе со студентом y, то и студент y учится в одной группе со студентом x. Транзитивность  означает, что если студент x учится в одной группе со студентом y, а студент y учится в одной группе со студентом z, то студент x учится в одной группе со студентом z.

    Отношение эквивалентности часто обозначают знаком .

    Определение 4.7. Рассмотрим множество A и  – отношение эквивалентности на множестве A. Пусть  – подмножество множества A, определяемое следующим образом: . Тогда множество называется классом эквивалентности элемента x, порожденным отношением эквивалентности .

    Свойства классов эквивалентности

1. Классы эквивалентности элементов множества не пусты. Действительно, класс эквивалентности множества x содержит элемент x: .

2. Пусть . Тогда .

Доказательство. Пусть . Это значит, что . Но , значит . Из транзитивности отношения  следует, что . Значит, . Следовательно, .

Пусть теперь . Это значит, что . Поскольку , имеем . Из симметричности отношения  следует, что , а тогда по транзитивности отношения  получим, что . Это значит, что . Следовательно, .

Если  и , то .

3. Если , то .

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

Определение 4.8. Рассмотрим множество A. Пусть , . Множество  называется разбиением множества A, если оно удовлетворяет условиям:

1) ,

2) , при .

    Примеры. 1) Множества четных чисел и нечетных чисел составляют разбиение множества целых чисел.

2) Множество всех людей живущих на Земле можно представить в виде разбиения на подмножества, состоящих из людей определенного года рождения.

    Теорема 4.1. Классы эквивалентности множества A составляют разбиение множества A.

    Доказательство.  Рассмотрим множество  – классов эквивалентности множества A, порожденных некоторым отношением эквивалентности. Докажем, что множество является разбиением множества A.

1) Докажем, что . Пусть  и , . Очевидно, что , , следовательно, .

Пусть . Тогда найдется такой класс эквивалентности , что

. Значит, , и тогда .

Если  и , то .

2) Условие  при  следует из свойства 3 классов эквивалентности. Теорема доказана.

    Определение 4.9. Рассмотрим множество A и  – отношение эквивалентности на A. Пусть  – классы эквивалентности, порожденные отношением  . Множество называется фактор-множеством множества A по отношению эквивалентности  , и обозначается   A │_̴̴ .

Примеры. 1) Пусть A – множество студентов потока. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: студенты x и y учатся в одной группе. Тогда, как было установлено выше, отношение  является отношением эквивалентности. При этом элементами фактор-множества A │_Δ, порожденного отношением , являются группы данного потока.

2) Рассмотрим множество целых чисел Z и введем на этом множестве бинарное отношение :  разность является четным числом. Отношение  , очевидно, является отношением эквивалентности. Фактор-множество Z│_Δ  состоит из двух элементов – множества четных чисел и множества нечетных чисел.

 

Продолжим изучение свойств бинарных отношений.

 

4. Бинарное отношение  на множестве A называется антисимметричным,  если из условия  следует, что .

Пример. Пусть . Рассмотрим бинарное отношение