double arrow

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

Для приложения теории множеств к решению практических задач часто приходится рассматривать множества, между элементами которых определены те или иные отношения. Так, например, во множестве офицеров данного полка для некоторых пар элементов (a, b) справедливо утверждение «Офицер a служит в одной роте с офицером b», для других пар справедливо утверждение «Офицер a старше по званию офицера b», для третьих - утверждение «Офицер a имеет то же звание, что и офицер b». Каждое из этих утверждений задает некоторое отношение между офицерами a и b (совместной службы, старшинства, равенства званий). Примерами отношений могут служить неполные предложения - предикаты:

... меньше, чем...,... делится на...,

... включено в...,... конгруэнтно....

В приведенных примерах речь шла об отношениях между элементами одного и того же множества. Можно говорить и об отношениях (точнее, соответствиях) между элементами различных множеств - например, утверждение «Офицер a служит в роте b» задает соответствие между множеством офицеров и множеством рот.

Для определения понятия соответствия используем представление о множестве упорядоченных пар элементов, троек, n-строчек, т.е. кортежей.

Бинарным соответствием (отношением) называется всякое подмножество множества X ´ Y. В этом случае говорят, что между множествами X и Y установлено бинарное соответствие. Этот факт символически записывается в виде:

x R y, x Î X, y Î Y,

где R - символ отношения, указывающий конкретное подмножество множества X ´ Y.

Тернарным соответствием (отношением) называется подмножество множества упорядоченных троек, являющихся элементами декартова произведения X ´ Y ´ Z.

n - арное соответствие (отношение) определяется как подмножество множества n-строчек, являющихся элементами декартова произведения

X1 ´ X2 ´... ´ Xn.

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

Если множества X и Y в бинарном соответствии совпадают, то говорят об отношении между элементами множества X. Рассмотрим основные свойства отношений.

1. Отношение R на множестве X называется рефлексивным, если для любого элемента x Î X справедливо x R x или, иначе, (x, x) Î R.

2. Если условие рефлексивности не выполняется ни для одного элемента x Î X, то отношение R называется антирефлексивным.

3. Отношение R между элементами множества X называется симметрическим, если для любых элементов x, y Î X справедливо соотношение

x R y Þ y R x или (x, y) Î R Þ (y, x) Î R.

4. Отношение R между элементами множества X называется антисимметрическим, если для любых элементов x, y Î X справедливо утверждение (x, y) Î R Þ (y, x) Ï R. Антисимметрическое отношение является одновременно и антирефлексивным.

5. Отношение R между элементами множества X называется тождественным, если для любых элементов x, y Î X справедливо утверждение: x R y и y R x Þ x = y или (x, y) Î R и (y, x) Î R Þ x = y. Антисимметрическое отношение является пересечением тождественного и антирефлексивного отношений.

6. Отношение R между элементами множества X называется транзитивным, если для любых элементов x, y, z Î X справедливо

x R y, y R z Þ x R z или (x, y) Î R и (y, z) Î R Þ (x, z) ÎR.

Примерами транзитивных отношений являются отношения параллельности, равенства, «больше». Отношения перпендикулярности, неравенства представляют собой нетранзитивные отношения.

7. Отношение R между элементами множества X обладает свойством полноты, если для любой пары (x, y) элементов из X всегда выполняется одно из двух соотношений: x R y или y R x.

Для каждого отношения R можно определить обратное отношение R-1. Краткая запись этого определения выглядит следующим образом:

" R $ R-1, y R-1 x Û x R y.

Например, для отношения «x является делителем y» обратным является «y кратно x», для отношения «x больше y» обратно «y меньше x».

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

Дополнительным к R отношением `R называется такое отношение, что (x1, x2) Î`R Û (x1, x2) Ï R.

Рассмотрим теперь основные виды отношений.

1. Отношение R Ì X ´ X между элементами множества X, обладающее свойствами рефлексивности (x R x " x Î X), симметричности (x1 R x2 Þ x2 R x1 " x1, x2 Î X) и транзитивности (x1 R x2 и x2 R x3Þ x1 R x3 " x1, x2, x3 Î X), называется отношением эквивалентности и обозначается x1 ~ x2. Примерами отношения эквивалентности являются равенство векторов в евклидовом пространстве, равенство фигур в евклидовой геометрии. Любое отношение эквивалентности, заданное на множестве, разбивает это множество на непересекающиеся подмножества. Так, например, отношение «проживание в одном городе» на множестве жителей страны разбивает это множество на непересекающиеся подмножества, количество которых равно числу городов в стране. Эти подмножества называются классами эквивалентности. Справедливо и обратное утверждение: каждое разбиение множества на непересекающиеся подмножества определяет некоторое отношение эквивалентности.

2. Отношением квазипорядка на множестве X называется отношение R Ì X ´ X, обладающее свойствами рефлексивности и транзитивности. Например, отношение «x1 ³ x2» на множестве вещественных чисел есть отношение квазипорядка. Поэтому данное отношение часто обозначается символом ³.

3. Отношение квазипорядка, обладающее также свойством тождественности, называется отношением порядка. Оно должно, таким образом, удовлетворять аксиомам отношения «x ³ x»: x1 ³ x2 и x2 ³ x3 Þ x1 ³ x3, x1 ³ x2 и x2 ³ x1 Þ x1 = x2.

4. Отношение, обладающее свойствами транзитивности и антисимметричности, называется отношением строгого порядка. Это отношение часто обозначают символом >. Оно должно удовлетворять следующим аксиомам: x1 > x2 и x2 > x3 Þ x1 > x3, x1 > x2 Þ x2 > x1 – невозможно.

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

Наглядное представление о перечисленных типах отношений и их свойствах дает табл. 1.2.

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

Таблица 1.2. – Виды отношений и их свойства

  Отношения
Свойства Эквивалентность Квазипорядок Порядок Строгий порядок Полный порядок Нерефлексивный полный порядок
1.Рефлексивность * * *   *  
2.Антирефлексив-ность       *   *
3.Симметричность *          
4.Антисимметрич-ность       *   *
5.Тождественность     *   *  
6.Транзитивность * * * * * *
7.Полнота         * *

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: