Однородные бинарные отношения.

Определение 1.

называется однородным бинарным отношением на множестве А.

Определение 2.

Отношение называется:

1) рефлексивным, если ;

2) транзитивным, если

Пример.

1. Отношение делимости на множестве целый чисел Z.

(отношение рефлексивно и транзитивно, не симметрично)

2. Отношение «быть знакомым» на множестве людей.

(отношение рефлексивно, но не транзитивно, симметрично, не антисимметрично)

Определение 3.

1. Отношение называется симметричным, если.

2. Отношение называется антисимметричным, если

.

Замечание.

Существуют отношения, которые антисимметричны и симметричны одновременно, например, отношение равенства.

Существуют отношения, которые ни симметричны, ни антисимметричны.

Пример.

Отношение «быть братом» на множестве людей человекy является братом человека x.

Теорема 1.

Пусть множество А кончено и состоит из n элементов, тогда на А существует ровно:

1) различных однородных бинарных отношений;

2) различных рефлексивных отношений;

3) различных симметричных отношений;

4) различных рефлексивных и симметричных одновременно отношений.



1) Следует из теоремы о числе n-арных отношений;

Зададим отношения матрицами из 0 и 1

2)

На диагонали R все 1. Остальных элементов (могут быть и 0 и 1).

3) Симметричные матрица симметрична

!!! степеньвсегда целое число, т. к.

4) Матрица симметрична, но на диагонали одни единицы



Теорема 2.

Пусть – отношение равенства на А (), тогдаявляется рефлексивным.

Определение 4.

Пусть . Транзитивным замыканием отношенияназывается отношение

Пример.

Лекция № 4. Однородные бинарные отношения.

Лемма 1.

Отношение транзитивно на множестве А .



Теорема 1.

Пусть , тогда:

1. транзитивно;

2. транзитивно



1. Покажем, что .

Пусть

Таким образом . Согласно лемме 1транзитивно.

Пусть транзитивно

Всегда .

Пусть .

Замечание.

может быть неверным даже для транзитивного отношения.

Пример.

Отношение эквивалентности.

Определение 1.

Отношение называется эквивалентностью на множестве А, если оно рефлексивно, симметрично и транзитивно.

Определение 2.

Пусть – эквивалентность на А,.

–класс эквивалентности, содержащий элемент :

Определение 3.

Множество всех классов эквивалентности называется фактор-множеством множества А по эквивалентности и обозначается.

Пример.

Т. о. различных классов эквивалентности всего два: множество всех чётных и нечётных чисел.

Теорема 1.

Пусть – эквивалентность на А,, тогда классы эквивалентностилибоØ.

Имеем две возможности:

1.

2.

1) Пусть , тогда

Известно

2) Пусть , тогда

Получили противоречие с .

Определение 4.

Система подмножеств множества А называется разбиением множества А, если:

1. 

2. 

Следствие.

Классы эквивалентности образуют разбиение.

Замечание.

Эквивалентность на множестве А существует тогда и только тогда, когда существует разбиение множества А на классы эквивалентности.

Разбиение множества А на подмножества порождает эквивалентностьна множестве А.

входят в одно подмножество разбиения.