XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 9
Текст из файла (страница 9)
Поскольку в общем случае могут найтись такие два различных элемента х и х', что 1(х) = 1(х'), то соответствие 1 1 в общем случае не будет функиионально по второй компоненте и поэтому не будет отображением. Если отображение 1 иньективно, то обратное соответствие есть частичное отображение из В в А. Если отображвнив У бивктпивно, то обратное соответствие является отображением из В в А, причем имеют место равенства 1.4. Ояерацли ялд соответстлялмя упорядоченные пары, первая компонента которых принадлежит подмножеству С, а вторая — подмножеству Р.
Можно записать р[с и = р П (С х Р). Так, „малый" арксинус, т.е. функция у = агсвшг, есть ограничение „большого" арксинуса у = Агсвш я, который является соответствием на подмножества [ — 1, 1] и [--, -]. Рассмотрим некоторые важные частные случаи ограниче. ний соответствий (в частности, бинарных отношений и отображений). Всякое (С, В)-ограничение соответствия р С А х В будем называть сужением соотпветпстпвия р на подмножестпво С (коротко — С-сужением соотпветпстпвия р), а всякое (С, р(С))-ограничение соответствия р — стпрогим сужением соотпветпстпвия р на подмножестпво С (отправим С-сужением соотпветпстпвия р). С-сужения соответствия р будем обозначать р[с, а строгое сужение — р[ес соответственно.
Полезно заметить, что для любого отображения у: А-+ -+ В строгое сужение Дел есть сюръекция А на у(А). Если, сверх этого, у является инъекцией, то Дел есть биекция А на 1(А). Допуская некоторую вольность речи', можно сказать, что любое отображение сюръективно отображает свою область определения на свою область значений, в частности, любая инъекция устанавливает взаимно однозначное соответпстпвие между областью определения и областью значений. Так, функция у = зшг сюръективно отображает множество Й всех действительных чисел на отрезок [-1, 1], а любая показательная функция биективно отображает Й на подмножество всех положительных действительных чисел.
Для бинарного отношения р С Аз и любого подмножества М С А (М, М)-ограничение бинарного отношения называют 'Вольность состоит в том, что мм отомдествллем фултотюо у с фуюсяяей Дол. 60 1. МНОЖЕСТВА И ОТНОШЕНИЯ ограничением бинарного отпношенил р на подмножестпво М и обозначают р[м. Можно записать р~м = рО Мз. Рассмотрим, например, отношение естественного порядка < на множестве действительных чисел [Ц. Тогда отношение < ~х = Цтп, и): тп < и; тп, и е Е) есть ограничение этого порядка на подмножество целых чисел.
Но ни в коем случае нельзя путать это отношение с Е-сужением отношения <! Это последнее состоит из всех таких упорядоченных пар (тп, х), что тп Е Е, х Е Ж и тп < х, т.е. вторая компонента пары может быть произвольным действительным числом, не меньшим заданного целого тп. 1.5. Семейства множеств Рассматриваемое ниже понятие семейства множеств обобщает аналогичное понятие, сформулированное в [?]. Пусть У вЂ” универсальное мноэсвстпво. Если каждому натуральному числу и взаимно однозначно сопоставлено некоторое подмножество А„С У, то тем самым определена последовательность множеств Ам ..., А„, ..., или, в короткой записи, (А„)„ен.
Предположим теперь, что вместо множества 1Ч натуральных чисел задано произвольное множество 1 и каждому элементу т' Е 1 взаимно однозначно сопоставлено подмножество А; С У. Тогда говорят, что задано ~индексированное) семет2стпво множестпв (А);ет. Множество 1 называют множеством индексов, а множества А; — элементами семейства (А;)тет В случае 1 = Я получаем последовательность множеств, или счетное семейстпво множестпв; если множество 1 конечно, получаем конечное семейстпво множестпв.
Таким обра зом, семейство (А;)шт определено, если задано отпображение ьс 1-+ 2п. Отметим, что любое множество, элементы которого есть некоторые подмножества универсального множества У, т.е. любое множество А С 2тт, можно считать семейством (А;);ет, 1.5. Семейства множеств где Х = А, а м — тождественное отображение множества А на себя. Пример 1.11. Рассмотрим в качестве множества индексов множество точек некоторой гладкой плоской кривой [1Ц (рис. 1.6) и каждой точке сопоставим касательную, проведенную к кривои в этой точке (которзя будет единствен- 1' ной в силу гладкости).
Тогда получаем в семейство множеств, элементами которого служат множества точек различных касательных. Рнс. 1.6 Операции объединения и пересечения множеств можно распространить на произвольные семейства множеств [Ц. 1. Объединение семейства множеств: Ц А; = (х: (Эв)(х Е А;)) . ввн1 2. Пересечение семейства множеств: [ [А; =(х: (Чв)(х ЕА;О. вви1 Методом двух включений можно доказать следующие тождества: А О ф Вв) = Ц(А 0 Вв)в А О ф Вв) = Д(А О Вв). ввт ввт ввн1 вЕ1 Аналогично можно доказать тождества АП фВ1) =( )(АПВ1), Аи (ДВ1) = [" [(АиВ;), (1.6) все1 ввя1 ввн1 ве1 [ [А; = ДА;, ДА; = ЦЛ,. (1.6) вн1 вет вот ве1 Тождества (1.5) выражают свойство бесконечной дистрибувнивносвни операций пересечения и объединения, а тождества (1.6) называют бесконечнььни эоконаяви де Моргана.
62 1. МНОЖЕСТВА Н ОТНОШЕНИЯ 1.6. Специальные свойства бинарных отношений В этом параграфе дана определенная классификация бинарных отношений на множесшве. В основе этой классификации лежат специальные свойства отношений. Бинарное отношение р на множестве А называют рефлексивнььк, если диагональ множества А содержитасл в р: ЫА С р, т.е. х р х для любого элемента х множества А.
Если же ИА Пр = Я, то бинарное отношение р на множестве А называют иррефлексивным. Указанные свойства бинарных отношений на множестве А называют рефлексивностпью и иррефлексивностпью. Бинарные отношения равенства и подобия на множестве геометрических фигур рефлексивны: каждый треугольник равен самому себе и подобен самому себе. На самом деле рефлексивны все отношения равенства: равенство чисел, равенство векторов, равенство множеств и т.п.
Также рефлексивными являются, например, бинарное отношение нестрогого неравенства на множестве действительных чисел, поскольку для любого числа х всегда х < х, и отпношение С вклюненил множеств, так как для любого множества Х всегда Х С Х. Напротив, бинарное отношение на множестве действительных чисел, задаваемое строгим неравенством х < у, иррефлексивно, равно как 'я отношение С сшрогого включения множеств. Не следует путать иррефлексивное отношение с нерефлексивным, т.е. не являющимся рефлексивным, отношением.
Иррефлексивное отношение нерефлексивно, но не всякое нерефлексивное отношение иррефлексивно. Иррефлексивному отношению на А не принадлежит ни один элемент диагонали 16А, а нерефлексивное отношение может содержать некоторые (но не все!) элементы диагонали. На рис. 1.7 приведены примеры графиков иррефлексивного и нерефлексивного отношений (пунктиром указаны диагонали множеств). Ь6. Слецлатьлые свовсгла блварвых огяошелий бЗ Рнс. 1.7 Бинарное отношение р на множестве А называтот: 1) симметричным, если для любых х, у Е А из х р у следует урх; 2) антттисимметнричным, если для любых х, у Е А из одновременной справедливости х р у и у р х следует, что х=у.
Соответствующие свойства бинарных отношений на множестве А называют симме- шричностнью и антписимметаричностпью. График симметричного бинарного отношения на множестве А симметричен относительно диагонали (рис. 1.8). Рис. 1.8 Теорема 1.1. Бинарное отношение р на множестве А симметрично, если и только если бинарное отаношение на множестпве А, обратное к р, совпадает с р: р т = р.
Теорема 1.2. Бинарное отношение р на множестве А антисимметрично, если и только если рй р 1 С Ыл. ° 4 Действительно, если(х, у) Ерйр ~,то(х, у) Ери(х, у) Ер ~ (т.е. (у, х) Е р). Но из выполнения соотношений х р у и у р х ввиду антисимметричности р следует, что х = у, т.е. (х, у) Е Ыл. ° е Пусть (х, у) Е р ~, т.е. (у, х) Е р. Тогда, в силу симметричности р, (х, у) Е р.
Следовательно, р т С р. Аналогично доказывается включение р С р '. Теперь пусть р = р '. Тогда (х, у) Е р и (х, у) Е р 1. Из определения обратного отношения вытекает, что (у, х) Е р. Следовательно, р — симметричное бинарное отношение. ° 64 В МНОЖЕОТВА И ОТНОШЕНИЯ Обратно, пусть рП р 1 С к4. Предположим, тго (х, у) е р и (у, я) Е р, причем я ф у. Тогда (х, у) Е р 1 и (х, р) Е рО р но (х, у) ф и4. Получаем противоречие.
~ь Отметим, что для антисимметричного бинарного отношения на множестве А может иметь место равенство рО р 1 = И. Все бинарные отношения в геометрии типа равенства или подобия симметричны. Так, если треугольник АВС подобен треугольнику А'В'С', то и второй из зтих треугольников подобен первому. Бинарные отношения неравенства чисел и включения множеств, как строгие, так и не строгие, антисимметричны. Бинарное отношение р на множестве А называют тираизипиюеиым, если для любых х, у, я Е А из того, что я р у и р р я, следует х р ю Соответствующее свойство бинарного отношения называют тпранэитпивностпью.
Пример 1.12. а. Пусть М вЂ” некоторое множество населенных пунктов. Зададим на нем бинарное отношение достижимости: из пункта А достижим пункт В, если есть дорога, по которой можно доехать из А в В. Это отношение транзитивно, поскольку если из пункта А можно доехать до пункта В, а из В есть дорога до С, то из А можно проехать в С. б. Бинарные отношения равенства и подобия в геометрии являются транзитивными: если треугольник АВС подобен треугольнику А1В1СМ а зтот последний подобен треугольнику АгВзСз, то первый треугольник подобен третьему.
в. Бинарное отношение неравенства на множестве действительных чисел не транзитивно, так как из того, что х у6 у и у ф я, вовсе не следует, что х у6 ю Аналогично, если я друг у, а р друг я, то — вопреки известной поговорке — зто не означает, что х друг ю ф Докажем следующее важное свойство транзитивного бинарного отношения. 1.б. Саеаввльяые свойства аияврлых отяошввий 65 Теорема 1.3. Бинарное отношение р на множестве А транзитивно тогда и только тогда, когда его квадрат содержится в нем, т.е. рорС р. < Пусть бинарное отношение р на множестве А транзитивно и (х, «) Е рз = рор. В силу определения композиции бинарных отпношений на мноэсестве А существует такой элемент у, что х р у и у р «, откуда ввиду транзитивности р получаем х р «, т.е. (х, «) бр, а значит, р~ С р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
