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

Отношения. Функции. Взаимно однозначные соответствия

Часто при решении задач необходимо выбирать элементы, связанные некоторым соотношением. Примерами таких связей между элементами могут служить функциональные: зависимости или отношение «меньше либо равно».

n -местным отношением или n -местным предикатом Р на множествах A 1, А 2, ..., Апназывается любое подмножество прямого произведения A 1× А 2× ... × Ап. Другими словами, элементы x 1, x 2, ..., x п(где x 1∈ A 1,..., xn∈ Ап) связаны соотношением Р (обозначается P ( x 1, x 2, ..., x п)) тогда и только тогда, когда ( x 1, x 2, ..., x п) ∈ Р .

При п = 1 отношение Р является подмножеством множества A 1и называется унарным отношением или свойством .

Наиболее часто встречаются двухместные отношения (п = 2). В этом случае они называются бинарными отношениями или соответствиями . Таким образом, соответствием Р между множествами А и В является подмножество множества А × В . Если Р ⊆ А × В и (х , у ) ∈ Р , то пишут также хРу .

Отношение Р ⊆ Апназывается п-местным отношением (предикатом ) на множестве А .

Пример 2.1.Если А = {2, 3, 4, 5, 6, 7, 8}, то бинарное отношение Р = {( x , y ) | x , у ∈ А , х делит y и x ≤ 3} можно записать виде Р = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6)}.

Пример 2.2.Рассмотрим отношение Р = {{х , у ) | х , у ∈ ℝ , х ≤ у } на множестве ℝ . Тогда запись хРу означает, что х ≤ у , и в качестве имени (обозначения) этого отношения можно взять сам символ ≤.

Бинарные отношения Р ⊆ А × В иногда удобно изображать графически. Рассмотрим два таких представления. Начертим пар y взаимно перпендикулярных осей (Ох горизонтальная ось, Оу — вертикальная. ось), на каждой оси отметим точки, представляющие элементы множеств А и B соответственно. Отметив на плоскости точки с координатами (х , у ) такие, что (х , у ) ∈ Р , получаем множество, соответствующее отношению Р . На рис. 1.3 показано множество точек, соответствующих отношению из примера 2.1.

Рис. 1.3.

Другой способ состоит в том, что элементы х ∈ А и y ∈ B , связанные отношением Р , соединяются стрелками.

Пример 2.4.На рис. 1.4 графически показаны отношение Р 1= {(а , 2), ( b , 1), ( c , 2)} между множествами А = {а , b , с } и В = {1, 2, 3}, а также отношение Р 2= {(а , b ), ( b , b ), (с , а )} на множестве А .

Рис. 1.4.

Для любого множества A определим тождественное отношение idA⇌ {( x , x ) | x ∈ А } и универсальное отношение UA⇌ A 2. Отношение idAназывается также диагональю , а UA— полным отношением .

Пусть P — некоторое бинарное отношение. Областью определения отношения Р называется множество

δ p⇌ {x | ( x , y ) ∈ P для некоторого y },

областью значений отношения Р — множество

ρ p⇌ {y | ( x , y ) ∈ P для некоторого x },

06ратным к Р отношением называется множество

Р –1⇌ {( y , x ) | ( x , y ) ∈ P },

Образом множества X относительно предиката Р называется множество

Р (Х ) ⇌ {у | (х , у ) ∈ Р для некоторого х ∈ X },

прообразом множества X относительно Р — множество Р –1(Х ) или, другими словами, образ множества X относительно предиката Р –1.

Пример 2.5.Для отношения Р из примера 2.1 и множества X = {3} имеем δ p= {2, 3}, ρ p= {2, 3, 4, 6, 8}, Р –1= {(2, 2), (4, 2), (6, 2), (8, 2), (3, 3), (6, 3)}, P ( X ) = {3, 6}, P –1( X ) = {3}.

Произведением бинарных отношений Р 1⊆ А × В и P 2⊆ В × С или композицией Р 1и Р 2называется множество P 1 ○ P 2= {( x , у ) | x ∈ А , у ∈ С , и найдется элемент z ∈ В такой, что ( x , z ) ∈ P 1и ( z , y ) ∈ Р 2} (рис. 1.5). В дальнейшем произведение P 1 ○ P 2будем также обозначать через P 1P 2.