Транзитивное замыкание — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(наброски статьи)
 
м
Строка 10: Строка 10:
  
 
* <math>R \subset R^+</math> по определению <math>R^+</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>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^+ \rightarrow 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>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>

Версия 05:40, 26 сентября 2010

Эта статья находится в разработке!

Транзитивным замыканием [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^+ \rightarrow 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]