上一页 下一页

包含与排斥原理

一．包含排斥原理：设A，B为有限集合，则有：

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

包含排斥原理的推广：设A₁,A₂,…,A_n为有限集合，则：

 |A₁∪A₂∪…∪A_n|= - +…+ |A₁∩A₂∩…∩A_n|。

¨    例:某系有 100 个学生至少要学法、德、英三种语言中的一种。现在这 100 个学生中有42人学法语，45人学德语，65人学英语，15人学法语和德语，20人学法语和英语，25 人学德语和英语。问同时学三种语言的有多少? 仅学英语的有多少?

¨    解:令A,B,C分别表示学法语、德语、英语学生的集合。则

¨    |A|=42,|B|=45,|C|=65,|A∩B|=15,|A∩C|=20,|B∩C|=25, |A∪B∪C|=100。

¨    由容斥原理得：

¨    |A∪B∪C| =(|A|+|B|+|C|)-(|A∩B|+|A∩C|+|B∩C|)+ |A∩B∩C|

¨    所以|A∩B∩C|=|A∪B∪C|-(|A|+|B|+|C|)+(|A∩B| +|A∩C|+|B∩C|)=8

¨    仅学英语的人数为：

¨    |C|-|A∩C|-|B∩C|+|A∩B∩C|=28

二．关系的性质

•      设R是集合A上的二元关系。

•      (1)自反：如果对任意aÎA,有aRa,则称R是自反的。

•      自反的定义要求是对所有的A中元素，因此讨论自反关系，应在一给定集合下。

•      如：A={1,2,3,4}，

•      R₁={(1,1),(2,2),(3,3)}，因为4ÎA,而(4,4)ÏR₁,所以R₁不是A上的自反关系

 R2={(1,1),(1,2),(2,2),(3,3),(4,4)} ，对i=1,2,3,4,都有iRi,因此R2是A上的自反关系

•      注意：对于自反,必须是对于每个xÎA,都去检验是否有xRx。

•      (2)反自反：如果对任意aÎA,有(a,a)ÏR ,则称R是反自反的。

•      反自反要求对任意的A中元素a，有(a,a)ÏR。

•      如：A={1,2,3,4}，

•      R₁={(1,1),(2,2),(3,3)} ，因为1ÎA,而(1,1)ÎR₁,所以R₁不是A上的反自反关系，又因为4ÎA, (4,4)ÏR，所以R₁也不是A上的自反关系。因此R₁既不是A上的自反关系,也不是反自反关系。

•      结论1：一个关系若是自反的，则一定不是反自反。反之

•               亦然。

•      结论2：一个关系可以既不是自反的，也不是反自反。

•       (3)对称：对任意a,bÎA ,如果aRb必有bRa , 则称R是对称的。

•      A={1,2,3,4}

•      S₁={(1,2),(2,1),(1,3),(3,1)}和S₂={(1,2),(2,1),(3,3)}都是对称的；

•      S₃={(1,2),(2,1),(1,3)}，因为(1,3)ÎS₂,而(3,1)ÏS₂,所以S₂不是对称的；

•       (4) 反对称：对任意a,bÎA,如果aRb且bRa,必有a=b,则称R是反对称的。

•      该定义实际上表明：当a¹b时，若有(a,b)ÎR,则(b,a)ÏR。S₄={(1,2),(1,3),(2,3)} 和S₅={(1,1),(1,2),(1,3),(2,3)} 是反对称；

•      S₂={(1,2),(2,1),(1,3)}，因为(1,2)ÎS₂,而且(2,1)ÎS₂,所以S₂不是反对称的；

•      因此S₂既不是A上的对称关系,也不是反对称关系

•      结论3：一个关系可以既是对称的，又是反对称的。

•      结论4：一个关系可以既不是对称的，又不是反对称的。

•      (5) 传递：对任意a,b,cÎA, 如果aRb且bRc,必有aRc , 则称R是传递的。

