Теория множеств(пособие ЕНФ)(Водопьянов)

Министерство образования и науки Российской Федерации

ГОУ ВПО УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕ-

СКИЙ УНИВЕРСИТЕТ Кафедра математики

МНОЖЕСТВА И ОПЕРАЦИИ НАД НИМИ. ОТНОШЕНИЯ И ФУНКЦИИ. МОЩНОСТЬ МНОЖЕСТВ. КОМБИНАТОРИКА

Учебное пособие

Уфа - 2007

3

Составители: Ахметова Н.А., Водопьянов В.В.

УДК

Множества и операции над ними. Отношения и функции. Мощность множеств. Комбинаторика. Учебное пособие/Уфимск. авиац. техн. унив-т; Сост. Н.А.Ахметова, В.В.Водопьянов.- Уфа, 2007.- 37 с.

Предлагаемое учебное пособие содержат теоретические и практические задания по разделу, который относится к основаниям математики. Данный раздел читается для студентов, обучающихся на направлениях и специальностях «Прикладная математика и информатика», «Прикладная математика», «Компьютерная математика», как правило, в курсе «Математического анализа». Излагаемый материал представляет интерес и как вводная часть для многих курсов: «Дискретная математика», «Функциональный анализ», «Теория вероятности и математическая статистика» и др. В пособии достаточно подробно рассмотрены вопросы аксиоматического построения теории множеств, операции над множествами, понятие мощности множества. Пособие представляет интерес также для студентов других специальностей, которые изучают упоминаемые разделы математики, в первую очередь для студентов, обучающихся по направлению “Информатика и вычислительная техника”.

Ил. 1. Библиогр.: 9 назв.

Рецензенты:

4

«Высшее назначение математики…состоит в том, чтобы находить скрытый порядок в хаосе, который нас

окружает»

Н.Винер1 «Жизнь украшается двумя вещами: занятием математикой и ее преподава-

нием»

С.Д.Пуассон1

§1. Введение. Понятие множества

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

значительно позже - в 19 веке. Большое влияние на формирование этого понятия оказали работы Больцано1, Дедекинда1, Дюбуа-Реймона1, но эти математики рассматривали лишь конечные множества. Переход к изучению бесконечных множеств и операций над ними представлял принципиальную трудность. Свидетельством последнего являются различные противоречия (антиномии теории множеств), открытые разными учеными к 1900 г. Изучение бесконечных множеств было начато в работах Георга Кантора в 1871-1883 гг., которые встречали активное сопротивление современников. Кантор употреблял вначале термин Inbegrift - “совокупность”, затем Mannigfaltigkeit - “многообразие”, и наконец, Menge - “множество”, в настоящее время сохранилось его обозначение множества M = {m}, которое он ввел в 1895 году. Официальное признание теории множеств прозвучало на Первом международном математическом конгрессе (Цюрих, 1897 г.), где Адамар и Гурвиц указали на важные применения этой теории к анализу. Большое значение в распространении идей теории множеств принадлежит Гильберту. Именно он сказал: “Никто не сможет нас изгнать из рая, созданного Кантором”.

Георг Кантор считается основателем современной теории множеств. В его работах началось построение аксиоматической теории множеств, хотя первая система аксиом теории множеств была предложена позднее в работах Цермело

в1904-1908 гг. Эта система аксиом позволила получить важные для математики результаты по теории множеств. Но лишь в 1940 году Гедель построил наиболее полную систему аксиом и доказал ее непротиворечивость.

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

1 См. биографическую справку

5

Что же такое множество по Г.Кантору? Множество по Кантору - это любое собрание определенных и различных между собой объектов нашей интуиции или интеллекта, мыслимое как единое целое.

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

Интуитивный принцип объемности Г. Кантора (1 аксиома Геделя):

множества А и В считаются равными (А = В), если они состоят из одних и тех же элементов.

