集合和二元关系
例题
已知： A = {1,2,3,4}，A上的关系 R = {⟨1,3⟩, ⟨1,4⟩, ⟨2,3⟩, ⟨2,4⟩, ⟨3,4⟩}
求：(1) 画出R的关系图；(2) 写出R的关系矩阵；(3) 求domR, ranR；(4) 求R⁻¹；(5) 求R∘R；(6) 说明R的性质。
(2) 关系矩阵：
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 1 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 |
(3)
- domR = {1, 2, 3}
- ranR = {3, 4}
(4)
R⁻¹ = {⟨3,1⟩, ⟨4,1⟩, ⟨3,2⟩, ⟨4,2⟩, ⟨4,3⟩}
(5)
R∘R = R² = {⟨1,4⟩, ⟨2,4⟩}
(6) R的性质：
- ∵ ⟨1,1⟩ ∉ R，∴ R不是自反的 ✓
- ∵ ∀x ∈ A，⟨x,x⟩ ∉ R，∴ R是反自反的 ✓
- ∵ ⟨1,3⟩ ∈ R，但 ⟨3,1⟩ ∉ R，∴ R不是对称的
- ∴ R是反对称的 ✓
- ∴ R是传递的 ✓
二元关系概念
关系的定义
定义： 如果一个集合满足以下条件之一：
- 集合非空，且它的元素都是有序对
- 集合是空集
则称该集合为一个二元关系，简称为关系。
1、A 与 B 的笛卡尔积：
A × B = { (x,y) | x ∈ A ∧ y ∈ B }
2、A 到 B 的关系： A × B 的所有子集都是从 A 到 B 的关系。
A 上的关系： A × A 的子集都是 A 上的关系。
A 上的特殊关系： 空关系（∅）、全域关系（E_A）、恒等关系（I_A）。
例：
A = {1, 2}，B = {a, b}
A × B = { ⟨1,a⟩, ⟨1,b⟩, ⟨2,a⟩, ⟨2,b⟩ }
A × B ⊇ R = { ⟨1,a⟩, ⟨1,b⟩ }，R 是 A 到 B 上的关系。
若 |A| = m，|B| = n，则 |A × B| = mn
全域关系：
E_A = { ⟨1,1⟩, ⟨1,2⟩, ⟨2,1⟩, ⟨2,2⟩ }
恒等关系：
I_A = { ⟨1,1⟩, ⟨2,2⟩ }
例：画偏序集(A,R)的哈斯图，找出A的极大元、极小元、最大元和最小元
已知：
A = {a, b, c, d, e, f}
R = { ⟨a,d⟩, ⟨a,c⟩, ⟨a,b⟩, ⟨a,e⟩, ⟨b,e⟩, ⟨c,e⟩, ⟨d,e⟩ } ∪ I_A
(1) 哈斯图：
e f
/|\
b c d
\|/
a(2) 结果：
- 极大元：e、f
- 极小元：a、f
- 无最大元和最小元
例：（第二图）
(1) 哈斯图：
g
/ \
e f
\ /
d
|
c
/ \
a b(2) 结果：
- 极大元：g
- 极小元：a、b
- 最大元：g
- 无最小元
群
群： 非空集合 G 与一个二元运算 *，使得 (G, *) 满足以下四个条件：
- 封闭性：∀a, b ∈ G，a * b ∈ G
- 结合律：∀a, b, c ∈ G，(a * b) * c = a * (b * c)
- 单位元：∃e ∈ G，∀a ∈ G，e * a = a * e = a
- 逆元：∀a ∈ G，∃b ∈ G，a * b = b * a = e
例1：Klein 四元群
(S, ∗) 是群，其中 S = {a,b,c,d}，"∗" 为S上的二元运算，运算表如下：
| ∗ | a | b | c | d |
|---|---|---|---|---|
| a | a | b | c | d |
| b | b | a | d | c |
| c | c | d | a | b |
| d | d | c | b | a |
此代数系统称为 Klein 四元群，因为它满足群的四个条件：
① "∗" 是S上的闭运算
观察运算表，所有运算结果均在 S = {a,b,c,d} 中，∴ 满足封闭性。
② "∗" 适合结合律
可逐一验证，例如：
- (a∗b)∗c = b∗c = d，a∗(b∗c) = a∗d = d ✓
- (b∗c)∗d = d∗d = a，b∗(c∗d) = b∗b = a ✓
所有情况均满足结合律，∴ 成立。
③ 存在幺元 e ∈ S
观察运算表第一行和第一列：
- a∗x = x∗a = x 对所有 x ∈ S 成立
∴ a 是幺元，即 e = a。
④ 每个元素存在逆元
对于S中任意元素 x，存在 x⁻¹ ∈ S，使得 x∗x⁻¹ = x⁻¹∗x = e = a：
| 元素 | 逆元 | 验证 |
|---|---|---|
| a | a | a∗a = a = e ✓ |
| b | b | b∗b = a = e ✓ |
| c | c | c∗c = a = e ✓ |
| d | d | d∗d = a = e ✓ |
每个元素的逆元都是其自身，∴ 满足逆元条件。
结论： (S, ∗) 满足群的全部四个条件，故 (S, ∗) 是群，称为 Klein 四元群。
此外，由于运算表关于主对角线对称，即 x∗y = y∗x 对所有 x,y ∈ S 成立，故 Klein 四元群还是交换群（Abel群）。
例2
设 A 为非空有限集合，P(A) 为 A 的幂集，∩ 为集合的交运算，则群 ⟨P(A), ∩⟩ 的单位元是____，零元是____。
解：
P(A) 是 A 的所有子集构成的集合，∩ 是交运算。
单位元：
单位元 e 满足：对任意 X ∈ P(A)，有 X ∩ e = e ∩ X = X
因为 X ∩ A = A ∩ X = X 对所有 X ∈ P(A) 成立
∴ 单位元是 A
零元：
零元 θ 满足：对任意 X ∈ P(A)，有 X ∩ θ = θ ∩ X = θ
因为 X ∩ ∅ = ∅ ∩ X = ∅ 对所有 X ∈ P(A) 成立
∴ 零元是 ∅