Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

1. Понятие о множестве. Типовые обозначения

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

Объекты, из которых состоит множество, называют его элементами или точками.

Слова множество, совокупность, класс, набор, семейство - синонимы.

Множества обозначаются большими латинскими буквами: , элементы множеств - маленькими: .

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

Часто приходится рассматривать не все множество, а только его часть. Например, рассматривается не все множество натуральных чисел, а только множество простых чисел. Вместо слов «часть множества» говорят «подмножество».

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

Если два множества состоят из одних и тех же элементов, то они называются равными.

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

Пример 1.1

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

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

Более подробно о свойствах универсального множества мы поговорим, обсуждая операции над множествами. Скажем только, что если роль нуля в алгебре множеств играет пустое множество. То универсальное множество, играет роль единицы в алгебре множеств.

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

- элемент принадлежит множеству ,

- элемент не принадлежит множеству ,

- множество является подмножеством множества ,

- множество не является подмножеством множества ,

- совокупность подмножеств множества ,

- множества и равны,

- множества и не равны,

Ш - пустое множество,

- мощность множества,

- мощность совокупности подмножеств множества (смысл понятия мощности множества будет раскрыт чуть позже).

Замечание 1.1

1) любое множество является подмножеством самого себя: ,

2) тогда и только тогда, когда одновременно и ,

3) по определению полагают, что пустое множество есть подмножество любого множества: Ш .

2. Способы задания множеств

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

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

Запись означает, что множество состоит из элементов .

2) описание общего свойства элементов множества

В общем случае это выглядит так: , где - общее свойство элементов множества .

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

3) процедурный (рекурсивный)

Задается процедура (рекурсивный алгоритм) порождения элементов множества по некоторым, уже имеющимся в нем, элементам:

Пример 2.1

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

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

Для наглядности мы будем рассматривать множества в виде некоторых совокупностей точек плоскости, а вводимые операции сопровождать рисунками - так называемыми кругами Эйлера. Результатами операций будут являться заштрихованные области на соответствующих рисунках.

Итак, на множествах можно ввести следующие операции:

1) объединение

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

,

Рис. 1

2) пересечение

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

,



Рис. 2

3) разность

Разностью множеств и называется множество (), состоящее из элементов, которые принадлежат множеству, но не принадлежат множеству (Рис. 3.3).

То есть, по определению,

.

Рис. 3

4) дополнение

Если  - универсальное множество, то дополнением множества А до U называют разность (Рис. 4).

То есть, по определению,

.



Рис. 4

5) также часто рассматривают дополнительную операцию, которая называется симметрическая разность.

Симметрической разностью множеств и называется множество элементов, которые принадлежат множеству, но не принадлежат множеству , или принадлежат множеству , но не принадлежат множеству . (Рис. 3.5)

То есть, по определению,

.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 5

математический множество разность

Пример 3.1

1) Пусть , , тогда

, , , , .

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

2) Пусть , , тогда

, , , , .

Если взять в качестве универсального множества взять - множество действительных чисел, то

, а .

3) Пусть , , тогда

, , , , .

Если взять в качестве универсального множества взять, например,

, то

, а .

4. Характеристические функции множеств. Свойства операций над множествами

Определение 4.1

Функция называется характеристической функцией множества .

Свойства характеристических функций

1. (равенство множеств означает равенство их характеристических функций и наоборот),

2. (характеристическая функция произведения множеств равна произведению характеристических функций сомножителей),

3. (характеристическая функция суммы множеств равна разности суммы характеристических функций слагаемых и их произведения),

4. (характеристическая функция дополнения множества равна разности единицы и значения его характеристической функции),

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

6. (характеристическая функция универсального множества тождественно равна единице),

7. _Ш (характеристическая функция пустого множества тождественно равна нулю).

Свойства характеристических функций, очевидно, следуют непосредственно из определения 4.1. Читателю предлагается проверить это самостоятельно.

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

Теорема 4.1

Пусть - универсальное множество, , тогда справедливы следующие свойства операций над множествами:

1) коммутативность

,

2) ассоциативность

,

3) дистрибутивность

пересечения относительно объединения

,

объединения относительно пересечения

,

4) Ш, Ш ,

5) , ,

6) Ш , Ш =Ш,

7) , Ш,

8) идемпотентность

, ,

9) законы Де'Моргана

,

,

Доказательство:

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

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

Доказано.

5. Декартово произведение множеств. Отношения на множествах

Определение 5.1

Пусть и - непустые множества. Множество - всевозможных упорядоченных пар вида , где , - называется декартовым произведением множеств и .

Если , то вместо пишут. Множество называют декартовым квадратом множества .

Пример 5.1

1) Пусть и , тогда

.

2) Пусть и , тогда - прямоугольник на плоскости (Рис. 5.1).

Рис. 5.1

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

.

Если , вместо пишут. Множество называют -й декартовой степенью множества .

Отношения на множествах

Пусть - непустые множества.

Определение 5.2

Бинарным отношением называется любое подмножество декартова произведения двух множеств.

называют бинарным отношением на множестве , если . При этом вместо записи часто используют запись , где .

Если , где , то говорят, что определено на паре множеств и .

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

Определение 5.3

называется отношением эквивалентности (~) если:

- (рефлексивность),

- (симметричность),

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

Пример 5.2

Пусть - множество треугольников на плоскости.

Введем на бинарное отношение равенства площадей треугольников: . По определению, является отношением эквивалентности. Убедитесь в этом самостоятельно.