Рассмотрим некоторые примеры множеств (одновременно мы увидим некоторые способы их задания):

А = {множество всех положительных четных целых чисел}, В = {множество всех положительных целых чисел, представимых в виде

суммы двух положительных нечетных целых чисел},

C = {2, 4, 6},

D = {2, 6, 4}.

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

Рассмотрим еще два примера: А = {1, 2}, B = {{1}, 2}. Нетрудно заметить, что А В. Это связано с тем, что множество А состоит из двух элементов: 1 и 2, а множество В из двух элементов: {1} и 2, где {1} не является числом, а является множеством, состоящим из одного элемента.

Для некоторых множеств существуют стандартные обозначения:

- пустое множество, т.е. множество не имеющее ни одного элемента (наличие такого множества предполагается второй аксиомой Геделя);

N - множество натуральных чисел; Z - множество целых чисел;

Q - множество всех рациональных чисел; R - множество всех действительных чисел;

Добавление к упомянутым множествам знака “+” выделяет из них только положительные числа, например, Z+ - множество целых положительных чисел.

6

Одним из основных приемов задания множества является задание его с помощью так называемых форм, т.е. выражения вида А= {x: P(x)}. Здесь P(x) некоторое высказывание и множество А состоит только из тех x, для которых

высказывание P(x) является верным. Например,

A = {x: x2 + x + 1 > x};

B = {x: х любит Джона}.

Отметим, что множеству А принадлежат все действительные числа, т.е. оно совпадает с множеством R.

Интуитивный принцип абстракции Г.Кантора: любая форма Р(х)

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

Оказалось, что интуитивный принцип абстракции не совсем точен и может привести к парадоксам. Один из таких парадоксов был приведен в 1902 году Б.Расселом. Он состоит в следующем: будем говорить, что множество А обладает свойством D, если для него верно А А. Введем теперь множество

Т = {А: А удовлетворяет свойству D}.

Заметим, что если Т Т, то множество Т не удовлетворяет свойству D и, следовательно, Т Т. Если же Т Т, то множество Т удовлетворяет свойству D и, следовательно, Т Т.

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

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

Уточнением интуитивного принципа абстракции является аксиома выбора Геделя, позволяющая избежать указанного парадокса: для любого высказывания Р и любого множества А существует множество, состоящее из тех и только тех элементов множества А, для которых высказывание Р(х) является истинным, то есть форма задается в виде {x A: P(x)}.

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

Задачи.

1)Равны ли множества:

a){{1, 2}, {2, 3}} и {1, 2, 3};

7

b){{1, 2}} и {1, 2};

c){x: x N и x < 5} и {x: x N и (x+1)2 < 29}.

2)Верно ли, что {1, 2} {{1, 2, 3}, {1, 3}, 1, 2}.

3)Привести пример множеств A, B, C: A B, B C, но A C.

4)Доказать, что для всех a, b, c, d равенство {{a}, {a, b}} = {{c}, {c, d}} выполняется тогда и только тогда, когда a = c и b = d.

§ 2. Включение множеств. Операции над множествами

Определение. Говорят, что множество А включено в множество В (и пишут А В или В А), если для любого элемента а А справедливо а В.

Например, очевидны следующие включения N Z Q R. Свойства:

1)для любого множества А справедливо включение А А;

2)если А В и В А, то А = В;

3)если А В и В С, то А С;

4)для любого множества А справедливо включение А. Доказательство. Приведем доказательство лишь одного - четвертого

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

Замечание. Необходимо различать символ принадлежности и символ включения . Символ принадлежности не обязан удовлетворять тем же свойствам что и символ включения. Так, например, 1 Z, Z {Z}, однако 1 {Z}.

Операция “объединение множеств”. Пусть А и В два множества. Объ-

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

А В = {x: х А либо х В}.

Операция “разность множеств”. Для множеств А и В разность множеств А-В состоит из тех и только тех элементов х, которые удовлетворяют следующим двум условиям х А и х В:

