第二篇 集 合 论

第三章 集合与关系 3.1 集合论的基本概念 3.2 集合上的运算 3.3 集合的笛卡儿乘积 3.4 关系 3.5 关系的运算 第三章 集合与关系 3.1 集合论的基本概念 3.2 集合上的运算 3.3 集合的笛卡儿乘积 3.4 关系 3.5 关系的运算 3.6 次序关系 3.7 等价关系和划分

3.1 集合论的基本概念 3.1.1 集合的概念 集合在某些场合又称为类、族或搜集, 它是数学中最基本 的概念之一, 如同几何中的“点”、 “线”等概念一样, 不可精确定义, 现描如下: 一个集合是能作为整体论述的事物的集体。如 ; (1) “高二(1)班的学生”是一集合。 ; (2) 硬币有两面——正面和反面, “正面、 反面”构成一集合。 ; (3) 计算机内存之全体单元构成一集合。 ; (4) 1, 2, 3, …, n, …构成正整数集合。 ; (5) 所有三角形构成三角形集合。 ; (6) 坐标满足方程x2+y2≤R2的全部点构成图 2.1-1所示的点集。

图 2.1-1

组成集合的每个事物叫做这个集合的元素或成员。 通常用大写字母A, B, C, …代表集合; 用小写字母a, b, c, …代表元素。 如果a是集合A的一个元素, 则记为  a∈A 读做“a属于A”, 或说“a在A中”。 ; 如果a不是集合A的一个元素, 则记为  a A 读做“a不属于A”, 或说“a不在A中”。 ; 任一元素, 对某一集合而言, 或属于该集合, 或不属于该集合, 二者必居其一, 不可兼得。

通常采用3种方法表示集合。 ; 第一种是列举法。就是把集合中的元素一一列举出来。例如“所有小于5的正整数”这个集合的元素为1, 2, 3, 4, 除这4个元素外, 再没有别的元素了。 如果把这个集合命名为A, 就可记为 A={1, 2, 3, 4} 在能清楚表示集合成员的情况下可使用省略号, 例如, 从1 到50 的整数集合可记为{1, 2, 3, …, 50}, 偶数集合可记为{…,-4,-2,0,2,4,…}。

A={a|a∈I∧0＜a∧a＜5}, {a|a∈I∧1≤a≤50} 第二种是描述法。就是用谓词描述出集合元素的公共特征来表示这个集合。例如, 上述各例可分别写成 A={a|a∈I∧0＜a∧a＜5}, {a|a∈I∧1≤a≤50} 和  这里I表示整数集合。一般地 S={a|P(a)} 表示a∈S当且仅当P(a)是真。

集合的元素可以是一个集合, 例如A={a,b,c,D}, 而 D={0,1}。 仅含有一个元素的集合称为单元素集合。 应把单元素集合与这个元素区别开来。例如{A}与A不同, {A}表示仅以A为元素的集合, 而A对{A}而言仅是一个元素, 当然这个元素也可以是一个集合, 如A={1,2}。 称含有有限个元素的集合为有限集合。称不是有限集合的集合为无限集合或无穷集。有限集合的元素个数称为该集合的基数或势第五章将给出有限集、无限集、基数等概念的更精致的陈述。集合A的基数记为|A|, 例如 若 A={a, b}, 则 |A|=2, 又|{A}|=1

外延公理 两个集合A和B相等, 即A=B, 当且仅当它们有相同的成员(也就是, A的每一元素是B的一个元素而B的每一元素也是A的一个元素)。 ; 用逻辑符号表达是: 或

外延公理断言: 如果两个集合有相同的元素, 那么不管集合是如何表示的, 它们都相等。因此, (1) 列举法中, 元素的次序是无关紧要的。例如{x,y,z}与{z,x,y}相等。 (2) 元素的重复出现无足轻重。例如, {x,y,x}、 {x,y}、 {x,x,x,y}是相同的集合。 (3) 集合的表示不是唯一的。例如, {x|x2-3x+2=0}、 {x|x∈I∧1≤x≤2} 和{1, 2}均表示同一集合。

3.1.2 罗素悖论 1901年罗素(Bertrand Russell)提出以下悖论: 设论述域是所有集合的集合, 并定义S为下述集合 这样, S是不以自身为元素的全体集合的集合, 我们现在问“S是不是它自己的元素?” ; 假设S不是它自己的元素, 那么S满足谓词A A, 而该谓词定义了集合S, 所以S∈S。 另一方面, 如果S∈S, 那么S必须满足定义S的谓词, 所以SS。

这样, 我们导致了一个类似于谎言悖论的矛盾: 既非S∈S也非SS是真。 一个“集合”, 诸如S, 它能导致矛盾的称为非良定的。 罗素悖论起因于不受限制的定义集合的方法, 特别, 集合可以是自己的元素的概念值得怀疑。康脱以后创立的许多公理化集合论都直接地或间接地限制集合成为它自己的元素, 因而避免了罗素悖论。 公理化集合论用某个方法避免了罗素悖论, 但怎能确信没有其它悖论潜伏在这些形式结构中呢? 回答是悲观的, 业已证明, 应用现今有效的数学技术, 没有方法能证明新的悖论不会产生。

3.1.3 集合间的包含关系 定义2.1-1 设A和B是集合, 如果A的每一元素是B的一个元素, 那么A是B的子集合, 记为AB, 读做“B包含A”或“A包含于B中。 用逻辑符表示为: 有时也记作 , 称B是A的扩集。

定义3.1-2 如果AB且A≠B, 那么称A是B的真子集,记作AB , 读作“B真包含A”。 ; 用逻辑符表示为: 要注意区分从属关系“∈”及包含关系“”。 从属关系是集合元素与集合本身的关系, 包含关系是集合与集合之间的关系。

定理3.1-1 对任意集合A有 证 对任意元素x, x∈U是真, 所以 是真。由全称推广规则得 所以 (这是一个平凡证明的例子)

定理 3.1-2 设A和B是集合, A=B当且仅当AB和BA。 证

推论 3.1-2 对任何集合A, 恒有AA。 ; 定理 3.1-3 设A、B、C是集合, 若AB且BC, 则AC。 证 设x是论述域中任意元素, 因为 所以, x∈A→x∈B= x∈B→x∈C 由前提三段论得  x∈A→x∈C 由全称推广规则得 即

定义3.1-3 没有元素的集合叫空集或零集, 记为 。 定理 3.1-4 对任意集合A有 。 证 设x是论述域中任意元素, 则 常假, 所以 无义地真，由全称推广规则得 即

定理 3.1-5 空集是唯一的。 证 设和 都是空集, 由定理3.1-4得 和 , 根据定理3.1-2得 。 注意与{}不同, 后者是以空集为元素的一个集合, 前者没有元素。 能用空集构造不同集合的无限序列。在序列  中, 每一集合除第一个外都确实有一元素, 即序列中前面的集合。 在序列 中, 如果我们从0开始计算, 则第i项有i个元素。 这一序列的每一集合, 以序列中在它之前的所有集合作为它的元素。

例 1 (a) 集合{p,q}有4个不同子集: {p,q}、{p}、{q}和, 注意{p}{p,q}但p{p,q}, p∈{p,q}但{p}{p,q}。再者{p,q}, 但 (b) 集合{{q}}是单元素集合, 它的唯一元素是集合{q}。每一单元素集合恰有两个子集, {{q}}的子集是{{q}}和 。 一般地, n个元素的集合有2n个不同的子集合.

3.2 集合上的运算 3.2.1 并、 交和差运算; 定义 3.2-1 设A和B是集合。 (a) A和B的并记为A∪B, 是集合。 3.2 集合上的运算 3.2.1 并、 交和差运算; 定义 3.2-1 设A和B是集合。 (a) A和B的并记为A∪B, 是集合。 A∪B={x|x∈A∨x∈B} (b) A和B的交记为A∩B, 是集合。 A∩B={x|x∈A∧x∈B} (c) A和B的差, 或B关于A的相对补, 记为A-B, 是集合。 A-B={x|x∈A∧xB}

例 1 设A={a,b,c,d)和B={b,c,e}, 那么 A∪B={a, b, c, d, e} A∩B={b, c} ; A-B={a, d} ; B-A={e}

定义 3.2-2 如果A和B是集合, A∩B=, 那么称A和B是不相交的。如果C是一个集合的族, 使C的任意两个不同元素都不相交, 那么C是(两两)不相交集合的族。 ; 例 2 如果C={{0}, {1}, {2}, …}={{i}|i∈N}, 那么C是不相交集合的族。 定理 3.2-1 集合的并和交运算是可交换和可结合的。也就是对任意A、B和C。 ; (a) A∪B=B∪A ; (b) A∩B=B∩A ; (c) (A∪B)∪C=A∪(B∪C) ; (d) (A∩B)∩C=A∩(B∩C) ; 我们仅证明(a)和(c), (b)和(d)是类似的。

证 (a) 设x是论述域U的任意元素, 那么   ∪的定义 ∨的可交换性 ∪的定义 因为x是任意的, 得 即A∪B=B∪A

(c) 设x是任意元素, 那么 x∈A∪(B∪C) x∈A∨x∈(B∪C) ∪的定义  x∈A∨(x∈B∨x∈C) ∪的定义  (x∈A∨x∈B)∨x∈C ∨的结合律  x∈(A∪B)∨x∈C ∪的定义  x∈(A∪B)∪C ∪的定义 因为x是任意的, 得出  x(x∈A∪(B∪C)x∈(A∪B)∪C) 因此, A∪(B∪C)=(A∪B)∪C。

