1. 等价关系定义
设 R 是非空集合 A 上的关系, 如果 R 是自反的、对称的、传递的，则称 R 为 A 上的等
价关系(equivalent relation).
以 n 为模的同余关系
设 n 为正整数，定义整数集合 Z 上的以 n 为模的同余关系 R = {< x, y > |n|(x − y)}, 证
明 R 是一个等价关系
1 自反性: 对任意 x ∈ Z, 有 n|(x − x), 所以 < x, x >∈ R，即 R 是自反的;
2 对称性: 对任意 x, y ∈ Z, 若 < x, y >∈ R, 则有 n|(x − y), 因为 (y − x) = −(x − y), 所以
n|(y − x), 从而 < y, x >∈ R, 即 R 是对称的;
3 传递性: 对任意 x, y, z ∈ Z，若 < x, y >∈ R 且 < y, z >∈ R，则有 n|(x − y) 且 n|(y − z)。因
为 (x − z) = (x − y) + (y − z), 所以 n|(x − z), 从而 < x, z >∈ R，即 R 是传递的.
由 (1),(2) 和 (3) 知，R 是 Z 上的等价关系。
等价类
设 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}.
设集合 A = {0, 1, 2, 4, 5, 8, 9}, 则
在 A 上定义的以 4 为模的同余关系 R 中,
A/R = {[0]R, [1]R, [2]R} = {{0, 4, 8}, {1, 5, 9}, {2}};
在 A 上定义的以 3 为模的同余关系 S 中,
A/S = {[0]S, [1]S, [2]S} = {{0, 9}, {1, 4}, {2, 5, 8}}.
2. 集合的划分
在等价关系中我们已经发现, 同一个等价类中的元素具有相同的属性，因而可将集合
中的元素分成不同的类别，对应于集合的划分。
等价关系-> 集合划分
设 R 是非空集合 A 上的等价关系，则 A 对 R 的商集 A/R 是 A 的一个划分，称为由 R 所导出的等价划分.
集合划分-> 等价关系
给定集合 A 的一个划分 π = {S1, S2, · · · , Sm}, 则由该划分确定的关系 R = (S1 × S1) ∪ (S2 × S2) ∪ · · · ∪ (Sm × Sm) 是 A 上的等价关系。我们称该关系 R 为由划分 π 所导出的等价关系。
3. 偏序关系定义
偏序关系
设 R 是非空集合 A 上的关系, 如果 R 是自反的、反对称的、传递的，则称 R 为 A 上
的偏序关系(partial order relation), 记为“⩽”. 读作“小于等于”, 并将“< a, b >∈⩽”记为
a ⩽ b. 序偶 < A, ⩽> 称为偏序集 (partial order set).
用“⩽”来表示偏序关系是由于“小于等于关系”是偏序关系的典型范例, 此时已不
局限于” 小于等于” 关系, 它指代的是在偏序关系中元素之间的先后顺序, 不局限
于通常的数的大小;
可比与覆盖
设 R 是非空集合 A 上的偏序关系,∀x, y ∈ A,
如果 x ⩽ y 或 y ⩽ x, 则称 x 与 y 可比;
如果 x ⩽ y 且不存在 z ∈ A 使得 x ⩽ z ⩽ y, 则称 y 覆盖 x.
4. 哈斯图及特殊元素
哈斯图
最大元和最小元
极大元和极小元
上界和上确界
下界和下确界
5. 其它次序关系
拟序关系
设 R 是非空集合 A 上的关系, 如果 R 是反自反的和传递的，则称 R 为 A 上的拟序关
系(quasi-order relation), 记为“< ”, 读作“小于 ”, 并将“< a, b >∈< ”记为 a < b. 序偶
< A, <> 称为拟序集 (quasi-order set).
全序关系
设 < A, ⩽> 是一个偏序关系, 若对任意 x, y ∈ A,x 与 y 都是可比的, 则称关系“⩽ ”为全序关
系(total order relation) 或线序关系. 称 < A, ⩽> 为全序集(total order set)，或线序集, 或链。
集合 A = {a, b, c} 上的关系“⩽ ”= {< a, a >, < b, b >, < c, c >,
< a, b >, < b, c >, < a, c >} 是全序关系;
数集上的小于等于关系是全序关系;
正整数集合上的整除关系不是全序关系, 但集合 A = {1, 2, 4, 8} 上的整除关系是全序关系;
幂集 P(A) 上的包含关系在 |A| < 2 时是全序关系; 但 |A| ⩾ 2 时则不是全序关系;
计算机科学中常用的字典排序关系是全序关系。
良序关系
设 < A, ⩽> 是全序集,若 A 的任何一个非空子集都有最小元素，则称“⩽ ”为良序关
系(well order relation), 此时 < A, ⩽> 称为良序集(well order set)。