•      注意：传递要求是：只要有aRb,bRc,则必须有aRc，但若没有aRb,bRc ，当然也就不需要讨论是否有aRc 。

•      T₁={(1,2),(1,3)} 是传递的

•      T₂={(1,1)} 传递

•      T₃={(1,2),(2,3),(1,3)} 传递

•      T₄={(1,2),(2,3),(1,3),(2,1),(1,1)} ，因为(2,1)ÎT₄, (1,2)ÎT₄,

•      而(2,2)ÏT₄ ，所以T₄不是传递的。

•      例：A上的非空关系R是对称的和反自反的，则R不是传递的。

•      证明:反证法.假设R传递.

•           则因为R反自反,所以对任意的aÎA，有(a,a)ÏR

•           现在的条件是R对称,反自反, 传递。

•           又因为R非空，故必存在a,bÎA，使得(a,b)ÎR

•           由于R对称，所以有(b,a)ÎR

•           而R传递，故当(a,b)ÎR，且(b,a)ÎR时，必有(a,a)ÎR，

•           与R反自反矛盾。

•          所以R不是传递的。

•      注意，当导出(a,a)ÎR时，千万不能说R自反。因为自反的要求是：如果对任意aÎA,有aRa。

三． 次序关系

•      集合中有一种重要的关系：次序关系。它可用来比较集合中元素的次序,其中最常用的是偏序关系和全序关系。

1.偏序关系

•      定义1:设R是集合A上的二元关系, 若R是自反的, 反对称的和传递的, 则称R是A上的偏序关系。又记为≤(注意,此符号在这里并不意味着小于或等于)。若集合A具有偏序关系R,则称A为偏序集,记为(A,R)。

•   如：实数集R上的小于或等于关系≦、+正整数集Z⁺上的整除关系、集合A的幂集P(A)上的包含关系Í，由于它们都是偏序关系，因此(R,≦) (Z⁺,|), (P(A),Í)都是偏序集。

•   偏序集必须有一个具体给定的偏序关系

•   例：A={1,2},P(A)={Æ,{1},{2},{1,2}},则A的幂集P(A)上的包含关系：{(Æ,Æ),(Æ,{1}),(Æ,{2}),(Æ,{1,2}), ({1},{1}),({1},{1,2}),({2},{2}), ({2},{1,2}),({1,2},{1,2})}

•      定义2：对于集合A上的偏序关系R, 如果A中两个元素a,b有aRb,则称a与b是可比较的。

•      在上例中，Æ与Æ,{1},{2}与{1,2}都是可以比较的，而{1}与{2}无包含关系，故不可比较

•      由此可见：偏序集合中任意两个元素不一定可比较的。

•      但对于实数集上的小于或等于关系≦，对任意两个实数x,y,或者x≦y,或者y≦x，必有一个成立，故x和y是可以比较的。

2. 全序关系

•      定义 3：设≤是集合A上的二元关系, 如果对于A中任意两个元素a,bÎA,必有a≤b或b≤a, 则称≤是A上的全序关系(或称线性次序关系)。而该集合称为全序集或线性次序集,记为(A,≤)。

•      整数集I上的小于或等于关系≦是全序关系, 但I上的整除关系/不是全序关系。而前面给出的幂集P(A)上的Í关系也不是全序关系。

3.拟序关系

•      定义 4:集合A上的二元关系R是反自反的和传递的, 称R为A上的拟序关系。称(A, R)为拟序集,或记为(A,<)(注意, 此符号<在这里也不意味着小于)。

•      常见的拟序关系有：实数集R上的小于关系<；集合A的幂集P(A)上的真包含关系Ì。

•      定理 1:集合A上的二元关系R是拟序的, 则R必为反对称的。

•      证明：若R不是反对称的，则存在a,bÎA，使得(a,b)ÎR,(b,a) ÎR,因为R拟序,故传递，因此有(a,a)ÎR,与R反自反矛盾。所以R反对称。