Определение 5.4

Система непересекающихся подмножеств , в сумме дающая само множество, называется его разбиением.

Утверждение 5.1

1) Всякое отношение эквивалентности ~ на задает его разбиение на классы эквивалентности (, где - класс эквивалентности, содержащий ).

2) Всякое разбиение множества задает на нем отношение эквивалентности ~: две точки эквивалентны, если они лежат в одном элементе разбиения (Рис. 5.2).



Рис. 5.2

Определение 5.5

Пусть ~ - отношение эквивалентности на и - разбиение множества на классы эквивалентности по этому отношению.

Возьмем по одному представителю из каждого класса, получим некоторое подмножество . Это подмножество называется фактор-множеством по отношению эквивалентности ~ и обозначается .

.

Пример 5.3

Рассмотрим отношение эквивалентности на множестве целых чисел : , то есть два целых числа эквивалентны, если их разность делится на два.

Очевидно, что отношение ~ разбивает на два класса эквивалентности - множество четных чисел и - множество нечетных чисел. . В качестве фактор множества по отношению эквивалентности ~ можно взять множество

Определение 5.6

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

- (сравнимость в одну строну),

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

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

Если рефлексивно, то говорят об отношении нестрогого порядка, в противном случае, рассматривают строгий порядок.

Пример 5.4

1) Введем на множестве целых чисел бинарное отношение сравнения чисел: , то есть два целых числа эквивалентны, если первое из них в обычном смысле меньше второго.

По определению, отношение , заданное таким образом является отношением строгого линейного порядка.

2) Пусть - совокупность множеств точек плоскости.

Введем на бинарное отношение вложения множеств:

.

Возможны две ситуации: и (Рис. 5.3).

Рис. 5.3

По определению, является отношением нестрогого частичного порядка.

6. Мощность множества

Понятие мощности множества служит для количественной характеристики множеств.

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

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

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

Введем аккуратно понятие взаимно-однозначного соответствия множеств. Из школы вам, наверняка, уже известно понятие функции. Вспомним, что это такое.

Пусть - непустые множества.

Определение 6.1

Функцией называется правило, по которому каждому элементу - аргументу функции, ставится в соответствие единственный элемент , - значение функции.

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

Определение 6.2

Функция называется взаимно-однозначной (по-другому, биекцией, взаимно-однозначным соответствием), если для каждого элемента найдется единственный элемент такой, что . Обозначение .

Определение 6.3

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

Если и количественно эквивалентны, то пишут (читается «мощность множества равна мощности множества »).

Если - конечное множество, то равномощное ему множество содержит одинаковое с ним количество элементов, поэтому полагают , где - количество элементов в .

Пример 6.1

Если А={-9;0;7;23}, то |А|=4.

Если =Ш, полагают .

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

Определение 6.4

Бесконечное множество называется счетным (счетной мощности), если оно равномощно множеству натуральных чисел, то есть (, - множество натуральных чисел).

Если - счетное, пишут .

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

Пример 6.2 (примеры счетных множеств)

1) N={1;2;3;4;…} - множество натуральных чисел,

2) Z={0;1;-1;2;-2;3;-3;4;-4;…} - множество целых чисел,

3) Q={| m, n - целые числа, n?0} - множество рациональных чисел.

Определение 6.5

Множество называется несчетным, если оно не является счетным.

Утверждение 6.1

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

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

Определение 6.6

Говорят, что - множество мощности континуум (или имеет мощность континуум), если оно равномощно множеству действительных чисел ().

Если - множество мощности континуум, пишут .

Пример 6.3 (примеры множеств мощности континуум)

1) - множество действительных чисел,

2) все числовые промежутки, содержащие больше одной точки,

3) совокупность подмножеств множества натуральных чисел (),

4) множество бесконечных двоичных последовательностей .

Утверждение 6.2 (свойства мощностей множеств)

1) Всякое бесконечное подмножество содержит счетное подмножество,

2) Всякое подмножество счетного множества конечно или счетно,

3) Добавление к бесконечному множеству конечного или счетного множества не меняет его мощности.

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

Мощность множества считается меньшей, чем мощность множества , если в найдется подмножество равномощное , но в подмножество равномощное отсутствует.

То есть, .

Теорема 6.1 (Кантора-Бернштейна)

Если одновременно и , тогда .

Теорема 6.2 (Кантора)

Мощность совокупности подмножеств любого непустого множества больше мощности самого множества (Ш).

Следствие 6.1

Существуют мощности больше любой наперед заданной.

Для подтверждения этого достаточно перейти от множества заданной мощности к совокупности его подмножеств и воспользоваться теоремой Кантора.

Замечание 6.1

1) Если конечно и , то можно показать, что ,

2) Для обозначения различных мощностей множеств используют так называемые кардинальные числа .

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

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

Формулы включений и исключений

Пусть - конечные множества. Причем нам известны их мощности и мощность пересечения . И мы хотим через эти известные значения выразить мощность объединения , то есть количество элементов в нем (Рис. 6.1).

Рис. 6.1

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

,

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

Аналогичную формулу можно выписать для случая трех множеств :

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

Пример 6.4

В доме проживает 200 семей, из которых 180 имеют компьютер и 150 автомобиль, при этом 14 семей не имеют компьютер, но имеют автомобиль.

Сколько семей имеют и то и другое.

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

По условию получаем

, , .

С одной стороны, имеем

,

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

а с другой,

,

значит,

.

Размещено на Allbest.ru

...