第3章
集合






本章将用谓词逻辑表达集合论中的基本概念及其运算，并根据命题演算与集合运算之间的联系，构成一种集合代数。它类似于命题代数，同时还将给出数学中常用的重要证明方法——数学归纳法。最后讨论多重序元与笛卡儿乘积等重要概念，以便为学习后续理论知识打下基础。

3.1集合的基本概念

集合是不能严格定义的原始概念，对它只能给予直观的描述。一般来说，把具有共同性质的一些东西或客体汇成一个整体，就形成了一个集合(set)。

举例如下。

(1) 全体中国人的集合。

(2) 全体素数的集合。

(3) 方程x2+x+1=0的实根的集合。

(4) 直线y=2x-5上的点的集合。

上述4种集合中的客体(或称为元素)均具有共同的“性质”。但是，一支钢笔、一只老鼠汇成一个整体也可以看成一个集合，而这种集合中的客体就不具有共同“性质”了。一般来说，研究这种集合没有实际意义。

属于集合的任何客体称为该集合的成员(member)或元素(element)。

通常用大写英文字母表示一个集合，用小写英文字母表示集合中的客体或元素。若元素a属于集合A，记作a∈A，读为“a属于A”； 反之，若元素a不属于集合A，记作aA，读为“a不属于A”。

例如，令A={a,b,d}，则a∈A，b∈A，d∈A，常简记为a,b,d∈A，但cA，eA或c,eA。

为叙述方便，给出几种常见的集合，以后遇到此类集合不再重述。

Q——有理数(rational number)集合；

N——自然数(natural number)集合(包括0)；

I——整数(integer)集合；

R——实数(real number)集合；

Nm——小于m的自然数集合；

I+——正整数集合；

I-——负整数集合。



定义3.1.1设A为任意集合。

(i) 集合A含有的元素个数，称为基数(cardinality)，记为card(A)或|A|。

(ii) 若|A|=0，即A中不包含任何元素，则称A为空集(empty set)，记为。

(iii) 若|A|为某个自然数，则称A为有限集(finite set)。

(iv) 若|A|为无穷大，则称A为无限集(infinite set)。

(v) 若|A|≠0，则称A为非空集(nonempty set)。




集合与元素的关系是从属关系，即一个元素属于或不属于某集合。为此，对集合中所含元素必须给予直观、确切的描述，其常用方法有下列3种。

1. 枚举法(或称列举法，list notation)

依照任意一种次序，不重复地列举出集合中的全部元素，并用一对花括号括起来，元素间用逗号分开。

例如，A={1,3,5,7}，B={a,a2,a3,a4}，这种方法比较直观。

2. 部分列举法(partially list notation)

依照任意一种次序，不重复列出集合中的部分元素，元素间用逗号分开。但这部分元素充分体现出该集合的元素在上述次序下的构造规律，从而能够容易地得出该集合中的任意一个未列出的元素。未列举出的元素用“…”表示，然后用一对花括号{}括起来。例如，

N={0,1,2,3,…}

I={…,-3,-2,-1,0,1,2,3,…}

3. 构造法(或称谓词公式法，set builder notation)

如果P(x)是表示元素x具有某种性质P的谓词，则所有具有性质P的元素就构成一个集合，记为A={x|P(x)}。显然，元素a∈AP(a)为真。例如： 


A={x|x∈R∧x2-3x+2=0}={1,2}
B={x|(x=1)∨(x=3)∨(x=a)}={1,3,a}
C={x|x是正偶数}={2,4,6，…}

对集合必须注意以下几点。

(1) 集合中的元素必须是确定的，即对集合A，任一元素a或者属于A或者不属于A，两者必具其一，且仅具其一。

(2) 集合中的每个元素均不相同，如{a,b,b,c,c,d}与{a,b,c,d}表示同一个集合。

(3) 对集合中的元素不做任何限制，甚至一个集合可作为另一个集合的元素。例如，A={1,2,{a,b}}，其中集合{a,b}是集合A的一个元素。显然，有{a,b}∈A，但a,bA。


公理3.1.1给定两个集合A和B，当且仅当A和B具有同样的成员或元素，A和B是相等的(equal)，记为A=B； 否则，称为A和B不相等，记为A≠B。




集合A和B相等这个公理可用谓词公式描述如下。


A=B(x)(x∈Ax∈B)

或


A=B(x)(x∈A→x∈B)∧(x)(x∈B→x∈A)

举例如下。

(1) {a,b,c}={c,a,b}={a,a,b,c}。

(2) 设P={{a,b},c}，Q={a,b,c}，则P≠Q。

(3) 设A={x|x(x-1)=0}，B={0,1}，则A=B。

(4) {1,3,5,…}={x|x是正奇数}。

(5) {a}≠{{a}}。


定义3.1.2设A和B是两个任意集合。如果A的每个元素均属于B，则称A是B的子集(subset)，或A包含于B，或B包含A，记为AB或BA。




A是B的子集的定义也可用谓词公式描述为AB(x)(x∈A→x∈B)。

例如，令A={1,2,3}，B={1,2}，C={1,2,4}，则BA但CA。

根据子集的定义立即可以得出下面两个性质。

① 自反性： AA。

② 传递性： (AB)∧(BC)(AC)。


定理3.1.1集合A和B相等的充要条件是它们互为子集，即A=BAB∧BA。




证(充分性)若AB，BA，证明A=B。现假设A≠B，则A和B的元素不完全相同，至少有一个元素x∈A，但xB，这与AB矛盾； 或至少有一个元素x∈B，但xA，这又与BA相矛盾。故A和B必然相等。

(必要性)若A=B，证明AB，且BA。因为A和B相等，所以它们的元素相同，即(x)(x∈A→x∈B)为真，且(x)(x∈B→x∈A)也为真，故AB，且BA成立。■

此定理建立了集合间的相等与包含关系，当证明两个集合是否相等时，常常使用这个定理，即不直接证明A=B，而是证明AB，且BA。

在证明此定理的充分性时，使用了反证法(proof by contradiction)，这是数学中经常使用的重要证明方法。有些证明直接求证困难较大，这时可考虑使用反证法，甚至有些问题不使用反证法便不能得到证明。


定义3.1.3如果集合A的每个元素均属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集(proper subset)，记为AB。




