第3讲 集合间的关系

关系 • 定义 ○ 对于任意集合 A，定义 A 上的一个关系为 A×A 的子集 R • 记号 ○ A×A={(x,y)|x,y∈A} ○ 若 (x,y)∈R, 我们可以写作 xRy • 例1 ○ A={全世界的人} ○ A×A={(甲,乙)|甲,乙∈A} ○ 定义 R={(甲,乙)∈A×A|甲是乙的父亲} ○ 其中 R 为父子关系 • 例2 ○ 对于任意集合 A，定义对角线 Δ={(x,x)|x∈A}⊆A×A ○ Δ 定义了 A 上元素的相等关系 ○ xΔy⇔x=y 偏序关系 • 定义：A 上的一个偏序关系 R 是符合以下三个条件的关系 a. 自反性：∀x∈A, xRx b. 反对称性：如果 xRy 且 yRx，那么 x=y c. 传递性：如果 xRy 且 yRz，那么 xRz • 例子 ○ 对于实数集 R：≤ ○ 对于任意集合 A：= 等价关系 • 定义：A 上的一个等价关系 R 是符合以下三个条件的关系 a. 自反性：∀x∈A, xRx b. 对称性：如果 xRy 那么 yRx c. 传递性：如果 xRy 且 yRz，那么 xRz • 思考题：是否能通过 b, c 推出 a ○ 不能，自反性要求对任意 x∈A 都成立 ○ 无法保证对任意 x∈A 都存在 y 使得 xRy • 一般会用 ~ 来表示等价关系 等价类 • 定义 ○ 令 A 为任意集合，~ 为 A 上的等价关系 ○ 对于 a∈A ，定义 a 的等价类为 ○ [a]={b∈A|a~b} • 定理 1：如果[a]∩[b]≠∅，那么 [a]=[b] ○ 首先证明 [a]⊆[b] ○ 让 c∈[a]∩[b]， ○ 对于所有 x∈[a], a~x ○ 根据传递性有 c_x⇒bx，即 x∈[b] ○ 所以 [a]⊆[b]，同理可得 [b]⊆[a] ○ 即 [a]=[b] • 定理 ○ ∀a∈A, a∈[a]⇒a∈⋃8_(a∈A)▒[a] ⇒A⊆⋃8_(a∈A)▒[a] ○ [a]⊆A⇒⋃8_(a∈A)▒[a] ⊆A ○ 故 A=⋃8_(a∈A)▒[a] ○ 又由定理1得 [a] 之间互不相交 ○ 注：我们将这一过程称为等价类分割 商集 • 定义 ○ 令 A 为任意集合，~ 为 A 上的等价关系 ○ 定义 {[a]|a∈A } 为 A 除以 ~ 的商集 ○ 记作 A\~ • 例1 ○ 对于任意集合 A 和等价关系 = ○ A\\ ={[a]|a∈A }={{a}|a∈{A}} • 例2 ○ 令 A={所有人} ○ 定义等价关系 ~ 为性别相同 ○ 则 A\~ ={{所有男人},{所有女人}} • 例3 ○ 令 A=Z ○ 定义 m,n∈Z 等价当且仅当 m≡n mod a ○ 则 A\~ ={0,1,…,a−1} A Δ A