Алгебра отношений.

Пусть заданы отношения R Í M x M и S Í M x M.

1. R È S = { (x, y): x, y Î M & ( (x, y) Î R v (x, y) Î S ) }

x (R È S) y => xRy v xSy

2. R Ç S = { (x, y): x, y Î M & ( (x, y) Î R & (x, y) Î S ) }

x (R Ç S) y => xRy & xSy

3. Обратное отношение: R^-1 = { (y, x): x, y Î M & (x, y) Î R }

4. R · S = { (x, y): x, y Î M & $z Î M [ xRz & zSy ] }

5. Транзитивное замыкание:

6. Рефлексивное замыкание:
17. Свойства отношений. Эквивалентность и классы эквивалентности по заданному отношению.

Свойства порождаются выполнением неких абстрактных ограничений. © Красюк. Это справедливо не только для данного билета. ;)

1. Рефлексивность. "x Î M [ (x, x) Î R ]

2. Антирефлексивность. не$x Î M [ (x, x)ÎR ]

3. Симметричность. "x, y Î M [ (x, y) Î R => (y, x) Î R ]

4. Антисимметрич-ть. "x, y Î M [ (x, y) Î R & (y, x) Î R => x = y ]

5. Иррефлексивность. $x Î M [ (x, x) Î R ] & $y Î M [(y, y) Ï R ]

6. Транзитивность. "x, y, z Î M [ (x, y) Î R & (y, z) Î R => (x, z) Î R ]

– транзитивное замыкание б.о. R.

– рефлексивное замыкание б.о. R.

Ахтунг! Различие асимметричности и антисимметричности:

R Ç R^-1 = Æ для асимметричного R

R Ç R^-1 = I_M для антисимметричного R

Бинарное отношение называется отношением эквивалентности на множестве X, если оно рефлексивно, симметрично и транзитивно.

Далее символом X обозначается множество, на котором задано отношение эквивалентности R.

Каждое подмножество A из X называется классом эквивалентности, если:

1) оно состоит из эквивалентных друг другу элементов и

2) если эквивалентен хотя бы одному элементу из , то .

(Пример: x, yÎN (x=y)_{mod 7}. d₁: (x)_{mod 7}=0. X₁={0,7,14,...}. d₂: (x)_{mod 7}=1. X₂={1,8,15,...}. X₁ и X₂ – классы эквивалентности, т.к. отношение (x=y)_{mod 7} явл. отношением эквивалентности.)

Система классов эквивалентности (например, система множеств X₁,X₂,... из предыдущего примера) называется фактор-множеством.

Теорема. Два класса эквивалентности либо совпадают, либо не пересекаются.

Доказательство. Пусть A и B – два класса эквивалентности из X. Допустим, что они пересекаются и c – общий элемент, то есть . Если x – произвольный элемент из A, то x~c. Поскольку , то и . Таким образом, . Аналогично доказывается, что . Итак, A = B. Теорема доказана.