离散数学第5章 函数.ppt

第5章 函数 5.1 函数的基本概念 5.2 反函数和复合函数 5.3 集合的基数 以下证明f是I到N的双射函数。 任取n?N，若n是偶数，有 ?I且 ≥0， 使f( )=2? =n； 若n是奇数，有 ?I且 ＜0，使f( )= -2?( )-1=n。 所以f是满射。 按照这个定义将I中的元素如下排列与N中的元素对应：? I 0 -1 1 -2 2 -3 3 -4 4 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ N 0 1 2 3 4 5 6 7 8 … 若有n1?I，n2?I且n1≠n2。分下列4种情况讨论： ⑴假定n1≥0且n2≥0，则f(n1)-f(n2)=2n1-2n2=2(n1-n2)≠0，所以f(n1)≠f(n2)。 ⑵假定n1＜0且n2＜0，则f(n1)-f(n2)=(-2n1-1)-(-2n2-1)=2(n2-n1)≠0，所以f(n1)≠f(n2)。 ⑶假定n1≥0且n2＜0，则f(n1)-f(n2)=2n1-(-2n2-1)=2(n1＋n2)+1≠0(因为一个偶数与1的和或差永远不能为0)，所以f(n1)≠f(n2)。 ⑷假定n1＜0且n2≥0，类似⑶，同样有f(n1)≠f(n2)。 所以f是单射。于是f是I到N的双射函数。 I~N 定理5.3.1设A，B，C是任意三个集合。则集合的等势有下列性质。 ⑴ 自反性: 即A~A。 ⑵ 对称性: 即若A~B，则B~A。 ⑶ 传递性: 即若A~B，B~C，则A~C。 证明：仅证明⑶。 因为A~B，B~C，由等势的定义知，存在双射函数f：A→B和双射函数g：B→C，由定理5.2.4知，g°f是A到C的双射函数。 所以A~C。 5.3.2有限集和无限集 定义5.3.2 如果集合A与集合?0,1,2,…,n-1?(n是某个自然数)等势，则称A为有限集，如果集合A不是有限集，则称A为无限集。 定理5.3.2 自然数集N是无限集。 证明：?n?N，设f是任意集合?0,1,2,…,n-1?到N的函数，令k=1+max?f(0), f(1),…,f(n-1)?，k?N。?x??0,1,2,…,n-1?, f(x)≠k。因此，f不是从?0,1,2,…,n-1?到N的满射函数。当然不是从?0,1,2,…,n-1?到N的双射函数。因为n和f都是任意的，所以，自然数集N不是有限集，而是无限集。 定理5.3.3 有限集不与它的任何真子集等势。 证明：设A为任一有限集，B?A，则C=A-B≠?。 |B|=|A|-|C|＜|A|，即|A|≠|B|，根据5.1节中双射的性质，A与B之间不存在双射函数。A与B不等势。 定理5.3.4 无限集必与其某个真子集等势。 证明：首先证明在任何一个无限集a中，一定能取出一系列元素a1,a2,…。 在A中任取一个元素，记为a1。 因为集合A是无限集，显然，集合A-?a1?不空。再从A-?a1?中取一个元素，记为a2。 同样，集合A-?a1,a2?不空。继续做下去，可从A中取出一系列元素a1,a2,…。 记?=a-?a1,a2,…?，令?=?a2,a3,…?∪?，显然??A。 f：A→?，定义为： f(ai)=ai+1 i=1,2,… f(x)=x x?? 显然，f是A到?的双射。A~? 根据定理5.3.3和定理5.3.4可以给出有限集与无限集的另外一个定义如下： 不能和自己的任何真子集等势的集合称作有限集。 能与自己的某个真子集等势的集合称作无限集。 5.3.3集合的基数 定义5.3.3 将相互等势的集合归于同一类，对这样的每一类集合规定一个记号，称这个记号是这一类集合中每一个集合的基数或者势。集合A