定理 3.2-2 对任意集合A、B和C有: ; (a) A∪(B∩C)=(A∪B)∩(A∪C) ; (b) A∩(B∪C)=(A∩B)∪(A∩C) = 即集合运算∩和∪, ∩在∪上可分配, ∩在∪上可分配。 ; 证 设x是任意元素, 那么 x∈A∪(B∩C) x∈A∨x∈(B∩C) ∪的定义  x∈A∨(x∈B∧x∈C) ∩的定义  (x∈A∨x∈B)∧(x∈A∧x∈C) ∨在∧上可分配 (x∈A∪B)∧(x∈A∪C) ∪的定义  x∈(A∪B)∩(A∪C) ∩的定义 因此, A∪(B∩C)=(A∪B)∩(A∪C)。

定理 3.2-3 设A、B、C和D是论述域U的任意子集合, 那么下列断言是真: ; (a) A∪A=A ; (b) A∩A=A ; (c) A∪=A ; (d) A∩= ; (e) A-=A ; (f) A-BA ; (g) 如果AB和CD, 那么, (A∪C)(B∪D) ; (h) 如果AB和CD, 那么, (A∩C)(B∩D) ; (i) AA∪B ; (j) A∩BA ; (k) 如果AB, 那么, A∪B=B ; (l) 如果AB, 那么, A∩B=A

(g) 设x是A∪C的任意元素, 那么x∈A∨x∈C。现在分情况证明。 情况1: 设x∈A, 因为AB, 得x∈B, 所以x∈B∨x∈D, 因此x∈B∪D。 情况2: 设x∈C, 用与情况1相似的论证得x∈B∪D。 因此, x∈A∪C, 那么x∈B∪D。 所以A∪CB∪D。 (k) 因AB, 又BB根据(g)得A∪BB∪B, 但B∪B=B, 因此A∪BB。 另一方面由(i)得BA∪B。 所以, A∪B=B。

推论2.2-3 (a) A∪U=U, (b) A∩U=A。 ; 本推论可由定理2.2-3的(k)(l)部分得出。 ; 3.2.2 补运算 定义2.2-3 设U是论述域而A是U的子集。A的(绝对)补, 记作A, 是集合 。 例 3 (a) 如果U={p,q,r,s}和A={p,q}, 那么A ={r,s}。 (b) 如果U=N和A={x|x＞0}, 那么A={0}。 (c) 如果U=I和A={2x+1|x∈I}, 那么A={2x|x∈I}。

定理 2.2-4 设A是某论述域U的任意子集, 那么 证

定理3.2-5 (补的唯一性)设A和B是论述域U的子集,那么B=A当且仅当A∪B=U和A∩B=。 证 必要性从定理 2.2-4 直接得到。现证明充分性。 ; 设A∩B=和A∪B=U, 那么 B=U∩B =(A∪ )∩B =(A∩B)∪( ∩B) =∪( ∩B) =( ∩A)∪( ∩B) = ∩(A∪B) = ∩U =

推论3.2-5 证 因U∪=U和U∩=, 所以,   。 定理 3.2-6 设A是U的任意子集, 那么 。也就是说, A的补的补是A。 证 因为 ∪A=U和 ∩A=, 根据上一定理A是 的补, 但 A 也是的补, 而补是唯一的, 所以, 。

定理3.2-7 (德·摩根定律)设A和B是U的任意子集, 那么 证 (a) 根据定理2.2-5, 是A∪B的补, 但A∪B也是A∪B的补, 而补是唯一的, 所以 (b)的证明是类似的, 故略。

定理 3.2-8 设A、B是U的任意子集, 若 证 根据逆反律得 x是任意的, 所以

图 2.2-1

另外, 根据并、交、补等定义, 亦知命题演算中的∨、∧、 、 →、T、F等分别与集合论中的∪、∩、-、 、U、 等有对应关系, 因此, 有关它们的公式也有相似性。 例如命题演算中有公式 (P∨Q) P∧Q, P∧TP, … 集合论中有对应公式 又如命题演算中有范式等概念  P∧Q∨R(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) 如果需要, 在集合论中也可引入范式等概念, 使  A∩B∪C=(A∪B∪C)∩(A∪B∪C)∩(A∪B∪C)

3.2.3 并和交运算的扩展 扩展后并和交运算都定义在集合的搜集上。 ; 定义 3.2-4 设C是某论述域子集的搜集。 ; (a) C的成员的并、记为 , 是由下式指定的集合 (b) 如果C≠, C的成员的交, 记为 , 是下式指定的集合

定义说明如果 , 那么x至少是一个子集S∈C的元素; 如果 , 那么x是每一个子集S∈C的元素。注意对 的定义来说, C必须非空, 否则, 由于 , 蕴含式S∈C→x∈S对每一S将是无义地真。这样, 谓词 s(S∈C→x∈S)对每一x是真。因此, 所定义的集合就是全集合U。要求 , 这个可能消除。

设D是一集合, 如果给定D的任一元素d, 就能确定一个集合Ad, 那么d叫做Ad的索引, 搜集C={Ad|d∈D}叫做集合的加索引搜集; 而D叫做搜集的索引集合。当D是一个搜集C的索引集合, 符号 表示 , 而 表示 。

如果加索引搜集C的索引集合是前n+1个自然数{0, 1, 2, …, n}, 或全体自然数{0, 1, 2, …}, 那么C的成员的并和交能用类似于和式概念的符号表示。 例如 一般地, 索引集合不必须是N的子集, 可以是任意集合, 例如R+。

*3.2.6 有限集的计数 定理 3.2-15 设A和B都是有限集合, 则以下公式成立:

证 A和B之间可能有公共元素, 公共元素个数是|A∩B|, 在计算|A∪B|时每个元素只计算一次, 但在计算|A|+|B|时, 公共元素计算了二次, 一次在算|A| 时, 一次在算|B|时, 因此, 右边减去|A∩B|才能相等。证毕。 ; 公式(a)可以推广, 三个集合时为

图 2.2-3

一般地成立以下公式: 证 用归纳法证明(未学过归纳法的同学可在学完下节后, 再看此证明)。 n=2时, 已证明成立, 即

设n-1(n≥3)时公式成立, 现证明n时也成立。 根据归纳假设得

例 6 (a) 在一个班级50个学生中, 有 26 人在第一次考试中得到A, 21人在第二次考试中得到A, 假如有17 人两次考试都没有得到A, 问有多少学生在两次考试中都得到A? 解 设第一次考试得A的是集合A1, 第二次考试得A的是集合A2。 则 但 所以 答: 两次考试都得A的 14 人。

(b) 某教研室有30名老师, 可供他们选修的第二外语是日语、 法语、德语。已知有 15 人进修日语, 8 人选修法语, 6 人选修德语, 而且其中 3 人选修三门外语, 我们希望知道至少有多少人一门也没有选修。 解 设A1、A2、A3分别表示选修日语、法语和德语的人, 因此

因为 我们得 即至多有 23 人在进修第二外语, 因此至少有 7 人没有进修第二外语。

3.3 集合的笛卡儿乘积 定义3.3-1 (1) 两个元素a1、a2组成的序列记作〈a1,a2〉, 称为二重组或序偶。a1和a2分别称为二重组〈a1,a2〉的第一和第二个分量。 (2) 两个二重组〈a,b〉和〈c,d〉相等当且仅当a=c并且b=d。 (3) 设a1,a2,…,an是n个元素, 定义 〈a1,a2,…,an〉=〈〈a1,a2,…,an-1〉,an〉为n重组, 这里n＞2。

(1) 由两个二重组相等的定义可以看出, 二重组中元素的次序是重要的, 例如〈 2,3〉≠〈3,2〉, 这一点和集合相等的定义不同, 在集合中元素的次序是无关紧要的, 例如{2,3}={3,2}。 (2) n重组是一个二重组, 其第一分量是n-1重组。〈2,3,5〉代表〈〈2,3〉,5〉而不代表〈2,〈3,5〉〉, 按定义后者不是三重组, 并且〈〈2,3〉,5〉≠〈2,〈3,5〉〉。

(3) 由二重组相等的定义容易推得两个n重组〈a1,a2,…,an〉和〈b1,b2,…,bn〉相等当且仅当ai=bi, 1≤i≤n。 例如, 由二重组相等的定义得〈〈a,b〉,c〉=〈〈d,e〉,f〉当且仅当c=f∧〈a,b〉=〈d,e〉, 再由二重组相等的定义得〈a,b〉=〈d,e〉当且仅当a=d∧b=e。这样, 〈〈a,b〉,c〉=〈〈d,e〉, f〉当且仅当a=d∧b=e∧c=f。 我们通常需要由集合族A1,A2,…,An的元素生成的所有n重组, 因而有以下定义。

定义3.3-2 (1)集合A和B的叉积记为A×B, 是二重组集合{〈a,b〉|a∈A∧b∈B}。 (2) 集合A1,A2,…,An的叉积记为A1×A2×…×An或 , 定义为 叉积又叫做集合的笛卡儿乘积。 ; 由定义可看出, 是n重组集合  {〈a1,a2,…,an〉|ai∈Ai∧1≤i≤n} 另外, 对一切i, Ai=A时, 可简记为An。