•      由此定理, 我们可知拟序关系实际上是满足反自反的, 反对称的和传递的。

•      定理 22：设R是A上的二元关系,则

•      (1)若R是A上的拟序关系, 则r(R)=R∪I_A是A上的偏序关系。

•      (2)若R是A上的偏序关系, 则R-I_A是A上的拟序关系。

4.偏序集合中的几个特殊元素

（1）最小元和最大元

§    定义：设(A,≤)是一个偏序集合, BÍA,若存在一个元素bÎB,对所有b'ÎB都有b'≤b, 则称b是B的最大元；若都有b≤b', 则称b是B的最小元。特别B=A时，称b为A的最大元。

§    例：A₁={1,2,3,4,5,6},

§    (A₁,£),1为A₁的最小元，6为A₁的最大元

§    (A₁,|),A₁的最小元为1，A₁的最大元无。

§    B₁={1,2,3,6},(B₁,|)最小元为1，最大元为6。

§    C₁={2,3},(C₁,|)既无最小元，也无最大元。

§    这说明整体存在最小(大)元，子集不一定存在最小(大)元。

§    A₂={2,3,6,12,24,36},关系为|，则A₂既无最小元，也无最大元。子集B₂={2,6,12},最小元为2，最大元为12。这说明：

l      偏序集或它的子集不一定存在最小元(最大元)

l      偏序集存在最小元(最大元)，它的子集也不一定存在最小元(最大元)

§    定理：在(A,≤)中，BÍA，若B存在最大元(最小元)，则必唯一。

（2）极大元和极小元

§    定义：设(A,≤)是一个偏序集合, BÍA,若存在一个元素bÎB, 且在B中不存在元素b‘使b¹b’,b≤b‘,则称b是B的极大元；若B中不存在元素b’使b¹b‘, b’≤b,则称b是B的极小元。特别B=A时，称b为A的极大元(极小元)

§    注意极大元与最大元的区别。

§    例：A1={1,2,3,4,5,6},

§    (A1, ≤)中，1为A1的极小元，6为A1的极大元

§    (A1,|)中，A1的极小元为1，A1的极大元为4,5,6，这是因为不存在aÎA1,使得4 ≤ a，5 ≤ a,6 ≤ a。

§     再例：B1={1,2,3,6},(B1, ≤)的极小元为1，极大元为6。

§    C1={2,3},(C1,|)中极小元为2,3，极大元为2,3。

§    A₂={2,3,6,12,24,36},(A₂,|)，A₂极小元为2，3，极大元为24，36。

§    这些说明：

l       极大元(极小元)不唯一

l       最大元(最小元)必是极大元(极小元)

l       对任何非空有限子集，极大元、极小元一定存在

l       若子集B有最大元(最小元)，则B的极大元(极小元)唯一

（3） 上界和下界

§    定义：设(A,≤)是一个偏序集合, BÍA,若存在一个元素aÎA, 对所有b'ÎB都有b'≤a, 则称a是B的上界；对所有b'ÎB都有 a≤b', 则称a是B的下界。

§    注意最大元(最小元)与上界(下界)的区别

§    最大元(最小元)要求最大元(最小元)ÎB,而上界(下界)无此要求

§    例:A₂={2,3,6,12,24,36},(A₂,|)

§    P={2,3,6},P的上界为6,12,24,36,其中6ÎP,而12,24,36ÏP。

§    P无下界。

§    B={2,3}, B的上界为6,12,24,36,B无下界

§    结论：

l        上界(下界)可能存在，也可能不存在。

l        上界(下界)不一定唯一。

l        上界(下界)可以是B中的元素，也可以不是。

（4） 上确界和下确界

§    定义：设(A,≤)是一个偏序集合, BÍA，若aÎA是B的上界且对B中每个上界a'都有a≤a', 则称a为B的上确界(或称最小上界)；若aÎA是B的下界且对B中每个下界a'都有a'≤a,则称a为B的下确界(或称最大下界)。

