304
правки
Изменения
наброски статьи
{{В разработке}}
'''Транзитивным замыканием''' <math>\mathrm{TrCl}(R)</math> отношения <math>R</math> на множестве <math>X</math> называется пересечение всех транзитивных отношений, содержащих <math>R</math> как подмножество (иначе, минимальное транзитивное отношение, содержащее <math>R</math> в качестве подмножества). Например, если <math>V</math> - множество городов, и на них задано отношение <math>R</math>, означающее, что если x R y, то "существует автобусный маршрут из x в y", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из x в y, передвигаясь на автобусах".
== Существование и описание ==
Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее <math>R</math> как подмножество (например, <math>X \times X</math>).
Докажем, что <math>R^+</math> является транзитивным замыканием отношения <math>R</math>.
:<math>R^+ = \bigcup\limits_{i \in \mathbb{N}} R^i</math>
* <math>R \subset R^+</math> по определению <math>R^+</math>
* <math>R^+</math> транзитивно. Пусть <math>a R^+ b</math> и <math>b R^+ c</math>. Это значит, что существуют i, j такие, что <math>a R^i b</math> и <math>b R^j c</math>. Но тогда <math>a R^{i+j} b</math>, и, так как <math>R^{i+j} \subset R^+ \leftarrow a R^+ b</math>
* <math>R^+</math> - минимальное отношение, удовлетворяющее представленным требованиям. Пусть <math>T</math> - транзитивное отношение, содержащее <math>R</math> в качестве подмножества. Покажем, что <math>R^+ \subset T</math>. <math>R \subset T \longleftrightarrow R^i \subset T</math> для любого натурального <math>i</math>
'''Транзитивным замыканием''' <math>\mathrm{TrCl}(R)</math> отношения <math>R</math> на множестве <math>X</math> называется пересечение всех транзитивных отношений, содержащих <math>R</math> как подмножество (иначе, минимальное транзитивное отношение, содержащее <math>R</math> в качестве подмножества). Например, если <math>V</math> - множество городов, и на них задано отношение <math>R</math>, означающее, что если x R y, то "существует автобусный маршрут из x в y", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из x в y, передвигаясь на автобусах".
== Существование и описание ==
Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее <math>R</math> как подмножество (например, <math>X \times X</math>).
Докажем, что <math>R^+</math> является транзитивным замыканием отношения <math>R</math>.
:<math>R^+ = \bigcup\limits_{i \in \mathbb{N}} R^i</math>
* <math>R \subset R^+</math> по определению <math>R^+</math>
* <math>R^+</math> транзитивно. Пусть <math>a R^+ b</math> и <math>b R^+ c</math>. Это значит, что существуют i, j такие, что <math>a R^i b</math> и <math>b R^j c</math>. Но тогда <math>a R^{i+j} b</math>, и, так как <math>R^{i+j} \subset R^+ \leftarrow a R^+ b</math>
* <math>R^+</math> - минимальное отношение, удовлетворяющее представленным требованиям. Пусть <math>T</math> - транзитивное отношение, содержащее <math>R</math> в качестве подмножества. Покажем, что <math>R^+ \subset T</math>. <math>R \subset T \longleftrightarrow R^i \subset T</math> для любого натурального <math>i</math>
