离散数学第四章(精品).pptVIP

集 合 论 第四章 函 数 §1 函数的概念 §2 逆函数和复合函数 §3 基数的概念 §4* 可数集与不可数集 第四章 函数 函数是二元关系中特殊的一类，也就是说，函数是一种特定类型的二元关系。本章讨论的是离散函数，它能把一个有穷集合变换到另一个有穷集合。 例：在计算机上执行程序可以看作是函数的变换： （自变量）输入-----计算机-----输出（函数值） 在这章我们主要讨论：函数定义、特殊函数及其性质、函数的运算。最后利用函数的概念，特别是双射函数，介绍一下无限集合的基数问题。 §1 函数的概念 １．函数的定义： 《定义》设X和Y是任意两个集合，f是从X→Y的一种关系，若对于每一个x∈X，都存在一个唯一的 y∈Y，能使 x,y∈f ，则称关系f为函数（映射）,并记为： f：X→Y。 讨论定义： §1 函数的概念 （2）X中每一个元素均有定义， §1 函数的概念 例：判定下列关系是否为函数 §1 函数的概念 例：设X=Y=R（实数） §1 函数的概念 《定义》：给定函数f:A→B和g:C→D，如果A=C，B=D，并对所有的 §1 函数的概念 但在64个子集中只有8个 §1 函数的概念 讨论：从此例中可得到三点结论： （1）设|X|=m，|Y|=n，则函数f: X→Y中均是m个序偶的集合；（即序偶个数=定义域的基数） §1 函数的概念 （3）X→Y有别函数的个数和 §1 函数的概念 §1 函数的概念 §1 函数的概念 §2逆函数和复合函数 设 §2逆函数和复合函数 （3）一个函数的反函数存在的话，则此函数一定是双射函数，而入射，满射函数的逆关系均不满足函数的定义 §2逆函数和复合函数 《定义》：设f: X→Y和g:W→Z是二个函数，若 §2逆函数和复合函数 《定理》：设f:X→Y和g:Y→Z是二个函数，于是复合函数 §2逆函数和复合函数 §2逆函数和复合函数 §2逆函数和复合函数 §2逆函数和复合函数 解： §2逆函数和复合函数 《定理》：设f: X→Y，g:Y→Z， §2逆函数和复合函数 §2逆函数和复合函数 例：设 §2逆函数和复合函数 《定义》：给定f: X→Y，如果对于所有的 §2逆函数和复合函数 《定义》：给定 §2逆函数和复合函数 《定理》：对于任何函数f: X→Y，其中 §2逆函数和复合函数 《定理》：如果函数f: X→Y有逆函数 §2逆函数和复合函数 《定理》：若f是一双射函数，则 §2逆函数和复合函数 证明：由给定条件f,g均为双射函数, 则 §3基数的概念 1.基数的概念 对于有限集：集合中不同元素的个数。 对于无限集：？ 是否所有无限集的基数都一样？ 为了比较两个集合的“大小”，确定有限集和无限集的概念， 我们首先引进自然数集合。 《定义》给定集合A，A+=A?{A}，称A+是A的后继集合。 利用后继集合的概念来定义自然数集合{0，1，2，??} §3基数的概念 设A=?，则A的后继集合可写成： A+=??{?}={?}，（A+）+={?}?{{?}}={?，{?}} （（A+）+）+={?，{?}}?{{?，{?}}}={?，{?}，{?，{?}}} 令：?=0 则?+=0+=1，（?+）+=1+=2 上述求0的后继集合而得到N={0，1，2，??} Peano公理 (1)0?N (这里规定0=?) (2) n?N?n+?N (这里n+是n的后继数) (3)若S?N，且(ⅰ)0?S (ⅱ)n?S?n+?S，则可得S=N §3基数的概念 《定义》：给定二个集合P和Q，如果我们对P中每一个不同元素与Q中每一个不同元素可以分别两两成对，则我们说P中的元素和Q中的元素存在着一一对应。 例:P={1,3,5……2n-1,……}——奇正数，Q={2,4,6……2n,……}——偶正数 则P和Q之间存在着一一对应，其函数关系为： f:P→Q，f(n)=n+1， §3基数的概念 例：N和正偶整数集合E是等势的。 §3基数的概念 《定理》：集合族上的等势关系是一等价关系 §3基数的概念 《定义》：如果从集合{0，1，2，…n-1}是到集合A的双射函数，那么称A是有限集合，若集合A不是有限的，则它一定是无限的。 此定义也可叙述为：基数为某一自然数的任何集合是有限集合，反之为无限集合。 《定理》：自然数集合N是无限集合。 §3基数的概念 只要证明它不是双射函数，则N一定为无限集合 定义一个k，设k=1+max{f(0),f(1)…f(n)},则 §4可数集与不可数集