А - В = {х: х А и х В}.

Операция “пересечение множеств”. Для множеств А и В их пересечени-

ем А В называется множество таких элементов х, которые принадлежат как А, так и В:

А В = {х: х А и х В}.

Операция “симметрическая разность множеств”. Для множеств А и В их симметрической разностью называется множество

А В = (А – В) (В – А).

8

Наиболее часто нами будут использоваться операции объединения и пересечения. Они могут быть распространены на любое число множеств (так же как и другие операции):

I А = {х: I: х А },

I А = {х: I: х А }.

Вслучае, когда множество индексов I = N, применяется запись вида n .

Например,

если Аn = (–1/n, 1/n ), то nАn = {0}.

Если В А, то разность множеств А – В называют еще дополнительным множеством к В или просто дополнением в А и обозначают ВC.

Операции над множествами хорошо иллюстрируются диаграммами Венна

Теорема 1. Для любых множеств A, B, C, D справедливы равенства

1. A (B C) = (A B) C	1'. A (B C) = (A B) C
2. A B = B A	2'. A B = B A
3. A (B C) = (A B) (A C)	3'. A (B C) = (A B) (A C)
4. А А = А	4'. А А = А
5. A = A, A D = D (при усло-	5'. A = , A D = A (при
вии A D)	условии A D)
6. A (D – A) = D	6'. A (D – A) =

(Некоторые из приведенных выше свойств имеют специальные названия: 1 и 1' - свойства ассоциативности, 2 и 2' - коммутативности, 3 и 3' - дистрибутивности, 4 и 4' - идемпотентности).

Доказательство. Приведем доказательство свойств 3 и 5' (остальные доказываются просто или аналогично). Начнем со свойства 3. В силу одного из

9

свойств операции включения (свойство 2), достаточно показать, что множество справа включено в множество, стоящее слева, и наоборот. Пусть х A (B C). Тогда либо х A, либо х B C. Если х A, то х A B и х A C, т.е. х (A B) (A C). Если же х B C, то х B и х C. Следовательно х A B и х A C, т.е. снова х (A B) (A C). Этим показано включение

A (B C) (A B) (A C). Наоборот, если х (A B) (A C), то х A B и

х A C. Если х A, то х A (B C). Если же х A, то обязательно х B и х C. Следовательно х B C и х A (B C), что и доказывает утверждение.

Докажем свойство 5'. Из свойства 4 операции включения имеем A . Покажем обратное включение. Предположим противное, что A не включено в . Тогда существует х A , т.е. х A и х , такое, что х . Но здесь написаны две противоречивые принадлежности. Это доказывает, что наше исходное предположение не верно и A . Аналогично показывается и вторая часть рассматриваемого свойства.

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

Операции над множествами, хотя и являются похожими на операции сложения (объединение), вычитания (разность множеств), и умножения (пересечение) над обычными числами, отличны от них по своим свойствам. Так, например, (А-В) В = А верно не всегда (приведите пример).

Другим существенным отличием являются так называемые законы поглощения: для множеств из универсума U справедливы равенства:

1.А (А В) = А;

2.А (А В) = А;

3.А (АС В) = А В.

Доказательства этих равенств несложные и опираются на теорему 1. Так первое из них получается из следующих равенств:

А (А В) = (А U) (A B) = A (U B) = A U = A.

Для множеств из универсума U справедливы следующие два закона де Моргана.

Теорема 2. Справедливы равенства:

(А В)С = АС ВС и (А В)С = АС ВС.

Доказательство. Докажем первое из этих равенств. Пусть а (А В)С. Тогда а А В, т.е. а А и а В. Последнее означает, что а АС и а ВС, а значит и

а АС ВС. Цепочку этих рассуждений легко теперь провести в обратном порядке.

Второе равенство доказывается по аналогии.

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

10

множество на U, то получим верное равенство. Новое равенство называется двойственным по отношению к заданному.

