§ 1.2. Бинарные отношения, их свойства. Отношения эквивалентности и порядка.

Определение. Бинарным отношением на множестве A называется любое подмножество Условимся писать ab, если

Рассмотрим множество из трех элементов. Бинарное отношение на множестве C – это любое подмножество декартова квадрата Например, это бинарное отношение на C. Такое бинарное отношение можно задать в виде матрицы размера Будем считать, что первая строка и столбец соответствуют элементу a, вторая – b и третья – c. Если данная пара принадлежит данному бинарному отношению, то на соответствующем месте в матрице будем ставить 1, в противном случае – 0. Тогда отношение можно задать следующей матрицей

Задача 1.2.1.а) Бинарное отношение на множестве задано матрицей

Выпишите все пары, из которых состоит отношение .

б) На множестве дано бинарное отношение Задайте его матрицей.

а)

б) Решите самостоятельно.

Подсчитаем, сколько всего бинарных отношений существует на множестве C. Множество состоит из девяти элементов. Каждое бинарное отношение – это подмножество в . Число подмножеств в множестве из 9 элементов равно

Определение. Бинарное отношение  на множестве A называется рефлексивным, если каждый элемент множества A состоит сам с собой в бинарном отношении .

Определение. Бинарное отношение  на множестве A называется симметричным, если тогда и только тогда, когда .

Определение. Бинарное отношение  на множестве A называется антисимметричным, если и может быть только в том случае, когда a=b.

Определение. Бинарное отношение  на множестве A называется транзитивным, если всегда, когда и , пара (a,c) также принадлежит .

Задача 1.2.2. Какими свойствами (рефлексивность, симметричность, антисимметричность, транзитивность) обладает данное бинарное отношение на множестве ?

а) б)

а) Отношение не рефлексивно, т.к. Отношение симметрично. Далее, не антисимметрично, т.к. и принадлежат , однако Отношение не транзитивно, т.к. но

б) Решите самостоятельно.

Задача 1.2.3. Подсчитайте число а) рефлексивных; б) симметричных; в) антисимметричных бинарных отношений на множестве из n элементов.

а) На главной диагонали в матрице должны стоять единицы. Остальные элементы могут быть произвольными. Поскольку число остальных элементов равно то число рефлексивных бинарных отношений будет равно

б), в) Решите самостоятельно.

Определение. Бинарное отношение , обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности. Для элемента множество называется смежным классом отношения  , содержащим a. Новое множество, элементами которого являются смежные классы отношения , называют фактор-множеством и обозначают A/.

Определение. Бинарное отношение , обладающее свойствами рефлексивности, антисимметричности и транзитивности, называется отношением порядка. Множество с заданным на нем отношением порядка называется частично упорядоченным. Два элемента, состоящие в отношении , называются сравнимыми. Частично упорядоченное множество, в котором любые два элемента сравнимы, называется линейно упорядоченным.

Приведем еще некоторые примеры бинарных отношений.

Пример 1. На множестве рассмотрим бинарное отношение

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

Пример 2. На множестве натуральных чисел рассмотрим отношение делимости . Будем считать, что (n,m ), если n делит m. Например, . Тот факт, что n делит m, часто обозначают следующим образом n / m. Отношение также будет являться отношением порядка, однако этот порядок уже нелинейный.

Пример 3. Пусть имеется функция f(x), заданная на . Для x,y будем считать, что если y=f(x). Множество всех является графиком функции f(x). Для того, чтобы отношение было рефлексивным, нужно, чтобы x=f(x) для всех x. Симметричность будет иметь место тогда, когда f(f(x))=x. Таких функций много, например, (можно доопределить f(0)=0).

Пример 4. На множестве M₂( ) матриц размера с действительными коэффициентами рассмотрим бинарное отношение :

если det(A)=det(B) (A,B M₂( ) )

Отношение будет рефлексивным, симметричным и транзитивным, т.е. будет являться отношением эквивалентности.

Пример 5. Рассмотрим множество всех непрерывных функций на отрезке . Будем считать, что Тогда будет отношением порядка, а множество – частично упорядоченным.

Пример 6. Пусть A= – множество целых чисел. Зададим отношение следующим образом. Для будем считать, что , если n – m делится на 5. Несложно проверить, что будет отношением эквивалентности. Фактор-множество будет состоять из пяти элементов. Одним из элементов будет являться множество всех целых чисел, делящихся на 5. Другой элемент будет образовывать множество всех целых чисел, которые при делении на пять дают в остатке 1 и т.д..

Определение. Разбиением множества A называется любое семейство его подмножеств

обладающее двумя свойствами

1)

2)

Если  – отношение эквивалентности на множестве A, то семейство всех его смежных классов образуют разбиение множества A. Действительно, поскольку объединение всех смежных классов отношения  даст A. Покажем, что любые два смежные класса либо не пересекаются, либо совпадают. Если то Пусть Тогда Таким образом, Аналогично, Следовательно,

Обратно, если имеется разбиение множества A, то существует единственное отношение эквивалентности  на множестве A такое, что каждое из подмножеств разбиения является смежным классом эквивалентности . Отношение  можно определить следующим образом: x и y принадлежат одному и тому же подмножеству данного разбиения.

Задача 1.2.4. Подсчитайте число отношений а) эквивалентности; б) порядка на множестве .

а) Задать отношение эквивалентности на множестве C означает разбить его на подмножества. Множество C можно рассматривать как одно подмножество. Соответствующее отношение эквивалентности есть

Далее, множество C можно разбить на два подмножества из одного и из двух элементов. Это можно сделать тремя способами. Получим следующие три отношения эквивалентности

Наконец, C можно представить в виде объединения трех подмножеств, состоящих из одного элемента. Это будет отношение

Таким образом, на множестве C существют пять отношений эквивалентности.

б) Решите самостоятельно.

Ответы

1.2.1.б) 1.2.2.б) Рефлексивно , не симметрично, антисимметрично, не транзитивно. 1.2.3.б) в) 1.2.4.б) 21.