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

Пусть на множестве А задано два отношения R и S. Определим отношение Q как результат операции транзитивного продолжения отношений R на S, если (a_i ,a_k ) Э Q тогда и только тогда, когда (a_i , a_j ) Э R и ( aj ,ak) Э S. Обозначим это Q=R°S. Если R = S, то обозначим S° S=S2 и по аналогии введем
k-ю степень транзитивного продолжения как последовательное выполнение (k+1) раз операции°. Обозначим S как S1.

Пример. Пусть на множестве всех людей задано бинарное отношение R «быть отцом». Тогда R2 будет соответствовать бинарное отношение «быть отцом отца» или, что то же самое, «быть дедом по отцу».

Транзитивным замыканием (или просто замыканием) отношения K называется бесконечное объединение Rⁱ . Обозначим замыкание как R*, т.е. R*=R u R² u ... u R^k.

Пример. Пусть на множестве целых чисел N задано отношение R={(x,y)|y=x+1}. Тогда замыканием R* будет отношение {(x,y) | x < y}.