资源描述：
《离散数学第六章 集合-自然数与自然数集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章集合6.1集合的基本概念6.2集合的基本运算6.3全集和集合的补6.4自然数与自然数集6.5包含与排斥原理后继：A+=A∪{A}定义1A是一个给定的集合，存在一个集合叫做A的后继，记为A+。例设A={a},则A+={a}∪{{a}}={a,{a}}例设B={a,b},则B+={a,b}∪{{a,b}}={a,b,{a,b}}自然数(冯·诺伊曼JohnvonNeumann,1903年12月28日生于匈牙利,1957年2月8日卒于美国)0=Ø1={Ø}2={Ø，{Ø}}3={Ø，{Ø}，{Ø，{Ø}}}4={Ø，{Ø}，{Ø，
2、{Ø}}，{Ø，{Ø}，{Ø，{Ø}}}}┅┅┅┅1={0}2={0，1}=1+3={0，1，2}=2+4={0，1，2，3}=3+┅┅┅┅自然数的定义定义2对于一个集合S，如果它是空集Ø（亦即0），或者有一个自然数n，使得S=n+，则称S为一个自然数。0=Ø1={0}=0+2={0，1}=1+3={0，1，2}=2+4={0，1，2，3}=3+┅┅┅┅后继、前驱对于任意两个自然数m和n，如果m=n+，即m=n∪{n}，称m为n的后继，可以记为m=n+1，也称n为m的前驱，也可以记为n=m-1。自然数集N定义3存在一个由所有自然
3、数组成的集合叫自然数集，记为N皮亚诺公设(Peano’sAxioms)设N表示自然数集。则：1．0∊N2．如果n∊N，那么n+∊N，3．0不是任何自然数集的后继，即不存在自然数m∊N，使得0=m+。4．n和m均是自然数，如果n+=m+，那么n=m。5．如S是N的子集，有性质(1)0∊S,(2)如果n∊S，那么n+∊S，则有S=N。数学归纳法——皮亚诺公设的第5条设n是一个自然数，P(n)表示一个与n有关的公式或命题，令S={n∊N│P(n)为真}。若证明了P(0)为真，也即0∊S(归纳基础)；若P(n)为真，则P(n+)也为真，
4、即若n∊S，则n+∊S(归纳步骤)。则由皮亚诺公设第5条,得S=N。第二归纳法若n=0时命题成立，假定当n小于等于k时命题成立，可以证明n等于k+1时命题也成立。则对于一切自然数命题成立。这种归纳方法又叫第二归纳法。性质①设n1,n2和n3是三个任意的自然数，若n1∊n2,n2∊n3，则n1∊n3。②设n1和n2是两个任意的自然数，则下述三个式中有一个成立：n1∊n2,n1=n2,n2∊n1③设S是自然数集的任意非空子集，则存在n0∊S，使得n0∩S=Ø。例1(传递性)设n是一个自然数，求证：若n1和n2为两个集合，且n1∊n2
5、，n2∊n，则n1∊n。设S={n∊N│若有n1,n2,且n1∊n2，n2∊n，则n1∊n}，要证S=N。证明思路：0∊S?若n∊S，n+=n+1∊S?✔例1证（续）若n∊S，要证n+=n+1∊S。设有两个集合n1和n2，且n1∊n2，n2∊n+=n∪{n}。因n2∊n∪{n}，所以n2∊n或者n2∊{n}。若n2∊n，由于n∊S，所以n1∊n。若n2∊{n}，则n2=n，即n1∊n2=n。综上所述n1∊n⊆n∪{n}=n+,故n+=n+1∊S。所以归纳得证S=N。1908年Zermelo(蔡梅罗)定义的自然数0=Ø1={Ø}2
6、={{Ø}}3={{{Ø}}}4={{{{Ø}}}}┅┅显然，0∊1∊2∊3∊4∊┅┅但“∊”不满足传递性，未能准确刻画出自然数本身所固有的良好性质。例求证：对于任意自然数m和n， 若n∊m,则n+∊m或者n+=m之一成立.证明：对m用归纳法。若m=n+，则n∊m成立,此时有n+=m。归纳假设对任意的m，若n∊m，则n+=m，或者n+∊m之一成立。考察m+=m∪{m},若n∊m+={m}∪m，n∊{m}∪mn∊mn=mn+=m+n+∊mn+∊m+n+=m例求证：对于任意自然数m和n， 若n∊m,则n+∊m或者n+=m之一成立.证
7、明：对m用归纳法。若m=n+，则n∊m成立,此时有n+=m。归纳假设对任意的m，若n∊m，则n+=m，或者n+∊m之一成立。考察m+=m∪{m},若n∊m+={m}∪m，则n=m，或者n∊m。于是有n+=m+,或者n+=m，或者n+∊m之一成立。从而分别有n+=m+，或者n+=m∊m+,或者n+∊m∊m+之一成立,即有n+=m+或者n+∊m+之一成立。所以归纳得证结论成立。例2(p69)证明：对于任意自然数m和n，都有m∊n或者m=n或者n∊m之一成立。证明：对n用归纳法。当n=0时，n=Ø.显然,对于任意的自然数m,只有两种情
8、况：m=Ø,或者Ø∊m(对于非0自然数)即有m=n,或者n∊m之一成立.可以对m运用数学归纳法证明(详见教材)例2(p69)证明：对于任意自然数m和n，都有m∊n或者m=n或者n∊m之一成立。当n=0时，已经证明了结论成立。对n作归纳假设，假设对任意自然数m,有