§    例:A₂={2,3,6,12,24,36},(A₂,|)

§    P={2,3,6},P的上界{6,12,24,36}中，6≤12,6≤24,6≤36,所以6为P的最小上界

B={2.3},同样可以知道6为B的最小上界。

§    例:A₃={6,9,36,54},(A₃,|)

§    B={6,9},B的上界为36,54,但无最小上界。

§    结论：

l        上确界(下确界)唯一。

l        上确界(下确界)可以是B中的元素，也可以不是。

l        存在上界(下界)，上确界(下确界)不一定存在。

•      四、集合的递归定义

•      定义:集合A的递归(归纳)定义由三部分组成:

•      (1)基础:设置某些对象是在所要定义的集合A中的(作为A的基本元素,目的说明集合A是非空的)。

•      (2)归纳(递归):建立一种由集合A的现有元素产生A中新元素的方法。(实质上就是给出一组规则,以确定如何从集合A的现有元素得到A的其他元素。)

•      (3)闭合：除了有限次应用(1)和(2)产生集合A的元素外,A中再没有其它元素。

•      关于闭合还有其他的等价叙述，

•      1)除了有限次应用(1)和(2)产生集合A的元素外,A中再没有其它元素。

•      2)集合A是满足(1)和(2)的最小集合。

•      3)集合A满足(1)和(2), 但不存在A的真子集能满足(1)和(2), 即若SÍA,且S满足(1)和(2), 则S=A。

•      4)集合A是满足由(1)和(2)给定性质的所有集合之交。

•      以上四种闭合的说法虽然形式上不同, 但它们是等价的。证明从略。

•      例1：设整数集Z是全集,非负偶整数集E⁺={x|x≧0,且x=2y,yÎZ},它可以递归定义如下:

•      (1)(基础)0ÎE⁺。

•      (2)(归纳)如果nÎE⁺,则n+2ÎE⁺。

