ОПРЕДЕЛЕНИЕ 3. n-арным отношением на множествеA называется подмножество G прямого произведения An. Таким образом, n-арное отношение на A это некоторое семейство размещений с повторениями элементов из множества A по n.
При n=1 это просто подмножество A,такое отношение называют свойством. Так, если в множестве натуральных чисел выделить подмножество четных чисел, то такое 1-арное отношение ассоциируется со свойством четности.
При n=2 отношение называется бинарным, это будет основным объектом рассмотрения в этом параграфе.
Приведем пример 3-арного отношения на множестве целых чисел. Числа a,b,c находятся в отношении, если a+b=c.
Примеры бинарных отношений.
А) На множестве натуральных чисел.
А1) Отношение ≤. Числа 5 и10 находится в этом отношении, а числа 10 и 5 нет.
А2) Отношение <.
А3) Быть делителем. Числа 2 и 10 находится в этом отношении, а 4 и 10 нет.
А4) Равенство «=». 5=5 (т.е. числа 5 и 5 находятся в отношении равенства (как звучит!)), а 5 и 6 нет.
А5) Числа a,b находятся в этом отношении, если a+b≤10.
В) На множестве точек плоскости (точки считаем заданными декартовыми координатами).
В1) Расстояние 1. Точки (a1,a2) и (b1,b2) находятся в отношении, если .
B2) Симметрия относительно оси 0х. Точки (a1,a2) и (b1,b2) находятся в отношении, если a1=b1, a2+b2=0.
B3) Неравенство ≤. Точки (a1,a2) и (b1,b2) находятся в отношении, если a1≤b1, a2≤b2. Рассмотрите, что это означает графически.
С) На множестве людей.
С1) Отношение «жить в одном доме».
С2) Быть родственником.
С3) Быть потомком.
С4) Дружить.
D) На булеане некоторого множества.
D1) Быть подмножеством.
D2) Иметь непустое пересечение.
D3) Множества A и B находятся в отношении, если |AB |=1.
Сформулируем основные свойства, которыми могут обладать бинарные отношения.
ОПРЕДЕЛЕНИЕ 4. Бинарное отношение G на множестве A называется рефлексивным, если
Бинарное отношение G на множестве A называется антирефлексивным, если
Бинарное отношение G на множестве A называется симметричным, если из условия следует включение .
Бинарное отношение G на множестве A называется антисимметричным, если либо не существует элементов a и b таких, что и , либо a=b. (Если пользоваться смыслом операции импликации из математической логики, то первое условие можно опустить.)
Бинарное отношение G на множестве A называется транзитивным,если из условий и следует, что .
Вопрос. Верно ли, что если бинарное отношение не является рефлексивным, то оно антирефлексивное?
Из перечисленных выше бинарных отношений
- рефлексивными являются А1, А3, А4, В3, С1, С2, С4, D1;
- антирефлексивными являются A2, B1, C3, D3;
- симметричными являются А4, А5, B1, В2, С1, С2, С4, D2;
- антисимметричными являются А1, А2, А3, А4, В3, С3, D1;
- транзитивными являются А1, А2, А3, А4, В3, С1, С3, D1.
Проверьте, что это так, убедитесь также, что не перечисленные в этих перечнях отношения соответствующим свойством не обладают.
На основе введенных свойств выделяются некоторые важные классы бинарных отношений.
ОПРЕДЕЛЕНИЕ 5. Рефлексивное, симметричное и транзитивное бинарное отношение G на множестве A называется отношением эквивалентности. Мы будем использовать стандартное обозначение a~b.
Среди перечисленных отношением эквивалентности является С1. Это отношение обладает важным свойством. Множество людей распадается на подмножества людей, состоящих из соседей (т.е. живущих в одном доме). Например, подмножество образуется теми, кто проживает по адресу: Уфа, ул. Ленина, 2. Каждый дом порождает такое подмножество. Это свойство является характерным для отношения эквивалентности.
Теорема 3. Если на множестве A задано отношение эквивалентности, то , где при i¹j и a~b тогда и только тогда, когда они входят в одно множество . Эти множества называются классами эквивалентности.
В нашем примере множества .это отдельные дома. Число множеств может быть как конечным, так и бесконечным.
Вопрос. Для какого бинарного отношения класс эквивалентности всего один?
Доказательство. Каждый элемент порождает множество , состоящее из элементов, ему эквивалентных. Докажем, что эти подмножества и есть классы эквивалентности. Для этого последовательно проверим несколько утверждений.
1. Каждое из множеств непустое. Действительно, в силу рефлексивности , следовательно, .
2. Если , то . Пусть , . Докажем, что . Действительно, из условия следует, что . Вследствие симметричности отношения эквивалентности из следует . По транзитивности из следует, что . Далее, , поскольку . По транзитивности из условий , следует, что , т.е. . Доказанное означает, что . Но множества и равноправны, поэтому и . А тогда , что и требовалось.
Таким образом, множества либо не пересекаются, либо совпадают.
3. Докажем, что эквивалентные элементы входят в одно из построенных множеств. Пусть . Это означает, что . В силу рефлексивности (п. 1). Утверждение доказано.
4. Докажем, наконец, что если два элемента входят в одно множество, то они эквивалентны. Пусть . Тогда . В силу симметричности , а тогда в силу транзитивности , что и требовалось.
Теорема доказана.
Рассмотрим еще один класс бинарных отношений.
ОПРЕДЕЛЕНИЕ 6. Рефлексивное, антисимметричное, транзитивное бинарное отношение называется отношением нестрогого порядка. Антирефлексивное, антисимметричное, транзитивное бинарное отношение называется отношением строгого порядка.
Примерами отношений первого вида являются А1, В1, второго – А2, С3.
Отношения строгого и нестрогого порядка тесно связаны между собой. Пусть G – отношение нестрогого порядка на множестве A. Бинарное отношение является отношением строгого порядка. Столь же просто (добавлением диагонального множества) можно из отношения строгого порядка получить отношение порядка нестрогого.
Отношения нестрогого порядка А1и В1 имеют существенное различие: для любых двух натуральных чисел a,b выполняется хотя бы одно из условий: a≤b, b≤a. Иначе говоря, любые два натуральных числа сравнимы по отношению порядка. А вот для отношения В1 (на множестве точек плоскости) это не так. Действительно, какая из точек больше по введенному ранее отношению: (2,3) или (3,2)? Отношения порядка, при котором любые два элемента множества сравнимы, называется линейным.
Определим полезное отношение строгого порядка (обозначение ) на множестве слов (см. выше). Греческими буквами (a,b,g) обозначаются произвольные слова языка, ab это слово, в котором к слову a приписано слово b (конкатенация слов). Порядок определяется двумя правилами.
1. a ,
2. aak, если k<m.
Вопрос. Доводилось ли вам встречаться с этим отношением раньше? Оно называется лексикографическим.