传递闭包

集合的传递闭包

我们把满足这三个条件的唯一传递集合 $Y$ 称作 $X$ 的传递闭包（Transitive Closure），记作 ${𝒯}{𝒞}(X)$：

对任意集合 $X$，存在唯一集合 $Y$，满足如下条件

• $Y$ 是传递集；
• $X\subseteq Y$；
• 如果传递集 $Z$ 满足 $X\subseteq Z$，则 $Y\subseteq Z$。

定理

• 传递闭包唯一存在

证明

使用自然数集上的归纳法，定义集合列 $X_0,X_1,X_2,\cdots$ 满足：

• $X_0=X$；
• $X_{n+1}=X_n\cup (\bigcup X_n)$。

这里的 $\bigcup X_n$ 是广义并，定义为 $\{x\mid \mathrm{\exists }y\in X_n,x\in y\}$。这个集合的存在性由并集公理保证。

令 $Y=\bigcup \{X_n\mid x\in \mathbb{\mathbb{N}}\}$，这里又用到了广义并。

下面证明，这样构造出的 $Y$ 满足定理要求。

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

显然 $X=X_0\subseteq Y$。

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

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

因为 $X_0\subseteq Z$，且若 $X_n\subseteq Z$ 则 $X_{n+1}\subseteq Z$，所以对任意 $n\in \mathbb{\mathbb{N}}$ 都有 $X_n\subseteq Z$。所以 $Y\subseteq Z$。

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

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

证毕。

关系的传递闭包

设 ${{ℛ}}_1$ 是集合 $A$ 上的一个二元关系，如果 $A$ 上的一个二元关系 ${{ℛ}}_2$ 满足如下条件，就称为 ${{ℛ}}_1$ 的传递闭包。

• ${{ℛ}}_2$ 有传递性。
• ${{ℛ}}_1\subseteq {{ℛ}}_2$。
• 如果 $A$ 上的一个二元传递关系 ${{ℛ}}_3$ 满足 ${{ℛ}}_1\subseteq {{ℛ}}_3$，则 ${{ℛ}}_2\subseteq {{ℛ}}_3$。