§ 8. Замыкание отношений

Понятие замыкания является фундаментальным ма­тематическим понятием и используется в большинстве разделов математики. Чтобы проиллюстрировать это по­нятие, рассмотрим следующий пример.

Возьмем объект x₀ и процесс p, который порождает множество и определяет последовательность х₁, x₂, ..., х_n, ... такую, что

x₁ р(x₀),

x₂ p(x₁),

. . . . .

x_n p(x_n-1),

. . . . .

Множество, содержащее все элементы всех последова­тельностей, которые могут быть выведены при помощи р, и начинающиеся с х₀, называется замыканием процес­са р относительно х₀. Поэтому «ответ» будет содержать­ся в рⁿ(х₀) при некотором п. Однако мы не знаем зара­нее значение п. Более того, если мы возьмем произволь­ный элемент y из этого замыкания и выполним процесс p, начиная с у, то не получим ничего нового. Результат уже содержится в замыкании. Множество не может быть расширено таким путем (оно замкнуто).

П ример 8.1. Возьмем квадрат S, размеченный, как это показано на рис. 2.13, и определим процесс r следу­ющим образом.

Рис. 2.13 Рис. 2.14

Из заданного положения S процесс r по­рождает множество всех положений, получаемых в ре­зультате поворота по часовой стрелке на прямой угол.

Таким образом, r(S) дает конфигурацию, изображенную на рис. 2.14. После применения r четыре раза, мы вер­немся к положению, с которого начали, и, следователь­но, замыкание в данном случае есть множество из че­тырех позиций.

. //

Рассмотрим теперь, что произойдет, если процесс определить при помощи отношения. (В действительности это всегда возможно, потому что мы можем определить подходящее отношение при помощи множества {(x, у): у р(x), где р — изучаемый процесс}.) Для построения замыкания отношения A достаточно иметь составные отношения A, А²,…, Аⁿ,…, которые затем комбинируются обычным теоретико-множественным путем.

Определение. Транзитивным замыканием (или просто замыканием) отношения A на множестве назы­вается бесконечное объединение

Транзитивность замыкания отношения следует, оче­видно, из его определения, однако слово «транзитивное» часто включают, чтобы подчеркнуть различие между этой и подобной ей операцией, которая вскоре будет оп­ределена. Транзитивное замыкание отношения A обозна­чают A⁺.

Пример 8.2.

1. Пусть R — отношение на N такое, что R = {(x, y): x < y}.

Тогда R⁺ = {(x, y): х<у}.

2. Пусть — отношение на Q такое, что = {(x, y): х < у}. Тогда ⁺= .

3. Пусть — отношение на Q такое, что {(x, y): х у = 1}. Тогда

⁺{(х, х): х ≠ 0) .

4. Пусть L — множество станций Лондонского метро и a, b и c — последовательные станции. Если отношение N на L определено как N = {(x, y): x является следую­щей за y станцией}, то (а, b) и (b, c) N и (a, a), (b, b), (c, c) и (a, c) N². Следовательно N⁺ = U_L = L x L. //

Из этих примеров легко видеть, что замыкание отно­шения в общем случае не является рефлексивным. Од­нако иногда удобно сделать его таким. Это можно легко сделать. Вначале мы примем удобное допущение, что тождественное отношение на X, I = {(х, х): х X} яв­ляется нулевой степенью произвольного отношения на X. Таким образом, A⁰ = I для любого A.

Определение. Рефлексивным замыканием A* отношения А называют множество

Замыкания отношений связаны между собой очевидным соотношением

//

Пример 8.3. Используя отношения, определенные в предыдущих примерах, получаем

R* = {(x, у): x<y}, * = {(x, y): x ≤ y},

* = ⁺ {(0, 0)}, N* = N⁺. //

Практические методы получения замыканий отноше­ний будут обсуждаться в гл. 6, 7.

Упражнение 2.7.

1. Используя отношения R и S упражнения 2.6, опи­сать замыкания следующих отношений:

а) R⁺; б) S⁺; в) R*; г) S*;

д) (S ° S^-1)⁺; e) (R^-1° R)*; ж) (S² ° R²)⁺.