例1 设A={a,b}, B={1,2,3}, C={p,q}, D={0}, E= 。 (a) A×B={〈a,1〉,〈a,2〉,〈a,3〉,〈b,1〉,〈b,2〉,〈b,3〉} (b)A×B×C={〈a,1,p〉,〈a,1,q〉,〈a,2,p〉,〈a,2,q〉,〈a,3,p〉,〈a,3,q〉,〈b,1,p〉,〈b,1,q〉,〈b,2,p〉,〈b,2,q〉,〈b,3,p〉,〈b,3,q〉}, 如图2.5-1所示。 (c) C×D={〈p,o〉,〈q,o〉}。 ; (d)D×(C2)=D×{〈p,p〉,〈p,q〉,〈q,p〉,〈q,q〉}={〈0,〈p,p〉〉,〈0,〈p,q〉〉,〈0,〈q,p〉〉,〈0,〈q,q〉〉}。 (e) A×E= 。 当A和B是实数集合, 那么A×B能代表笛卡儿平面的点的集合。

图 2.5-1

例2 设A={x|1≤x≤2}和B={y|0≤y}。 ; (a) A×B={〈x,y〉|1≤x≤2∧0≤y} ; (b) B×A={〈y,x〉|1≤x≤2∧0≤y}

图 2.5-2

定理3.3-1 如果A、B和C都是集合, 那么 (a) A×(B∪C)=(A×B)∪(A×C) (b) A×(B∩C)=(A×B)∩(A×C) (c) (A∪B)×C=(A×C)∪(B×C) (d) (A∩B)×C=(A×C)∩(B×C)

证 设〈x,y〉是A×(B∪C)的任一元素, 那么 所以, A×(B∪C)=(A×B)∪(A×C)。

定理3.3-2 如果所有Ai(i=1,2,…,n)都是有限集合, 则 |A1×A2×…×An|=|A1|·|A2|·|A3|…｜An| 证 n=1时, |A1|=|A1|显然成立。对n≥2用归纳法证明。 n=2时, 设|A1|=p, |A2|=q, A1中的每一个元素与A2中的q个不同元素可构成q个不同序偶, 故共可构成pq个不同序偶, 所以  |A1×A2|=pq=|A1|·|A2|

=|A1|·|A2|…|An|·|An+1| 设对任意n≥2定理成立, 现证n+1也成立。  |A1×A2×…×An×An+1|=|A1×A2×…×An|·|An+1| =|A1|·|A2|…|An|·|An+1| 这里第一步是根据叉积定义和基础步骤, 第二步是根据归纳假设。 所以, 对一切n≥1, 定理成立。 最后说明一点: n重组的概念可以推广到n=1的情况, 称〈a〉为一重组。这主要为了在一些场合能方便地与多重组统一叙述, 它实质上仍代表一个元素。

3.4 关系 3.4.1 关系 关系的数学概念是建立在日常生活中关系的概念之上的.让我们先看两个例子 3.4 关系 3.4.1 关系 关系的数学概念是建立在日常生活中关系的概念之上的.让我们先看两个例子 例1 设A={a,b,c,d}是某乒乓球队的男队员集合, B={e,f,g}是女队员集合.如果A和B元素之间有混双配对关系的是a和g,d和e. 我们可表达为: R={〈a,g〉,〈d,e〉}

这里R表示具有混双配对关系的序偶集合.所有可能具有混双配对关系的序偶 集合是: A×B={〈x,y〉|x∈A∧y∈B} ={〈a,e〉,〈a,f〉,〈a,g〉,〈b,e〉,〈b,f〉,〈b,g〉〈c,e〉,〈c,f〉,〈c,g〉,〈d,e〉,〈d,f〉,〈d,g〉}

例2 设学生集合A1={a,b,c,d},选修课集合A2={日语,法语},成绩等级集合A3={甲,乙,丙}.如果四人的选修内容及成绩如下: 我们可表达为S={〈a,日,乙〉,〈b,法,甲〉,〈c,日,丙〉,〈d,法,乙〉},这里S表示学生和选修课及成绩间的关系.而可能出现的全部情况为

A1×A2×A3={〈x,y,z〉|x∈A1∧y∈A2∧z∈A3} ={〈a,日,甲〉,〈a,日,乙〉,〈a,日,丙〉,〈a,法,甲〉,〈a,法,乙〉,=〈a,法,丙〉,〈b,日,甲〉,〈b,日,乙〉,〈b,日,丙〉,〈b,法,甲〉,=〈b,法,乙〉,〈b,法,丙〉,〈c,日,甲〉,〈c,日,乙〉,〈c,日,丙〉,=〈c,法,甲〉,〈c,法,乙〉,〈c,法,丙〉,〈d,日,甲〉,〈d,日,乙〉,=〈d,日,丙〉,〈d,法,甲〉,〈d,法,乙〉,〈d,法,丙〉}

定义 3.4―1 (1)A×B的子集叫做A到B的一个二元关系. (2)A1×A2×…×An(n≥1)的子集叫做A1×A2×…×An上的一个n元关系.

从定义可看出,关系是一个集合,所有定义集合的方法,都可用来定义关系 例1,例2是列举法的例子一个谓词P(x1,x2,…,xn)可以定义一个n元关系R: R={〈x1,x2,…,xn〉|P(x1,x2,…,xn)} 例如,实数R上的二元关系＞可定义如下: ＞={〈x,y〉|x∈R∧y∈R∧x＞y} 反之,一个n元关系也可定义一个谓词:

当n=1时,R={〈x〉|P(x)}称为一元关系 当n=1时,R={〈x〉|P(x)}称为一元关系.它是一重组集合,表示论述域上具有性质P的元素集合,其意义与R={x|P(x)}相同,仅记法不同而已。例如,设P(x)表示“x是质数”,论述域是N,则质数集合可表示为 {〈x〉｜P(x)} 或 {x｜P(x)}

关系也可归纳地定义.自然数上的小于关系可定义如下: (1) (基础)〈0,1〉∈＜ (2) (归纳)如果〈x,y〉∈＜,那么 (i)〈x,y+1〉∈＜ (ii)〈x+1,y+1〉∈＜ (3)(极小性)对一切x,y∈N,x＜y当且仅当〈x,y〉是由有限次应用条款(1)和(2)构成

定义3.4―2设R是 的子集,如果R=,则称R为空关系,如果 R= ,则称R为全域关系. 现在定义关系相等的概念,在关系相等的概念中不仅需要n重组集合相等,还需其叉积扩集也相同. 定义3.4―3设R1是 上的n元关系,R2是 上的m元关系.那么R1=R2,当且仅当n=m,且对一切i,1≤i≤n,Ai=Bi,并且R1和R2是相等的有序n重组集合

3.4.2 二元关系 最重要的关系是二元关系.本章主要讨论二元关系,今后术语“关系”都指二元关系.若非二元关系将用“三元”或“n元”一类术语指出. 二元关系有自己专用的记法和若干新术语 设 A={x1,x2,…,x7}, B={y1,y2,…,y6} R={〈x3,y1〉,〈x3,y2〉,〈x4,y4〉,〈x6,y2〉}

A到B的二元关系R可如图3. 1―1那样形象地表示. 〈x3,y1〉∈R,也可写成x3Ry1,称为中缀记法,读做x3和y1有关系R

图 3.1―1

A叫做关系R的前域,B叫做关系R的陪域 D(R)={x｜y(〈x,y〉∈R)}叫做关系R的定义域 R(R)={y｜x(〈x,y〉∈R)}叫做关系R的值域 关系是序偶的集合,对它可进行集合运算,运算结果定义一个新关系.设R和S是给定集合上的两个二元关系,则R∪S,R∩S,R-S, 等可分别定义如下: x(R∪S)y xRy∨xSy x(R∩S)y xRy∧xSy x(R-S)y xRy∧x$y x( )y xRy

例3平面上的几何图形是平面R2的子集,也是一种关系.设(参看图3.1―2) R1={〈x,y〉|〈x,y〉∈R2∧x2+y2≤9} R2={〈x,y〉|〈x,y〉∈R2∧1≤x≤3) ∧(0≤y≤3)} R3={〈x,y〉|〈x,y〉∈R2∧x2+y2≥4} 则 R1∪R2={〈x,y〉|〈x,y〉∈R2∧(x2+y2 ≤9∨(1≤x≤3∧0≤y≤3))}

