集合论中, 传递集合指的是满足 “元素的元素都是元素” 的集合, 即属于关系具有某种传递性.
目录1定义2例子3性质传递闭包4传递模型5相关概念1定义定义 1.1 (传递集合). 称集合 a 为传递, 指的是∀x∀y((x∈a∧y∈x)→y∈a).
注意这和集合 a 上的二元关系 ∈ 的传递性是两个概念.
对类也有一样的概念.
定义 1.2 (传递类). 称类 A 为传递, 指的是∀x∀y((x∈A∧y∈x)→y∈A).
2例子•
依定义, 序数都是传递集合.
•
每个 von Neumann 层级与 Gödel 可构造层级也都是传递集合.
•
还可随手写出其它具体例子, 比如{{},{{}},{{{}}}}.
3性质下面是传递性的几个显然等价的描述.
命题 3.1. 集合 a 传递当且仅当其每个元素都是其子集, 等价于 ∪a⊆a, 也等价于 a⊆P(a). 这里 ∪a 的意思和并公理中一样, 表示 a 的所有元素的并; P(a) 表示 a 的幂集.
以下是从传递集产生新的传递集的方法.
命题 3.2.
•
如 a 为传递, 则 ∪a 亦然.
•
如 a 的每个元素都为传递, 则 ∪a 与 a∪∪a 都是传递集合.
•
传递集合的任意交仍为传递集合.
证明.
•
如 a 为传递, 则 ∪a⊆a, 从而 ∪∪a⊆∪a, 于是 ∪a 亦为传递.
•
如 a 的每个元素都为传递, 考虑任一 x∈∪a. 设 b∈a 满足 x∈b, 则由 b 传递便知 x⊆b⊆∪a, 所以 ∪a 传递. 再考虑任一 y∈a∪∪a. 如 y∈∪a, 同上; 如 y∈a, 也有 y⊆∪a; 不论如何, y⊆∪a⊆a∪∪a, 所以 a∪∪a 传递.
•
考察交集的一个元素. 它属于这些传递集合中每一个, 从而由传递性它也包含于这些传递集合中每一个, 从而包含于交集. 故交集传递.
□
传递闭包集合 a 的传递闭包是包含 a 的最小传递集. 由命题 3.2, 只要存在包含 a 的传递集, 全取交就会得到最小的. 下面的命题显式描述了传递闭包, 自然也证明了存在性.
命题 3.3. 集合 a 的传递闭包为tr.cl(a)=∪{a,∪a,∪∪a,…},可用并公理、替换公理模式、无穷公理作出.
证明. 先来作命题中的集合. 首先用无穷公理取出自然数集 N. 再用替换公理模式, 将自然数 n 替换为 ∪na, 即 a 做 n 次并集操作, 可得集合{a,∪a,∪∪a,…}.更严格地说, 就是把替换公理模式中的公式 Q(x,y,w) 取为∃f(Fun(f)∧f(0)=a∧∀v(f(v∪{v})=∪f(v))∧f(x)=y),集合 w 取为 N; 这里 Fun(f) 指的是 f 是个映射, 后面的 f(0),f(v) 是映射代值的简写. 这样再用并公理即可作出 tr.cl(a).
再来证明它就是传递闭包. 首先它传递: 如 x∈tr.cl(a), 设 n∈N 满足 x∈∪na, 则有 x⊆∪n+1(a)⊆tr.cl(a). 其次它显然包含 a. 最后, 如传递集合 t 满足 a⊆t, 则利用 ∪t⊆t 容易归纳证明对任意 n∈N 都有 ∪na⊆t, 于是 tr.cl(a)⊆t. 所以这样作出的 tr.cl(a) 就是 a 的传递闭包. □
4传递模型5相关概念•
序数
•
传递关系
•
Mostowski 收缩
术语翻译
传递集合 • 英文 transitive set • 德文 transitive Menge • 法文 ensemble transitif • 拉丁文 copia transitiva
传递闭包 • 英文 transitive closure • 德文 transitive Hülle • 法文 clôture transitive • 拉丁文 clausura transitiva