集合 A 上的一个 n 元关系 是一个子集 R⊆An . 我们用R(a1,⋯,an) 来表示 (a1,⋯,an)∈R .
最常见的关系是二元关系. 对于二元关系, 我们习惯上会把 R(a,b) 写成 aRb. 类似, 对于一元关系, 通常把 R(a) 写成 Ra.
例1. =,<,≤这些都是二元关系.
一般情况下, R⊆A1×⋯×An也是 n 元关系.
A 上的二元关系 ∼ 叫做等价关系, 如果它满足以下性质:
(1). 自反性: 对任何 a∈A , 有 a∼a ;
(2). 对称性: 若 a∼b , 则 b∼a ;
(3). 传递性: 若 a∼b,b∼c, 则 a∼c .
例2. =是等价关系.
例3. 三角形的全等和相似都是等价关系.
例4. 矩阵的相抵, 相似, 合同均为等价关系.
有未定向的超链接.
假设在 A 上有一个二元关系 ∼ , 那么一个 a∈A 的等价类是一个集合
[a]:={b∈A∣b∼a}.
我们下面来证明等价类构成了 A 的一个划分.
命题1. 若 [a]∩[b]=∅ , 则 [a]=[b].
证. 设 c∈[a]∩[b] , 于是 c∼a,c∼b . 由传递性和对称性, a∼b . 所以对于任一 x∈[a] , 有 x∼a , 于是 x∼b , 故 x∈[b]. 因此 [a]⊆[b] , 反之亦然, 于是 [a]=[b] .
因此, 我们把 S 的所有等价类取出, 它们两两不交, 并且包含了 S 中的所有元素(可以取自身的等价类). 所有等价类的集合叫做 S 在 ∼ 下的商集, 记作 S/∼. 而每一等价类都可以取定一个元素, 这个元素叫做它的一个代表元, 由命题证明可知一个元素属于某一等价类当且仅当它与这个等价类的代表元等价.
有限集合上可以定义的不同等价关系个数叫做Bell数, n 元集上的等价关系个数记为 Bn.
事实上, 我们发现如下的命题:
命题2. 等价关系与划分是一一对应的.
证. 一个等价关系自然诱导出一个等价类作为划分. 反过来, 对于一个划分, 我们把每个划分出的子集内部两两定义为等价, 就得到了一个以特定划分为等价类的等价关系.
因此, 只要探究 n 元集合不同划分的个数就可给出Bell数. 前几个Bell数如下:
B0=1,B1=1,B2=2,B3=5,B4=15,B5=52,⋯.
递推式为
Bn+1=k=0∑nCnkBk
其中 Cnk 为组合数.
有未定向的超链接.
A 上的二元关系 ⪯ 叫做偏序关系, 如果它满足以下性质:
(1). 自反性: 对任何 a∈A , 都有 a⪯a ;
(2). 反对称性: 若 a⪯b,b⪯a , 则 a=b ;
(3). 传递性: 若 a⪯b,b⪯c , 则 a⪯c .
我们会把 a⪯b 也写成 b⪰a .
例5. 数的小于等于 ≤ 和大于等于 ≥ 都是偏序关系. 注意 ⪯ 只是一个记号, 它不表示类似“小于”的方向性.
例6. 集合的包含关系 ⊆ 是一个偏序关系. 偏序关系只要求上面的三个条件, 无需任何两个元素都能比较.
任何两个元素都能比较的偏序关系叫做全序关系. 严格地说, 就是满足以下条件的 ≤ :
(1). 自反性: 对任何 a∈A , 都有 a≤a ;
(2). 反对称性: 若 a≤b,b≤a , 则 a=b ;
(3). 传递性: 若 a≤b,b≤c , 则 a≤c ;
(4). 对任意的 a,b , a≤b 和 b≤a 至少有一个成立.
显然数的小于等于是全序关系.
任何子集都有所谓“最小元”的全序关系叫做良序关系. 严格地说, 就是满足以下条件的 ≤ :
(1). 自反性: 对任何 a∈A , 都有 a≤a ;
(2). 反对称性: 若 a≤b,b≤a , 则 a=b ;
(3). 传递性: 若 a≤b,b≤c , 则 a≤c ;
(4). 对任意的 a,b , a≤b 和 b≤a 至少有一个成立;
(5). 对任一子集 B⊆A , 都存在一个 x0 , 使得 x0≤x 对一切 x∈B 都成立.
例7. 自然数的 ≤ 是良序关系, 而整数上的 ≤ 则不然. 但是证书上仍然能定义良序关系如下:
(1) 若 x,y≥0 , 则 x⪯y 当且仅当 x≤y;
(2) 若 x,y<0, 则 x⪯y 当且仅当 x≥y;
(3) 若 x≥0,y<0, 则 x⪯y.
按这个序, 整数被排列成如下:
0,1,2,3,⋯,−1,−2,−3,⋯.
有未定向的超链接.
与良序有关的良序定理是一个相当重要的命题.
假如 (A,⪯) 是一个偏序集, B⊆A . B 的一个上界是一个 x0∈A, 如果对一切 x∈B , 都有 x⪯x0 成立. 一个上界 x0 叫做最大元, 如果同时还有 x0∈B. 类似地可以定义下界和最小元.
我们注意到一个集合的上界可能有很多, 但根据反对称性, 最大元只能有一个.