Теория множеств

Министерство образования и науки РФ НИ Иркутский государственный технический университет Л.Л. Носырева Конспект лекций Часть 1 Теория множеств Иркутск 2010 «Дискретная математика. Конспект лекций. Часть 1. Теория множеств». Предназначено для студентов специальностей АСУ, ИСТ факультета Кибернетики. Составитель Л.Л. Носырева. Иркутск, 2010, 17 - с. Содержит конспект лекций по разделу «Теория множеств» учебной дисциплины «Дискретная математика». Библ. 6 назв. Рецензент: Белых Татьяна Ивановна, доцент кафедры информатики и кибернетики БГУЭП Содержание Введение 4 Лекция 1 5 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ 5 § 1. МНОЖЕСТВО 5 § 2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ 9 § 3. АЛГЕБРА ПОДМНОЖЕСТВ 12 Лекция 2 15 ОТНОШЕНИЯ. 15 § 4. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ 15 § 5. БИНАРНЫЕ ОТНОШЕНИЯ 17 § 6. N-АРНЫЕ ОТНОШЕНИЯ 19 § 7. СПЕЦИАЛЬНЫЕ БИНАРНЫЕ ОТНОШЕНИЯ 20 § 8. ОПЕРАЦИИ НАД БИНАРНЫМИ ОТНОШЕНИЯМИ 21 § 9. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ 25 Лекция 3 28 ФУНКЦИИ (ОТОБРАЖЕНИЯ) 28 § 9. ФУНКЦИЯ (ОТОБРАЖЕНИЕ) 28 § 10. СВОЙСТВА УМНОЖЕНИЯ ОТОБРАЖЕНИЙ 34 § 11. ОБРАТНОЕ ОТОБРАЖЕНИЕ 36 Лекция 4 37 ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И ПОРЯДКА 38 § 12. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ 38 § 13. ОТНОШЕНИЯ ПОРЯДКА 41 § 14. ЭКВИВАЛЕНТНОСТЬ МНОЖЕСТВ. ПОНЯТИЕ МОЩНОСТИ МНОЖЕСТВА . 47 Введение Для создания и эксплуатации комплексных интегрированных автоматизированных систем обработки информации и их компонент (математического обеспечения, пакетов прикладных программ, распределенных банков данных, встроенных микропроцессорных систем, сетей передачи данных, систем с разделением ресурсов и распределенной обработкой информации) необходимо знание дискретной математики, основной особенностью которой является отсутствие предельного перехода и непрерывности, характерных для классической математики. В этом курсе мы не будем обсуждать, как и где это применять, и какая от этого будет польза. Например, в книгах по электротехнике не принято объяснять, что такое интеграл по контуру или векторное произведение: само собой разумеется, что нужные сведения читатель получил из курса математического анализа. Аналогично, здесь мы будем изучать основы дискретной математики, с тем, чтобы вы могли ими пользоваться при изучении других специальных дисциплин. Лекция 1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ § 1. МНОЖЕСТВО Эта глава, по существу, служит развернутым словарем для всех остальных глав. Любое понятие дискретной математики можно определить с помощью понятия множества. «Множество» не является строго определяемым понятием Примеры множеств Элементы множеств Выражение означает, что x принадлежит множеству А, а - x не принадлежит множеству А Конечное множество, Бесконечное множество Способы задания множеств: 1. Полный список (полный перечень) элементов. 2. Задание с помощью характеристического свойства множества А. 3. Порождающая процедура. Пустое множество Подмножество Равные множества и Собственное подмножество множества Булеан множества Мощность конечного множества Понятие «множество» относится к исходным понятиям математической теории и не является строго определяемым. Его синони­мами являются «совокупность», «семейство», «класс», «система», «собрание» и др. Георг Кантор (1845–1918), немецкий математик, созда­тель теории множеств, дал такое определение: «под множеством понимают объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью». Например, можно рассматривать: • множество столов в комнате; • множество всех атомов на Марсе; • множество всех рыб в океане; • множество футболистов команды «Звезда»; • множество всех футбольных команд. В математике рассматриваются: • множество то­чек (например, окружности); • множество всех решений уравнения sinx = 0,5; • множество всех чисел вида Для числовых множеств будем использовать следующие обозначения: • N – множество натуральных чисел; • Z – множество целых чисел; • Q – множество рациональных чисел; • R – множество действительных чисел; • C – множество комплексных чисел. Объекты, составляющие данное множест­во, называют его элементами. При этом никаких ограни­чений на природу элементов множества не наклады­вается. Предполагается только, что для любых двух эле­ментов данного множества имеется возможность выяс­нить, различны они или одинаковы. Тот факт, что элемент x принадлежит множеству А (x является элементом множества А), записывается так: . Если же x не является элементом множества А (x не принадлежит множеству А), то пишут . Таким образом, принадлежность - это отно­шение между элементами и множествами, при этом пред­полагается, что для любого конкретного элемента и любого конкретного множества можно определить, принад­лежит этот элемент данному множеству или нет. Существенным в понятии «множество» является то, что мы объединяем некоторые предметы в одно целое. Кантор так подчеркнул это обстоятель­ство: «Множество есть многое, мыслимое нами как еди­ное». Чтобы наглядно представить понятие «множество», академик Н.Н. Лузин (1883–1950) предложил следую­щий образ. Представим прозрачную непроницаемую обо­лочку, нечто вроде плотно закрытого непроницаемого мешка. Предположим, что внутри этой оболочки заклю­чены все элементы x данного множества А и что кроме них внутри оболочки никаких других предметов нет. Эта оболочка с предметами x, находящимися внутри нее, и может служить образом множества А, составленного из элементов x. Сама же прозрачная оболочка, охваты­вающая все элементы (и ничего другого кроме них), довольно хорошо изображает тот факт объединения эле­ментов x, в результате которого создается множество А. Понятие множества — одно из основных понятий со­временной математики. Понятия и теоремы теории мно­жеств обладают большой общностью, так как элементы множеств могут быть различной природы, а потому одни и те же утверждения, касающиеся множеств, можно истолковать как утверждения о точках, натуральных числах, молекулах и т.д. Множество называется конечным, если оно состоит из конечного числа элементов, и бесконечным — в проти­воположном случае. Возможны различные способы задания множеств. Один из них состоит в том, что дается полный список (полный перечень) элементов, входящих в данное мно­жество. Так, множество студентов некоторой группы определяется списком в журнале. Если множество А конечное, состоя­щее из элементов a1, … , an, то используют обозначение А = {a1, … , an}. В частности, {а} — множество, состоя­щее из одного элемента а. Но этот способ применим лишь к конечным множест­вам, да и то не ко всем. Например, множество рыб в океане конечно, однако задать их списком трудно. К бесконечным множествам данный способ вовсе не применим. Множество всех целых чисел таким способом задать нельзя. Имеется другой, универсальный способ задания мно­жеств. Это - задание с помощью характеристического свойства множества А, т.е. такого свойства, которым обладают все элементы множества А и не обладают эле­менты, не принадлежащие А. Если, например, Z - мно­жество всех целых чисел, то , , крокодил не принадлежит Z. Окружность радиуса 2 с центром в на­чале координат - это множество всех таких x, что x есть точка плоскости и x находится на расстоянии в две еди­ницы от начала координат. Если Р(x) - некоторое свойство, то предполагается, что оно определяет некоторое множество А, состоящее из всех тех элементов x, которые удовлетворяют свой­ству Р(x). В этом случае множество А обозначают так: A = {x| P(x)} или A = {x: P(x)}. Например, если А = {a1, … , an}, то оно может быть определено с помощью характеристического свойства следующим образом: A = {x| x = a1 или x = a2, или … или x = an}. Множество всех депутатов Государственной думы может быть определено с помощью характеристического свойства так: {x| x — депутат Госдумы}, и это задание экономнее задания данного множества с по­мощью списка всех депутатов. Третий способ задания множества – это порождающая процедура. Порождающая процедура описывает способ получения элементов множества из уже полученных элементов либо из других объектов. Элементами множества считаются все объекты, которые могут быть построены с помощью такой процедуры. Примером служит следующее множество: A = {n | for n from 1 to 10 yield n} Ясно, что существуют множества, состоящие из трех, двух или одного элемента. Например, множество родите­лей любого человека двухэлементное. Однако иногда приходится рассматривать и множество, не содержащее ни одного элемента. Оно называется пустым и обозна­чается . При задании множества характеристическим свойством не всегда известно, существует ли элемент с таким свойством. Например, мы говорим о множестве решений какого-либо уравнения, которое может и не иметь решения, т.е. это множество решений уравнения пустое. Более того, часто бывает очень трудно выяснить, является ли пустым данное множество. Неизвестно, на­пример, до сих пор, является ли пустым множество всех натуральных п > 2 таких, что уравнение xn + yn = zn имеет положительное целочисленное решение (проблема Ферма). Рассмотрим теперь понятие «подмножество». Определение1.1. Пусть А и В — непустые мно­жества. Если каждый элемент множества А является вместе с тем и элементом множества В, то говорят что А - подмножество множества В (или А содержится в В, или В содержит А, или А включено в В) и обозначают . По определению пустое множест­во есть подмножество любого множества В**, в том числе и пустого. Например, выполняются следующие включения для рассмотренных выше числовых множеств: . Чтобы в множестве А выделить подмножество В, к характеристическому признаку множества А до­бавляют то или иное дополнительное свойство Р(х) и обозначают это так: B = {| P(x)}. Например, М={| x > 0} — множество всех положительных действительных чисел. Определение1.2. Пусть А и В — два множества. Множества А и В называются равными, если каждый элемент множества А является вместе с тем и элементом множества В, и обратно, каждый элемент множества В является и элементом множества А. Другими словами, множества А и В называются равными, если выполняют­ся два включения: и . Докажем, что пустое множество единственно. Действительно, пусть и — два пустых множества. Так как для любого множества А имеем, что , то взяв в качестве А множество , получим , а взяв в качестве А множество , получим . Отсюда . Если и , то А называют собственным подмножеством множества В и обозначают . Введенное отношение называется отношением строгого включения. Например, . Определение1.3. Пусть А — непустое множество. Совокупность всех подмно­жеств множества А обозначим через Б(А) и будем назы­вать булеаном множества А. Ясно, что и . Например, если А = {а, b}, то Б (A) = {, {a}, {b}, A}. Число элементов конечного множества А будем называть его мощностью и обозначать |А|. Пусть, например, |А| = n, тогда мощность булеана | Б (A)| =2 n. Замечание. О мощности бесконечного множества поговорим позже (§ 14). § 2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ Универсум Пересечение множеств Примеры Объединение множеств Примеры Разность множеств А\В Примеры Дополнение множества Примеры Симметрическая разность АВ (АВ) Круги Эйлер (или Диаграммы Венна) Во всех рассуждениях о нескольких множествах бу­дем предполагать, что они являются подмножествами некоторого фиксированного множества, которое назо­вем универсальным, универсумом или пространством и обозначать U (или E). На практике это множество часто явно не указывают, предполагая, что в случае необходи­мости оно может быть восстановлено. Это делается для того, чтобы избежать известных парадоксов теории множеств, о которых мы поговорим позже Рассмотрим теперь операции над множествами, с помощью которых из некоторых заданных множеств можно получать новые, более сложные множества. Определение2.1. Пересечением множеств А и В называется множество, обозначаемое и состоящее из всех тех и только тех элементов, которые принадлежат как множеству А, так и множеству В. Это определение символически можно записать так: . Примеры: • ; • . • Если А — множество всех четных чисел; В — множество всех простых чисел, то . • Если А — множество студентов мужского пола; В — множество мужчин старше 20 лет, то — множество студентов мужского пола старше 20 лет. Определение2.2. Объединением множеств А и В называется множество, обозначаемое и состоящее из всех тех и только тех элементов, которые принадле­жат хотя бы одному из множеств А, В. Это определение символически можно записать так: . Примеры: • . • Если — множество всех положительных действительных чисел, — множество всех отрицательных действительных чисел, то — множество всех действительных чисел, кроме 0. • Если — множество всех действительных чисел мень­ше 1, то — множество всех действительных чисел. Замечание. Объединение множеств А и В называют иногда суммой и обозначают А + В, а их пересечение — произведением и обозначают АВ. Определение2.3.Разностью множеств А и В называют множество, обозначаемое А\В и состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В. Это определение символически можно записать так: . Примеры: • если А — множество всех действительных чисел, В — множество всех рациональных чисел, то А\В — множество всех иррациональных чисел. Определение2.4. Пусть А — подмножество мно­жества Е. Дополнением множества А в множестве U называют множество, состоящее из всех тех и только тех элементов из U, которые не принадлежат А, и обозначают . Это определение символически можно записать так: . Примеры: • если Е — множество всех целых чисел, А — множество всех четных чисел, то — множество всех нечетных чисел. • Если Е — множество всех людей, А — множество всех мужчин, то — множество всех женщин. Определение2.5. Симметрической разностью множеств А и В называют множество, обозначаемое АВ и состоящее из элементов, принадлежащих множеству А или множеству В не принадлежащих множеству . Это определение символически можно записать так: АВ = . Замечание. Симметрическую разность множеств А и В называют иногда кольцевой суммой и обозначают АВ. Введенные операции объединения, пересечения, разности и симметрической разности являются двуместными. Операция дополнения является одноместной. Рассмотренные операции над множествами допускают очень наглядное графиче­ское истолкование с помощью так называемых кругов Эйлера (или диаграмм Венна). Рис. 1. Изображение операций с помощью кругов Эйлера Универсальное множест­во U изображается при этом множеством точек некото­рого прямоугольника, а его подмножества — в виде кру­га (или какой-нибудь другой простой области внутри этого прямоугольника). Если изобразить таким образом множества А и В, то множества АВ (рис.1,а), АВ (рис.1,b) и (рис.1,c), А\В (рис.1,d), АВ (рис.1,e) изображаются заштрихованными областями. § 3. АЛГЕБРА ПОДМНОЖЕСТВ Буле­ва Алгебра подмножеств Законы основные Доказательство закона дистрибутивности Доказательство закона де Моргана Пусть Б(Е) - совокупность всех подмножеств мно­жества Е. Б(Е) замкнуто относительно операций объеди­нения, пересечения и дополнения множеств, т.е. произ­водя эти операции над элементами множества Б(Е), получаем элементы, принадлежащие Б(Е). Множество Б(Е) с введенными операциями объединения, пересечения и дополнения называют буле­вой алгеброй подмножеств множества Е. Подобно тому, как сложение и умножение чисел удовлетворяют известным законам коммутативности ассоциативности и дистрибутивности, операции объеди­нения, пересечения и дополнения в алгебре подмножеств подчинены аналогичным законам, а также ряду других. Замечание. Формальное изучение этих законов восходит к англий­скому математику Дж. Булю (1815-1864). Выпишем основные законы, которым подчиняются эти операции: (законы поглощения) Универсальным методом доказательства вышеприве­денных равенств является доказательство, основанное на определении равенств двух множеств, т.е. два множест­ва А и В равны тогда и только тогда, когда выполнены два включения: и . Приведем доказатель­ства некоторых из этих соотношений. Чтобы доказать 7), достаточно проверить два вклю­чения: Доказательство 7а). Пусть . Тогда или . Если, то и , а следовательно, х является элементом пе­ресечения этих множеств. Если , то и . Значит, и , так что и в этом случае х есть элемент их пересечения. Доказательство 7б). Пусть . Тогда и . Следовательно, или же и . Из этого вытекает, что . Равенство 7) с помощью кругов Эйлера наглядно представлено на рис.2 и 3. На рис.2 множество А за­штриховано горизонтально, а — вертикально; по­этому — область, попадающая под верти­кальную или горизонтальную штриховку. На рис.3 мно­жество заштриховано горизонтально, a — вертикально; тогда — область, попадающая под обе штриховки. Легко видеть, что обе эти области совпадают. Рис.2. Рис.3 Докажем 9). Для этого достаточно проверить: Доказательство 9а. Пусть. Тогда . Значит и . Отсюда и , а потому . Доказательство 9б. Пусть . Тогда и . Следовательно, и . Отсюда , а потому . Равенство 9) наглядно представлено на рис.4 и 5. Рис.4 Рис.5. На рис.4 множество заштриховано, поэтому — не заштрихованная область. На рис.5 множест­во заштриховано горизонтально, а — вертикально; тогда — область, попадающая под обе штриховки. Легко видеть, что обе эти области совпадают. Отметим в заключение без доказательства, что мно­жество соотношений 1) – 15) полно в том смысле, что любое равенство, образованное при помощи (относительно U) и любого числа букв А, В, С, … , имею­щее место для любых подмножеств А, В, С, … множест­ва Е, может быть выведено из 1) – 15). Лекция 2. ОТНОШЕНИЯ § 4. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ Упорядоченная пара Декартово произведение не­пустых множеств Декартов квадра­т множества А2 Примеры Упорядоченная n-ка Декартово произведение не­пустых множеств A1× A2 ×…× An Декартова степень множества Аn Примеры Введем понятие упорядоченной пары, которое будем считать неопределяемым понятием. При этом нужны следующие факты: каждая упорядоченная пара состоит из первой и второй координат (компонент). Упорядочен­ная пара, первой координатой которой является эле­мент а, а второй — элемент b, обозначается (а, b), где а, b — элементы непустых множеств А и В соответствен­но. Две упорядоченные пары равны (или совпадают) тогда и только тогда, когда совпадают их первые и вто­рые координаты, т.е. (а, b) = (х, у) тогда и только тогда, когда а = х и b = у. Например, упорядоченные пары (1, 2) и (2, 1) различны. Определение4.1. Декартовым произведением не­пустых множеств А и В называется совокупность всех упорядоченных пар вида (а, b), где , , и обо­значается . Если хотя бы одно из множеств А или В пусто, то их декартовым произведением будем на­зывать пустое множество . Другими словами, . Пусть, например, А = {a1, a2}, В = {b1, b2, b3}. Тогда = {(a1, b1); (a1, b2); (a1, b3); (a2, b1); (a2, b2); (a2, b3)}. Если А = В, то А × В называют декартовым квадра­том множества А и обозначают А2. Еще раз отметим, что . Примеры. • Пусть, например, А = {a1, a2}. Тогда А2 = {(a1, a1); (a1, a2); (a2, a1); (a2, a2)}. • Рассмотрим еще один пример. Упорядоченную пару (а, b), где а, b — действительные числа, будем отождествлять с точкой плоскости, абсцисса которой равна а, а ордина­та — b. Тогда R2 (R — множество всех действительных чисел) гео­метрически изображается как плоскость X0Y. • Если же А = [1, 3], В = [1, 2], то А × В на плоскости изображается за­штрихованным прямоугольником (рис.6). • Прямая с уравнением у = 2х + 1 может быть истолкова­на как «множество точек, соот­ветствующих множеству ». • Аналогично область, для которой у < х, — это множество точек, соот­ветствующих множеству . По аналогии с понятием упорядоченной пары вво­дится понятие упорядоченного набора из п элементов, который будем обозначать (a1, …, аn), где , (i = 1, …, n). Элемент аi называется при этом i-й коор­динатой (компонентой), а п — длиной этого упорядочен­ного набора. Два упорядоченных набора одной и той же длины (a1, …, аn) и (b1, …, bn) считаются равными тогда и только тогда, когда ai = bi для всех i = 1, …, n. Определение4.2. Декартовым произведением не­пустых множеств A1, …, An называется совокупность всех n-ок вида (a1, …, аn), где (i = 1, …, n), и обозначается A1 × … × An. Если хотя бы одно из мно­жеств A1, …, An пустое, то декартовым произведением множеств A1, …, An будем называть пустое множество. Другими словами, A1 × … × An = {(a1, …, аn) | , i = 1, …, n}. Если A1 = … = An = А, то A1 × … × An называют n-й декартовой степенью множества А и обозначают Аn. Примеры. • Пусть, например, А= {а, в, с}, В={с, d}, C={1, 2}. Тогда А×В×С = {(а,с,1), (а,d,1), (а,с,2), (а,d,2), (в,с,1), (в,d,1), (в,с,2), (в,d,2), (с,с,1 ), (с,d,1), (с,с,2), (с,с,2)}. • Пусть Е={0,1}. Тогда ={(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}. § 5. БИНАРНЫЕ ОТНОШЕНИЯ Для обозначения связи между предметами или понятиями используют термин «отношение» Бинарное отношение Равные отношения Область определения отношения Область значений отношения Примеры Графический способ изображения бинарных отношений Пример В математике (да и не только в математике) для обозначения связи между предметами или понятиями используют термин «отношение». Например, отношение «меньше» в множестве действительных чисел, отношение подобия треугольников, отношение равенства дробей, отношение делимости в множестве целых чисел, отношение включения подмножеств некоторого множества, отно­шения родства и старшинства в множестве людей и т.д.. Это примеры отношений между двумя элементами (по­нятиями), так называемых бинарных отношений. Можно рассмотреть отношения и между тремя, че­тырьмя и более элементами. Например, отношение «точ­ка А лежит между точками В и С», отношение между целыми числами а, b, с, d, если они образуют пропорцию а:b = с:d, отношение между действительными числами (a1, …, аn), заключающееся в том, что их сумма равна 0, т.е. a1 + … + аn = 0. Пока мы будем рассматривать только бинарные отношения. Определим понятие «бинарное отношение» через понятия «множество» и «упорядоченная па­ра». При этом будем исходить из следующих соображе­ний: бинарное отношение используется в связи с парами некоторых элементов, рассматриваемых в определенном порядке, оно касается существования определенной связи между некоторыми парами. Если известен перечень всех упорядоченных пар, для которых имеет смысл говорить о данном отношении, то для каждой такой пары можно сказать, находится или не находится она в данном отношении. Следовательно, можно полностью охарактеризовать отношение, зная мно­жество всех пар и подмножеств тех пар, которые нахо­дятся в данном отношении. Рассмотрим, например, отно­шение «меньше» в множестве натуральных чисел N = {1, 2, …}. Здесь мы имеем дело с упорядоченными парами натуральных чисел, т.е. элементами множест­ва N2, а подмножество тех пар, которые находятся в от­ношении «меньше», состоит из пар вида {(1, 2), …, (1, n), …, (2, 3), …, (2, n), …, (3, 4), …, (3, n), …}. Пара (а, b) из N2 тогда и только тогда принадлежит этому подмножеству, когда а < b. Значит, отношение «меньше» в множестве натуральных чисел мож­но отождествить с указанным подмножеством мно­жества N2. Определение5.1. Бинарным отношением, опре­деленным на паре множеств А и В, называется любое подмножество их декартова произведения А × В. Если — бинарное отношение, а упорядо­ченная пара (а, b), где , , принадлежит R, то это записывают либо (согласно определе­нию), либо R(а, b), либо aRb. Обозначение aRb исхо­дит из обозначений вида а = b, а < b, и др. Если — бинарное отношение и А = В, то R называют бинарным отношением, определенным на множестве А (вместо того, чтобы говорить, что R — би­нарное отношение, определенное на паре множеств А, А). Так как бинарные отношения — множества, то имеет смысл говорить об их равенстве (как о равенстве мно­жеств) и об отношении включения, а именно: два бинар­ных отношения R1 и R2 равны тогда и только тогда, когда любая пара (а, b) из R1 принадлежит вместе с тем и R2, и обратно: любая пара (а, b) из R2 принадлежит и R1. Аналогично, тогда и только тогда, когда любая пара (а, b) из R1 принадлежит вместе с тем и R2. Определение5.2. Пусть — бинарное отношение, определенное на паре множеств А, В. Областью определения отношения R называется совокуп­ность всех таких , что хотя бы для одного . Областью значений отношения R назы­вают множество всех таких , что хотя бы для одного элемента . Примеры. • Пусть А = {a1, a2}, В = {b1, b2}. Выпишем все бинарные отношения, определенные на паре мно­жеств А, В, т.е. все подмножества множества . Их число равно 24 = 16: • Областью определения для бинарного отношения R1 является пустое множество, для R2, R3, R6 — одноэле­ментное множество {a1}, для R4, R5, R11 — {a2}, а для остальных — все множество А. • Областью значений для бинарного отношения R1 служит пустое множество, для R2, R4, R7 — одноэлементное множество {b1}, для R3, R5, R10 — {b2}, для остальных — все множество В. • Пусть А = {1, 2, 3}, В = {1, 2, 3, 4, 5, 6, 7}. Следующее подмножество множества А×В {(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (2, 2); (2, 4); (2, 6); (3, 3); (3, 6)} может быть задано короче (словесно) как отношение «а является делителем b», где , . Область определения этого отношения совпадает с А, а область значений - с В. • Область определения бинарного отношения {(2, 1), (2, 4), (3, 3), (3, 7)} — множество {2, 3}, а область зна­чений — {1, 3, 4, 7}. Однако это отношение не получило специального названия. Бинарные отношения иногда удобно изображать графически. Один способ состоит в том, что элементы х А и у В, связанные отношением , соединяются стрелками. Пример. На рис. 7 графически показаны отноше­ние R1 = {(а, 2), (b,1), (с, 2)} между множествами А = {а, b, с} и В — {1,2,3}, а также отношение R2 = {(а, b), (b, b), (с, а)} на множестве A. Рис.7 § 6. N-АРНЫЕ ОТНОШЕНИЯ Отношения можно рассматривать между тремя, че­тырьмя и более элементами N – арное отношение тернарное отношение Пример Как уже упоминалось выше, можно рассматривать отношения и между тремя, че­тырьмя и более элементами. Например, отношение «точ­ка А лежит между точками В и С», отношение между целыми числами а, b, с, d, если они образуют пропорцию а:b = с:d, отношение между действительными числами (a1, …, аn), заключающееся в том, что их сумма равна 0, т.е. a1 + … + аn = 0. Понятие n-арного (n-местного) отношения вводится по аналогии с понятием бинарного отношения. Определение6.1. Пусть A1, …, An — непустые множества. Всякое подмножество R их декартова про­изведения А1×…×An называется n-арным отношением, определен­ным на системе множеств A1, …, An. Т.е. А1×…×An. Если A1 = … = An = А, то отношение R, определен­ное на системе множеств A1, …, An, называют n-арным (n-местным) отношением, определенным на множестве А (вместо того, чтобы говорить: «n-арное отношение, опре­деленное на системе множеств A, …, A»). При n = 2 приходим к известному понятию бинарного отношения. При n = 3 используют термин тернарное отношение. Пример. Пусть А – множество дней учебного года, В = {8-00,14-00}, С - множество аудиторий ИрГТУ, D - множество учебных групп ИрГТУ, Е - множество учебных дисциплин, изучаемых в ИрГТУ, X - множество преподавателей ИрГТУ. Тогда расписание экзаменов – 6-арное отношение, определенное на множестве A×B×C×D×E×X. § 7. СПЕЦИАЛЬНЫЕ БИНАРНЫЕ ОТНОШЕНИЯ Универсальное (истинное) отношение Пустое (ложное) отношение Тождественное отношение (диагональ) Peфлексивное отношение Симметричное отношение Антисимметричное отношение Транзитивное отношение Примеры Рассмотрим некоторые специальные отношения, определенные на множестве А. Определение7.1. Пусть А — произвольное множество. Мно­жество А×A называют универсальным отношением, определенным на множестве А; любая пара (a1,a2), где , находится в этом отношении, поэтому его на­зывают иногда всюду истинным отношением. Пустое подмножество множества А2 называют пустым отноше­нием; ни одна из пар множества А2 не находится в этом отношении, поэтому оно называется еще всюду ложным отношением. Определение7.2 Пусть Р - бинарное отношение на множестве А: Р А2. Отношение Р называется тождественным или диагональю, если Р = (а, а), где , и обозначается еA или idA . Определение7.3.Пусть Р - бинарное отношение на множестве А: Р А2. Отношение Р называется: 1. peфлексивным, если (x, x) Р для всех xA. 2. симметричным, если для любых x, y А из (x, y) Р следует (y, x) Р, т. е. Р-1 = Р, 3. антисимметричным, если из (x, y) Р и (y, x) Р следует x = y, т. е. Р Р-1 idA. 4. транзитивным, если из (x, y) Р и (y, z) Р следует (x, z)Р , т. е. РРР. Отметим, что антисимметричностъ не совпадает с несимметричностью. Примеры. • Отношение Р={(1,2), (2,3), (3,2)} на множестве А = {1,2,3} не симметрично (так как (1,2) Р, а (2,1) Р) и не антисимметрично (поскольку 2 ≠ 3, но (2,3) Р и (3,2) Р). • Тождественное отношение idА является одновременно симметричным и антисимметричным. • Отношение ≤ на множестве R действи­тельных чисел, а также отношение включения подмно­жеств некоторого множества являются рефлексивными и транзитивными, но не являются симметричными. • Отно­шение < на множестве действительных чисел транзитивно, но не рефлексивно, не симметрично. • Отношение «х является матерью у» не рефлексивно, не симметрично, не транзитивно. § 8. ОПЕРАЦИИ НАД БИНАРНЫМИ ОТНОШЕНИЯМИ Теоретико-множественные операции: объединение, пересечение, дополнение, разность Примеры Отно­шение, обратное к бинарному отношению (операция обращения) R–1 Произведение отношений Примеры Теорема 1 Теорема 2 Так как бинарные отношения, определенные на фик­сированной паре множеств А, В, являются подмножест­вами А×В, то над ними можно производить все теоретико-множественные операции. Так, если R, S — два бинарных отношения, опре­деленных на паре множеств А, В, то для любых , тогда и только тогда, когда aRb или aSb; тогда и только тогда, когда aRb и aSb; тогда и только тогда, когда не aRb. Примеры. • Рассмотрим отношение равенства =, опре­деленное на множестве N натуральных чисел, т.е. сово­купность всех диагональных пар: (1, 1), (2, 2),… . Тогда дополнением (в множестве N2) этого отношения является отношение неравенства, обозначаемое обыч­но . • Отношение ≤ совпадает с объединением отноше­ний < и =; а пересечение этих отношений — пустое (всюду ложное) отношение; объединение отношений ≤ и > является всюду истинным отношением, т.е. совпа­дает с N2; объединение отношений < и > есть отноше­ние ≠. • Объединение отношений «х является отцом у» и «х является матерью у» есть отношение «х является ро­дителем (отцом или матерью) у», а объединением отно­шений «х является мужем у» и «х является женой у» служит отношение «х и у — супруги». Помимо теоретико-множественных операций над от­ношениями важное значение имеют еще две операции над ними: обращение и умножение отношений. Определение8.1. Пусть — бинарное отношение, определенное на паре множеств А, В. Отно­шением, обратным к бинарному отношению R, назы­вается отношение, определенное на паре множеств В и А и состоящее из всех тех и только тех пар (b, а), для ко­торых ( ). Бинарное отношение, обратное к отношению R, будем обозначать R–1. Таким образом, . Примеры. • Если < - отношение порядка на множест­ве N натуральных чисел, то <–1 - отношение >. • Пусть А - множество английских слов, В - множество русских слов, а R - такое отношение, определенное на паре множеств А, В, что aRb тогда и только тогда, когда b - возможный перевод слова a (, ), т.е. R - англо-русский словарь. Тогда R–1 - русско-английский словарь. • Если R - бинарное отношение «х является родите­лем у», то R–1 - отношение «х является ребенком (сы­ном или дочерью) у». Определение8.2. Пусть — бинарное отношение, определенное на паре множеств А, В, а — бинарное отношение, определенное на паре множеств В, С. Произведением (или композицией) отношений и называется бинарное отношение, определенное на паре множеств А и С и состоящее из всех тех и только тех пар (а, с) , , для которых существует элемент х из В такой, что ax и xc. Произведение бинарных отношений и обозначим через Р1°Р2 или Р1Р2. Таким образом, Р1Р2 и a(Р1Р2)c тогда и только тогда, когда сущест­вует элемент такой, что a Р1x и x Р2 c (Рис.8). Рис.8 Если отношение определено на паре мно­жеств А, В, а отношение — на паре множеств С, D и при этом В ≠ С, то произведение этих отношений не определено. Таким образом, произведение двух бинар­ных отношений может быть и не определено. Однако, если рассматривать совокупность всех бинарных отноше­ний, заданных на некотором фиксированном множест­ве А, то произведение двух таких бинарных отношений будет отношением, определенным на множестве А. Примеры. • Пусть < и > — бинарные отношения, определенные на множестве N натуральных чисел. Тогда a(< ∙ >)b тогда и только тогда, когда существует такое натуральное число х, что а < х и х > b, т.е. a(< ∙ >)b тогда и только тогда, когда существует такое натураль­ное число х, что х > а и х > b. Очевидно, это — всюду истинное отношение на множестве N, т. е. < ∙ > = N2. • Рассмотрим произведение > ∙ <: a(> ∙ <)b тогда и только тогда, когда существует натуральное число х та­кое, что a > х и х < b, т.е. тогда и только тогда, когда существует такое натуральное число х, что х < a и х < b. Следовательно, произведение > ∙ < на мно­жестве натуральных чисел не содержит только пар вида (а, 1) и (1, b), все остальные пары находятся в этом отношении. Отсюда вытекает, что отношения < и >, определенные на множестве натуральных чисел, не перестановочны. Так как отношение < совпадает с >–1, то отсюда следует, что R и R–1 не перестановочны. • Пусть < — отношение, определенное на множестве натуральных чисел. Рассмотрим отношение <2: a <2 b тогда и только тогда, когда существует такое натуральное число х, что а < х и х < b, т.е когда существует нату­ральное число х такое, что а < х < b. Для существова­ния такого числа х необходимо и достаточно, чтобы а + 1 < b. Следовательно, a <2 b тогда и только тогда, когда а + 1 < b. Например, 1<23, 1 <2 5, 2 <2 4, 2 <2 5, но пары (1, 2), (2, 3) не находятся в отношении <2. • Пусть R — отношение «а является от­цом b». Рассмотрим отношение R2: aR2b тогда и только тогда, когда «а является дедом b». • Пусть S — отношение супружества (т.е. aSb тогда и только тогда, когда а и b — супруги), а D — отношение дочерности (т.е. aDb тогда и только тогда, когда а явля­ется дочерью b). Рассмотрим произведение SD: a(SD)b тогда и только тогда, когда существует такое х, что aSx и xDb, т.е. а и х — супруги, а х — дочь b. Таким образом, a(SD)b тогда и только тогда, когда а является зятем по отношению к b (тестю или теще), т.е. SD — отношение зятя к тестю и теще. Теорема 1. Пусть , , — бинарные отношения. Тогда произведения (RS)T и R(ST) определены и (RS)T = R(ST). Короче, умножение би­нарных отношений ассоциативно. Доказательство. Непосредственно проверяет­ся, что и , т.е. оба этих отношения определены на паре множеств А, D. Первая часть теоремы доказана, осталось проверить равенство (RS)T = R(ST). Рассмотрим произведение (RS)Т. Пусть , : a[(RS)T]d тогда и только тогда, когда в С существует такой элемент у, что a(RS)y и yTd. Но a(RS)y тогда и только тогда, когда в В существует такой элемент х, что aRx и xSy. Итак, a[(RS)T]d тогда и только тогда, когда существуют такие элементы и , что aRx, xSy и уТb. Рассмотрим произведение R(ST). Пусть , : a[R(ST)]d тогда и только тогда, когда сущест­вует такой элемент х из В, что aRx и x(ST)d. Но x(ST)d тогда и только тогда, когда существует такой элемент у из С, что xSy и yTd. Итак, a[R(ST)]d тогда и только тогда, когда существуют такие элементы и , что aRx, xSy и yTd. Следовательно, множества (RS)T и R(ST) являются подмножествами одного и того же множества и определяются одним и тем же характеристическим свойством, поэтому (RS)T = R(ST). Теорема доказана. Рассмотрим еще одно свойство введенных операций умножения и обращения бинарных отношений. Теорема 2. Пусть , — бинар­ные отношения. Тогда выражения (RS)–1 и S–1R–1 опре­делены и имеет место равенство (RS)–1 = S–1R–1. Доказательство. Непосредственно проверяется, что (RS)–1 и S–1R–1 — бинарные отношения, определен­ные на паре множеств С, А, т.е. и . Первая часть теоремы доказана. Дока­жем равенство (RS)–1 = S–1R–1. Рассмотрим отношение (RS)–1. Пусть , : c(RS)–1a тогда и только тогда, когда a(RS)c. Далее, a(RS)c тогда и только тогда, когда существует такой элемент х из В, что aRx и xSc. Рассмотрим отношение S–1R–1. Пусть , : c(S–1R–1)a тогда и только тогда, когда существует такой элемент х из В, что cS–1x и xR–1a, т.е. тогда и только тогда, когда xSc и aRx. Следовательно, множества (RS)–1 и S–1R–1 являются подмножествами одного и того же множества C×A и определяются одним и тем же характеристическим свойством, поэтому (RS)–1 = S–1R–1. Теорема доказана. Помимо рассмотренных тождеств, относящихся к опе­рациям умножения и обращения бинарных отношений, имеются тождества, связывающие эти операции с теоре­тико-множественными операциями над отноше­ниями. Некоторые из них рассмотрим в задачах на практических занятиях. § 9.МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ Матрица бинарного отношения Пример Свойства матриц бинарных отношений 1. [Р Q] = [Р] + [Q], [Р Q] = [Р] * [Q]. 2. [Р ° Q] = [Р] [Q]. 3. [Р-1] = [Р] T. 4. Если Р Q то pij < qij. 5. Матрица тождественного отношения единична 6. Матрица peфлексивного отношения имеет вид 7. Если Р А2 – симметричное бинарное отношение на множестве А, то [Р]T =[Р] 8. Если Р антисимметрично, то в [Р] * [Р]T все элементы вне главной диагонали являются нулевыми Пример Рассмотрим два конечных множества А = {a1, а2, ..., am}, В = {b1, b2,…,bn} и бинарное отношение Р А×В. Определим матрицу [Р] = (pij) размера m × n бинарного отношения Р по следующему правилу: Полученная матрица содержит полную информацию о связях между элементами и позволяет представлять эту информацию графически и на компьютере. Заметим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения. Пример Матрица бинарного отношения Р А2, А = {1, 2, 3}, заданного на рис. 9, имеет вид . Рис.9 Отметим основные свойства матриц бинарных отношений. 1. Если P, Q А×В, [Р] = (pij) , [Q] = (qij) , то [Р Q] = (pij + qij) и [Р Q] = (pij qij), где сложение осуществляется по правилам 0 + 0 = 0, 1 + 1 = 1 + 0 = 0 + 1 = 1, а умножение -обычным образом. Итак, [Р Q] = [Р] + [Q], а матрица [Р Q] получается перемножением соответствующих элементов из [Р] и [Q]: [Р Q] = [Р] * [Q]. Пример. Пусть [Р] =, [Q] = матри­цы отношений Р и Q. Тогда . 2. Если Р А × В, Q В × С, то [Р ° Q] = [Р] [Q], где умножение матриц [Р] и [Q] производится по обычному правилу умножения матриц, но произведение и сумма элементов из [Р] и [Q] - по определенным в п. 1 правилам. Пример. Если [P] = , [Q] = , то 3. Матрица обратного отношения Р-1 равна транспонированной матрице отношения Р: [Р-1] = [Р] T. 4. Если Р Q, [Р] = (рij), [Q] = (qij) , то pij < qij. 5. Матрица тождественного отношения единична: 6. Пусть Р А2 - рефлексивное бинарное отношение на множестве А. Матрица peфлексивного отношения имеет вид [Р] = 7. Пусть Р А2 – симметричное бинарное отношение на множестве А. Тогда [Р]T =[Р]. 8. Если отношение Р антисимметрично, то это означает, что в матрице [Р Р-1] = [Р] * [Р]T все элементы вне главной диагонали являются нулевыми. Пример Проверим, какими свойствами обладает отношение Р А2, А = {1, 2, 3}, изображенное на рис. 10. Составим матрицу отношения Р: [Р] = . Так как в матрице [Р] на главной диагонали имеются нулевые элементы, отношение Р не рефлексивно. Несимметричность матрицы [Р] означает, что отношение Р не симметрично. Для проверки антисимметричности вычислим матрицу [Р Р-1] = [Р] * [Р]T . Имеем Поскольку в полученной матрице все элементы, стоящие вне главной диагонали, нулевые, отношение Р антисимметрично. Так как [Р ° Р] = [Р] (проверьте!), то Р Р Р , т. е. Р является транзитивным отношением. Лекция 3 ФУНКЦИИ (ОТОБРАЖЕНИЯ) § 10. ФУНКЦИЯ (ОТОБРАЖЕНИЕ) Определение функции Примеры Равные отображения Образ множества Сужение (ограничение) отношения на множество Примеры Понятие «функция» вам известно из курса высшей математики. «Отображение» - другое название этого понятия, больше используемое в «функциональном анализе». В классическом курсе математического анализа определение функции дается следующим образом: Пусть X, Y — непустые множества. Если каждому эле­менту соответствует единственный элемент , то говорят, что задано отображение множества Х в мно­жество Y или задана функция, определенная на множест­ве Х со значениями в множестве Y. Отображение множества Х в Y обозначим буквой f. Если f — отображение Х в Y, то это символически запи­сывают так: f : X → Y или Каждому элементу при отображении f : X → Y соответствует некоторый элемент из множества Y, кото­рый называется образом элемента х при отображении f и обозначается f(x). (Другие обозначения: fx, xf). Если у — образ элемента х при отображении f: X → Y, то это записывают так: y = f(x) или f: x → y. Элемент х называют прообразом элемента у при ото­бражении f: X → Y. Определить понятие «функция» можно используя понятие бинарного отношения. Определение10.1. Бинарное отношение f определенное на паре непустых множеств А и В, называется функцией, опреде­ленной на множестве А со значениями в В (или отображением из А в В) , если для любого эле­мента х А существует один и только один элемент у В, удовлетворяющий условию x f y. Другими словами, отношение f , заданное на паре не­пустых множеств А и В, является функцией из А в В, если из того, что (x, y1) f и (x, y2 ) f следует y1 = y2. а) не функция б) функция в) функция г) функция Рис. 11. Примеры. • Следующие бинарные отношения между х и у, задан­ные на множестве R действительных чисел, являются функциями (отображениями R в себя): 1) х2 = у; 2) |x| = у; 3) 2х + 3у = 12. • Отношение < на множестве Z всех целых чисел не есть отображение Z в себя, ибо для каждого целого чис­ла х существует не одно, а бесконечно много целых чи­сел у таких, что х < у. • 3.Бинарное отношение между х и у, определенное на множестве R действительных чисел условием : х2 + у2 = 25, не является отображением R в себя. Действительно, если |x| > 5, то в R нет такого у, которое с х было бы свя­зано соотношением х2 + у2 = 25. Для |x| < 5 в R есть элемент у такой, который связан с х соотношением х2 + у2 = 25, но он не единствен (число таких у равно 2). • Следующие отношения, определенные на множестве R действительных чисел, не являются отображениями R в себя: 1) х = у2; 2) х =|у|. • Отношение «х является отцом у», заданное на мно­жестве людей, не является отображением. • Отношение «х является сыном у», определенное на множестве людей мужского пола, является отображе­нием этого множества в себя. Если данное отношение рассматривать определенным на множестве всех людей, то оно не есть отображение. • Отношение равенства на произвольном множестве А является отображением множества А в себя. Оно назы­вается тождественным, или единичным, отображением А в себя. Определение10.2. Два отображения F: X → Y и G: X → Y называются равными (обозначение F = G), если F(x) = G(x) для любого элемента (т.е. если результаты их действия одинаковы). Определение10.3. Пусть F: X → Y — отображе­ние, а А — непустое подмножество множества X. Обра­зом множества А при отображении F называют совокуп­ность образов всех элементов множества А и обозначают F(А). Другими словами, . Ясно, что . В частности, для имеем . Определение10.4. Пусть F: X → Y — отображе­ние и . Отображение, которое каждому элементу рассматриваемому как элемент из X, ставит в со­ответствие , называется сужением, или ограни­чением, F на А и обозначается FA или F/A. Примеры. 1. Найдем все отображения множества X = {x1, x2, x3} в множество Y = {y1, y2}, и для каждого такого отображения найдем образ множества X. Отображения F: X → Y в случае, когда Х — конечное множество, зададим таблицей, состоящей из двух строк. В верхней строке запишем элементы множества X, а под ними — их образы из множества Y. Итак, запись означает, что F(x1) = y1, F(x2) = y2, F(x3) = y1. Выпишем все отображения множества Х в Y: 2. Отображение множества всех точек плоскости в себя, которое каждую точку плоскости переводит в точку, по­лученную из данной поворотом плоскости вокруг начала координат на угол φ, показано на рис.12, а отображение множества всех векторов трехмерного пространства, вы­ходящих из начала координат, в себя, которое каждый вектор переводит в его ортогональную проекцию на пло­скость X0Y, — на рис.13. Рис.12 Рис.13 3. Следующие примеры отображений хорошо известны (ниже: R — множество всех действительных чисел; — множество всех положительных действительных чисел; — множество всех неотрицатель­ных действительных чисел): а) F: R → R, F(x) = sin x. Здесь (строгое включение); б) F: R → [–1, 1], F(x) = sin x. В этом случае F(R) = [–1, 1]; в) F: R → R, F(x) = х2. Тогда (стро­гое включение); г) F: R → R≥0, F(x) = х2. Имеем F(R) = R≥0; д) F: (R≥0) → R≥0, F(x) = х2. Здесь F(R≥0) = R≥0. Подчеркнем, что в рассмотренных примерах образ F(X) множества Х может совпадать с множеством Y (как в примерах б, г, д предыдущего абзаца) либо быть его собственным подмножеством (примеры а, в), а образы различных элементов из Х могут быть различ­ны (как в примере д), либо совпадать (как в приме­рах в, г, когда F(2) = F(-2) = 4), причем образы даже бесконечного множества различных элементов из Х могут совпадать (как в примерах а, б, когда, напри­мер, F(kπ) = 0, где k = 0, ±1, ±2, …). § 11. ИНЪЕКТИВНЫЕ И СЮРЪЕКТИВНЫЕ ФУНКЦИИ Инъективное отображение Примеры Сюръективное отображение Примеры Биективное отображение Примеры Определение11.1. Функция (отображение) F: X→Y назы­вается инъективным (или инъекцией), если различным элементам из множества Х соответствуют различные эле­менты из множества Y при отображении F: X → Y, т.е. если для любых x1 и x2 из Х выполняется следующее условие: . Другое название инъективного отобра­жения F: X → Y — взаимно однозначное отображе­ние из Х в Y. Примеры. • Отображение F: R>0 → R, F(x) = lg x инъективно, ибо из lgx1 = lgx2 по известному свойству логарифмической функции следует, что x1 = x2; • Анало­гично отображение F: R≥0 → R≥0, F(x) = х2 инъективно, так как если и , то x1 = x2. • Отображение F: R → R≥0, F(x) = х2 не является инъективным, так как, например, F(2) = F(-2) = 4, хотя . Определение11.2. Функция (отображение) F: X → Y назы­вается сюръективным (или сюръекцией), если каждый элемент множества Y является образом хотя бы одного элемента из Х при отображении F: X → Y (или: если каждый элемент множества Y имеет хотя бы один прообраз в множестве Х при отображении F). Иными словами, отображение F: X → Y называется сюръективным, если образ F(X) множества Х при ото­бражении F: X → Y совпадает с Y, т.е. F(X) = Y. Другое название сюръективного отображения F: X → Y — отображение множества Х на множество Y. Примеры. • Отображения F: R → [–1, 1], F(x) = sin x, F: R → R≥0, F(x) = х2 и F: R≥0 → R≥0, F(x) = х2 сюръективны, • Отображения F: R → R, F(x) = х2 и F: R → R, F(x) = sin x не являются сюръективными. Подчеркнем, что для доказательства сюръективности отображения F: X → Y необходимо проверить, что для любого элемента существует элемент такой, что у0 = F(x), т.е. необходимо проверить, что для лю­бого уравнение F(x) = у0 имеет хотя бы одно ре­шение . Например, отображение F: R>0 → R, F(x) = lg x сюръективно, ибо уравнение имеет решение (единственное) относительно x: , а ото­бражение F: R → R, F(x) = 2x не является сюръективным, так как уравнение не имеет реше­ния, если у0 ≤ 0. Определение11.3. Отображение F: X → Y назы­вается биективным (или биекцией), если оно одновре­менно и инъективно, и сюръективно. Другое название биективного отображения F: X → Y — взаимно однозначное отображение множества Х на мно­жество Y. Примеры. • Отображение F: R → R, F(x) = 2x + 1 биективно. Действительно, F инъективно, так как из 2x1 + 1 = 2х2 + 1 следует, что x1 = x2. Кроме того, ото­бражение F сюръективно, ибо для любого урав­нение у0 = 2x + 1 имеет решение (и даже единственное) относительно х: х = (у0–1)/2. • На рис.14. показаны различные виды функций. а)инъекция, б) сюръекция, в)биекция но не сюръекция но не инъекция Рис.14 • На рис. 15. графически показаны функции fi : [0,1] → [0,1], i {1,2,3,4}. Функция f1 сюръективна, нo не инъективна, функция f2 инъективна, но не сюръективна, функция f3 биективна и является подстановкой, а функция f4 нe инъективна и не сюръективна. Рис.15 § 12. СВОЙСТВА УМНОЖЕНИЯ ОТОБРАЖЕНИЙ Произведение отображений (композиция, суперпозиция отображений, сложная функция) Теорема 1 Следствие Пусть F: X → Y, G: Y → Z — два отображения. Каж­дому элементу при отображении F соответствует единственный элемент у = F(x) из множества Y. Эле­менту у при отображении G соответствует единственный элемент z = G(y) из множества Z. Сопоставив каждому элементу таким образом полученный элемент , получим отображение H: X → Z, которое является результатом последовательного применения отображе­ния F, а потом отображения G. Это отображение Н на­зывают произведением отображений G и F и обозна­чают GF. Определение 12.1. Произведением отображений F: X → Y и G: Y → Z (обозначение GF) называется ото­бражение множества Х в множество Z, определяемое следующим образом: GF(x) = G[F(x)] для любого эле­мента Короче: произведение отображений — это результат их последовательного выполнения. Произведение отображений называют иногда компо­зицией, суперпозицией отображений или сложной функцией (особенно в математическом анализе). Например, если F: R → R, F(x) = sin x; G: R → R, G(x) = 2x, то FG(x) = sin 2x, GF(x) = 2sin x. Заметим, что не всегда произведение двух отображе­ний определено, но если, например, F: X → X, G: X → X — отображения множества Х в себя, то произведения GF и FG определены. Вообще говоря, FG ≠ GF даже если определены FG и GF, т.е. умножение отображений не­коммутативно, но ассоциативно. Теорема 1. Пусть F: X → Y, G: Y → Z. Произведение GF инъективных отображений G и F инъективно, а про­изведение GF сюръективных отображений G и F сюръективно. Доказательство. Докажем сначала первое утверждение теоремы. Пусть F и G инъективны, т.е. если F(x1) = F(x2), то x1 = x2; а из G(y1) = G(y2) следует, что y1 = y2 (x1, ; y1, ). Проверим, что GF инъек­тивно. Пусть GF(x1) = GF(x2). Тогда, по определению произведения отображений, имеем G[F(x1)] = G[F(x2)]. Обозначив y1 = F(x1), a y2 = F(x2), в силу инъективности G получим F(x1) = F(x2), откуда в силу инъективности F x1 = x2. Первое утверждение доказано. Докажем вторую часть теоремы. Пусть F и G — сюръективные отображения. Требуется доказать, что GF: X → Z — сюръективное отображение, т.е. для лю­бого существует хотя бы один элемент та­кой, что z = GF(x). Пусть z0 — произвольный элемент множества Z. Так как G: Y → Z — сюръективное отобра­жение, то z0 является образом хотя бы одного элемента из множества Y. Пусть y0 — некоторый образ элемента z0 при отображении G, т.е. z0 = G(y0). Аналогично в силу сюръективности отображения F: X → Y элемент y0 явля­ется образом хотя бы одного элемента из множества X. Пусть x0 — некоторый образ элемента y0 при отображе­нии F, т.е. y0 = F(x0). Из полученных отношений z0 = G(y0) и y0 = F(x0) выводим, что z0 = G(y0) = G[F(x0)] = GF(x0), т.е. произвольный элемент есть образ элемента x0 при отображении GF: X → Z, что и требовалось доказать. Следствие. Произведение биективных отображений биективно. § 13. ОБРАТНОЕ ОТОБРАЖЕНИЕ (ФУНКЦИЯ) Обратное отображение Обратимое отобра­жение Теорема 1 Следствие Подстановка множества Определение 13.1. Пусть F: X → Y. Если сущест­вует такое отображение Φ: Y → X, что ΦF = eX, FΦ = eY, то отображение Φ называют обратным к отобра­жению F. В этом случае F называют обратимым отобра­жением. Если F — обратимое отображение, то отображение, обратное к F, обозначают F–1. Очевидно, если F–1 — отображение, обратное к F, то F — отображение, обратное к F–1, так что F и F–1 обратны друг другу. Докажем критерий обратимости отображений. Теорема 1. Отображение F: X → Y тогда и только тогда обратимо, когда оно биективно. Доказательство. Необходимость. Пусть F: X → Y — биективное отображение. Докажем, что отобра­жение F обратимо. Так как F сюръективно, то каждый элемент является образом хотя бы одного (одного или несколь­ких) элемента из множества X. Далее, каждый элемент есть образ точно одного элемента из Х в силу инъективности. Действительно, если — образ эле­ментов x1 и x2 из множества X, то y = F(x1) и y = F(x2). Откуда F(x1) = F(x2) и, следовательно, по инъектив­ности F получаем x1 = x2. Итак, если F: X → Y — биек­тивное отображение, то каждый элемент является образом точно одного элемента Сопоставив каж­дому элементу тот элемент , единственным образом которого он является, получим отображение Φ: Y → X. При этом Φ(у) = х, если у = F(x), , . Покажем, что Φ — отображение, обратное к F, для чего проверим, что ΦF = eX и FΦ = eY. Пусть x — лю­бой элемент множества X, а у — образ элемента х при отображении F, т.е. у = F(х). Тогда ΦF(х) = Φ(F(x)) = Φ(y) = x (по определению Φ). Отсюда и вытекает ра­венство ΦF = eX. Пусть у — произвольный элемент мно­жества Y. По определению Φ, элемент является образом элемента при отображении Φ (т.е. х = Φ(у)), когда у = F(x). Поэтому FΦ(y) = F(Φ(y)) = F(x) = y = eY(y). Равенство ΦF = eY доказано. Достаточность. Пусть F: X → Y — обратимое отобра­жение, т.е. отображение, для которого существует ото­бражение Φ: Y → X такое, что ΦF = eX и FФ = eY. Покажем инъективность и сюръектнвность отображе­ния F. Проверим сначала инъективность F. Пусть F(x1) = F(x2). Применяя к обеим частям этого равенства ото­бражение Φ, получаем Φ[F(x1)] = Φ[F(x2)] или ΦF(x1) = ΦF(x2) (по определению произведения). Так как по условию ΦF = eX, то x1 = x2. Инъективность F проверена. Проверим, что F сюръективно, т. е. что для любого элемента в множестве Х существует элемент x0 такой, что y0 = F(x0). Так как по условию eY = FΦ, то y0 = FΦ(y0) = F[Φ(y0)] = F(x0), где x0 = Φ(y0). Это по­казывает, что y0 является образом элемента x0, где x0 = Φ(y0). Сюръективность F проверена. Теорема доказана. Следствие. Если F — биективное отображение, то F–1 также биективно. Определение13.2. Биективное отображение мно­жества Х в себя называется подстановкой множества X. Пример Пусть σ – подстановка множества М = {1, 2, …, n}. Тогда σ(k) = sk , где 1 ≤ sk ≤ n, k = 1, 2, …, n, {s1 , s2 , ..., sn} = {1, 2, ..., n}, и поэтому подстановку σ можно представить в виде матрицы, состоящей из двух строк: . Лекция 4 ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И ПОРЯДКА § 14. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ Отношение эквивалентности Примеры Ядерная эквивалентность отображения Смежный класс множества (класс эквивалент-ности) Теорема 1 Лемма 1 Лемма 2 Фактор-множество множества Каноническое отображение Разбиение (или расслое­ние) множества Теорема 2 Теорема 3 Теорема 4 Определение14.1. Бинарное отношение α, опре­деленное на множестве А, называется отношением экви­валентности или просто эквивалентностью на множест­ве А, если α рефлексивно, симметрично и транзитивно. Примеры: • отношение подобия в множестве треугольников в евклидовой плоскости; • отношение равенства в произвольной системе мно­жеств; • отношение равночисленности, т.е. иметь одинаковое число элементов, в системе конечных множеств; • отношение равносильности в множестве формул логики высказываний; • отношение «учиться в одной группе» в множестве студентов факультета кибернетики; • отношение сравнимости по модулю п в множестве всех целых чисел. Это отношение для любого натураль­ного п определяется так: х сравнимо с у по модулю п (обозначается: х ≡ y(mod п)), если х – у делится на n. Определение14.2. Пусть F: A → B — отображение. Отношение σ, определяемое следующим образом: , является отношением эквивалентности на А. Оно назы­вается ядерной эквивалентностью отображения F. Пусть σ — отношение эквивалентности на множест­ве А, и пусть . Определение14.3. Множество всех таких элемен­тов , что хσа истинно, называют смежным классом множества А по эквивалентности σ, или классом эквива­лентности, и обозначают [а]σ. Другими словами, [а]σ = {| хσа}. Вместо [а]σ часто пишут [а], если относительно σ нет никаких неяс­ностей. Теорема 1. Свойство I: . Свойство II: если aσb, то [а] = [b]. Доказательство. Свойство I вытекает из реф­лексивности. Докажем свойство II. Пусть aσb. Требуется доказать, что [a] = [b]. Для этого достаточно проверить два включения: и . Проверим первое из этих включений. Пусть , тогда хσа. Из хσа и данного условия aσb, в силу транзитивности σ, полу­чаем хσb, т.е. . Итак, включение прове­рено. Докажем обратное включение: . Пусть , тогда хσb. В силу симметричности из данного в теореме 6 условия aσb следует bσa. Тогда из условий хσb и bσa, в силу транзитивности σ, вытекает, что хσа, т.е. . Следовательно, и обратное включение тоже доказано. Итак, [а] = [b], если aσb. Теорема доказана. Содержательный смысл свойства II состоит в том, что любой класс определяется однозначно своим представи­телем, т.е. любые элементы из одного класса равноправ­ны при определении этого класса. Отметим, что свойство II допускает обращение, а именно: если [а] = [b], то aσb. Действительно, пусть [а] = [b]. Тогда по свойству I . Следователь­но, aσb. Таким образом, мы доказали лемму 1. Лемма 1. Условия aσb и [а] = [b] равносильны. Докажем еще одно нужное в дальнейшем утвержде­ние, вытекающее из свойства II. Лемма 2. Любые два смежных класса множества А по эквивалентности σ либо не пересекаются, либо совпа­дают. Доказательство. Пусть [а] и [b] — два смеж­ных класса, , . Тогда по свой­ству II [с] = [а] и [с] = [b]. Следовательно, [а] = [b], что и требовалось доказать. Из леммы 2 вытекает, что различные смежные классы не имеют общих элементов. Определение14.3. Совокупность всех различных смежных классов множества А по эквивалентности σ на­зывается фактор-множеством множества А по эквива­лентности σ и обозначается А/σ. Еще раз отметим, что лемма 1 утверждает, что усло­вие aσb на множестве А равносильно равенству [а] = [b] в фактор-множестве А/σ. Это простое утверждение часто используется в математике, ибо позволяет переходить от классов эквивалентности множества А к элементам фактор-множества А/σ. Определение14.4. Каноническим отображением множества А на фактор-множестве А/σ по эквивалент­ности σ называется отображение, которое каждому эле­менту ставит в соответствие содержащий его смеж­ный класс [a]σ. Очевидно, это каноническое отображение сюръективно. Отношения эквивалентности произвольного мно­жества тесно связаны с понятием разбиения этого мно­жества. Определение 15. Разбиением (или расслое­нием) множества А называется система S непустых под­множеств множества А таких, что каждый элемент из А принадлежит одному и только одному подмножеству из системы S. Из определения 15 вытекает, что любые два подмно­жества из S не имеют общих элементов (не пересекают­ся). Поэтому система S непустых подмножеств множест­ва А является разбиением множества А, если любые два различных множества из S не пересекаются и любой элемент из А попадает в одно (а тогда и только в одно) подмножество из семейства S. Подмножества из S называются смежными классами (или слоями) разбиения S. Рассмотрим связи между отношениями эквивалент­ности некоторого множества и его разбиениями. Теорема 2. Если σ — отношение эквивалентности на множестве А, то совокупность всех различных смежных классов множества А по эквивалентности σ является раз­биением множества А. Доказательство. Из свойства I классов экви­валентности вытекает, что каждый элемент содер­жится в смежном классе [а] и, кроме того, что каждый смежный класс [а] не пуст. Далее, по лемме 2, различные смежные классы по эквивалентности σ не имеют общих элементов (не пересекаются). Теорема доказана. Теорема 3. Пусть S — разбиение множества А, а σ — бинарное отношение на множестве А такое, что, по опре­делению, хσу () истинно тогда и только тогда, когда в S есть подмножество М, для которого , . Тогда σ — отношение эквивалентности на мно­жестве А. Эта эквивалентность σ называется эквивалент­ностью, отвечающей разбиению S. Доказательство. Для доказательства теоремы надо проверить, что отношение σ, определенное на мно­жестве А, рефлексивно, симметрично и транзитивно. Ясно, что σ симметрично. Далее, σ рефлексивно, ибо каж­дый элемент попадает в некоторый класс разбие­ния, а тогда хσх для любого . Осталось проверить, что σ транзитивно. Пусть хσу и yσz. Это означает, что х и у попадают в один класс разбиения, скажем M1, а у и z тоже попадают в один класс разбиения, скажем М2. Так как элемент у принадлежит M1 и М2, то, по определению разбиения, M1 = M2. Следовательно, х и z лежат в одном классе разбиения и, значит, хσz. Теорема доказана. Теорема 4. Для любого множества А существует взаимно однозначное соответствие между множеством разбиений множества А и множеством отношений экви­валентности на А. § 15. ОТНОШЕНИЯ ПОРЯДКА Частичный поряд­ок Частично упорядоченное множество Примеры Сравнимые элементы Наибольший и наимень­ший элементы Примеры Лемма 1 Максимальный элемент Минимальный элемент Лемма 2 Непосредственно меньший (непосредственно предшествующий) элемент Непосредственно больший (непосредственно следующий) элемент Линейный порядок Линейно упорядоченное множество Свойства частично упорядо­ченного множества Вполне упорядоченное множество Трансфинит-ные числа Предельный элемент Теорема 2 Определение 15.1. Бинарное отношение ρ, опре­деленное на множестве А, называется частичным поряд­ком, или отношением частичного порядка, если оно удов­летворяет следующим условиям: 1) хρх для любого (рефлексивность); 2) из хρу и yρz следует xρz для любых (транзитивность); 3) из хρу и уρх следует х = у для любых (антисимметричность). Множество А, на котором задан какой-нибудь частич­ный порядок, называется частично упорядоченным. Примерами отношения частичного порядка являются: отношение включения на множестве подмножеств не­которого множества; отношение ≤ на множестве дей­ствительных чисел; отношение «х делит у» на множестве натуральных чисел. Частичный порядок на множестве А будем обозна­чать символом ≤, и если a ≤ b для некоторых элемен­тов , то будем говорить, что а меньше или рав­но b, а также, что а содержится в b или равно b. Если a ≤ b и а ≠ b, то будем писать а < b и говорить, что а строго меньше b или а строго содержится в b. Определение 15.2. Элементы а, b множества А называются сравнимыми относительно частичного поряд­ка ≤ на этом множестве, если a ≤ b или b ≤ a. Определение 18. Пусть А — частично упорядо­ченное множество с частичным порядком ≤. Элемент называется наибольшим элементом, если х ≤ а для любого . Элемент называется наимень­шим элементом, если b ≤ х для любого . Наиболь­ший элемент часто называют единицей, а наименьший — нулем. Частично упорядоченное множество может обладать или не обладать наименьшим или наибольшим элемен­том. Приведем соответствующие примеры. Множество действительных чисел с обычным отношением ≤ не имеет ни наибольшего, ни наименьшего элемента. Мно­жество неотрицательных действительных чисел имеет наименьший элемент (число 0), но не имеет наибольшего элемента. Множество неотрицательных целых чисел с отношением делимости в качестве отношения частич­ного порядка (т.е. т ≤ n тогда и только тогда, когда т делит п) имеет наименьший элемент (число 1) и наиболь­ший элемент (число 0). Однако если частично упорядоченное множество обла­дает наибольшим (наименьшим) элементом, то он един­ственный. Лемма 1. В любом частично упорядоченном множест­ве имеется не более одного наибольшего (наименьшего) элемента. Доказательство. Пусть a1, a2 — два наиболь­ших элемента частично упорядоченного множества А. Так как a1 — наибольший элемент множества А, то a2 ≤ a1. Так как a2 — наибольший элемент множества А, то a1 ≤ a2. В силу антисимметричности отношения ≤ из условий a1 ≤ a2 и a2 ≤ a1 следует a1 = a2. Утверждение о единственности наименьшего элемента доказывается аналогично. Определение 15.3. Максимальным элементом частично упорядоченного множества А называется такой элемент , что каждый элемент х из А либо не сравним с а, либо х ≤ а, т.е., другими словами, если А не содержит элементов, строго больших а. Минимальным элементом частично упорядоченного множества А назы­вается такой элемент , что каждый элемент x из А либо не сравним с b, либо b ≤ х, т.е. если А не содер­жит элементов, строго меньших b. В отличие от наибольшего (наименьшего) элемента частично упорядоченное множество может содержать несколько максимальных (минимальных) элементов. Так, например, в множестве целых положительных чисел, от­личных от 1, с отношением делимости в качестве отно­шения частичного порядка (т.е. m ≤ n тогда и только тогда, когда m делит п) минимальными элементами являются простые числа. Лемма 2. Всякий наибольший элемент частично упо­рядоченного множества является максимальным, а вся­кий наименьший — минимальным. Обратное, вообще говоря, не имеет места. Действи­тельно, предыдущий пример показывает, что в множестве целых положительных чисел, отличных от 1, с отноше­нием делимости минимальными элементами являются простые числа, а наименьшего элемента нет. Определение 15.4. Пусть а, b — элементы час­тично упорядоченного множества А. Элемент а назы­вается непосредственно меньшим (непосредственно пред­шествующим) для элемента b, а b — непосредственно большим (непосредственно следующим) за а, если a < b и не существует элемента , который удовлетворял бы отношению a < х < b. Другими словами, непосредственно следующий за а элемент — это минимальный элемент множества {x| a < x}, а непосредственно предшествующий для а элемент — это максимальный элемент множества {x| x < a}. Ясно, что элемент частично упорядоченного множества может вообще не иметь непосредственно следующего (непосредственно предшествующего), а может иметь их несколько. Строение конечных частично упорядоченных множеств задается иногда при помощи диаграмм. С этой целью элементы множества изображаются точками, располо­женными на разных горизонталях, причем большие эле­менты располагаются выше меньших. Линиями соеди­няют только непосредственно большие элементы с непо­средственно меньшими. Тогда можно без труда опреде­лить, какой из любых двух элементов больше: элемент b оказывается большим а тогда и только тогда, когда на диаграмме от b можно перейти к а по опускающимся вниз линиям. Действительно, если a < b, то b может быть непосредственно большим а. В противном случае найдется элемент x1 такой, что a < x1 < b. Через конеч­ное число шагов придем к отношению a < x1 < … < xn = b, причем каждый из элементов а, x1, …, xn, b непосредственно следует за предыдущим. Таким обра­зом, если непосредственно большие элементы соединять линиями с непосредственно меньшими элементами и если a < b, то от b к а можно перейти по опускающимся вниз линиям. Обратное тоже верно в силу транзитивности отношения <. Совокупность подмножеств трехэлементного мно­жества, частично упорядоченная посредством отношения включения , представлена на рис.16. Точка, располо­женная на самом низком уровне, изображает пустое мно­жество; точки, расположенные на следующем (втором снизу) уровне, — одноэлементные подмножества и т.д. Определение 15.5. Частичный порядок на множестве А называется линейным порядком, если любые два элемента из А сравнимы относительно ≤. Множест­во А, на котором задан какой-либо линейный порядок, называется линейно упорядоченным множеством, или цепью. Примером линейно упорядоченного множества может служить множество всех действительных чисел с обычным отношением ≤. Линейно упорядоченное множество из пяти элементов представлено на рис.17. Отсюда понятно происхождение названия «цепь» для линейно упорядоченного множества. Рис. 16 Рис.17 Отметим, что в случае линейно упорядоченного мно­жества его максимальный (минимальный) элемент явля­ется также наибольшим (наименьшим). Пусть А — частично упорядоченное множество с отно­шением ≤, а В — его подмножество. Тогда ограничение отношения ≤ на подмножество В, т.е. отношение xρy x ≤ y (), является частичным порядком на В. Обычно его обозначают тем же символом, что и задан­ный частичный порядок на А. Таким образом, любое под­множество В частично упорядоченного множества А отно­сительно отношения ≤ есть частично упорядоченное. Более того, если А — линейно упорядоченное множество, то и В линейно упорядочено. Теорема 1. Следующие свойства частично упорядо­ченного множества А равносильны: 1) (условие минимальности). Всякое непустое под­множество множества А является частично упорядочен­ным множеством, содержащим минимальные элементы; 2) (условие индуктивности). Если все минимальные элементы множества А обладают некоторым свойством Р и из того, что все элементы х из А, удовлетворяющие условию х < а, обладают свойством Р, вытекает, что эле­мент а также обладает свойством Р, то свойством Р обладают все элементы множества А; 3) (условие обрыва убывающих цепей). Для всякой цепочки a1 ≥ … ≥ an ≥ … элементов из А найдется такой номер n, что an = an+1 = an+2 = … . Доказательство. Проверим 1) 2). Пусть выполнены посылки условия индуктивности. Обозначим через М множество всех тех элементов х из А, которые не обладают свойством Р. Пусть, вопреки доказываемому, М ≠ . Тогда ввиду 1) в М имеется минимальный элемент а. По условию этот элемент не мо­жет быть минимальным элементом частично упорядочен­ного множества А. Пусть х < а, тогда и, следова­тельно, обладает свойством Р. Но тогда а обладает свойством Р по условию. Противоречие. Проверим 2) 3). Условимся считать, что элемент обладает свойством Р, если всякая убывающая цепочка, начинающаяся с элемента а, обрывается, т.е. удовлетворяет условию 3). Всякий минимальный элемент обладает свойством Р, так как для соответствую­щей цепочки имеем m = a1 = a2 = … . Если та­ков, что все х < а обладают свойством Р, то рассмотрим цепочку a = a1 ≥ a2 ≥ … . Если знаки равенства стоят не всюду, то пусть i — такой номер, что a1 = … = ai–1 и ai–1 > ai. Но тогда элемент ai обладает свойством Р, т.е. цепочка ai ≥ ai+1 ≥ …, а потому и цепочка a1 ≥ … ≥ ai ≥ ai+1 ≥ … обрываются. Таким образом, элемент а обладает свойством Р. В силу условия индук­тивности 2) все элементы множества А обладают свой­ством Р. Это и означает, что А удовлетворяет усло­вию 3). Проверим 3) 1). Пусть, вопреки доказываемому, подмножество М множества А является частично упоря­доченным множеством без минимальных элементов. Пусть a1 — произвольный элемент множества М и пусть уже построена цепочка a1 > a2 > … > an элементов из М. Так как an не минимален в М, то в М существует элемент an+1 < an. Таким образом, получаем бесконеч­ную цепочку a1 > … > an > …, не удовлетворяющую условию 3). Противоречие. Определение 15.6. Линейно упорядоченное мно­жество, удовлетворяющее условию минимальности (а сле­довательно, и остальным условиям теоремы), называется вполне упорядоченным множеством. Примерами вполне упорядоченных множеств явля­ются конечное линейно упорядоченное множество и мно­жество натуральных чисел, упорядоченное естественным образом. Множество всех целых чисел относительно есте­ственного порядка не будет вполне упорядоченным, так как оно не имеет наименьшего элемента. Однако оно ста­нет вполне упорядоченным, если установить порядок сле­дующим образом: 1 < 2 < 3 < … < 0 < –1 < –2 < –3 < … . Другим примером не вполне упо­рядоченной цепи служит отрезок [0, 1], ибо, напри­мер, интервал ]1/2, 1[ не содержит минимального эле­мента. Очевидно, что каждое подмножество вполне упорядо­ченного множества вполне упорядочено. Отметим, что элементы вполне упорядоченного мно­жества носят название трансфинитных чисел, или транс-финитов, и что метод трансфинитной индукции, широко используемый в математике, основан на условии индук­тивности 2) теоремы 1. Из определения вполне упорядоченного множества вытекает, что оно всегда содержит наименьший эле­мент 0. Далее, во вполне упорядоченном множестве А для всякого элемента α, который не является наиболь­шим в А, имеется единственный непосредственно следую­щий за α элемент (т.е. наименьший элемент множества {х| α < х}). Естественно обозначить непосредственно следующий за 0 элемент через 1, непосредственно сле­дующий за 1 элемент через 2 и т.д. Определение 15.7. Элемент а вполне упорядочен­ного множества А, не имеющий непосредственно пред­шествующего, называется предельным. Наименьший элемент 0 любого вполне упорядоченного множества может служить примером предельного эле­мента. Другим, менее тривиальным примером может слу­жить 0 в рассмотренном выше вполне упорядоченном множестве целых чисел. Условимся еще о следующих обозначениях. Если α — элемент вполне упорядоченного множества А, то через α + 1 будем обозначать непосредственно следующий за α элемент (который, как отмечалось выше, существует, если только α не является наибольшим элементом в А). Далее, множество {x| x < α} будем обозначать [0, α[ и называть начальным отрезком. При этом символ [0, 0[ будет означать пустое множество. Теорема 2. Если α — предельный элемент вполне упорядоченного множества, то . Доказательство. Проверим сначала, что . Пусть . Так как между γ и γ + 1 нет элементов, то γ + 1 ≤ α. Однако равенство, в силу предельности α, невозможно, поэтому γ + 1 ≤ α. Таким образом, и требуемое включение проверено. Обратное включение очевидно. Теорема доказана. § 16. ЭКВИВАЛЕНТНОСТЬ МНОЖЕСТВ. ПОНЯТИЕ МОЩНОСТИ МНОЖЕСТВА. Конечные и бесконечные множества Счетные множества Примеры Несчетное множество Свойства счетных множеств Эквивалентные множества Примеры Всякое бесконечное множество эквивалентно некоторому сво­ему собственному подмножеству Несчетность множества действительных чисел Теорема 1 Примеры несчетных множеств Теорема Кантора-Берштейна Мощность множества Сравнение мощностей бесконечных множеств Теорема 3 1. Конечные и бесконечные множества. Рассматривая раз­личные множества, мы замечаем, что иногда можно, если не фактически, то хотя бы примерно, указать число элементов в данном множестве. Таковы, например, множество всех вершин некоторого многогранника, множество всех простых чисел, не превосходящих данного числа, множество всех молекул воды на Земле и т. д. Каждое из этих множеств содержит конечное, хотя, быть может, и неизвестное нам число элементов. С другой сто­роны, существуют множества, состоящие из бесконечного числа элементов. Таково, например, множество всех натуральных чи­сел, множество всех точек на прямой, всех кругов на плоскости, всех многочленов с рациональными коэффициентами и т. д. При этом, говоря, что множество бесконечно, мы имеем в виду, что из него можно извлечь один элемент, два элемента и т. д., при­чем после каждого такого шага в этом множестве еще останутся элементы. Два конечных множества мы можем сравнивать по числу эле­ментов и судить, одинаково это число или же в одном из мно­жеств элементов больше, чем в другом. Спрашивается, можно ли подобным же образом сравнивать бесконечные множества? Иначе говоря, имеет ли смысл, например, вопрос о том, чего больше: кругов на плоскости или рациональных точек на пря­мой, функций, определенных на отрезке [0, 1], или прямых в пространстве, и т. д.? Посмотрим, как мы сравниваем между собой два конечных множества. Можно, например, сосчитать число элементов в ка­ждом из них и, таким образом, эти два множества сравнить. Но можно поступить и иначе, именно, попытаться установить биекцию, т. е. взаимно однозначное соответствие между элементами этих множеств, иначе говоря, такое соответствие, при котором каждому элементу одного множества отвечает один и только один элемент другого, и наоборот. Ясно, что взаимно однознач­ное соответствие между двумя конечными множествами можно установить тогда и только тогда, когда число элементов в них одинаково. Например, чтобы проверить, одинаково ли число сту­дентов в группе и стульев в аудитории, можно, не пересчитывая ни тех, ни других, посадить каждого студента на определенный стул. Если мест хватит всем и не останется ни одного лишнего стула, т. е. если будет установлена биекция между этими двумя множествами, то это и будет означать, что число элементов в них одинаково. Заметим теперь, что если первый способ (подсчет числа эле­ментов) годится лишь для сравнения конечных множеств, вто­рой (установление взаимно однозначного соответствия) приго­ден и для бесконечных. 2. Счетные множества. Простейшим среди бесконечных мно­жеств является множество натуральных чисел. Назовем счетным множеством всякое множество, элементы которого можно биек­тивно сопоставить со всеми натуральными числами. Иначе гово­ря, счетное множество — это такое множество, элементы которо­го можно занумеровать в бесконечную последовательность: а1, а2…, аn, … . Приведем примеры счетных множеств. 1. Множество всех целых чисел. Установим соответствие ме­жду всеми целыми и всеми натуральными числами по следую­щей схеме: 0 - 1 1 –2 2... 1 2 3 4 5 .... Вообще, неотрицательному числу n≥ 0 сопоставим нечетное число 2n+1, а отрицательному n < 0 - четное число 2│n│: п ↔ 2п + 1 при n≥ 0, п ↔2 │n│ при п < 0. 2. Множество всех четных положительных чисел. Соответ­ствие очевидно: п ↔2n. 3. Множество 2, 4, 8, . .., 2n, ... степеней числа 2. Здесь со­ответствие также очевидно. Каждому числу 2n сопоставляется число п. 4. Рассмотрим более сложный пример, а именно, покажем, что множество всех рациональных чисел счетно. Каждое рацио­нальное число однозначно записывается в виде несократимой дроби α=p/q, q > 0. Назовем сумму |p|+q высотой рацио­нального числа α. Ясно, что число дробей с данной высотой п конечно. Например, высоту 1 имеет только число 0/1, высоту 2— числа 1/1 и —1/1, высоту 3—числа 2/1, 1/2, —2/1 и —1/2 и т. д. Будем нумеровать все рациональные числа по возрастанию вы­соты, т. е. сперва выпишем числа высоты 1, потом—числа вы­соты 2 и т. д. При этом всякое рациональное число получит не­который номер, т. е. будет установлено взаимно однозначное соответствие между всеми натуральными и всеми рациональны­ми числами. Бесконечное множество, не являющееся счетным, называется несчетным множеством. Установим некоторые общие свойства счетных множеств. 1. Всякое подмножество счетного множества конечно или счетно. Доказательство. Пусть А—счетное множество, а В— его подмножество. Занумеруем элементы множества A: a1, а2, … , an .... Пусть - те из них, которые входят в В. Если среди чисел п1, п2, ... есть наибольшее, то В конечно, в противном случае В счетно, поскольку его члены а1, a2, … за­нумерованы числами 1, 2, .... 2. Сумма любого конечного или счетного множества счетных множеств есть снова счетное множество. Доказательство. Пусть А1, A2, ... — счетные множества. Мы можем считать, что они попарно не пересекаются, так как иначе мы рассмотрели бы вместо них множества А1, А2\А1, A3\(A1 A2), ... - каждое из которых не более чем счетно, - имеющие ту же самую сумму, что и множества А1, A2, .... Bce элементы множеств А1, A2, ... можно записать в виде следую­щей бесконечной таблицы: где в первой строке стоят элементы множества А1, во второй - элементы множества A2 и т. д. Занумеруем теперь все эти эле­менты «по диагоналям», т. е. за первый элемент примем a11, за второй a12, за третий а21 и т. д., двигаясь в порядке, указанном стрелками на следующей таблице: Ясно, что при этом каждый элемент каждого из множеств полу­чит определенный номер, т. е. будет установлено взаимно одно­значное соответствие между всеми элементами всех множеств A1, A2, ... и всеми натуральными числами. Наше утверждение доказано. 3. Всякое бесконечное множество содержит счетное подмно­жество. Доказательство. Пусть М - бесконечное множество. Выберем в нем произвольный элемент a1. Поскольку М беско­нечно, в нем найдется элемент а2, отличный от а1, затем найдет­ся элемент а3, отличный от а1 и от a2 и т. д. Продолжая этот процесс (который не может оборваться из-за «нехватки» эле­ментов, ибо М бесконечно), мы получаем счетное подмножество A = {a1, a2, … , an, …} множества М. Предложение доказано. Это предложение показывает, что среди бесконечных мно­жеств счетные являются «самыми маленькими». Ниже мы выяс­ним, существуют ли несчетные бесконечные множества. 3. Эквивалентность множеств. Сравнивая те или иные беско­нечные множества с натуральным рядом, мы пришли к понятию счетного множества. Ясно, что множества можно сравнивать не только с множеством натуральных чисел; установление взаимнооднозначного соответствия (биекции) позволяет сравнивать ме­жду собой любые два множества. Введем следующее опреде­ление. Определение. Два множества, М и N, называются экви­валентными (обозначение М ~ N), если между их элементами можно установить взаимно однозначное соответствие. Понятие эквивалентности применимо к любым множествам, как конечным, так и бесконечным. Два конечных множества эквивалентны между собой тогда (и только тогда), когда число элементов у них одинаково. Определение счетного множества можно теперь сформулировать следующим образом: множество называется счетным, если оно эквивалентно множеству нату­ральных чисел. Ясно, что два множества, эквивалентные тре­тьему, эквивалентны между собой; в частности, любые два счет­ных множества эквивалентны между собой. Примеры. • Множества точек на любых двух отрезках [a, b] и [с, d] эквивалентны между собой. Из рис. 5 ясно, как установить между ними биекцию. Именно, точки р и q соответствуют друг другу, если они являются проекциями одной и той же точки r вспомогательного отрезка ef. • Множество всех точек на расширенной комплексной пло­скости эквивалентно множеству всех точек на сфере. Биекцию a —^ z можно установить, например, с помощью стереографиче­ской проекции (рис. 6). • Множество всех чисел в интервале (0, 1) эквивалентно множеству всех точек на прямой. Соответствие можно устано­вить, например, с помощью функции y =1/πarctgx+1/2. Рассматривая примеры, приведенные здесь и в п. 2, можно заметить, что иногда бесконечное множество оказывается эквивалентным своей истинной части. Например, натуральных чисел оказывается «столько же», сколько и всех целых или даже всех рациональных; на интервале (0, 1) «столько же» точек, сколько и на всей прямой, и т. д. Это явление характерно для бесконечных множеств. Действительно, в п. 2 (свойство 3) мы показали, что из всякого бесконечного множества М можно вы­брать счетное подмножество; пусть A = {a1, a2, ..., аn, ...} - та­кое подмножество. Разобьем его на два счетных подмножества A1 = {a1, a3, а5, ...} и A2 = {a2, a4, а6, ...} и установим между A и А1 взаимно однозначное соответствие. Это соответствие можно затем продолжить до взаимно однознач­ного соответствия между множествами A(M\A) = M и А1 (M\A) = M\A2, отнеся каждому элементу из М\А сам этот элемент. Между тем множество М\А не совпадает с М, т. е. является собственным подмножеством для М. Мы получаем, таким образом, следующее предложение: Всякое бесконечное множество эквивалентно некоторому сво­ему собственному подмножеству. Это свойство можно принять за определение бесконечного множества. 4. Несчетность множества действительных чисел. В п. 2 мы привели примеры счетных множеств. Число этих примеров мож­но было бы увеличить. Кроме того, как мы показали, сумма ко­нечного или счетного числа счетных множеств снова есть счет­ное множество. Естественно возникает вопрос: а существуют ли вообще не­счетные множества? Положительный ответ на него дает следую­щая теорема. Теорема 1. Множество действительных чисел, заключенных между нулем и единицей, несчетно. Доказательство. Предположим, что дано какое-то счет­ное множество (всех или только некоторых) действительных чисел α, лежащих на отрезке [0, 1]: (1) Здесь aik - k-я десятичная цифра числа аi. Построим дробь β =0, b1b2 ... bn ... диагональной процедурой Кантора, а именно: за b1 примем про­извольную цифру, не совпадающую с a11, за b2 - произвольную цифру, не совпадающую с a22, и т. д.; вообще, за bп примем про­извольную цифру, не совпадающую с ann. Эта десятичная дробь не может совпасть ни с одной дробью, содержащейся в переч­не (1). Действительно, от α1 дробь β отличается по крайней мере первой цифрой, от α2 - второй цифрой и т. д.; вообще, так как bп ≠ aпп для всех п, то дробь β отлична от любой из дробей αi , входящих в перечень (1). Таким образом, никакое счетное мно­жество действительных чисел, лежащих на отрезке [0, 1] , не ис­черпывает этого отрезка. Приведенное доказательство содержит небольшой «обман». Дело в том, что некоторые числа (а именно, числа вида р/10g) могут быть записаны в виде десятичной дроби двумя способами: с бесконечным числом нулей или с бесконечным числом девяток, например, 1/2 = 5/10 = 0.5000… = 0.4999… Таким образом, несовпадение двух десятичных дробей еще не гарантирует различия изображаемых ими чисел. Однако если дробь β строить осторожнее, так, чтобы она не содержала ни нулей, ни девяток, полагая, например, bn = 2, если апп = 1, и bn ≠ 2, то доказательство стано­вится вполне корректным. Итак, отрезок [0,1] дает пример несчетного множества. При­ведем некоторые примеры множеств, эквивалентных отрезку [0,1]: 1. Множество всех точек любого отрезка [а, b] или интервала (a, b). 2. Множество всех точек на прямой. 3. Множество всех точек плоскости, пространства, поверхно­сти сферы, точек, лежащих внутри сферы, и т. д. 4. Множество всех прямых на плоскости. 5. Множество всех непрерывных функций одного или несколь­ких переменных. В случаях 1 и 2 доказательство не представляет труда (см. примеры 1 и 3 п. 3). В остальных случаях непосредствен­ное доказательство довольно сложно. 5. Теорема Кантора—Бернштейна. Следующая теорема яв­ляется одной из основных в теории множеств. Теорема 2 (Кантор-Бернштейн). Пусть А и В — два произвольных множества. Если существуют взаимно одно­значное отображение f множества А на подмножество В1 мно­жества В и взаимно однозначное отображение g множества В на подмножество А1 множества А, то А и В эквивалентны. Доказательство. Не ограничивая общности, можно счи­тать, что A и B не пересекаются. Пусть х — произвольный эле­мент из А. Положим х = x0 и определим последовательность элементов {xn} следующим образом. Пусть элемент xn уже опре­делен. Тогда, если п четно, то за xn+1 примем элемент из В, удо­влетворяющий условию g(xn+1) = xn (если такой элемент суще­ствует), а если п нечетно, то xn+1 - элемент из А, удовлетворяю­щий условию f(xn+1)= xn (если он существует). Возможны два случая. 1°. При некотором п элемента xn+1, удовлетворяющего ука­занным условиям, не существует. Число п называется порядком элемента х. 2°. Последовательность {xn} бесконечна . Тогда х называет­ся элементом бесконечного порядка. Разобьем теперь A на три множества: AE , состоящее из эле­ментов четного порядка, A0—множество элементов нечетного порядка и AI — множество всех элементов бесконечного порядка. Разбив аналогичным образом множество В, заметим, что f ото­бражает AE на B0 и AI на BI, а g-1 отображает A0 на BE. Итак, взаимно однозначное отображение φ, совпадающее с f на AE AI и с g-1 на A0, есть взаимно однозначное отображение всего A на все B. 6. Понятие мощности множества. Если эквивалентны два ко­нечных множества, то они состоят из одного и того же числа элементов. Если же эквивалентные между собой множества М и N произвольны, то говорят, что М и N имеют одинаковую мощ­ность. Таким образом, мощность—это то общее, что есть у лю­бых двух эквивалентных между собой множеств. Для конечных множеств понятие мощности совпадает с привычным понятием числа элементов множества. Мощность множества натуральных чисел (т. е. любого счетного множества) обозначается символом (читается: «алеф нуль»). Про множества, эквивалентные мно­жеству всех действительных чисел отрезка [0, 1], говорят, что они имеют мощность континуума. Эта мощность обозначается символом с (или символом ). Весьма глубокий вопрос о существовании мощностей, проме­жуточных между и с, будет затронут ниже в § 4. Как пра­вило, бесконечные множества, встречающиеся в анализе, или счетны, или имеют мощность континуума. Для мощностей конечных множеств, т. е. для натуральных чисел кроме понятия равенства имеются также понятия «боль­ше» и «меньше». Попытаемся распространить эти последние на бесконечные мощности. Пусть A и B—два произвольных множества, а m(A) и m(B)—их мощности. Тогда логически возможны следующие случаи: 1. A эквивалентно некоторой части множества В, а В эквива­лентно некоторой части множества A. 2. A содержит некоторую часть, эквивалентную B, но в В нет части, эквивалентной A. 3. B содержит некоторую часть, эквивалентную A, но в A нет части, эквивалентной B. 4. Ни в одном из этих двух множеств нет части, эквивалент­ной другому. В первом случае множества A и B в силу теоремы Кантора-Бернштейна эквивалентны между собой, т. е. m(A) = m(B). Во втором случае естественно считать, что m(A) > m(B), а в тре­тьем, что m(A) < m(B). Наконец, в четвертом случае нам при­шлось бы считать, что мощности множеств A и B несравнимы между собой. Но на самом деле этот случай невозможен! Итак, любые два множества А и В либо эквивалентны между собой (и тогда m(A)=m(B)), либо удовлетворяют одному из двух соотношений: m(A) < m(B) или m(A) > m(B). Мы отметили выше, что счетные множества—это «самые ма­ленькие» из бесконечных множеств, а затем показали, что суще­ствуют и бесконечные множества, бесконечность которых имеет более «высокий порядок», - это множества мощности континуума. А существуют ли бесконечные мощности, превосходящие мощ­ность континуума? Вообще, существует ли какая-то «наивыс­шая» мощность или нет? Оказывается, верна следующая теорема. Теорема 3. Пусть М — некоторое множество и пусть ₤ — множество, элементами которого являются всевозможные под­множества множества М. Тогда ₤ имеет мощность большую, чем мощность исходного множества М. Доказательство. Легко видеть, что мощность m множе­ства ₤ не может быть меньше мощности m исходного множе­ства M; действительно, «одноэлементные» подмножества из M об­разуют в ₤ часть, эквивалентную множеству М. Остается дока­зать, что мощности ₤ и m не совпадают. Пусть между элементами a, b, ... множества M и какими-то элементами A, B, ... множества ₤ (т. е. какими-то подмножествами из М) установлено взаимно однозначное соответствие а ↔A, b ↔В, . . . Покажем, что оно наверняка не исчерпывает всего ₤. Имен­но, сконструируем такое множество Х М, которому не соответ­ствует никакой элемент из М. Пусть Х—совокупность элемен­тов из М, не входящих в те подмножества, которые им соответ­ствуют. Подробнее: если а↔А и аА, то элемент а мы не включаем в X, а если а ↔ А и а А, то мы включаем элемент а в X. Ясно, что Х есть подмножество множества М, т. е. некото­рый элемент из ₤. Покажем, что подмножеству Х не может со­ответствовать никакой элемент из М. Допустим, что такой эле­мент х ↔ Х существует; посмотрим, будет ли он содержаться в Х или нет? Пусть хХ; но ведь по определению в Х входит всякий элемент, не содержащийся в подмножестве, которое ему соответствует, следовательно, элемент х должен быть вклю­чен в X. Обратно, предположив, что х содержится в X, мы полу­чим, что х не может содержаться в X, так как в Х включены только те элементы, которые не входят в соответствующие им подмножества. Итак, элемент х, отвечающий подмножеству X, должен одновременно и содержаться и не содержаться в X. От­сюда следует, что такого элемента вообще не существует, т. е. что взаимно однозначного соответствия между элементами мно­жества М и всеми его подмножествами установить нельзя. Тео­рема доказана. Итак, для любой мощности мы действительно можем по­строить множество большей мощности, затем еще большей и т. д., получая, таким образом, не ограниченную сверху шкалу мощностей. Замечание. Мощность множества ₤ обозначают симво­лом 2m, где m — мощность М. (Читатель легко поймет смысл этого обозначения, рассмотрев случай конечного М.) Таким об­разом, предыдущую теорему можно выразить неравенством т «< 2"1. В частности, при m = % получаем неравенство %<2%. Покажем, что 2% = %, т. е. покажем, что мощность мно­жества всех подмножеств натурального ряда равна мощности континуума. Разобьем подмножества натурального ряда на два класса, Ћ и ®,—на те (классЋ ), у которых дополнение бесконечно, и на те (класс ®), у которых оно конечно. К классу ® относится, в частности, сам натуральный ряд, ибо его дополнение пусто. Чис­ло подмножеств в классе ® счетно (доказать). Класс ® не влияет на мощность множества ₤. = Ћ ®. Между подмножествами класса Ћ и действительными числа­ми из полусегмента [0, 1) можно установить взаимно однозначное соответствие. Именно, сопоставим подмножеству AЋ число α, 0 ≤ α < 1, с двоичным разложением α= e1/2+e2/22+ … + en/2n + … где en = 1 или 0 в зависимости от того, принадлежит ли п мно­жеству А или нет. Проверку деталей предоставляем читателю. Библиография 1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. –304 с.: ил. 2. Судоплатов С.В., Овчинников Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск : Изд-во НГТУ, 2002.-280 с.- (Серия «Высшее образование». 3. Шапорев С.Д. Курс лекций и практических занятий.- СПб.: БХВ-Петербург,2006 – 400 с.: ил. 4. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: Учебник для втузов.- М.: Наука. Физматлит, 2000.-544с. 5. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера – М: Энергоатомиздат, 1988 – 480 с.: ил. 6. Вольвачев Р.Т. Элементы математической логики и теории множеств: Учеб. Пособие для мат. спец. вузов. - Мн.: изд-во «Университетское», 1986. – 112 с.: ил.