Пример 7.1. Пусть о и р— отношения на N такие, что
о=={(х, а-+1): дет, р={[х2, х): хе=Ю. Тогда
Пример 7.1. Пусть о и р— отношения на N такие, что
о=={(х, а-+1): дет, р={[х2, х): хе=Ю. Тогда
3), = {х2: х е N}, 3), == {х: х, х + 1 е N} = N,
0)^ = о-13)о ="
- {х: х е N и х + 1 = у2, где у <= N} = {3, 8, 15, 24, ...}
(рис. 2.12). II
В случае, когда мы рассматриваем отношение па множестве, оно может быть скомбинировано само с
собой. Например, используя отношения из примера 7.1, имеем
о ° a =•= {(а;, а: + 2): а; е N) и р°р={ (а-4, д;): х <=• N}.
Эти отношения можно также обозначать соответственно о2 и р2. В общем-то эти обозначения не совсем законны для множеств, однако их легко можно обосновать, поскольку если (х, у)ео°а, то ((х, у))еоХа при некотором z; никакого недоразумения при этом не возникает, поскольку известна структура получаемого результата. z), (z,
Используя это обозначение, мы можем определить о" для любого п<=Ц, п> 1, следующим образом:
о"=.{(х, у): xoz и zon~\y для некоторого z}.
Еслп мы вновь возьмем отношения о и р из примера 7.1,
то получим
0"={(х, х+п), xeW и р" = {(.с2", д-): a:eN}. Хотелось бы рассмотреть вопрос о том, насколько в этих
Определение. Транзитивным замыканием (идя просто замыканием.) отношения А на множестве называется бесконечное объединение
Транзитивность замыкания отношения следует, очевидно, из его определения, однако слово “транзитивное” часто включают, чтобы подчеркнуть различие между этой и подобной ей операцией, которая вскоре будет определена. Транзитивное замыкание отношения А обозначают А*.
Пример 8.2.
1. Пусть Л — отношение на N такое, что R "
•=К"с, У)'- У-ж-И}. Тогда ^“"{(д, у): х<у}.
2. Пусть о — отношение на Q такое, что о =• “= {(х, у}: х< у}. Тогда о* •= о.
3. Пусть р — отношение на Q такое, что р "•
•= {(“с, у): х • у =” I). Тогда
р*{(х, х): a-^0}Up.
4. Пусть L — множество станций Лондонского метро ид, Ь и с — последовательные станции. Если отношение N Ей L определено как Nя•{(x, у): а; является следующей аа у станцией), то (д, Ь) в (b, с}е N и (в, в), (Ь, Ь), (с, с) и (в, с)^^. Следовательно Л'4'-”^,— ^LXL./ •:
Из этих примеров легко видеть, что замыкание отношения в общем случае не является рефлексивным. Однако иногда удобно сделать его таким. Это можно легко сделать. Вначале мы примем удобное допущение, что тождественное отношение на X, I " {(х, х): же X} является нулевой степенью произвольного отношения на X. Таким образом, А° •°= I для любого А.
Определение. Рефлексивным замыканием А* отношения А называют множество
А* - 5 Л".
п~0
Замыкания отношений связаны между собой очевидным соотношением
'А*"А^\!1. /
Пример 8.3. Используя отношения, определенные в предыдущих примерах, получаем
R*={(x, у): х^у), o*-{(z, у): х^у}, р-^р^ ((О, О)}, N*^N\'/
^Практические методы получения замыканий отношений будут обсуждаться в гл. 6, 7.
Упражнение 2.7.
1. Используя отношения R и S упражнения 2.6, описать замыкания следующих отношений-
а) Л^ б) ^; в) Д*; г) S*;
Д). {S'S-1^;^ (Л-'“Д)*;ж) (^.Д2)^