查看“︁传递闭包”︁的源代码

=== 集合的传递闭包 ===
我们把满足这三个条件的唯一传递集合 <math>Y</math> 称作 <math>X</math> 的'''传递闭包（Transitive Closure）'''，记作 <math>\mathcal{TC}(X)</math>：

对任意集合 <math>X</math>，存在唯一集合 <math>Y</math>，满足如下条件
* <math>Y</math> 是[[传递集]]；
* <math>X\sube Y</math>；
* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。

==== 定理 ====
* '''传递闭包唯一存在'''

证明

使用[[序数#有限序数|自然数]]集上的归纳法，定义集合列 <math>X_0,X_1,X_2,\cdots</math> 满足：
* <math>X_0=X</math>；
* <math>X_{n+1}=X_n\cup(\bigcup X_n)</math>。
这里的 <math>\bigcup X_n</math> 是'''<span id="广义并">广义并</span>'''，定义为 <math>\{x\mid\exist y\in X_n,x\in y\}</math>。这个集合的存在性由[[ZFC公理体系#并集公理|并集公理]]保证。

令 <math>Y=\bigcup\{X_n\mid x\in\N\}</math>，这里又用到了广义并。

下面证明，这样构造出的 <math>Y</math> 满足定理要求。

对任意的 <math>y\in Y</math> 和 <math>x\in y</math>，设 <math>y\in X_n</math>，则 <math>x\in\bigcup X_n\sube X_{n+1}</math>，即 <math>x\in X_{n+1}</math>，所以 <math>x\in Y</math>。所以 <math>Y</math> 是传递集。

显然 <math>X=X_0\sube Y</math>。

设传递集 <math>Z</math> 满足 <math>X\sube Z</math>，即 <math>X_0\sube Z</math>。我们证明：对任意 <math>n\in\N</math>，若 <math>X_n\sube Z</math>，则 <math>X_{n+1}\sube Z</math>。

假设 <math>X_n\sube Z</math>。对任意的 <math>y\in X_n</math> 和 <math>x\in y</math>，有 <math>y\in Z</math>。因为 <math>Z</math> 是传递集，所以 <math>x\in Z</math>。这说明 <math>\bigcup X_n\sube Z</math>。又因为 <math>X_n\sube Z</math>，所以 <math>X_{n+1}=X_n\cup(\bigcup X_n)\sube Z</math>。

因为 <math>X_0\sube Z</math>，且若 <math>X_n\sube Z</math> 则 <math>X_{n+1}\sube Z</math>，所以对任意 <math>n\in\N</math> 都有 <math>X_n\sube Z</math>。所以 <math>Y\sube Z</math>。

这就证明了定理中的存在性。下面证明唯一性。

若 <math>Y_1,Y_2</math> 都满足以上三个条件，那么根据第三个条件，有 <math>Y_1\sube Y_2</math> 且 <math>Y_2\sube Y_1</math>，即 <math>Y_1=Y_2</math>。所以满足以上三个条件的集合唯一。

证毕。

=== 关系的传递闭包 ===
设 <math>\mathcal R_1</math> 是集合 <math>A</math> 上的一个二元关系，如果 <math>A</math> 上的一个二元关系 <math>\mathcal R_2</math> 满足如下条件，就称为 <math>\mathcal R_1</math> 的'''传递闭包'''。

* <math>\mathcal R_2</math> 有传递性。
* <math>\mathcal R_1\sube\mathcal R_2</math>。
* 如果 <math>A</math> 上的一个二元传递关系 <math>\mathcal R_3</math> 满足 <math>\mathcal R_1\sube\mathcal R_3</math>，则 <math>\mathcal R_2\sube\mathcal R_3</math>。
[[分类:集合论相关]]