•      (3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在E⁺中。

•      例2：下面的归纳定义所给出的是怎样的集合？

•      (1)(基础)3ÎS。

•      (2)(归纳)如果x,yÎS,则x+yÎS。

•      (3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在S中。

•      答案是3的正整数倍全体。

•      例3：设Σ是一个有限非空字符集,称为字母表。从Σ中选取有限个字符组成的串称为Σ上的字符串或字。

•      设x是Σ上的一个字, x=a₁a₂…a_n,其中a_iÎΣ,1≦i≦n,n是正整数,表示字的长度

•      长度为0的字称为空串,记为Ù。

•      若x,y是Σ上的两个字,x=a₁a₂…a_n, y=b₁b₂…b_m,其中a_i,b_jÎΣ(1≦i≦n, 1≦j≦m),

•      则由x和y毗连得到新的字记为xy。

•      即:xy=a₁a₂…a_n b₁b₂…b_m。

•      例4:设Σ是一个字母表, Σ上所有的有限非空字符串集合记为Σ⁺,递归定义如下:

•      (1)(基础)如果aÎΣ,则aÎΣ⁺。

•      (2)(归纳)如果xÎΣ⁺,且aÎΣ,则axÎΣ⁺(ax表示字符a与字x毗连得到的新的字)。

•      (3)(闭合)除有限次应用(1)和(2)产生Σ⁺中的字外, Σ⁺中再没有其它字。

•      集合Σ⁺包含长度为1,2,3,…的字,即Σ⁺包含无限个字, 但每个字的字符个数是有限的。

•      例5:设Σ是一个字母表, Σ上所有的有限字符串集合记为Σ^*,Σ^*包含空串，即Σ^*=Σ⁺∪{Ù},可递归定义如下:

•      (1)(基础) ÙÎΣ^*。

•      (2)(归纳)如果xÎΣ^*,且aÎΣ,则axÎΣ^*。

•      (3)(闭合)除有限次应用(1)和(2)产生Σ^*中的字外, Σ^*中再没有其它字。

•      例如,若Σ={0,1}, 则Σ^*={Ù,0,1,00,01, 10,11,000,001…},是有限二进制序列的集合, 其中包含空序列。

•      算术表达式集合是包含整数, 一元运算符+,-, 以及二元运算符+,-,* ,/的符号序列所组成的集合, 其中包含如“((3+5)/4)”,“(((-5)+6)*3)”等算术表达式。

•      例6。算术表达式集合的递归定义如下:

•      (1)(基础)如果D={0,1,2,3,4,5,6,7,8,9}和xÎD⁺ ,则x是算术表达式。其中D⁺是D上所有非空数字串的集合。

•      (2)(归纳)如果x和y都是算术表达式, 则

•      (+x)是算术表达式;    (-x)是算术表达式;

•      (x+y)是算术表达式;   (x-y)是算术表达式;

•      (x*y)是算术表达式;   (x/y)是算术表达式。

•      (3)(闭合)一个符号序列是一个算术表达式当且仅当它能通过有限次应用(1)和(2)而得到。

•      五、基数概念

•      首先我们从古老的传说来引进大数。

•      在64个小方格组成的棋盘中放米的问题：

•      印度的舍罕王要重赏国际象棋的发明人达依尔，达依尔要求：“在棋盘的第一个方格内放一粒米，以后每一小格内都比前一小格加一倍，最后摆满所有64格，将这些米赏给我”。国王认为他的要求不高，爽快地答应了。可结果却无法满足。1+2+2²+¼+2⁶³=2⁶⁴-1,约合140亿升

•      所有整数的个数，一条线上所有几何点个数(即区间[a,b]上个数)，

•      上面两个数哪个大些？这个问题最初是由Cantor提出的。

•      从原始部落物品交换中得到启发。

•      在古代原始部落中，不存在比3大的数，若问他们当中的一个人有几个孩子，当孩子多于3个时，其回答是很多。

•      在比较一堆珠子和一堆铜币哪个多时，他们将怎么完成呢？

•      他们是通过把珠子和铜币逐个比较，最后看哪堆有多余，若同时没有则两者相同。

•      对于无穷大数比较，我们面临的也类似于原始部落问题。

•      Cantor的解决办法与上述方法相同：给两组元素无穷多的序列中的各个数一一配对，若最后这两组元素恰配对完毕，则认为这两个无穷大数就是相等的，若有一组还没配完，则该组就比另一组大。

•      正是基于这一基本设想，我们可给出对于两个集合比较其元素个数大小的方法。

•      定义：设A,B是任意两个集合,若存在一个双射f:A→B,则称A和B对等(或等势),记为A～B;或称A和B的基数相同。A的基数记为|A|;A和B的基数相同记为|A|=|B|。

•      六、无限集

•      定义：设A为一个集合, 若A为空集或与集合{0,1,2,…,n-1}的基数相同, 则称A为有限集,且|A|=nÎN。若集合A不是有限集, 则称A为无限集。

•      定义：若存在从N到A的双射, 则称A为可列无限集, 简称可列集或可数集,|A|=À₀。

•      定理：(1)设A是可列集, 若存在从A到B的双射,则B也是可列集。

•      (2)集合A是可列集的充要条件是集合A中的元素可以排成一个无穷序列的形式:a₀,a₁,a₂,a₃,a₄,…。

•      这里要注意：定理中的“无限”两字不能去掉。这是因为可列集是指可列无限集。

•      定理：可列集中加入有限个元素(或删去有限个元素), 仍为可列集。

•      定理：两个可列集之并仍为可列集。

•      推论：有限个可列集之并仍为可列集。

•      定理：可列个可列集之并仍为可列集。

•      定理:  [0,1]是不可列集。

•      这样[0,1]的基数就不是À₀,我们称[0,1]为连续统,基数记为À或c,有时也记为À₁.

•      定理:设A是有限集或可列集,B是任一无限集, 则|A∪B|=|B|。

•      实数集R的基数。构造(0,1)到R的双射f: f(x)=tg(px-p/2)。因此我们可以知道|R|=|(0,1)|=c。

•      由此可以发现，线段上的点数和实数轴上的点数是一样的。

•      现在，整数集，非负整数集，，正整数集，有理数集，它们的基数是À₀。

•      实数集为À。

•      那么无理数集？

•      设P表示无理数集，显然P是无限集，而R=P∪Q,因为|Q|=À₀,所以由定理知，|R|=|P∪Q|=|P|,所以P的基数是À。

  基数的比较

•      定义：设A和B是两个集合, 若存在从A到B的内射, 则称A的基数小于或等于B的基数,记为|A|≦|B|或|B|≧|A|。若|A|≦|B|且|A|≠|B|, 则称A的基数小于B的基数, 记为|A|<|B|。

•      这定义是比较两个有限集的元素个数的推广。

•      定理：设A,B,C是任意集合, 那么

•      (1)若AÍB,则|A|≦|B|。

•      (2)若|A|≦|B|,|B|≦|C|,则|A|≦|C|。

•      定理  伯恩斯坦(F.Bernstein)定理

•      设A和B是两个集合,若|A|≦|B|,又|B|≦|A|,则|A|=|B|。

•      这个定理常用来证明两个集合有相同的基数。

•      作一内射f:A→B, 得到|A|≦|B|,

•      再作一内射g:B→A,得到|B|≦|A|,

•      从而得到|A|=|B|。 

•      伯恩斯坦定理告诉我们:在从A到B和从B到A的两个内射的基础上, 可以得出存在从A到B的双射。找出两个内射往往比直接证明从A到B存在双射要来得容易。

•      例：证明|(0,1)|=|[0,1]|。

•      证明：作内射g:[0,1]→(0,1),g(x)=0.25+x/2，故|[0,1]|≦|(0,1)|,

•      作内射f:(0,1)→[0,1],f(x)=x，故|(0,1)|≦|[0,1]|,

•      由伯恩斯坦定理即证得。

•      有限集基数、可列集基数和连续统基数之间有如下关系:

•      定理：设A是有限集, 则|A|<À₀<c=À₁。

•      是否有一个无限集,它的基数<À₀?由定理4.4易知À₀是最小的无限基数。

•      是否有基数大于À₁=c的集合?是否有最大基数的集合?

•      定理 康托尔定理：对于任何集合A , 必有|A|<| P(A)|。

•      对于|N|=À₀,可以证明|P(N)|=À₁=c。

•      现在我们对有限集的基数计数：0,1,2,3,…,

•      对无限集的计数：À₀,À₁,|P(P(N))|=À₂,…,

•      与现实生活能对应的：

•      À₀：所有整数或分数的个数

•      À₁：线段上所有几何点的个数，或实数的个数

•      |P(P(N))|=À₂：所有几何曲线的个数。

•      说自然数集基数为À₀，曲线集基数为À₂，就如同说一付牌有54张一样。它们都是计数形式。

•      到现在为止，对于比À₂大的有实际意义的无限集还没有发现。

•      现在什么都可以计数，但没有那么多的内容供数。

•      前面已经有结论表明À₀<c, À₀是最小的无限基数, 现在要问:在À₀和c之间有没有其它的基数呢?

•      康托尔早在一百年前就提出了一个猜想:

•      在À₀与c之间没有其它的基数,

•      是著名的连续统假设。

•      1900年著名数学家希尔伯脱(Hilbet.D)在巴黎数学大会上列举了23个未解决的数学问题, 向数学家们进行挑战, 其中第一个就是“康托尔的连续统基数问题”。

      返回                                    返回页首