Akhmetova_Vodopyanov_-_Kurs_matana

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования

Уфимский государственный авиационный технический университет

Н. А. Ахметова, В. В. Водопьянов

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

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

Допущено Редакционно-издательским советом УГАТУ в качестве учебного пособия для студентов всех форм обучения,

по направлениям 230401 «Прикладная математика», 010500 «Прикладная математика и информатика», 010300 «Математика. Компьютерные науки»

Уфа 2009

УДК 510.5:517(07) ББК 22.12:22.176(я7)

А95

Рецензенты: д-р физ.-мат. наук, член-кор. АН РБ, зав. кафедрой ПиЭИ БашГУ Юлмухаметов Р. С.;

д-р физ.-мат. наук, зав. кафедрой ПиВМ БГПУ им. М.Акмуллы. Асадуллин Р. М.

Ахметова, Н. А., Водопьянов, В. В.

А95 Множества и операции над ними. Отношения и функции. Мощность множеств. Комбинаторика. Метод математической индукции: учебное пособие / Н. А. Ахметова, В. В. Водопьянов; Уфимск. гос. авиац. техн. ун-т.- Уфа: УГАТУ, 2009. ‒ 64 с.

ISBN 978-5-86911-796-0

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

Ил. 3. Библиогр.: 4 назв.

ISBN-978-5-86911-796-0 ©Уфимский государственный авиационный технический университет, 2009

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

рый нас окружает»

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

преподаванием»

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

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

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

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

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

3

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

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

Что же такое множество по Г. Кантору? Множество по Кантору

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

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

Интуитивный принцип объемности Г. Кантора (1 аксиома Геделя): множества А и В считаются равными (А = В), если они состоят из одних и тех же элементов.

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

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

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

C = {2, 4, 6},

D = {2, 6, 4}.

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

4

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

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

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

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

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

Q – множество всех рациональных чисел;

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

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

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

Например,

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

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

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

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

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

5

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

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

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

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

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

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

Задачи.

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

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

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

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

выполняется тогда и только тогда, когда a = c и b = d.

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

6

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

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

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

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

х А. Но для любого х справедливо х . Следовательно такого х не существует и А.

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

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

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

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

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

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

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

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

Операция “симметрическая разность множеств”. Для мно-

жеств А и В их симметрической разностью называется множество А В = (А – В) (В – А).

7

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

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

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

Операции над множествами хорошо иллюстрируются диаграммами Венна (рис. 1, 2, 3).

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

ства:

8

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

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

надлежности. Это доказывает, что наше исходное предположение не верно и A . Аналогично показывается и вторая часть рассматриваемого свойства.

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

универсумом.

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

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

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

9

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

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

ношению к заданному.

U.

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

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

– 15 элементов. Таким образом, в множестве МС не более, чем 30 + 25 + 20 + 15 = 90 элементов. Следовательно, в самом множестве М не менее, чем 10 элементов.

Задачи.

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

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

10