A是B的真子集的定义可用谓词逻辑描述如下。

① AB(x)(x∈A→x∈B)∧(x)(x∈B∧xA)。

② ABAB∧A≠B。

例如，自然数集合N是整数集合I的真子集。


定理3.1.2对任意集合A，有A，即空集是任意集合的子集。




证明(方法1) 使用反证法。假设A是假，则至少有一个元素x∈，且xA，而空集不包含任何元素，所以这种假设不成立。因此，必有A。

(方法2) 设x是集合A中的任意元素，由空集的定义可知，x∈为假，由逻辑联结词“→”的定义可知，x∈→x∈A为真。由x的任意性，根据全称推广规则有(x)(x∈→x∈A)为真，故A。■


定理3.1.3空集是唯一的。




证利用反证法。假设有两个不同的空集1和2，因为1是空集，所以必有12； 又因为2是空集，所以又必有21。即1和2互为子集，由定理3.1.1可知，1=2。因此假设不成立，即空集是唯一的。■


定义3.1.4如果有一个集合包含所要讨论的全部元素，则把该集合称为全集(universal set)，记为U或E。




全集是一个相对的概念，它随所要研究的范围不同而不同。如统计全国人口，则可以把全国的人的集合看作全集，而各省、市范围内的人的集合都是E的子集。但是，若统计全省人口，则可以把该省的人的集合看作全集。在任何一个集合论的应用中，所研究集合的元素总是属于某个大集合，它就被称为全集或论域。

有了全集的概念，元素与集合间关系的意义就更明显了，如对于元素a，可能有a∈A或aA，但必有a∈E。

显然，空集和全集可分别用谓词公式描述为


={x|P(x)∧�瘙
綈P(x)}，E={x|P(x)∨�瘙
綈P(x)}


定义3.1.5完全以集合为元素的集合，称为集类或集合族(family of sets)。




例如，设A={a,b,c,d}，令A*是A的含3个元素的那些子集构成的集类，则


A*={{a,b,c},{a,b,d},{a,c,d},{b,c,d}}


根据定理3.1.2，空集是任意集合的子集，即A； 对任意集合A，AA。一般来说，任意非空集合A至少有两个子集，一个是空集，另一个是它本身A。

【例3.1.1】设A={a,b,c}，试求集合A的所有子集。

解共有8个子集： A0=，A1={a}，A2={b}，A3={c}，A4={a,b}，A5={a,c}，A6={b,c}，A7=A={a,b,c}。


定义3.1.6由集合A的全部子集所组成的集类，称为A的幂集(
power set)，记为ρ(A)，即ρ(A)={Ai|AiA}。