R1∩R3={〈x,y〉｜〈x,y〉∈R2∧(x2+y2 R1-R3={〈x,y〉|〈x,y〉∈R2∧(x2+y2≤9∧ L (x2+y2≥4))} ={〈x,y〉|〈x,y〉∈R2∧L (x2+y2≥4)}

图 3.1―2

3.4.3 关系矩阵和关系图 表达有限集合到有限集合的二元关系时,矩阵是一有力工具定义3.4―4给定集合A={a1,a2,…,am}和B={b1,b2,…,bn},及一个A到B的二元关系R. 使. 1,如果aiRbj rij= 0,如 aiRbj 则称MR=［rij］矩阵是R的关系矩阵.

例 设A={a1,a2},B={b1,b2,b3},R={〈a1,b1〉,〈a2,b1〉,〈a1,b3〉,〈a2,b2〉},则其关系矩阵为 即

例5 设A={1,2,3,4},A上的二元关系R={〈x,y〉｜x＞y},试求出关系矩阵

图 3.1―3

例6 设A={1,2,3,4,5},R={〈1,2〉,〈2,2〉,〈3,2〉,〈3,4〉,〈4,3〉},其图示如图3. 1―3所示 例6 设A={1,2,3,4,5},R={〈1,2〉,〈2,2〉,〈3,2〉,〈3,4〉,〈4,3〉},其图示如图3.1―3所示.图中结点5叫做孤立点利用关系R的图示,也可写出关系R.

3.4.4 关系的特性 在研究各种二元关系中,关系的某些特性扮演着重要角色,我们将定义这些特性,并给出它的图示和矩阵的特点 定义3.4―5设R是A上的二元关系, (1)如果对A中每一x,xRx,那么R是自反的.即 A上的关系R是自反的 x(x∈A→xRx) A={1,2,3},R1={〈1,1〉,〈2,2〉,〈3,3〉,〈1,2〉} 是自反的.其关系图和关系矩阵的特点如图3.4―4所示.

图 3.4―4

(2)如果对A中每一x,xRx,那么R是反自反的.即 A上的关系R是反自反的 x(x∈A→xRx) 例如,A={1,2,3},R2={〈2,1〉,〈1,3〉,〈3,2〉}是反自反的,其关系图和关系矩阵的特点如图3.1―5所示. 图 3.4―5

有些关系既不是自反的,又不是反自反的(如图3.4―6),例如,R3={〈1,1〉,〈1,2〉,〈3,2〉,〈2,3〉,〈3,3〉} 图 3.4―6

(3)如果对每一x,y∈A,xRy蕴含着yRx,那么R是对称的.即A上的关系R是对称的 x y (x∈A∧y∈A∧xRy→yRx) 例如,A={1,2,3},R4={〈1,2〉,〈2,1〉,〈1,3〉,〈3,1〉,〈1,1〉}是对称的.其关系图和关系矩阵的特点如图3.4―7所示

图 3.4―7

(4)如果对每一x,y∈A,xRy,yRx蕴含着x=y,那么R是反对称的.即A上的关系R是反对称的 x ，y (x∈A∧y∈A∧xRy∧yRx→x=y) 例如,A={1,2,3},R5={〈1,2〉,〈2,3〉}是反对称的,其关系图和关系矩阵的特点如图3.4―8所示.

图 3.4―8

(5)如果对每一x,y,z∈A,xRy,yRz蕴含着xRz,那么R是传递的.即A上的关系R是传递的 x y z(x∈A∧y∈A∧z=∈A∧xRy∧yRz→xRz) 例如,A={1,2,3,4},R5={〈4,1〉,〈4,3〉,〈4,2〉,〈3,2〉,〈3,1〉,〈2,1〉}是传递的.其关系图和关系矩阵如图3.4―10所示. 图 3.4―9

图 3.4―10

例7 (a)任何集合上的相等关系是自反的,对称的,反对称的和传递的,但不是反自反的 (b)整数集合I上,关系≤是自反的,反对称的,可传递的.但不是反自反的和对称的.关系＜是反自反的,反对称的,可传递的,但不是自反的和对称的 (c)设={a,b},试考察上的下列关系: (i)关系“与……有同样长度”是自反的,对称的,可传递的,但不是反自反的和反对称的

(ii)“xRy”当且仅当x是y的真词头”,这里R是反自反的,反对称的,可传递的,但不是自反的和对称的 (iii)“xRy”当且仅当x的某真词头是y的一个真词尾”,这里R既不是自反的又不是反自反的,因为aaRaa,但abRab,既不是对称的也不是反对称的,并且不是传递的 (d)非空集合上的空关系是反自反的,对称的,反对称的和传递的,但不是自反的.空集合上的空关系则是自反的,反自反的,对称的,反对称的和可传递的

(e)基数大于1的集合上的全域关系是自反的,对称的和传递的,但不是反自反的和反对称的.例如图3.1―11所示的关系 图 3.1―11

3.5 关系的运算 3.5.1 关系的复合 前边已经指出,关系是序偶的集合,因此可以进行集合运算.本节介绍一种对关系来说,更为重要的运算——合成运算.假设R1是A到B的关系,R2是B到C的关系(参看图3.5―1).合成关系R1R2是一个A到C的关系:如果在关系图上,从a∈A到c∈C有一长度(路径中弧的条数)为2的路径,

其第一条弧属于R1,其第二条弧属于R2,那么〈a,c〉∈R1R2.合成关系R1R2就是由〈a,c〉这样的序偶组成的集合.

图 3.5―1

定义3.5―1设R1是从A到B的关系,R2是从B到C的关系,从A到C的合成关系记为R1R2,定义为 R1R2={〈a,c〉｜a∈A∧c∈C∧b［b∈B∧〈a,b〉 ∈R1∧〈b,c〉∈R2］① 例1 (a)如果R1是关系“…是……的兄弟”,R2是关系“…是……的父亲”,那么R1R2是关系“…是……的叔伯”.R2R2是关系“…是……的祖父”

(b)A={1,2,3,4},B={2,3,4},C={1,2,3},设R是A到B的关系;S是B到C的关系. R={〈x,y〉｜x+y=6}={〈2,4〉,〈3,3〉,〈4,2〉} S={〈y,z〉｜y-z=1}={〈2,1〉,〈3,2〉,〈4,3〉} 则R·S={〈2,3〉,〈3,2〉,〈4,1〉}.如图3.5―2所示.

图 3.5―2

(c)设A={1,2,3,4,5},R和S都是A上二元关系.如果 S·R={〈4,2〉,〈3,2〉,〈1,4〉} (R·S)·R={〈3,2〉} R·(S·R)={〈3,2〉} R·R={〈1,2〉,〈2,2〉} S·S={〈4,5〉,〈3,3〉,〈1,1〉}

(d)设R是A到B的二元关系,IA,IB分别是A和B上的相等关系,则 IA·R=R·IB=R (e)如果关系R的值域与关系S的定义域的交集是空集,则合成关系R·S是空关系.下边介绍合成关系的性质

定理3.5―1设R1是从A到B的关系,R2和R3是从B到C的关系,R4是从C到D的关系,那么 (a) R1(R2∪R3)=R1R2∪R1R3 (b) R1(R2∩R3) R1R2∩R1R3 (c) (R2∪R3)R4=R2R4∪R3R4 (d) (R2∩R3)R4 R2R4∩R3R4 (a),(c),(d)部分的证明留作练习,我们仅证明(b)部分

证先证明公式.因为 〈a,c〉∈R1(R2∩R3) b［〈a,b〉∈R1∧(〈b,c〉∈R2∩R3)］ b［〈a,b〉∈R1∧(〈b,c〉∈R2∧〈b,c〉∈R3)］ b［(〈a,b〉∈R1∧〈b,c〉∈R2)∧(〈a,b〉∈R1∧〈b,c〉 ∈R3)］ b［〈a,b〉∈R1∧〈b,c〉∈R2］∧b［〈a,b〉∈R1∧〈b,c〉∈R3］ 〈a,c〉∈R1R2∧〈a,c〉∈R1R3 〈a,c〉∈R1R2∩R1R3 即〈a,c〉∈R1(R2∩R3)〈a,c〉∈R1R2∩R1R3 所以,R1(R2∩R3)R1R2∩R1R3

再证包含可能是真包含.举反例证明 如果A={a},B={b1,b2,b3},C={c} A到B的关系R1={〈a,b1〉,〈a,b2〉} B到C的关系R2={〈b1,c〉,〈b3,c〉} B到C的关系R3={〈b2,c〉,〈b3,c〉} 那么,R1(R2∩R3)= ,R1R2∩R1R3={〈a,c〉}.此时R1( R2∩R3)≠R1R2∩R1R3.证毕

定理3.5―2 设R1,R2和R3分别是从A到B,B到C和C到D的关系,那么(R1R2)R3=R1(R2R3)证先证(R1R2)R3R1(R2R3) 设〈a,d〉∈(R1R2)R3,那么对某c∈C,〈a,c〉∈R1R2和〈c,d崐〉∈R3.因为〈a,c〉∈R1R2,存在b∈B使〈a,b〉∈R1和〈b,c〉∈R2.因为〈b,c〉∈R2和〈c,d〉∈R3,得〈b,d〉∈R2R3,所以〈a,d〉∈R1(R2R3).这样,就证明了(R1R2)R3R1(R2R3).R1(R2R3)(R1R2)R3的证明是类似的,留给读者自证.上述证明也可用等价序列表达

3.5.2 关系R的幂 当R是A上的一个关系时,R可与自身合成任意次而形成A上的一个新关系.在这种情况下,RR常表示为R2,RRR表示为R3等等,我们能归纳地定义这一符号如下 定义3.5―2 设R是集合A上的二元关系,n∈N,那么R的n次幂记为Rn,定义如下: (1) R0是A上的相等关系,R0={〈x,x〉｜x∈A} (2) Rn+1=Rn·R

定理3.5―3 设R是A上的二元关系,并设m和n是N的元素,那么 (a)Rm·Rn=Rm+n (b)(Rm)n=Rmn 可用归纳法证明.请读者自证.

定理3.5―4 设｜A｜=n,R是集合A上的一个关系,那么存在i和j使Ri=Rj而0≤i＜j≤ 证A上的每一二元关系是A×A的子集,因为｜A×A｜=n2,｜ρ(A×A)｜= ,因此A上有 个不同关系.所以,R的不同的幂不会超过 个.但序列R0,R1,…, 有 +1项,因此R的这些幂中至少有两个是相等的.证毕

  定理3.5―5设R是集合A上的一个二元关系.若存在i和j,i＜j,使Ri=Rj.记d=j-i,那么 (a) 对所有k≥0,Ri+k=Rj+k (b) 对所有k,m≥0,Ri+md+k=Ri+k (c) 记S={R0,R1,R2,…,Rj-1},那么R的每一次幂是S的元素,即对n∈N,Rn∈S

证(a)和(b)部分用归纳法证明,留作练习 对于(c),设n∈N,如果n＜j,那么根据S的定义,Rn∈S.假设n≥j,那么我们能将n表示为i+md+k,这里k＜d,根据(b)部分,得Rn=Ri+k,因为i+k＜j,这证明了Rn∈S. 定理中的i,j,在实用时宜取最小的非负整数,以保证S中无重复元素. 图 3.2―3

例2 设A={a,b,c,d},R={〈a,b〉,〈c,b〉, 〈b,c〉,〈c,d〉},其关系图如图3.2―3所示,则 R0={〈a,a〉,〈b,b〉,〈c,c〉,〈d,d〉} R2={〈a,c〉,〈b,b〉,〈b,d〉,〈c,c〉} R3={〈a,b〉,〈a,d〉,〈b,c〉,〈c,b〉,〈c,d〉} R4={〈a,c〉,〈b,b〉,〈b,d〉,〈c,c〉} 它们的关系图如图3.5―4所示

图 3.5―4

由于R4=R2,根据定理3. 5―5(c),对所有n∈N,Rn∈{R0,R1,R2,R3},可见不必再算了 由于R4=R2,根据定理3.5―5(c),对所有n∈N,Rn∈{R0,R1,R2,R3},可见不必再算了.事实上易证R5=R3,R6=R4=R2,用归纳法可得R2n+1=R3和R2n=R2,这里n≥1

3.5.3 复合关系的矩阵表达 定理3.5―6设X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp},R是X到Y的关系,MR=［aij］是m×n矩阵,S是Y到Z的关系,MS=［bij］是n×p矩阵.则MR·S=［cij］=MR·MS,这里

证因为如果存在某k使aik和bki都等于1,则cij=1. 但aik和bkj都等于1意味着xiRyk和ykSzj. 所以xi(R·S)zj 证因为如果存在某k使aik和bki都等于1,则cij=1.但aik和bkj都等于1意味着xiRyk和ykSzj.所以xi(R·S)zj.可见如此求得的MR·S确实表达了R·S的关系.因此上述等式是正确的. 如果不仅存在一个k使aik和bki都是1,此时cij仍为1,只是从xi到zj不止一条长度为2的路径,但等式仍然正确.上段的论证,已隐含了不止一个k的情况. 本定理说明合成关系矩阵可用关系矩阵(布尔矩阵)的乘法表达.

例3设X={1,2},Y={a,b,c},Z={α,β},R={〈1,a〉,〈1,b〉,〈2,c〉},S={〈a,β〉,〈b,β〉},则

图 3.5―5

定理3.5―7 关系矩阵的乘法是可结合的 证利用关系合成的可结合性证明. (MR·MS)·MT =MR·S·MT=M(R·S)·T=MR·(S·T)==MR·MS·T =MR·(MS·MT). 不仅合成关系可用关系矩阵表达,而且关系的集合运算也可用关系矩阵表达.设R和S是X到Y上的二元关系,MR=［aij］,MS=［bij］,cij是运算后所得新关系之关系矩阵的元素,则

MR∩S=MR∧MS cij=aij∧bij cij=L aij MR-S=MR∧ cij=aij∧(L bij)

3.5.4 逆关系 在讨论闭包运算时,要用到逆关系的概念,因此我们先介绍逆关系 定义1设R是从A到B的二元关系,关系R的逆(或叫R的逆关系)记为 ,是一从B到A的二元关系,定义如下:

例1 (a) I上的关系<的逆是> (b) 集合族上的关系的逆是关系 (c) 空关系的逆是空关系 (d) =B×A,即A×B的全域关系的逆等于B×A的全域关系. 定理3.5―8设R是从A到B的关系,而S是从B到C 的关系,则

定理3.5―9 设R,R1和R2都是从A到B的二元关系,那么下列各式成立: 这里 表示

3.5.5 关系的闭包运算 关系的闭包运算是关系上的一元运算,它把给出的关系R扩充成一新关系R′,使R′具有一定的性质,且所进行的扩充又是最“节约”的 定义2设R是A上的二元关系,R的自反(对称,传递)闭包是关系R′,使 (i)R′是自反的(对称的,传递的) (ii)R′R (iii)对任何自反的(对称的,传递的)关系R″,如果 R″R,那么R″R′

R的自反,对称和传递闭包分别记为r(R),s(R)和t(R) R的自反,对称和传递闭包分别记为r(R),s(R)和t(R).由定义可以看出,R的自反(对称,传递)闭包是含有R并且具有自反(对称,传递)性质的最小关系.如果R已经是自反的(对称的,传递的),那么,具有该性质并含有R的最小关系就是R自身.下一定理说明这一点. 定理3..5―10设R是集合A上的二元关系,那么 (a) R是自反的当且仅当r(R)=R (b) R是对称的当且仅当s(R)=R (c) R是传递的当且仅当t(R)=R

证 (a)如果R是自反的,那么R具有定义3. 3―2对R′所要求的性质,因此r(R)=R. 反之,如果r(R)=R. 那么,根据定义3 证 (a)如果R是自反的,那么R具有定义3.3―2对R′所要求的性质,因此r(R)=R.反之,如果r(R)=R.那么,根据定义3.3―2的性质(i),R是自反的. (b)和(c)的证明是类似的,略. 构造R的自反,对称和传递闭包的方法就是给R补充必要的序偶,使它具有所希望的特性.下面我们用关系图来说明如何实现这一点.

定理3.5―11 设R是集合A上的二元关系.那么,r(R)=R∪E(这里E是A上相等关系,在本节中均如此.) 证 设R′ =R∪E.显然,R′ 是自反的且R′R.余下只需证明最小性,现假设R″是A上的自反关系且R″R.因R″是自反的,所以R″E,又R″R,所以R″R∪E=R′.这样,定义3.3―2都满足.所以,R′=r(R).证毕

定理3.5―12 设R是集合A上的二元关系,那么 证 证明分两部分 (1) (基础)从定义3.6―2第(ii)条,立即得到Rt(R) (2) (归纳)假设Rnt(R),n≥1.设〈a,b〉∈Rn+1.因为Rn+1=Rn·R,存在c∈A,使〈a,c〉∈Rn和〈c,b〉∈R.根据归纳前提和基础步骤,〈a,c〉∈t(R)和〈c,b〉∈t(R).因为t(R)是传递的,得〈a,b〉∈t(R).这证明了Rn+1 t(R).

例2 (a)整数集合I上的关系＜的自反闭包是≤,对称闭包是关系≠,传递闭包是关系＜自身 (b)整数集合I上的关系≤的自反闭包是自身,对称闭包是全域关系,传递闭包是自身 (c)E的自反闭包,对称闭包和传递闭包都是E (d)≠的自反闭包是全域关系,对称闭包是≠,≠的传递闭包是全域关系 (e)空关系的自反闭包是相等关系,对称闭包和传递闭包是自身 (f)设R是I上的关系,xRy当且仅当y=x+1,那么t(R)是关系＜

定理3.5―13设R是集合A上的二元关系,这里A有n个元素,那么 证 设〈x,y〉∈t(R),于是必存在最小的正整数k,使〈x,y〉∈Rk.现证明k≤n.若不然,存在A的元素序列x=a0,a1,a2,…,ak-1,ak=y使xRa1,a1Ra2,…,ak-1Ry.因k＞n,a0,a1,…,ak中必有相同者,不妨设ai=aj,0≤i＜j≤k.于是 xRa1,a1Ra2,…,ai-1Rai,ajRaj+1,…,ak-1Ry 成立.即〈x,y〉∈Rs,这里s=k-(j-i).但这与k是最小的假设矛盾,于是k≤n,又〈x,y〉是任意的,故定理得证

例3设A={a,b,c,d},R如图3.6―1(a)所示,则t(R)=R∪R2∪R3∪R4,如图3.3―1(b)所示.(本例即是3.2 节例2.) 理3.6―9 (a)如果R是自反的,那么s(R)和t(R)都是自反的 (b)如果R是对称的,那么r(R)和t(R)都是对称的 (c)如果R是传递的,那么r(R)是传递的

图 3.6―1

定理3.5―14 设R是集合A上的二元关系,那么 (a)rs(R)=sr(R) (b)rt(R)=tr(R) (c)ts(R) st(R) 证

(b)注意到ER=RE=R和对一切n∈N,En=E,可得 于是 (c)不难证明如果R1R2,那么s(R1)s(R2)和t(R1) t(R2).现相继地应用这一结论于对称闭包的性质:s(R) R. 得 ts(R) t(R)和sts(R) st(R)

3.6 次序关系 3.6.1 偏序集合 定义3.6―1 如果集合A上的二元关系R是自反的,反对称的和传递的,那么称R为A上的偏序,称序偶〈A,R〉为偏序集合.

如果R是偏序,〈A,R〉常记为〈A,〉, 是偏序符号,由于难以书写,通常写作≤,读做“小于或等于”,因为“小于或等于”也是一种偏序,故不会产生混乱.R是偏序时,aRb就记成a≤b. 如果R是集合A上的偏序,则 也是A上的偏序;如果用≤表示 ,可用≥表示R.〈A,≤〉和〈A,≥〉都是偏序集合,并互为对偶.

例1 (a)〈I,≤ 〉是偏序集合,这里≤表示整数中的“小于或等于”关系 (b)〈ρ(A), 〉是偏序集合,这里是集合间的包含关系 (c)A={2,4,6,8},D代表整除关系,M代表整倍数关系,则 D={〈2,2〉,〈4,4〉,〈6,6〉,〈8,8〉,〈2,4〉,〈2,6〉,〈2,8〉,〈4,8〉} M={〈2,2〉,〈4,4〉,〈6,6〉,〈8,8〉,〈4,2〉,〈6,2〉,〈8,2〉,〈8,4〉} 〈A,D〉,〈A,M〉都是偏序集合,且互为对偶

图 3.6―1

(c)A={1,2,…,12},〈A,整除〉的哈斯图为图3.7―4 例2 (a)P={1,2,3,4},〈P,≤〉的哈斯图为图7.4―2 (b)A={2,3,6,12,24,36},〈A,整除〉的哈斯图为图3.7―3 (c)A={1,2,…,12},〈A,整除〉的哈斯图为图3.7―4 图 3.6―2 图 3.7―3 图 3.6―3

图 3.6―4

定义3.6―2 设〈A,≤〉是一偏序集合,B是A的子集 (a)元素b∈B是B的最大元素,如果对每一元素x∈B,x≤b (b)元素b∈B是B的最小元素,如果对每一元素x∈B,b≤x 例3考虑在偏序“整除”下整数1到6的集合,其哈斯图为图3.6―5 (a)如果B={1,2,3,6},那么1是B的最小元素,6是B的最大元素 (b)如果B={2,3},因为2和3互相不能整除,那么B没有最小元素和最大元素 (c)如果B={4},那么4是B的最大元素,也是B的最小元素

图 3.6―5

定理3. 6―1 设〈A,≤〉是一偏序集合且BA,如果B有最大(最小)元素,那么它是唯一的证假设a和b都是B的最大元素,那么a≤b和b≤a 定理3.6―1 设〈A,≤〉是一偏序集合且BA,如果B有最大(最小)元素,那么它是唯一的证假设a和b都是B的最大元素,那么a≤b和b≤a.从≤的反对称性得到a=b.当a和b都是B的最小元素时,证明是类似的定义3.6―3设〈A,≤〉是一偏序集合,B是A的子集 (a) 如果b∈B,且B中不存在元素x,使b≠x且b≤x,那么元素b∈B叫做B的极大元素. (b)如果b∈B,且B中不存在元素x,使b≠x且x≤b,那么元素b∈B叫做B的极小元素

定义3.6―4设〈A,≤〉是一偏序集合,B是A的子集 (a)如果对每一b∈B,b≤a,那么元素a∈A叫做B的上界;如果对每一b∈B,a≤b,那么元素a∈A叫做B的下界. (b)如果a是一上界并且对每一B的上界a′有a≤a′,那么元素a∈A叫做B的最小上界,记为lub;如果a是一下界并且对每一B的下界a′有a′≤a,那么元素a∈A叫做B的最大下界,记为glb .

例4 (a)考虑偏序集合〈{〈1,1〉,〈1,0〉,〈0,1〉,〈0,0〉},≤〉,这里≤按 a,b〉≤〈c,d〉a≤c∧b≤d 规定,其哈斯图如图3.6―6 如果B={〈1,0〉},那么〈1,0〉是B的最小和最大元素,也是B的极大和极小元素.B的上界是〈1,0〉和〈1,1〉,〈1,0〉是最小上界.B的下界是〈0,0〉和〈1,0〉,〈1,0〉是最大下界.

(b)考虑偏序集合〈I,≤〉,设B={2i｜i∈N},那么B既没有最大元素和极大元素,也没有上界和最小上界 (b)考虑偏序集合〈I,≤〉,设B={2i｜i∈N},那么B既没有最大元素和极大元素,也没有上界和最小上界.B的最小元素和极小元素是0,B的下界集合是{i｜i∈I∧i≤0},0是最大下界. (c)考虑在偏序集合〈{2,5,6,10,15,30},整除〉,其哈斯图如图3.7―7设B是全集合{2,5,6,10,15,30},那么2和5都是B的极小元素,但B没有最小元素.集合B没有下界,所以没有最大下界.元素30是B的最大元素,极大元素,上界,最小上界.

图 3.6―6

图 3.6―7

定理3.6―2 如果〈A,≤〉是非空有限的偏序集合,则A的极小(大)元素常存在最大下界和最小上界也可能存在或不存在,但如果它们存在,则是唯一的. 定理3.6―3设〈A,≤〉是偏序集合且B A, 如果B的最小上界(最大下界)存在,那么是唯一的.

下述定理描述了存在于诸特异元素之间的某些关系 定理3.6―4设〈A,≤〉是偏序集合,B是A的子集 (a)如果b是B的最大元素,那么b是B的极大元素 (b)如果b是B的最大元素,那么b是B的lub (c)如果b是B的一个上界且b∈B,那么b是B的最大元素 证明 可由最大元素,极大元素和lub的定义直接得出,故略去.另外,读者不难给出表达最小元素,极小元素和glb间关系的定理

3.6.2 拟序集合 定义3.6―5如果集合A上的二元关系R是传递的和反自反的,那么R叫做A上的拟序.〈A,R〉称为拟序集合. 常借用符号＜表示拟序拟序是反对称的,虽然定义中没有明确指出,但容易证明这一点.因为如果xRy和yRx,由R的传递性得xRx,但这与R的反自反性矛盾,所以xRy∧yRx常假,于是 xRy∧yRx→x=y 常真,即R是反对称的.

例5 (a) 实数集合中的＜是拟序关系 (b) 集合族中的真包含是拟序关系 拟序集合和偏序集合是紧密相关的,唯一区别是相等关系E.下述定理将说明这一点 定理3.6―5在集合A上, (a) 如果R是一拟序,那么r(R)=R∪E是偏序 (b) 如果R是一偏序,那么R-E是一拟序

3.6.3 线序集合和良序集合 如果≤是一偏序,或a≤b或b≤a,我们说a和b是可比较的.偏序集合中的元素不一定都可比较,所以叫“偏”序.下面介绍的都是可比较的情况. 定义3.6―6 在偏序集合〈A,≤〉中.如果每一a,b∈A,或者a≤b,或者b≤a.那么≤叫做A上的线序(或全序),这时的序偶〈A,≤〉叫做线序集合或链.

例6 (a)P={,{a},{a,b},{a,b,c}},〈P,〉是线序集合,其哈斯图如图3.6―8所示 (b)〈I,≤〉是线序集合,其哈斯图(不完全)如图3.6―9所示 (c)设S是区间套的集合{［0,a)｜a∈R+},则〈S,〉是线序集合 (d)〈{1,2,3,6},整除〉不是线序集合;如果A是多于一个元素的集合,那么〈ρ(A),〉不是线序集合.

图3.6―8 图3.6―9

定义3.6―7 如果A上的二元关系R是一线序,且A的每一非空子集都有一最小元素,那么R叫做A上的良序,序偶〈A,R〉叫做良序集合 定理3.6―6〈N,≤〉是良序集合 证 我们必须证明N的每一非空子集S,在关系≤之下,都有一最小元素.因为S非空,所以在S中可以取一个数n,显然,S中所有不大于n的数形成非空集TS.如果T有最小数,那么这最小数就是S中的最小数,但从0到n只有n+1个自然数,于是T中所含的数最多是n+1个,所以T有最小数.因此定理成立.

例7 (a)每一有限线序集合是良序的 (b)线序集合〈I,≤〉不是良序集合,因为I的某些子集(诸如I自身)不包含最小元素 (c)关系≤是实数R的线序,但不是良序.例如子集A=(0,1］无最小元素.如果A中的a是最小元素,那么 也在A中,而 ≤a且不相等.这与假设a是线序关系≤下A的最小元素矛盾

3.6.4 词典序和标准序 由已知的线序和良序集合可以诱导出新集合S上的线序和良序.常见的有以下几种方法 (1)首先,使集合S上的每个元素与集合N(也可选其它已知的良序或线序集合)的唯一不同的元素对应,然后应用N上的良序≤定义S上的良序R定义方法如下: 如果a,b∈S,且a对应于n1,b对应于n2,那么aRb n1n2

(2) 应用N上的良序定义出Nn上的良序 例如n=2时,N2上的次序关系可如下定义: 〈a,b〉〈c,d〉a＜c∨(a=c∧bd)〈N2,〉是良序集合.关系“严格小于”可如下定义:〈a,b〉＜〈c,d〉〈a,b〉≤〈c,d〉∧〈a,b〉≠〈c,d〉类似地,应用I上的线序能定义出线序集合〈In,≤〉 (3) 应用字母表Σ上的线序,可定义出Σ上的通常叫词典序的线序.

定义3.6―8设Σ是一有限字母表,指定了字母表序(线序).如果x,y∈Σ, (a)x是y的词头,或 (b)x=zu和y=zv,这里z∈Σ*是x和y的最长公共词头,且在字母表序中u的第一个字符前于v的第一个字符,那么x≤y.≤叫做词典序 (4)由于〈N, 〉和有限线序集合都是良序集合,可应用它们定义出Σ上的一个良序,通常叫标准序

定义3.6―9 设Σ是一有限字母表,指定了字母表序,‖x‖表示x∈Σ的长度,如果x,y∈Σ*, (a)‖x‖＜‖y‖,或. (b)‖x‖=‖y‖且在Σ的词典序中x前于y.那么x≤y, ≤叫做标准序.

不论在词典序和标准序下,Σ的每一元素都有直接后继者.设Σ={a,b,c}且a≤b≤c,x∈Σ*.在标准序下 xa和xb的直接后继者分别是xb和xc, xc的直接后继者是ya,这里y是x的直接后继者.在词典序下x的直接后继者是xa在标准序下 xb和xc的直接前趋分别是xa和xb, xa的直接前趋是yc,这里y是x的直接前趋.在词典序下 xa的直接前趋是x,非a结尾的串都无直接前趋,例如b,ab,aab,…,但有无限个前趋

3.6.5 数学归纳法的推广 前章我们把数学归纳法第一,第二原理看作是自然数域上的一个推理规则,本小节我们把它推广到一般的良序集合对任一个自然数n,我们先取0,如果n≠0,取0的后继者1,如果n≠1,再取1的后继者2,如此进行下去,最终会得出n. 给定一个良序集合,如果对它的任一元素x,我们先取该集合的最小元素m0,如果x≠m0,取m0的后继者m1,如果x≠m1,再取m1的后继者m2,如此以往,最终会得出x,那么就称这样的良序集合是“像自然数”的.

例 8 (a) 设Σ={a,b},良序集合〈Σ. ,标准序〉是像自然数的 例 8 (a) 设Σ={a,b},良序集合〈Σ*,标准序〉是像自然数的.因为定长的串的个数有限,给定任一个串x,在x之前的串的个数有限,所以从Λ开始,反复取后继者,终可得出x. (b)良序集合〈N×N,≤〉不像自然数,这里≤按上一小节规定.因为有许多元素没有直接前趋,例如〈5,0〉就是这样,因而有无限个元素前于〈5,0〉,所以,从〈0,0〉开始,反复地取后继者,不可能取得〈5,0〉.

像自然数的良序集合,可以应用数学归纳法第一原理 像自然数的良序集合,可以应用数学归纳法第一原理.因为第一原理是建立在后继运算上,而这种良序集合的每一元素都可通过重复地取后继者得到,设m0是该良序集合〈S,≤〉的最小元素,S(x)是元素x的后继者,则推理规则如下: 这样,如果我们能证明m0有性质P,和当x有性质P时, 则S(x)有同样性质,那么我们能得出S的每一元素有性质P.

对不像自然数的良序集合,不能应用数学归纳法第一原理,因为这种良序集合的有些元素不能由后继运算得到. 但对它可应用数学归纳法第二原理 对不像自然数的良序集合,不能应用数学归纳法第一原理,因为这种良序集合的有些元素不能由后继运算得到.但对它可应用数学归纳法第二原理.第二原理是建立在良序集合上的,适用于一切良序集合.设〈S,≤〉是良序集合,＜表示≤-E(即x＜y表示x≤y且x≠y),则推理规则如下:

这样,若每一小于x的元素有性质P,如果我们能证明任意元素x有性质P,那么我们能得出S的每一元素有性质P. 下面证明良序集合上这个推理规则是有效的 假设我们能证明前提

并假设T是S的子集,由S中没有性质P的所有元素组成. 因为S是良序的,如果T≠ ,那么T必有最小元素m;这得出对所有x＜m,P(x)是真 并假设T是S的子集,由S中没有性质P的所有元素组成.因为S是良序的,如果T≠ ,那么T必有最小元素m;这得出对所有x＜m,P(x)是真.可是,前提断言如果对所有x＜m,P(x)是真,那么P(m)是真,导致矛盾,我们得出T必须是空.因此,第二原理结论xP(x)是真,这得出对任意良序集合〈S,≤〉,数学归纳法第二原理是有效的推理规则 .

例9〈Q+,≤〉是线序集合.现说明在此线序集合中第二原理不是有效推理规则设谓词P(x)表示“x小于或等于5”. (i)当x≤5时, y［y＜x→P(y)］是真,P(x)也真. 所以 (ii)当x＞5时, 由于x＞5,所以存在有理数y0,使5＜y0＜x.这样P(y0) 是假,因而

是假,所以 是真 综合(i)和(ii),得: 在论述域Q+上, x ［ y(y＜x→P(y))→P(x)］是真,但结论 x P(x)是假.这说明第二原理不能应用于线序集合〈Q+,≤〉

3.7 等价关系和划分 3.7.1 等价关系 二元关系的另一重要类型是等价关系,其定义如下: 3.7 等价关系和划分 3.7.1 等价关系 二元关系的另一重要类型是等价关系,其定义如下: 定义3.7―1如果集合A上的二元关系R是自反的,对称的和传递的,那么称R是等价关系设R是A上的等价关系,a,b,c是A的任意元素.如果aRb(即〈a,b〉∈R),通常我们记作a～b,读做“a等价于b”.

定义3.7―2设k是一正整数而a,b∈I.如果对某整数m,a-b=m·k,那么a和b是模k等价,写成 a≡b(modk) 整数k叫做等价的模数 定理3.7―1 模k等价是任何集合AI上的等价关系 证如果A=,例1(c)已指出它是等价关系.如果A≠,则 (i)自反的.因为对任一a,a-a=0·k,得出a≡a(modk)

(1)因为R具有自反性,所以A上每一元素都和自己等价.反映到R的有向图上,每一结点都有一自回路. (2)因为R具有对称性,所以如果a等价于b,则b也等价于a,反映在有向图上,如果有从a到b的弧,那么也有从b到a的弧. (3)因为R具有传递性,所以如果a等价于b,b等价于c,则a等价于c.反映在有向图上,如果从a到c有一条路径,则从a到c有一条弧.

例1 (a) 同学集合A={a,b,c,d,e,f,g},A中的关系R是“住在同一房间” 例1 (a) 同学集合A={a,b,c,d,e,f,g},A中的关系R是“住在同一房间”.这是等价关系,因为(i)任一个人和自己同住一间,具有自反性.(ii)若甲和乙同住一间,则乙和甲也同住一间,具有对称性.(iii)若甲和乙同住一间,乙和丙同住一间,则甲和丙也同住一间,具有传递性 现假设a和b同住一间,d,e,f同住一间,c住一间.则 R={ 〈a,a〉,〈a,b〉,〈b,a〉,〈b,b〉,〈c,c〉,〈d,d〉,〈e,e〉,〈f,f〉,〈d,e〉,〈e,d〉,〈e,f〉,〈f,e〉,〈d,f〉,〈f,d〉}

其有向图如图3.7―1所示 (b)数中的相等关系,集合中的相等关系,命题演算中的关系等都是等价关系 (c)空集合中的二元关系R是等价关系,因为 (i) x(x∈→xRx) (ii) x y［x∈∧y∈∧xRy→yRx］ (iii) x y z［x∈∧y∈∧z∈∧xRy∧yRz→xRz］

图 3.7―1

(ii)对称的.因为a≡b(modk)时,存在某m∈I,使a-b=m·k,于是b-a=-m·k,因此b≡a(modk) (iii)传递的.设a≡b(modk)和b≡c(modk),那么存在m1,m2∈I,使a-b=m1k和b-c=m2·k,将两等式两边相加,得a-c=(m1+m2)·k,所以a≡c(modk)

例2 (a)若R是I上模4等价关系,则 ［0］4={…-8,-4,0,4,8,…} ［1］4={…-7,-3,1,5,9,…} ［2］4={…-6,-2,2,6,10,…} ［3］4={…-5,-1,3,7,11,…}

(b)若R是I上模2等价关系,则 ［0］2={…-4,-2,0,2,4,…} ［1］2={…-3,-1,1,3,5,…} 每一集合中的数相互等价 (c)时钟是按模12方式记数的设备,13点钟和1点钟有相同的记数.

定义3.7―3 设R是集合A上等价关系,对每一a∈A,a关于R的等价类是集合{x｜xRa},记为［a］R,简记为［a］;称a为等价类［a］的表示元素.如果等价类个数有限,则R的不同等价类的个数叫做R的秩;否则秩是无限的对每一a∈A,等价类［a］R非空,因为a∈［a］R.

例 3 (a)如图3.8―2,设A={a,b,c,d,e,f},R={〈a,a〉,〈b,b〉,〈c,c〉,〈a,b〉,〈b,a〉,〈a,c〉,〈c,a〉,〈b,c〉,〈c,b〉,〈d,d〉,〈e,e〉,〈d,e〉,〈e,d〉,〈f,f〉}, 则等价关系R的等价类如下: ［a］=［b］=［c］={a,b,c} ［d］=［e］={d,e} ［f］={f}. 等价关系R的秩是3

图 3.7―2

(b) I上模4等价的等价类是［0］4,［1］4,［2］4,［3］4(参看例2(a)),I上模2等价的等价类是［0］2, (c) 集合A上相等关系的秩等于A的元素个数. 定理3.7―2 设R是非空集合A上的等价关系,aRb 当且仅当［a］=［b］ 证 充分性.因为a∈［a］=［b］,即a∈［b］,所以,aRb.

定理3.7―3 设R是集合A上的等价关系,则对所有a,b∈A,或者［a］=［b］,或者［a］∩［b］= 证如果A=,断言无义地真,现设A≠ .若［a］∩［b］≠ , 则存在某元素c∈［a］和c∈［b］.根据定理3.5―2得［a］=［c］=［b］.又因［a］和［b］都非空,［a］∩［b］= 和［a］=［b］不能兼得.因而定理得证

定义3.7―4给定非空集合A和非空集合族π={A1,A2,…,Am},如果 ,那么称集合族π是A的覆盖. 定理3.7―4设R是集合A上的等价关系,则

定理3.7―5设R1和R2是集合A上的等价关系,那么R1=R2当且仅当{［a］R1｜a∈A}={［a］R2｜a∈A} 证 必要性.因为R1=R2,所以对任意a∈A,有 ［a］R1={x｜xR1a}={x｜xR2a}=［a］R2 故{［a］R1｜a∈A}={［a］R2｜a∈A} 充分性.因为{［a］R1｜a∈A}={［a］R2｜a∈A},得［a］R1=［a］R2,所以,对任意x∈A, 有 xR1a x∈［a］R1 x∈［a］R2 xR2a 又a是任意的,故R1=R2.证毕

定理3.7―6 设R是A上的二元关系,设R′=tsr(R)是R的自反对称传递闭包,那么 (a)R′是A上的等价关系,叫做R诱导的等价关系 (b)如果R″是一等价关系且R″R,那么R″R′.就是说,R′是包含R的最小等价关系.

证 (a) 根据闭包运算的定义和定理3.8―9可得 r(R)是自反的, sr(R)是自反的和对称的, tsr(R)是自反的,对称的和传递的. 因此,R′=tsr(R)是A上的等价关系 (b)设R″是任意的包含R的等价关系,那么R″是自反的和对称的,所以R″R∪ ∪E=sr(R).因为R″是传递的且包含sr(R),所以R″包含tsr(R).证毕

例4 设A={a,b,c}且A上的二元关系R如图3.7―3所示,则tsr(R)如图3.7―4所示. 图3.7―3 图3.7―4

3.7.2 划分 定义3.7―5给定非空集合A和非空集合族π={A1,A2,…,Am},如果 (i)π是A的覆盖,即 (ii)Ai∩Aj=或Ai=Aj(i,j=1,2,…,m)那么集合族π叫做集合A的一个划分划分的元素Ai称为划分π的块,如果划分是有限集合,则不同块的个数叫划分的秩.若划分是无限集合,则它的秩是无限的.划分的秩就是划分的大小 .

例5 (a) 设S={1,2,3} A= {1,2},{2,3} B= {1},{1,2},{1,3} C= {1},{2,3} D= {1,2,3} E= {1},{2},{3} F= {1},{1,2}}

则C,D,E都是S的划分,它们的秩分别是2,1,3,A,B是S的覆盖但不是划分,F不是S的覆盖也不是S的划分 π={A1,A2,A3,A4}是A的划分,秩是4. (c)集合族 {x,-x}|x∈I 是I的秩无限的一个划分 (d)设A是非空集合,那么ρ(A)-{}是非空集合族,这个集合族是A的一个覆盖,而不是A的划分,除非A是单元素集合.

图 3.7―5

定理3.7―7 设A是非空集合,R是A上的等价关系.R的等价类集合{［a］R｜a∈A}是A的划分 定义3.7―6 设R是非空集合A上的等价关系,称划分{［a］R｜a∈A}为商集A/R,也叫A模R由商集的定义和定理3.5―5立即可得: 定理3.7―8 设R1和R2是非空集合A上的等价关系,那么R1=R2当且仅当A/R1=A/R2

定理3.7―9 设π是非空集合A的一个划分,则A上的二元关系:

证 (a) R是自反的.因为A的每一元素是在π的某块B中,所以,对每一a∈A,aRa (b) R是对称的.假设aRb,那么有某块B∈π,使a∈B和b∈B.所以bRa (c) R是传递的.假设aRb和bRc,那么存在B1∈π和B2∈π,使a,b∈B1和b,c∈B2,即b∈B1∩B2,由划分的定义,要么B1∩B2= ,要么B1=B2,所以B1=B2.因此,c∈B1,aRc

定理3.7―10 设π是非空集合A上的划分,R是A上的等价关系,那么,π诱导出R当且仅当R诱导出π 设 a是A的任一元素,并设B和B′分别是π和π′的块,使a∈B和B′.那么对任一b b∈B aRbR的定义 ［a］R=［b］R 定理3.8―2 b∈B′ b∈［b］R=［a］R=B′

所以,B=B′.因为a是A的任一元素而π和π′都是A的覆盖,故π=π′. 充分性.假设R诱导出π,π诱导出等价关系R′.那么对任意a,b∈A aRb［a］R=［b］ R 定理3.8―2  a,b∈［a］R b∈［b］R=［a］R和a∈［a］R  B(B∈π∧a∈B∧b∈B) 上一行的改述  aR′b R′的定义 因此,R=R′.证毕.

例6设A={a,b,c,d,e},R={〈a,a〉,〈a,b〉,〈a,c〉,〈b,b〉,〈b,a〉,〈b,c〉,〈c,c〉,〈c,a〉,〈c,b〉,〈d,d〉,〈d,e〉,〈e,e〉,〈e,d〉},其有向图如图3.5―6所示,则R诱导的划分π={{a,b,c},{d,e}}.反之,若A的划分π={{a,b,c},{d,e}},则π所诱导的等价关系R={a,b,c}×{a,b,c}∪{d,e}×{d,e}={〈a,a〉,〈a,b〉,〈a,c〉,〈b,b〉,〈b,a〉,〈b,c〉,〈c,c〉,〈c,a〉,〈c,b〉,〈d,d〉,〈d,e〉,〈e,e〉,〈e,d〉}

图 3.7―6

3.7.3 划分的积与和 定义 3.7―7设π和π′是非空集合A上的划分.如果π′的每一块都包含于π的一块中,那么说π′细分π,或说π′是π的细分.如果π′细分π,且π≠π′,那么说π′是π的真细分 例7(a)设A={a,b,c},π={{a,b},{c}}, π′={{a},{b},{c}},则π′细分π (b) 把一张纸A撕碎得A的划分π,再撕碎,就是将π细分,所得之π′仍是A的划分(参看图3.7―7)

(c) I上模4等价诱导出的划分{［0］4,［1］4,［2］4,［3］4}细分模2等价诱导出的划分{［0］2,［1］2} ［3］4两者包含于［1］2中.

图 3.7―7

定理3.7―11 设π和π′是非空集合A上的划分,并设R和R′分别是由π和π′诱导的等价关系.那么π′细分π当且仅当R′ R 证我们首先证明如果π′细分π,那么R′R假设aR′b,那么有π′的某块B′使a,b∈B′.因为π′细分π,有π的一块B使B′B.所以a,b∈B.这得出aRb,因此R′R .

其次证明如果R′R,那么π′细分π. 设B′是π′的一块,且a∈B′,那么 B′=［a］R′={x｜xR′a}.但对每一x,如果xR′a,那么xRa,因为R′R.所以{x｜xR′a}{x｜xRa},即 ［a］R′［a］R,用B表示［a］R;那么B是π的一块 且B′B,这证明了π′细分π.

等价关系的大小,由该关系所含的序偶个数计算;划分的大小,由划分的秩计算,本定理说明大的等价关系诱导出小的划分 等价关系的大小,由该关系所含的序偶个数计算;划分的大小,由划分的秩计算,本定理说明大的等价关系诱导出小的划分.大的划分诱导出小的等价关系,但这是在π′细分π或R′R的条件下才能成立,如无此条件,一般不成立 定理3.7―12 设F是非空集合A上划分的族,则关系细分是F上的偏序

定义3.7―8设π1和π2是非空集合A的划分.π1和π2的积,表示为π1·π2是A的划分π,它使 (i)π细分π1和π2两者 (ii)如果π′细分π1和π2,那么π′细分π 本定义概括地说就是π1·π2是细分π1和π2的最小划分下述二定理表明二个划分的积常存在且是唯一的. 定理3.7―13设R1和R2是非空集合A的划分π1和π2所诱导出的等价关系.那么R=R1∩R2诱导出π1和π2的积的划分π.

定理3.7―14 设π1和π2是非空集合A的划分,则π1和π2的积是唯一的. 证 假设π和π′都是π1和π2的积划分,那么从定义3.8―8知π和π′彼此细分,根据定理3.8―12,关系“细分”是反对称的,所以, π=π′. 例8 假定一张纸画上红线和绿线,按红线剪开得划分π1,按绿线剪开得划分π2,那么按红线和绿线剪开产生积划分π1·π2(图3.7―8).

图 3.7―8

定义3.7―9 设π1和π2是非空集合A的划分,π1与π2的和记为π1+π2,是一划分π,它使 (i)π1和π2细分π (ii)如果π′是A的划分,使π1和π2细分π′,那么π细分π′本定义概括地说就是π1+π2是π1和π2所细分的最大划分下述二定理表明二划分之和常存在且唯一.

定理3. 7―15 设R1和R2是非空集合A上的划分π1和π2所诱导出的等价关系. 定义关系R是R1∪R2的传递闭包 定理3.7―15 设R1和R2是非空集合A上的划分π1和π2所诱导出的等价关系.定义关系R是R1∪R2的传递闭包. R=(R1∪R2)+=t(R1∪R2) 那么,R是A上的等价关系,划分A/R是π1和π2的和. 证 R1∪R2是自反的和对称的,因为并运算保持这些特性.所以根据定理3.8―6, R=t(R1∪R2)=tsr(R1∪R2) 是包含R1和R2的最小的等价关系.

定理3.7―16设π1和π2是非空集合A的划分,π1和π2的和是唯一的. 例9假定一张纸上的红线表示划分π1,绿线表示划分π2,那么,按既是红线又是绿线的线剪开就产生和划分π1+π2(图3.7―9)

图 3.7―9