Примеры. 1) А =А (А )С = АС АС С = АС АС U = АС. Последнее равенство в силу произвольности А (а следовательно и АС ) можно переписать В U = В для любого множества В из U.

2) (задача Льюиса Керролла) В одном жестоком бою из 100 пиратов 70 потеряли ногу, 75 – руку, 80 – глаз, 85 – ухо. Доказать, что как минимум 10 человек потеряли и руку, и ногу, и глаз, и ухо.

Решение. Обозначим через А – множество пиратов, потерявших ногу, В – потерявших руку, С – глаз, Е – ухо. Тогда нам необходимо найти М=А В С Е (точнее, показать, что там не менее 10 элементов). Рассмотрим МС = АС ВС СС ЕС . По условиям задачи в множестве АС – 30 элементов, в множестве ВС – 25 элементов, СС – 20, ЕС – 15 элементов. Таким образом, в множестве МС не более, чем 30 + 25 + 20 + 15 = 90 элементов. Следовательно, в самом множестве М не менее, чем 10 элементов.

Задачи.

1. Доказать следующие утверждения:

а) из А В вытекает, что А В = А и А В = В; б) из А В = А вытекает, что А В; в) из А В = В вытекает, что А В.

2. Доказать:

а) А (В С) = (А В) (А С); б) А (В С) = (А В) (А С). 3. Доказать включения:

а) (А С) (В D) (А В) (С D);

б) (В – С) – (В – А) А – С; в) А – С (А – В) (В – С).

4.Доказать: А В = (А В) – (А В).

5.Верны ли утверждения для любых множеств А, В, С: 1) если А В и В С, то А С; 2) если А В и В С, то А С?

6.При каких условиях на А и В выполняется равенство (А – В) В = А.

7.Пусть U={a, b, c, d, e, f} – универсум, A = {a, b, c}, B = {a, c, e, f}, C =

{d, e, f}. Найти А – В, В – С, С – В, А – С, АC В, В АC, А С, С А.

8.Пусть А В = . Что можно сказать про множества А – В и В – А.

9.Пусть А ВС = . Что можно сказать про множества А В и А В.

10.Доказать равенства:

а) (А – В) – С = (А – С) – (В – С);

б) (А – В) (В – С) (С – А) (А В С) = А В С; в) А – В = А – (А В) = (А В) – В; г) А – (А – В) = А В;

11

д) А – (В С) = (А – В) (А – С); е) А – (В С) = (А – В) (А – С); ж) (А В) – С = (А – С) (В – С).

11.Вытекает ли из А – В = С, что А = В С?

12.Вытекает ли из А = В С, что А – В = С?

13.Пусть А – заданное множество, про другое множество Х известно, что

А Х = А. Доказать, что Х = . 14. Доказать равенства: а) А (В D) = (А В) D;

б) А (В D) = (А В) (А D);

в) А А = ; г) А = А.

15.Доказать следующие тождества:

а) (А В) (С D) = (А С) (В С) (А D) (В D); б) (А В) А = (А В) А = А;

в) А – (В – С) = (А – В) (А С); г) А (В – С) = (А В) – (А С) = (А В) – С;

д) А В = А (В – А); е) (АС)С = А;

ж) А АС = U; з) А АС = ;

и) [АС В] А = А В; к) А (В-А) = ;

л) А – (В С) = (А – В) – С. 16.Доказать, что а) (А В) С = А (В С) А С;

б) А = В А В = ; в) А В = А В А = В;

г) (А В) – В = А А В = ; д) (А – В) В = А В А;

е) (А В) С = А (В С) С А; ж) А В А С В С; з) А В А С В С;

и) А В (С-В) (С-А); к) А В ВС АС;

л) А = ВС А В= и А В = U. 17.Доказать тождества:

а) А В = А В (А В);

б) А – В = А – (А В); в) А = А;

12