传递闭包 - 版本历史

Apocalypse：已还原Apocalypse（讨论）的编辑至最后由Tabelog修订的版本

2025-09-04T00:10:45Z

已还原Apocalypse（讨论）的编辑至最后由Tabelog修订的版本

←上一版本		2025年9月4日 (四) 08:10的版本
第1行：		第1行：
	== 集合的传递闭包 ==		=== 集合的传递闭包 ===

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

第8行：		第7行：
	* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。		* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。

	=== 定理 ===		==== 定理 ====

	* '''传递闭包唯一存在'''		* '''传递闭包唯一存在'''

第39行：		第37行：
	证毕。		证毕。

	== 关系的传递闭包 ==		=== 关系的传递闭包 ===

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

第46行：		第43行：
	* <math>\mathcal R_1\sube\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>。		* 如果 <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>。
			[[分类:集合论相关]]

Apocalypse：已还原Tabelog（讨论）的编辑至最后由QWQ-bili修订的版本

2025-09-04T00:09:57Z

已还原Tabelog（讨论）的编辑至最后由QWQ-bili修订的版本

←上一版本		2025年9月4日 (四) 08:09的版本
第1行：		第1行：
	=== 集合的传递闭包 ===		== 集合的传递闭包 ==

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

第7行：		第8行：
	* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。		* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。

	==== 定理 ====		=== 定理 ===

	* '''传递闭包唯一存在'''		* '''传递闭包唯一存在'''

第37行：		第39行：
	证毕。		证毕。

	=== 关系的传递闭包 ===		== 关系的传递闭包 ==

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

第43行：		第46行：
	* <math>\mathcal R_1\sube\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>。		* 如果 <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>。
	~~[[分类:集合论相关]]~~

2025年8月31日 (日) 03:06 Tabelog

2025-08-31T03:06:58Z

←上一版本		2025年8月31日 (日) 11:06的版本
第1行：		第1行：
	== 集合的传递闭包 ==		=== 集合的传递闭包 ===

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

第8行：		第7行：
	* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。		* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。

	=== 定理 ===		==== 定理 ====

	* '''传递闭包唯一存在'''		* '''传递闭包唯一存在'''

第39行：		第37行：
	证毕。		证毕。

	== 关系的传递闭包 ==		=== 关系的传递闭包 ===

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

第46行：		第43行：
	* <math>\mathcal R_1\sube\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>。		* 如果 <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>。
			[[分类:集合论相关]]

QWQ-bili：文字替换 -“序数#有限序数与超限序数”替换为“序数#有限序数”

2025-08-08T09:39:25Z

文字替换 -“序数#有限序数与超限序数”替换为“序数#有限序数”

←上一版本		2025年8月8日 (五) 17:39的版本
第14行：		第14行：
	证明		证明

	使用[[序数#~~有限序数与超限序数~~\|自然数]]集上的归纳法，定义集合列 <math>X_0,X_1,X_2,\cdots</math> 满足：		使用[[序数#有限序数\|自然数]]集上的归纳法，定义集合列 <math>X_0,X_1,X_2,\cdots</math> 满足：
	* <math>X_0=X</math>；		* <math>X_0=X</math>；
	* <math>X_{n+1}=X_n\cup(\bigcup X_n)</math>。		* <math>X_{n+1}=X_n\cup(\bigcup X_n)</math>。

Zhy137036：/* 关系的传递闭包 */

2025-08-07T03:42:06Z

关系的传递闭包

←上一版本		2025年8月7日 (四) 11:42的版本
第41行：		第41行：
	== 关系的传递闭包 ==		== 关系的传递闭包 ==

	设 <math>\mathcal R_1</math> 是集合 <math>A</math> 上的一个二元关系，如果 <math>A</math> ~~上的一个关系~~ <math>\mathcal R_2</math> 满足如下条件，就称为 <math>\mathcal R_1</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_2</math> 有传递性。
	* <math>\mathcal R_1\sube\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>。		* 如果 <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>。

2025年8月7日 (四) 03:40 Zhy137036

2025-08-07T03:40:11Z

←上一版本		2025年8月7日 (四) 11:40的版本
第1行：		第1行：
			== 集合的传递闭包 ==

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

第6行：		第8行：
	* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。		* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</math>。

	== 定理 ==		=== 定理 ===

	* '''传递闭包唯一存在'''		* '''传递闭包唯一存在'''
第36行：		第38行：

	证毕。		证毕。

			== 关系的传递闭包 ==

			设 <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>。

QWQ-bili：修改排版

2025-08-04T09:31:07Z

修改排版

←上一版本		2025年8月4日 (一) 17:31的版本
第1行：		第1行：
	'''定理'''~~（传递闭包唯一存在）~~		我们把满足这三个条件的唯一传递集合 <math>Y</math> 称作 <math>X</math> 的'''传递闭包（Transitive Closure）'''，记作 <math>\mathcal{TC}(X)</math>：

	对任意集合 <math>X</math>，存在唯一集合 <math>Y</math>，满足如下条件		对任意集合 <math>X</math>，存在唯一集合 <math>Y</math>，满足如下条件
第6行：		第6行：
	* 如果传递集 <math>Z</math> 满足 <math>X\sube Z</math>，则 <math>Y\sube Z</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_1,X_2,\cdots</math> 满足：
	* <math>X_0=X</math>；		* <math>X_0=X</math>；
	* <math>X_{n+1}=X_n\cup(\bigcup X_n)</math>。		* <math>X_{n+1}=X_n\cup(\bigcup X_n)</math>。
	这里的 <math>\bigcup X_n</math> 是'''广义并'''，定义为 <math>\{x\mid\exist y\in X_n,x\in y\}</math>。这个集合的存在性由[[ZFC公理体系\|并集公理]]保证。		这里的 <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=\bigcup\{X_n\mid x\in\N\}</math>，这里又用到了广义并。
第32行：		第36行：

	证毕。		证毕。

	~~我们把满足这三个条件的集合 <math>Y</math> 叫做 '''<math>X</math> 的传递闭包'''，记作 <math>\mathcal{TC}(X)</math>。~~

Zhy137036：创建页面，内容为“'''定理'''（传递闭包唯一存在）对任意集合 $X$ ，存在唯一集合 $Y$ ，满足如下条件 * $Y$ 是传递集； * $X\sube Y$ ； * 如果传递集 $Z$ 满足 $X\sube Z$ ，则 $Y\sube Z$ 。 '''证明''' 使用自然数集上的归纳法，定义集合列 $X_0,X_1,X_2,\cdots$ 满足： * $X_0=X$ ； * $X_{n+1}=X_n\cup(\bigcup X_n)$ …”

2025-08-04T08:32:15Z

创建页面，内容为“'''定理'''（传递闭包唯一存在）对任意集合 <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>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> 是'''广义并'''，定义为 <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>Y</math> 叫做 '''<math>X</math> 的传递闭包'''，记作 <math>\mathcal{TC}(X)</math>。

传递闭包 - 版本历史

Apocalypse：​已还原Apocalypse（讨论）的编辑至最后由Tabelog修订的版本

Apocalypse：​已还原Tabelog（讨论）的编辑至最后由QWQ-bili修订的版本