Question

离散数学(等价关系)

Answer 1

设 R 是非空集合 A 上的关系, 如果 R 是自反的、对称的、传递的，则称 R 为 A 上的等
价关系(equivalent relation).

设 n 为正整数，定义整数集合 Z 上的以 n 为模的同余关系 R = {< x, y > |n|(x − y)}, 证
明 R 是一个等价关系

设 R 是非空集合 A 上的等价关系，对任意 x ∈ A，称集合 [x]R = {y|y ∈ A, < x, y >∈ R}为 x 关于 R 的等价类(equivalence class)，或叫作由 x 生成的一个 R 等价类，其中 x 称为 [x]R 的生成元(代表元或典型元)(generator).

设 R 是非空集合 A 上的等价关系，由 R 确定的一切等价类的集合，称为集合 A 上关于R 的商集(quotient set)，记为A/R，即 A/R = {[x]R|x ∈ A}.

在等价关系中我们已经发现, 同一个等价类中的元素具有相同的属性，因而可将集合
中的元素分成不同的类别，对应于集合的划分。

设 R 是非空集合 A 上的等价关系，则 A 对 R 的商集 A/R 是 A 的一个划分，称为由 R 所导出的等价划分.

给定集合 A 的一个划分 π = {S1, S2, · · · , Sm}, 则由该划分确定的关系 R = (S1 × S1) ∪ (S2 × S2) ∪ · · · ∪ (Sm × Sm) 是 A 上的等价关系。我们称该关系 R 为由划分 π 所导出的等价关系。

设 R 是非空集合 A 上的关系, 如果 R 是自反的、反对称的、传递的，则称 R 为 A 上
的偏序关系(partial order relation), 记为“⩽”. 读作“小于等于”, 并将“< a, b >∈⩽”记为
a ⩽ b. 序偶 < A, ⩽> 称为偏序集 (partial order set).