304
правки
Изменения
Нет описания правки
* <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^1 = R \subset R^+</math>, как было показано выше. Пусть верно для любого <math>i \le k</math>. Пусть <math>a R^{k+1} c</math>. Но тогда существует <math>b: aR^kb</math> и <math>bRc</math>, но <math>R \subset T, R^k \subset T</math>, следовательно <math>aTb, bTc</math>. Из транзитивности <math>T</math> следует, что <math>aTc</math>, следовательно <math>R^{k+1} \subset T</math>, что и требовалось доказать
== Построение транзитивного замыкания ==
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <math>R</math> --- это такое отношение <math>T</math>, что <math>aTb</math> тогда и только тогда, когда существуют <math>x_1, x_2, ..., x_n</math> такие, что <math>aRx_1</math>, <math>x_1Rx_2</math>, <math>x2_Rx_3</math>, ..., <math>x_{n-1}Rx_n</math>, <math>x_nRb</math>, то есть существует путь из вершины <math>a</math> в вершину <math>b</math> на графе отношения.