例如，设A={a,b,c}，则ρ(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。


定理3.1.4如果有限集A有n个元素，则其幂集ρ(A)有2n个元素，即|ρ(A)|=2n。




证在A中任取一个元素构成的子集共有C1n个，任取两个元素构成的子集共有C2n个，以此类推，直至从A中取n个元素构成的子集共有Cnn个。此外，空集也是A的一个子集，因此，全部子集的数目为


|ρ(A)|=1+C1n+C2n+…+Cnn


由二项式定理，有


(x+y)n=xn+C1nxn-1y+C2nxn-2y2+…+Cnnyn

令x=y=1，得2n=1+C1n+C2n+…+Cnn，故|ρ(A)|=2n成立。■

下面引进一种编码用来唯一地表示一个有限集合幂集的元素，这种方法称为子集的编码表示法，它将为求一个有限集的幂集带来极大方便。众所周知，一个集合中的元素的排列次序是无关紧要的，但是为了便于在计算机上表示集合，可以给元素编定次序，从而可以用二进制数为下标来确定集合中每一元素的位置。显然，对一个含有n个元素的集合A，则需要n位二进制数作为下标，对A的每个子集B，若第i位上记入1，则该位置对应的元素属于该子集； 否则，该元素不属于该子集。设集合A={a1,a2,a3,…,an}，再令


J=i|00…0n个≤i≤11…1n个


则ρ(A)={Ai|i∈J}。例如，A={a,b,c}，则J={i|000≤i≤111}，ρ(A)={Ai|i∈J}，其中

A0=A000=，
A1=A001={c}，
A2=A010={b}，
A3=A011={b,c}，

A4=A100={a}，
A5=A101={a,c}，
A6=A110={a,b}，
A7=A111={a,b,c}。

把集合J叫作加标集合(indexed set)。显然，可用这种编码方法确定具有n个元素的集合的各子集。实际上，这种方法与1.8节中介绍的求极大项和极小项的方法很相似。


习题3.1

(1) 列出下列集合的全部元素。

① A={x|x∈N,3<x<12}。

② B={x|x∈N,x是偶数，x<15}。

③ C={x|x∈N,4+x=3}。

④ D={x|x∈N,y∈N,x+y=10}。

(2) 用谓词公式法表示下列集合。

① {2,4,6,8,…}。

② {能被5整除的整数}。

③ {100，101，102，…，200}。

④ {a,a2,a3,…,a10}。

(3) 判别下列命题是真的还是假的，并简单说明理由。

① 。

② ∈。

③ {}。

④ ∈{}。

⑤ {a,b}{a,b,c,{a,b,c}}。

⑥ {a,b}∈{a,b,c,{a,b,c}}。

⑦ {a,b}{a,b,{{a,b}}}。

⑧ {a,b}∈{a,b,{{a,b}}}。

(4) 举出3个集合A,B,C，使A∈B、B∈C，但AC。

(5) 对任意集合A,B,C，判断下述每个论断是否正确，并论证你的答案。

① 若A∈B，BC，则A∈C。

② 若A∈B，BC，则AC。

③ 若AB，B∈C，则A∈C。

④ 若AB，B∈C，则AC。

(6) 求下列集合的幂集。

① {a}。

② {{a}}。

③ {,{}}。

(7) 设A={a,{a}}，下列各式成立吗?

① {a}∈ρ(A)。

② {a}ρ(A)。

③ {{a}}∈ρ(A)。

④ {{a}}ρ(A)。

(8) 设A={a1,a2,a3,a4,a5}，
在子集的编码表示法中，
由A6，A21所表示的A的子集是什么?子集{a2,a3}和{a1,a4,a5}应如何表示?

3.2集合的运算

本节将介绍集合的几种基本运算。集合运算是指按照一定的规则对一个或多个集合进行运算而产生一个新的集合。这几种基本运算是： 交运算A∩B； 并运算A∪B； 差运算A-B； 补运算~A； 对称差运算AB。下面将给出集合的5种基本运算规则，并用一种称为文氏图或文恩图(Venn diagram)的方法来直观地表示这5种基本运算的运算结果。值得注意的是，我们总是在一定的“范围”内讨论问题，这个“范围”指的就是前面介绍的全集，它包含了所要讨论的全部元素，至于全集究竟是什么并不重要。



定义3.2.1设A和B是两个任意集合，全集为E，则：

(i) A∩B={x|x∈A∧x∈B}，叫作A和B的交集(intersection)；

(ii) A∪B={x|x∈A∨x∈B}，叫作A和B的并集(union)；

(iii) A-B={x|x∈A∧xB}，叫作A和B的差集(difference)，又称B对A的相对补集(the relative complement)；

(iv) ~A=E-A={x|x∈E∧xA}，叫作A的绝对补集(complement)，简称补集；

(v) AB=(A-B)∪(B-A)=(A∪B)-(A∩B)，叫作A和B的对称差集(symmetric difference)或环和(cycle sum)。




全集的引入使我们得以利用图示的方法来研究问题，所用的图称为文氏图。文氏图是一种利用平面上点的集合构成的对集合的图示。全集E用一个矩形的内部表示，其他的集合(E的子集)则用矩形内的圆面来表示。下面给出上述5种基本运算结果的文氏图表示，其阴影部分表示运算结果，如图3.2.1所示。



图3.2.15种运算的文氏图表示



【例3.2.1】设E={0,1,2,3,4,5}，A={1,2,5}，B={2,4}，则

A∩B={2}，A∪B={1,2,4,5}，

A-B={1,5}，B-A={4}，

~A={0,3,4}，~B={0,1,3,5}，AB={1,4,5}。


定理3.2.1设A，B和C是任意集合，则有：

(i) AA∪B，BA∪B；

(ii) A∩BA，A∩BB；

(iii) A-B=A∩(~B)；

(iv) AC，BCA∪BC；

(v) AB，ACAB∩C。




这个定理的证明很容易，下面仅给出(iii)式的证明，其他留给读者练习。

证要证明A-B=A∩~B，即证明A-BA∩(~B)，且A∩(~B)A-B。

先证明A-BA∩(~B)。对任意的x∈A-B，有


x∈A∧xBx∈A∧x∈~Bx∈A∩(~B)

即


A-BA∩(~B)


再证明A∩(~B)A-B。对任意的x∈A∩(~B)，有


x∈A∩x∈(~B)x∈A∧xBx∈A-B

故


A∩(~B)A-B

所以，A-B=A∩(~B)。■

A-B=A∩(~B)是一个重要的公式，在集合的运算中经常用到，它的意义在于将相对补运算转换为绝对补和交运算。为书写方便，将A∩(~B)简写为A∩~B。

下面给出各运算的性质。

(1) 交运算的性质。

① A∩A=A。(等幂律)

② A∩=。(零律)

③ A∩E=A。(同一律)

④ A∩B=B∩A。(交换律)

⑤ (A∩B)∩C=A∩(B∩C)。(结合律)

若A和B没有共同的元素，则称A和B不相交(disjoint)，即A∩B=。

(2) 并运算的性质。

① A∪A=A。(等幂律)

② A∪=A。(同一律)

③ A∪E=E。(零律)

④ A∪B=B∪A。(交换律)

⑤ (A∪B)∪C=A∪(B∪C)。(结合律)



定理3.2.2设A，B和C是任意集合，则有：

(i) A∩(B∪C)=(A∩B)∪(A∩C)；

(ii) A∪(B∩C)=(A∪B)∩(A∪C)。(分配律)




证(ii)  对任意的x∈A∪(B∩C)x∈{x|x∈A∨x∈(B∩C)}

x∈{x|x∈A∨(x∈B∧x∈C)}

x∈{x|(x∈A∨x∈B)∧(x∈A∨x∈C)}

x∈{x|x∈A∪B∧x∈A∪C}

x∈(A∪B)∩(A∪C)

再由x的任意性可知，A∪(B∩C)=(A∪B)∩(A∪C)成立。

(i) 式的证明与此类似，请读者自己完成。■


定理3.2.3设A和B是任意集合，则有：

(i) A∪(A∩B)=A；

(ii) A∩(A∪B)=A。(吸收律)




证(i) A∪(A∩B)=(A∩E)∪(A∩B)=A∩(E∪B)=A∩E=A。

(ii) 式的证明与此类似，请读者自己完成。■

(3) 补运算的性质。

① ~(~A)=A。

② ~E=。

③ A∪~A=E。

④ A∩~A=。


定理3.2.4(i) ~(A∪B)=~A∩~B；

(ii) ~(A∩B)=~A∪~B。(德·摩根律)




证(i) 对任意的x∈~(A∪B)x∈{x|x∈~(A∪B)}

x∈{x|x∈E∧x(A∪B)}

x∈{x|x∈E∧(xA∧xB)}

x∈{x|(x∈E∧xA)∧(x∈E∧xB)}

x∈{x|x∈~A∧x∈~B}

x∈{x|x∈~A∩~B}

x∈~A∩~B

再由x的任意性可知，~(A∪B)=~A∩~B。

(ii) 同理可证，请读者自己完成。■


定理3.2.5设A、B和C是任意集合，则有A∩(B-C)=(A∩B)-(A∩C)。




证左＝A∩(B-C)=A∩(B∩~C)=A∩B∩~C


右=(A∩B)-(A∩C)=(A∩B)∩~(A∩C)
=(A∩B)∩(~A∪~C)=(A∩B∩~A)∪(A∩B∩~C)
=∪(A∩B∩~C)=A∩B∩~C


所以，原式成立。■


定理3.2.6设任意两个集合A、B，若AB，则：

(i) ~B~A；

(ii) (B-A)∪A=B。




证(ii) (B-A)∪A=(B∩~A)∪A

=(B∪A)∩(~A∪A)=(B∪A)∩E

=B∪A

=B(条件AB)

(i) 式的证明请读者自己完成。■

(4) 对称差的性质。

① AB=BA。(交换律)

② (AB)C=A(BC)。(结合律)

③ A=A。

④ AA=。

【例3.2.2】证明： AB当且仅当A∪B=B，或A∩B=A。

证在此只证明AB当且仅当A∪B=B。

(必要性)已知AB，证明A∪B=B。先证A∪BB。对任意的x∈A∪B，有


x∈A∪Bx∈A∨x∈B
x∈B∨x∈B(条件AB)
x∈B

即A∪BB。

再证BA∪B。这是显然的。

综上，知A∪B=B。

(充分性)已知A∪B=B，证明
AB。对任意的x∈A，有


x∈Ax∈A∪B
x∈B(条件A∪B=B)

所以，AB。

综上，知AB当且仅当A∪B=B。■

为了引用时方便起见，下面列出一些常用的集合基本恒等式，并附加上命题演算中与其相对应的等价式，从中会看到命题演算与集合代数之间的联系与相似之处。由于这些基本恒等式描述了它所包含的运算的某些性质，因此也称为集合定律。

C1： 等幂律


A∪A=A(P∨PP)
A∩A=A(P∧PP)


C2： 结合律


(A∪B)∪C=A∪(B∪C)((P∨Q)∨RP∨(Q∨R))
(A∩B)∩C=A∩(B∩C)((P∧Q)∧RP∧(Q∧R))


C3： 分配律


A∪(B∩C)=(A∪B)∩(A∪C)(P∨(Q∧R)(P∨Q)∧(P∨R))
A∩(B∪C)=(A∩B)∪(A∩C)(P∧(Q∨R)(P∧Q)∨(P∧R))


C4： 交换律


A∪B=B∪A(P∨QQ∨P)
A∩B=B∩A(P∧QQ∧P)


C5： 同一律


A∪=A(P∨FP)
A∩E=A(P∧TP)


C6： 零律


A∪E=E(P∨TT)
A∩=(P∧FF)


C7： 补余律


A∪~A=E(P∨�瘙
綈PT)
A∩~A=(P∧�瘙
綈PF)


C8： 吸收律


A∪(A∩B)=A(P∨(P∧Q)P)
A∩(A∪B)=A(P∧(P∨Q)P)


C9： 德·摩根律


~(A∪B)=~A∩~B(�瘙
綈(P∨Q)�瘙
綈P∧�瘙
綈Q)
~(A∩B)=~A∪~B(�瘙
綈(P∧Q)�瘙
綈P∨�瘙
綈Q)


C10： 双重否定律


~(~A)=A(�瘙
綈�瘙
綈PP)

C11： ~=E(�瘙
綈FT)

~E=(�瘙
綈TF)


此外，还有一些常用的恒等式和关系式。

C12： A∩BA，A∩BB

C13： AA∪B，BA∪B

C14： A-BA

C15： ABA∪B

C16： A-B=A∩~B

C17： A-B=A-(A∩B)

C18： AB=(A∩~B)∪(~A∩B)

C19： (A∪B≠)(A≠)∨(B≠)

C20： (A∩B≠)(A≠)∧(B≠)

C21： AB∧BCAC
C22： AB∧BCAC传递性

传递性定律的证明并不困难，下面只以C17和C21式为例来说明一般的证明方法。

证C17： A-B=A-(A∩B)

(方法1) 对任意的x∈A-(A∩B)x∈{x|x∈A∧x(A∩B)}

x∈{x|x∈A∧(xA∨xB)}

x∈{x|(x∈A∧xA)∨(x∈A∧xB)}

x∈{x|F∨(x∈A∧xB)}

x∈{x|x∈A∧xB}

x∈A-B

再由x的任意性可知，A-B=A-(A∩B)成立。

(方法2) A-(A∩B)=A∩~(A∩B)

=A∩(~A∪~B)

=(A∩~A)∪(A∩~B)=∪(A∩~B)

=A∩~B=A-B■

证C21： AB∧BCAC

(方法1) 任意x∈A，因为AB，所以x∈B； 又因为BC，所以由x∈B可知，必有x∈C。由此可得，任意x∈A，均有x∈C，故AC成立。

(方法2) 先将C21式符号化，可得谓词逻辑的推理形式，即


(x)(x∈A→x∈B),(x)(x∈B→x∈C)(x)(x∈A→x∈C)


(1) (x)(x∈A→x∈B)P

(2) y∈A→y∈BUS,(1)

(3) (x)(x∈B→x∈C)P

(4) y∈B→y∈CUS,(3)

(5) y∈A→y∈CT,(2),(4),假言三段论

(6) (x)(x∈A→x∈C)UG,(5)

故C21结论成立。■

上面已经定义过集合的运算，借助这些运算，可以由已知集合构造新的集合。大写字母被用来表示确定的集合，也用这些字母作为集合变量，这种习惯类似于命题演算中的用法。例如，大写字母A，B，C，…用作集合变量，它们未必是集合，而可以是集合公式。集合运算还能够扩充到集合公式，因而A∪B，A∩B，~A等全是集合公式，任何包含有集合变量，运算符∩，∪，~和括号的合式字符串都是一集合公式，为了简单起见把它们也叫集合。

事实上，以确定的集合去代替变量，就从一个集合公式得到一个集合。当出现于两个集合公式中的集合变量一旦用任意一个集合去代替后，如果它们作为集合是相等的，则说这两个集合公式是相等的。由于集合公式的相等不依赖于去代替那些变量的集合，因此这些等式就称为集合恒等式。某些基本恒等式描述所含运算的一定性质并给予专门名称。这些性质描述一种代数，称为集合代数(sets algebra)。

与命题代数一样，上面所列出的恒等式不全是独立的，某些恒等式可以由假定一些别的恒等式而推导出来。然而，我们已经列出了这些能显示某些基本和有用性质的全部恒等式。

另外，由上面列出的恒等式可以看到，除C10外都是成对出现的。这种成对出现的原因类似于命题代数中给出的对偶原理，在集合代数的情形下也成立。事实上，命题代数和集合代数都是一种称为布尔代数(Boolean algebra)的抽象代数的特殊情形。这个事实也说明了为什么在命题演算中的运算符和集合论中的运算符间能看到相似性。

习题3.2

(1) 设E={1,2,3,4,5}，A={1,4}，B={1,2,5}，C={2,4}，求下列集合。

① A∩~B。

② A∪~B。

③ A-B。

④ BC。

⑤ ~A∪~C。

(2) ① 若A∪B=A∪C，一定有B=C吗?

② 若A∩B=A∩C，一定有B=C吗?

③ 若AB=AC，一定有B=C吗?论证你的答案。

(3) 设A，B，C是任意3个集合，证明：

① (A-B)-C=A-(B∪C)。

② (A-B)-C=(A-C)-B。

③ (A-B)-C=(A-C)-(B-C)。

(4) 设A，B，C是任意3个集合，下述4个式子在什么条件下成立？

① (A-B)∪(A-C)=A。

② (A-B)∪(A-C)=。

③ (A-B)∩(A-C)=。

④ (A-B)(A-C)=。

(5) 若A∩CB∩C，且A∩~CB∩~C，则AB。请证明之。

(6) 证明： CA当且仅当(A∩B)∪C=A∩(B∪C)。

(7) 设A={a,b,{a,b},}，求出下列各式：

① A-{a,b}。

② A-。

③ A-{}。

④ {{a,b}}-A。

(8) 设A，B，C，D是任意4个集合，试证明：

① A-(B∪C)=(A-B)∩(A-C)。

② A-(B∩C)=(A-B)∪(A-C)。

③ A-(B-C)=(A-B)∪(A∩C)。

④ (A-B)∩(C-D)=(A∩C)-(B∪D)。

3.3包含排斥原理

本节主要讨论有限集的元素计数问题。首先给出集合计数问题的基本关系式，然后给出包含排斥原理以及它在实际中的应用。

根据集合运算的定义，显然以下各式成立。

(1) |A1∪A2|≤|A1|+|A2|。

(2) |A1∩A2|≤min{|A1|,|A2|}。

(3) |A1-A2|≥|A1|-|A2|。

(4) |A1A2|=|A1|+|A2|-2|A1∩A2|。

其中，等式(不等式)左边出现的运算符都是集合中的运算符，右边出现的运算符“＋”或“-”都是普遍意义上的加法和减法。


定理3.3.1设A，B为有限集，其元素个数分别为|A|和|B|，则有


|A∪B|=|A|+|B|-|A∩B|




证当|A∩B|=时，显然有|A∪B|=|A|+|B|，此时结论成立。

当|A∩B|≠时，|A|=|A∩~B|+|A∩B|，|B|=|~A∩B|+|A∩B|，


|A|+|B|=|A∩~B|+|~A∩B|+2|A∩B|，(1)
|A∪B|=|A∩~B|+|~A∩B|+|A∩B|(2)

由式(1)和式(2)可得 


|A∪B|=|A|+|B|-|A∩B|■


此定理被称为包含排斥原理(inclusionexclusion principle)。此原理在实际中具有广泛的应用。

【例3.3.1】某班30名学生中选学英语的有7人，选学日语的有5人，两科都选的有3人。问两科都不选的有多少人?

解用A表示选学英语的学生集合，B表示选学日语的学生集合。显然，|A|＝7(人)，|B|＝5(人)，|A∩B|＝3(人)，则


|A∪B|=|A|+|B|-|A∩B|＝7＋5-3＝9(人)

即至少选学一门外语的人数为9人，两科都不选的人数为


|~(A∪B)|=|E|-|A∪B|＝30-9＝21(人)



推论1设A，B，C是任意有限集，则有


|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|




【例3.3.2】某校举行数学、物理、英语3科竞赛，某班30名学生中有15人参加了数学竞赛，8人参加了物理竞赛，6人参加了英语竞赛，并且有3人同时参加了这3种竞赛，问最少有多少人一科竞赛都没有参加?

解用A1表示参加数学竞赛的学生集合； A2表示参加物理竞赛的学生集合； A3表示参加英语竞赛的学生集合。显然，有|A1|＝15(人)，|A2|＝8(人)，|A3|＝6(人)，|A1∩A2∩A3|＝3(人)。由推论1可知


|A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A2|
-|A1∩A3|-|A2∩A3|+|A1∩A2∩A3|

因为


|A1∩A2|≥|A1∩A2∩A3|＝3
|A1∩A3|≥|A1∩A2∩A3|＝3
|A2∩A3|≥|A1∩A2∩A3|＝3


所以


|A1∪A2∪A3|≤15＋8＋6-3×3＋3＝23(人)

即全班30人中最多有23人参加了竞赛活动，因此最少有7人没有参加任何一科的竞赛。


推论2设A1,A2,…,An为有限集合，其元素个数分别为|A1|，|A2|，…，|An|，则有


|A1∪A2∪…∪An|

=∑ni=1|Ai|-∑1≤i<j≤n|Ai∩Aj|+

∑1≤i<j<k≤n|Ai∩Aj∩Ak|+…+(-1)n-1|A1∩A2∩…∩An|





【例3.3.3】试求出1~250之间能被2、3、5、7任何一数整除的整数个数。

解用A1、A2、A3和A4分别表示1~250间能被2、3、5和7整除的整数集合，于是A1∪A2∪A3∪A4表示1~250间至少能被2、3、5和7之一整除的整数集合，其个数|A1∪A2∪A3∪A4|即为所求。按包含排斥原理的推论2展开，得


|A1∪A2∪A3∪A4|

=∑4i=1|Ai|-∑1≤i<j≤4|Ai∩Aj|+
∑1≤i<j<k≤4|Ai∩Aj∩Ak|+

(-1)4-1|A1∩A2∩A3∩A4|

= |A1|+|A2|+|A3|+|A4|-|A1∩A2|-|A1∩A3|-|A1∩A4|-

|A2∩A3|-|A2∩A4|-|A3∩A4|+|A1∩A2∩A3|+|A1∩A2∩A4|+

|A1∩A3∩A4|+|A2∩A3∩A4|-|A1∩A2∩A3∩A4|


显然，A1∩A2表示能同时被2和3整除的整数集合； A1∩A3表示能同时被2和5整除的整数集合； 其余类推。于是

|A1|=2502=125， 
|A2|=2503=83， 
|A3|=2505=50， 
|A4|=2507=35

|A1∩A2|=2502×3=41，
|A1∩A3|=2502×5
=25，
|A1∩A4|=2502×7=17

|A2∩A3|=2503×5
=16，
|A2∩A4|=2503×7=11，
|A3∩A4|=2505×7=7

|A1∩A2∩A3|=2502×3×5=8，
|A1∩A2∩A4|=2502×3×7=5

|A1∩A3∩A4|=2502×5×7=3，
|A2∩A3∩A4|=2503×5×7=2

|A1∩A2∩A3∩A4|=2502×3×5×7=1

于是得


|A1∪A2∪A3∪A4|=125+83+50+35-41-25-17
-16-11-7+8+5+3+2-1=193

即1~250间能被2，3，5，7中任何一个整除的整数有193个。

注： 这里的x」表示小于或等于x的最大整数。

习题3.3

(1) 在1~300的整数中，有多少个数同时不能被3，5，7整除?有多少个数能被3整除，但不能被5和7整除?

(2) 某足球队有运动服38件，篮球队有运动服15件，棒球队有运动服20件，3个队队员总数58人，且其中只有3人同时参加3个队，试求同时参加两个队的队员共有几个人?

(3) 根据调查，某高校在读学生阅读书籍的情况如下： 60%读甲类书籍，50%读乙类书籍，50%读丙类书籍，30%读甲与乙类书籍，30%读乙与丙类书籍，30%读甲与丙类书籍，10%读3类书籍。问：

① 阅读两类书籍学生的百分比?

② 不读任何书籍学生的百分比?

(4) ① 一个班里有50名学生，在第一次考试中有26人得到成绩A，在第二次考试中有21人得到成绩A。如果两次考试中都没有得到成绩A的学生是17人，那么，有多少学生在两次考试中都得到成绩A?

② 如果在两次考试中，成绩是A的学生数相等。在两次考试中，恰好得到一次A的学生数为40，而两次考试中都没有得到成绩A的学生数为4，那么，仅在第一次考试中得到成绩A的学生数是多少?仅在第二次考试中得到成绩A的学生数是多少?两次考试中都得到成绩A的学生数是多少?

3.4自然数与数学归纳法

众所周知，最古老而又最基本的数学系统就是自然数系统。本节中先给出所谓后继集合的概念，并从空集与后继集合的概念着手，把自然数一个一个地具体构造出来，然后研究自然数集合的某些重要性质(公理)。这些公理之一使我们能构成数学归纳法原理。


定义3.4.1设A为任意集合，则称A∪{A}为A的后继集合(successor of a set)，并记为A+，即A+=A∪{A}。




【例3.4.1】{a,b}+={a,b}∪{{a,b}}={a,b,{a,b}}，


+=∪{}={}，
(+)+={}∪{{}}={,{}}，
((+)+)+={,{}}∪{{,{}}}={,{},{,{}}}。


构造自然数的方法很多，常采用的方法是冯·诺依曼(John von Neumann)给出的方案： 


0=，
1=0+={}，
2=1+={,{}}，
3=2+={,{},{,{}}}，
︙


这样就得到了集合{0,1,2,3，…}，其中每个元素都是前一个元素的后继集合，除了元素0被假定存在外。

这样的讨论可以概括为： 自然数集合能从下列公理，即所谓皮亚诺(Peano)公理而得到。

(1) 0∈N(其中0=)。

(2) 如果n∈N，则n+∈N，其中n+=n∪{n}。

(3) 如果一个子集SN具有性质：

① 0∈S。

② 如果n∈S，则n+∈S，则S=N。

性质(3)通称为极小性质，它断言满足①和②的极小集合是自然数集合。把n+写成n+1是方便的，但是不一定要把“＋”作为N上的一个运算。

通常称皮亚诺公理的性质(3)为归纳原理，因为它是归纳法的基础。数学归纳法(mathematical induction)，简称归纳法，是数学中常用的重要证明方法之一。它有两种基本形式——第一数学归纳法和第二数学归纳法。下面就来讨论这两种基本形式及其具体使用方法。


定理3.4.1(第一数学归纳法，incomplete induction)设P(n)是遍及自然数集合N的任何性质的谓词，如果能证明：

(1) 基础步(basis step)，即P(0)为真；

(2) 归纳步(inductive step)，即如果P(n)为真，则P(n+1)也为真。

那么对一切n∈N，P(n)皆为真。




第一数学归纳法的应用可有两种形式，用谓词形式表示如下。

(1) P(0)∧(n)(P(n)→P(n+1))(n)P(n)。

(2) P(n0)∧(n)(P(n)→P(n+1))(n)(n≥n0→P(n))。

这里的n0是某一正整数，P(n0)为归纳基础。

【例3.4.2】证明： n3+2n(n∈N)可被3整除。

证设谓词P(n)： n3+2n=3k(k为某一整数)。

基础步： P(0)为03＋2×0＝3×0(k取0)，显然，P(0)为真，即当n=0时，n3+2n可被3整除。

归纳步： 设任意m∈N，假设P(m)为真，即m3+2m=3k成立，则


(m+1)3+2(m+1)=m3+3m2+3m+1+2m+2
=m3+2m+3m2+3m+3=3k+3(m2+m+1)
=3(k+m2+m+1)=3k′

其中k′=k+m2+m+1，故P(m+1)也为真。

由归纳假设原理可知，对任意的n∈N，P(n)为真，得证。

【例3.4.3】证明： 1+3+5+…+(2n-1)=n2。

证设P(n)： 1+3+5+…+(2n-1)=n2。

基础步： 对于P(1)，1＝12为真，即n=1时结论成立。

归纳步： 对任意的m∈N，假设P(m)为真，即1+3+5+…+(2m-1)=m2成立，则


1+3+5+…+(2m-1)+(2(m+1)-1)=1+3+5+…+(2m+1)
=1+3+5+…+(2m-1)+(2m+1)
=m2+2m+1=(m+1)2

故P(m+1)也为真。

由归纳假设原理可知，对一切n∈N且n≥1，P(n)为真，得证。


定理3.4.2(第二数学归纳法，complete induction)设P(n)为遍及自然数集合N的任何性质的谓词。如果能证明：

(1) 基础步，即n0∈N，P(n0)为真；

(2) 归纳步，即对任意m>n0，若对k∈N，且n0≤k<m，有P(k)为真，P(m)亦为真。

则对任意的n>m时，P(n)为真。




【例3.4.4】斐波那契(Fibonacci)数列定义为


F0=0； F1=1； Fn+1=Fn+Fn-1，n∈I+

证明： 若n∈I+，则


1+52n-2≤Fn≤1+52n-1


证(用第二数学归纳法)

基础步： 当n=1时，F1=1，显然有下式成立


1+52-1≤F1≤1+520


归纳步： 对任意m>1，假设k∈N且1≤k<m时，有


1+52k-2≤Fk≤1+52k-1

成立，证明当k=m时，上式也成立。

因为


Fm=Fm-1+Fm-2≥1+52m-3+1+52m-4
=1+52m-41+52+1=1+52m-414+52+54
=1+52m-4122+2×12×52+522
=1+52m-412+522=1+52m-41+522
=1+52m-2

另一方面，有


Fm=Fm-1+Fm-2≤1+52m-2+1+52m-3=1+52m-31+52+1
=1+52m-33+52=1+52m-31+522=1+52m-1


由上面推导结果可知，1+52m-2≤Fm≤1+52m-1成立。

由归纳假设可知，对一切n∈N
，原式成立，得证。

使用数学归纳法应注意以下几点。

(1) 验证P(0)成立，这是使用数学归纳法的前提之一。

(2) 对任意n∈N
，假设P(n)成立去推演出P(n+1)也成立，这个推演是必要的，这是使用数学归纳法的前提之二。

(3) 在证明上述两个前提之后，就可依据数学归纳法，得到对一切自然数都有P(n)成立的结论。

另外，在实际使用数学归纳法时，对于初始条件P(0)可做以下推广，从而使结论也有所改变，即

(1) 对某一自然数n0，先验证P(n0)成立。

(2) 再证明对任意自然数n，n0≤n，假设P(n)成立，推演出P(n+1)成立。

(3) 于是有对一切自然数n(n0≤n)，都有P(n)成立。

习题3.4

(1) 对所有n≥1，证明2n×2n-1能被3整除。

(2) 用归纳法证明： 


12-22+32-42+…+(-1)n-1·n2=(-1)nn(n+1)2


(3) 证明： 


12+32+52+…+(2n-1)2=n(2n-1)(2n+1)3


(4) 证明： 


1×2×3+2×3×4+3×4×5+…+n(n+1)(n+2)=n(n+1)(n+2)(n+3)4


(5) 证明： 


11×3+13×5+…+1(2n-1)(2n+1)=n2n+1


(6) 用第二数学归纳法证明： 若n∈I+，且a1,a2,…,an都是正数，则


na1a2…an≤（a1+a2+…+an）n

且等号仅在n=1或a1=a2=…=an时成立。

3.5笛卡儿乘积

众所周知，集合中元素的次序是无关紧要的，即{a,b}={b,a}。常把这种仅由两个元素a和b组成的集合{a,b}称为偶集。因为这种偶集与元素a和b的次序无关，所以也称为无序偶集，简称无序偶。本节将讨论另一种更常用的偶集，它不仅与含有的元素a和b有关，而且还与a和b出现的次序有关。为了强调次序性，常把这种偶集称为有序对或序偶。

首先给出序偶的定义，然后对序偶的概念加以推广去定义n重序元或多元有序组。


定义3.5.1由两个具有给定固定次序的客体组成的序列，称为序偶(ordered pair)，记为〈x,y〉。其中，x被看作第一个元素，y被看作第二个元素。




【例3.5.1】在笛卡儿坐标系中的二维平面上的一个点的坐标〈x,y〉就是一个序偶，如图3.5.1所示。



图3.5.1序偶表示图


显然，坐标〈1,2〉和〈2,1〉表示了平面上两个不同的点，因此〈1,2〉≠〈2,1〉。


定义3.5.2给定两个序偶〈a,b〉和〈c,d〉，〈a,b〉与〈c,d〉是相等的(equal)，当且仅当a=c且b=d，即


〈a,b〉=〈c,d〉(a=c)∧(b=d)





有了序偶的概念，下面将用递推的方式去定义n重序元。


定义3.5.3按递推方式，n重序元的定义如下。

(i) 三重序元(ordered triple)是个序偶，它的第一个元素本身也是个序偶，记为〈〈x,y〉,z〉，简记为〈x,y,z〉。

(ii) 四重序元(ordered 4tuples)是个序偶，它的第一个元素本身是个三重序元，记为〈〈x,y,z〉,w〉，简记为〈x,y,z,w〉。

(iii) n重序元(ordered ntuples)是个序偶，它的第一个元素本身是个n-1重序元，记为〈〈x1,x2,…,xn-1〉,xn〉，简记为〈x1,x2,…,xn-1,xn〉。




根据n重序元的定义可知，下式成立，即


〈a1,a2,…,an〉=〈〈a1,a2,…,an-1〉,an〉=〈〈〈a1,a2,…,an-2〉,an-1〉,an〉
=…=〈〈〈a1,a2〉,a3〉…〉,an-1〉,an〉


同理，两个n重序元相等，可以描述为


〈x1,x2,…,xn〉=〈a1,a2,…,an〉(x1=a1)∧(x2=a2)∧…∧(xn=an)


应该指出的是，一个序偶〈a,b〉的元素可以取自不同的集合。如果第一个元素取自集合A，第二个元素取自集合B，就可以得到若干个不同的序偶。这些序偶的集合描述了集合A和B的一个特征，称为笛卡儿乘积。它在关系与函数两章中有着重要的应用。


定义3.5.4设A，B为任意集合，则把所有这样的序偶〈x,y〉(其中x∈A,y∈B)组成的集合，称为A和B的笛卡儿乘积(Cartesian product)，记为A×B，即


A×B={〈x,y〉|x∈A∧y∈B}




【例3.5.2】设A={1,2}，B={α,β}，C={a}，D=，求


A×B，B×A，A×C，A×D，A×A，(A×B)∩(B×A)


解A×B={〈1,α〉,〈1,β〉,〈2,α〉,〈2,β〉}，

B×A={〈α,1〉,〈α,2〉,〈β,1〉,〈β,2〉}，

A×C={〈1,a〉,〈2,a〉}，

A×D=，

A×A={〈1,1〉,〈1,2〉,〈2,1〉,〈2,2〉}，

(A×B)∩(B×A)=。

显然，A×B≠B×A，即笛卡儿乘积不满足交换律。

【例3.5.3】设A={1,2}，B={α,β}，C={a}，求(A×B)×C，A×(B×C)。

解由例3.5.2可知


(A×B)×C={〈〈1,α〉,a〉,〈〈1,β〉,a〉,〈〈2,α〉,a〉,〈〈2,β〉,a〉}
A×(B×C)={1,2}×{〈α,a〉,〈β,a〉}
={〈1,〈α,a〉〉,〈1,〈β,a〉〉,〈2,〈α,a〉〉,〈2,〈β,a〉〉}


因为〈〈1,α〉,a〉是三重序元，而〈1,〈α,a〉〉是二重序元，〈〈1,α〉,a〉≠〈1,〈α,a〉〉，故(A×B)×C≠A×(B×C)，即笛卡儿乘积不满足结合律。


定理3.5.1设A,B,C,D为任意非空集合，则A×BC×D，当且仅当AC且BD。




证(必要性)若A×BC×D，证明AC且BD。对任意的x∈A，y∈B，有〈x,y〉∈A×B。因为A×BC×D，所以〈x,y〉∈C×D，得x∈C，y∈D。由x，y的任意性，知AC且BD成立。

(充分性)若AC且BD，证明A×BC×D。对任意的〈x,y〉∈A×B，则x∈A，y∈B。因为AC，BD，所以x∈C，y∈D，得〈x,y〉∈C×D。由〈x,y〉的任意性，知A×BC×D成立。■


定理3.5.2设A、B、C为任意集合，则：

(i) A×(B∪C)=(A×B)∪(A×C)；

(ii) (A∪B)×C=(A×C)∪(B×C)；

(iii) A×(B∩C)=(A×B)∩(A×C)；

(iv) (A∩B)×C=(A×C)∩(B×C)；

(v) A×(B-C)=(A×B)-(A×C)；

(vi) (A-B)×C=(A×C)-(B×C)。




证(i) A×(B∪C)=(A×B)∪(A×C)。

(方法1) 任意〈x,y〉∈A×(B∪C)〈x,y〉∈{〈x,y〉|x∈A∧y∈(B∪C)}


〈x,y〉∈{〈x,y〉|x∈A∧(y∈B∨y∈C)}
〈x,y〉∈{〈x,y〉|(x∈A∧y∈B)∨(x∈A∧y∈C)}
〈x,y〉∈{〈x,y〉|〈x,y〉∈A×B∨〈x,y〉∈A×C}
〈x,y〉∈(A×B)∪(A×C)

由〈x,y〉的任意性可知，(i)式成立。

(方法2) 先证A×(B∪C)(A×B)∪(A×C)。对任意的〈x,y〉∈A×(B∪C)，则x∈A，y∈B∪C，即x∈A，且y∈B或y∈C。由此可知，〈x,y〉∈A×B或〈x,y〉∈A×C，故〈x,y〉∈(A×B)∪(A×C)。由〈x,y〉的任意性可知，A×(B∪C)(A×B)∪(A×C)成立。

再证 (A×B)∪(A×C)A×(B∪C)。因为AA，BB∪C； AA，CB∪C，根据定理3.5.1可知，则有


A×BA×(B∪C)，A×CA×(B∪C)

所以(A×B)∪(A×C)A×(B∪C)成立。

综上可知，(A×B)∪(A×C)与A×(B∪C)互为子集，故(i)式成立。

其余的证明类似，留作练习，请读者自行完成。■

集合的笛卡儿乘积的概念，可以推广到任意有限多个集合的情况。下面给出n个集合的笛卡儿乘积的定义描述及其基数公式。


定义3.5.5设A1,A2,…,An为n个任意集合，则把所有这样的n重序元〈a1,a2,…,an〉(其中a1∈A1，a2∈A2，…，an∈An)构成的集合，称为集合A1,A2,…,An的笛卡儿乘积，并记作A1×A2×…×An或Xni=1Ai，即A1×A2×…×An={〈a1,a2,…,an〉|ai∈Ai,i=1,2,…,n}。




由于n个集合的笛卡儿乘积是利用n重序元来定义的，根据n重序元的定义，显然有


Xni=1Ai=A1×A2×…×An=(((A1×A2)×A3)×…×An-1)×An


例如，当n＝3时，有


X3i=1Ai=A1×A2×A3=(A1×A2)×A3
={〈〈a1,a2〉,a3〉|〈a1,a2〉∈A1×A2∧a3∈A3}
={〈a1,a2,a3〉|a1∈A1∧a2∈A2∧a3∈A3}


n个集合的笛卡儿乘积更具有普遍意义。例如，当n＝2时就是前面描述的两个集合的笛卡儿乘积的情况，特别是当A1=A2=…=An=A时，为了方便起见，引用下述记忆符号：

A2=A×A

A3=A2×A=(A×A)×A

︙

An=An-1×A=(An-2×A)×A=…=(((A×A)×A)×…×A)×A

根据笛卡儿乘积的定义，不难得出n个有限集合的笛卡儿乘积的基数公式为


|A1×A2×…×An|=|A1||A2|…|An|=∏ni=1|Ai|

特别地，当A1=A2=…=An=A时，有


|An|=|A×A×…×A|=|A|n

习题3.5

(1) 设A={0,1}，B={1,2}，求下列集合。

① A×{1}×B。

② A2×B。

③ (B×A)2。

(2) 设A={a,b}，试求ρ(A)×A。

(3) 设A、B、C、D是任意集合，试证明： 


(A∩B)×(C∩D)=(A×C)∩(B×D)


(4) 下列各式中哪些成立？哪些不成立?为什么?

① (A∪B)×(C∪D)=(A×C)∪(B×D)。

② (A-B)×(C-D)=(A×C)-(B×D)。

③ (AB)×(CD)=(A×C)(B×D)。

④ (A-B)×C=(A×C)-(B×C)。

⑤ (AB)×C=(A×C)(B×C)。

(5) ① 设AC，BD，证明A×BC×D。

② 给定A×BC×D，那么AC，BD一定成立吗?

(6) 在笛卡儿坐标系中，设X={x|x∈R∧-3≤x≤2}，Y={y|y∈R∧-2≤y≤0}，
试给出笛卡儿乘积X×Y的几何解释。