离散数学ch6 函数

第六章函数 第一节目录函数的基本概念第二节目录逆函数和复合函数第三节目录特征函数和模糊子集第四节目录基数的概念第五节目录可数集和不可数集第六节目录基数的比较 函数是具有特殊性质的关系 用于把一个集合元素变换成另一个集合的元素 第一节函数的基本概念 一 函数的定义1 函数的定义2 函数相等的定义3 函数的构成4 n之函数二 特殊函数1 定义2 有限集上单 满射关系3 举例 返回总目录 函数的定义 变换 映射 1 定义 设X和Y是集合 从X到Y的函数f是满足下列条件的关系 x X y Y 使 f 记为y f x X称为是f的定义域 Y称为是f的陪域 x称为自变元 y称为函数值 1 函数的定义 返回第一节目录 注 例题1例题2 1 函数的定义 注意1 关系R的前域 dom R x y R 关系R的值域 ran R y x R 注意2 若X X f X 读作函数f对X 的映象 f X y x x X y f x 注 在函数中 关系的前域为XDom f X ran f Y ranf也可记为f X 读为f的值域 或象集合 返回函数的定义 1 函数的定义 a f 是不是一个函数 不是b f 是不是一个函数 不是c f x1 x2 N x2为小于x1的素数个数 是d f x1 x2 N x1 x2 10 对于x1 x2不唯一 不是 例1 设X a b c Y a b c 返回函数的定义 1 函数的定义 即 f a 1 f a 1 f b 3 f a b 1 3 f c 2 f a b c 1 2 3 f d 4则f 例2 f a b c d 1 2 3 4 用图定义 返回函数的定义 函数相等的定义 设f X Y g W Z 若X W Y Z 且 x X 有f x g x 则称f g 例如 f I I f x x2 f 1 2 3 I f x x2是两个不同的函数 2 函数相等的定义 返回第一节目录 3 函数的构成 用YX表示从集合X到集合Y的所有函数的集合 设 X m Y n 因集合X中每个自变元 其函数值有n种取法 YX n n nm 返回第一节目录 4 n元函数 例4 a p X Y Y p x y x p称为投影函数 b f X X Y X Y 为X Y的幂集 f x x Y f称为截痕函数 c 若X Y是任意集合 则空关系是从X到Y的空函数 若X Y 则唯一的关系是空关系不是一个函数 条件为真 结论不成立 返回第一节目录 具有定义域X Xni 1xi的函数f叫做n元函数 函数值用f x1 xn 表示 二 特殊函数 定义 设f是从X到Y的函数 a 若f X Y 那么称为满射 即 y Y x X 使f x y b 若 x1 x2 X x1 x2 f x1 f x2 即若f x1 f x2 x1 x2 那么称f是入射 或单射 c 若f既是满射 又是入射 则称f是双射或称一一映射 返回第一节目录 例题1例题2 XYXYXYa1a1adb2b2be3cf单射 最多有满射 至少有不是单射 也不是一条弧终止于一条弧终止于满射Y的每一元素 Y的每一元素 例1 返回定义 解 a y R 取x y a b a 则f x y f是满射 b x1 x2 R x1 x2 则 b a x1 a b a x2 a 即f x1 f x2 f是入射 由a b 知 f是双射 例2 设f R R f x b a x a 试问f是什么函数 a b 返回定义 2 有限集上单 满射关系 定理1 若X和Y是有限集 且 X Y 则f为单射 f为满射 证明 若f为单射 则 X f X X Y Y f X 又 Y 是有限的 f X Y Y f X 若f为满射 则f X Y X Y f X 若 x1 x2 X x1 x2 有f x1 f x2 X Y集合有限 f X X 矛盾 f为单射 返回第一节目录 3 举例 G B A b B G b x x A f x b 试证 若f是满射 则G是入射 其逆成立吗 证明 b1 b2 B b1 b2 f是满射 G b1 G b2 非空 若G b1 G b2 则 x G b1 G b2 即f x b1 f x b2 这与f是函数矛盾 G b1 G b2 G是入射 其逆不是真的 返回第一节目录 设f A B 返回总目录 一 复合函数1 复合函数定义2 复合函数是一个函数 证明 3 复合函数性质4 常数函数 恒等函数二 逆函数1 引理2 定义3 逆函数的性质4 逆像f 1 Y 5 例题三 单侧逆函数1 定义2 左逆函数 右逆函数存在的充要条件3 函数f存在逆函数的充要条件是函数f是双射 第二节逆函数和复合函数 1 复合函数定义设f X Y g Y Z是两个函数 则g f y y Y y f x z g y 称为g和f的复合函数 记为z g f x 一 复合函数 返回第二节目录 2 复合函数是一个函数 证明 x X f是一个函数 y Y 有y f x 又 g是一个函数 对该y z Z 有z g y x z z Z 有z g f x g f x g f是函数 返回第二节目录 3 复合函数性质 性质1 定理3 a 若g f是满射 则g f是满射 b 若g f是入射 则g f是入射 c 若g f是双射 则g f是双射 返回第二节目录 证明a证明b c 例题 3 复合函数的性质 设f X Y g Y Z 则g f X Z z Z g是满射 y Y 有z g y 又 f为满射 对此y x 有y f x 即z g f x g f是满射 a 若g f是满射 则g f是满射证明 返回复合函数性质 例 设f x x 2 g x x 2 h x 3x 均为实数集合到实数集合的双射 则g f x g x 2 x 2 2 x 为双射 h g f x 3x 为双射 b 若g f是入射 则g f是入射证明 x1 x2 X 若x1 x2 f为入射 f x1 f x2 又 g为入射 g f x1 g f x2 g f为入射 c 由a b 知 若g f为双射 则g f为双射 3 复合函数的性质 定理 a 若g f是满射 则g是满射 b 若g f是入射 则f是入射 c 若g f是双射 则g是满射 f是入射 证明 a f X Y g Y Z z Z g f是满射 x 有g f x z 又 f是一个函数 对此x y 有y f x 即 z Z y Y 有g y z g是满射 b c 省略 返回复合函数性质 4 常数函数 恒等函数 定义 若f X Y 若f X c 则称f是常数函数 若f X X x X 有f x x 称f是恒等函数 返回第二节目录 二 逆函数 设f x X y Y y f x fc f 证明fc是一个函数 y Y f是满射 x X 有 f 若有x x X f 这与f是入射矛盾 y Y x X 有 fc fc这个关系是一个从Y到X的函数 证明fc是满射 x X y有 f 即 fc fc是满射 1 引理 设f X Y是双射 则f的逆关系fc是一双射函数 证明 返回第二节目录 y1 y2 Y y1 y2 f为满射 x1 x2有f x1 y1 f x2 y2 若x1 x2 f为入射 有y1 f x1 f x2 y2与y1 y2矛盾 x1 x2 即 y1 y2 Y 有fc y1 x1 x2 fc y2 fc是单射 证明fc是单射 返回第二节目录 2 定义 设f X Y 若有函数g Y X 且g f Ix f g Iy 则称g为f的逆函数 记为f 1 注 因为g f Ix 而Ix为双射 由复合函数性质 知g为满射 f为入射 因为f g Iy 而Iy为双射 由复合函数性质 知f为满射 g为入射 若函数f有逆函数 当且仅当f为双射 且f 1也为双射 返回第二节目录 3 逆函数的性质 a 若f为双射 则 f 1 1 f 证明 f 1 f Ix f f 1 Iy f 1 1 f b g f 1 f 1 g 1证明 设f X Y g Y Z 则g f X Z g f f 1 g 1 g Iy g 1 g g 1 Iz f 1 g 1 g f f 1 Iy f f 1 f Ix g f 1 f 1 g 1 返回第二节目录 4 逆像f 1 Y 定义 设函数f X Y 且Y Y f 1 Y x f x Y 叫作Y 在f下的逆像 注 f 1有两种用途 a 当f 1的自变元是Y的元素时 f 1用来表示双射函数f的逆函数 b 当f 1的自变元是Y的子集Y 时 f 1 Y 表示Y 在f 1下的逆像 返回第二节目录 5 例题1 则f没有逆函数 但f 1 0 b c f 1 1 a f 1 3 4 例1f 例题2 返回第二节目录 证明 T ai A S g g ai A 0 i n 1 定义函数f S T f a 任意从 0 1 n 1 到A的映射的集合表示为 对S中的任一映射 对S中任一元素 存在唯一的函数值与该映射对应 f是一个函数 b 任取 T 在集合S中 存在映射 f是满射 c 在S中任取二个不相等映射 设g1 g2 即f g1 f g2 f是满射 存在一个从S到T的双射函数 例2 令R 0 n 1 返回第二节目录 三 单侧逆函数 1 定义 设f X Y g Y X 如果g f Ix 则称g是f的左逆元 左逆函数 f是g的右逆元 右逆函数 返回第二节目录 2 左逆函数 右逆函数存在的充要条件 a f有左逆元当且仅当f是单射 b f有右逆元当且仅当f是满射 返回第二节目录 证明a证明b 2 充要条件证明 f有左逆元当且仅当f是单射a 必要性 若f有左逆元g g f Ix Ix是单射 由复合函数性质2 f是单射 充分性 设f是单射的 定义g如下 g Y X 若y f X 且f x y 则定义g y x 若y f X 则定义g y x0 y Y x 使g y x 又 f是单射 此x是唯一的 g是一个函数 x X gf x g f x g y x gf Ix 返回存在的充要条件 2 充要条件证明 b f有右逆元当且仅当f是满射 必要性 设g是f的右逆元 则fg Iy Iy是满射 由复合函数性质2 知 f是满射的 充分性 用构造性证明 定义g如下 g Y Z g y x x是满足f x y中的任意确定的一个 f是满射 有g的定义 y Y x 使g y x g是一个函数 y Y fg y f x y fg Iy 返回存在的充要条件 3 函数f存在逆函数的充要条件是函数f是双射 证明 设f X Y 必要性 若f是双射 由逆函数引理知 逆函数存在 充分性 若函数f存在逆函数f 1 则由逆函数性质1 知 f 1 f Ix f f 1 Iy f有左 右逆元 由2知 f是既满又单 f是双射函数 返回第二节目录 返回总目录 第三节特征函数与模糊子集 一 集合A的特征函数1 定义2 性质3 举例 1 定义 一 集合A的特征函数1 定义 设U是全集 A U 函数 A U 0 1 A x 10若x A否则称 A x 是集合A的特征函数 例 设U 0 1 A 1 2 1 A U 0 1 则 A x 10 x 0 1 2 x 1 2 1 返回第三节目录 2 特征函数性质 1 A x 0 A 2 A x 1 A U3 A x B x A B4 A x B x A B5 A x 1 A x 6 A B x A x B x 7 A B x A x B x A B x 返回第三节目录 证明3证明6 2 性质3证明 A x B x A B3 若 A x B x 则 x A A x 1 又 A x B x B x 1 x B A B 若A B A x B x A x B x 0 A x B x 0 x A 1 x B x A 0 x B 返回特征函数性质 2 性质6证明 证明 x A B 则 A B x 1 A x 1 B x 1 等式成立 x A B 则 A B x 0 A x 0 或 B x 0 A B x A x B x 返回特征函数性质 6 A B x A x B x 3 举例 试用特征函数证明 A B C A B A C证明 A B C x A x B C x A x B x C x B x C x A B x A C x A B C x A B x A C x A B A C x A B A C x A B C A B A C 返回第三节目录 返回总目录 第四节基数概念 为比较两个集合元素的多少 需要确定基数的概念 一 自然数的定义1 集合A的后继集定义2 Peano公理二 等势三 有限集与无限集四 基数1 定义2 举例 1 集合A的后继集定义 A A A 例 一 自然数的定义 返回第四节目录 2 peano公理 1 0 N 0 2 若n N 则n N n n 1 3 最小性条款 若S N 且S满足1 2 则S N 返回第四节目录 二 等势 1 等势定义 若集合A和B之间存在双射 称A B等势 即集合元素个数相等 记为A B 例 试证明 集合 1 1 与 等势 证明 令f x tg 2 x 1 则 y 取x arctgy 2 有f x y f是满射 2 又 x1 x2 则f x1 tg 2 x1 tg 2 x2 f x2 f是单射 集合 1 1 与 等势 2 等势关系是一个等价关系 返回第四节目录 三 有限集与无限集 1 定义 若 0 1 n 1 到集合A存在双射 称集合A为有限集 否则称为无限集 例 试证明自然数集N是无限集 证明 反证法 设N是有限集 f 0 1 n 1 N 是一一映射 设K 1 max f 0 f n 1 则K N 但不存在x 有f x K f不是满射 矛盾 自然数集N是无限集 返回第四节目录 四 基数 1 定义 所有与集合A等势的集合所组成的集合 称为集合A的基数 记为K A 注 k A K B A B等势 例 A a b c B 桌 灯 笔 C 1 2 3 则K A K B K C A B C 返回第四节目录 2 举例 证明 令A 0 1 1 2 1 3 1 n 则A 0 1 f x 现证f是双射 1 y 0 1 a 若y 0 1 A 则取x y 有f x y b 若y A 0 1 则取x 1 1 y 2 有f x y f满射 2 x1 x2 有f x1 f x2 f是单射 证毕 f 0 1 2 x 0 f 1 n 1 n 2 x 1 n n 1 f x x x 0 1 A 例 试证明 0 1 与 0 1 基数相等 一 可数集1 定义2 可数集判别法3 可数集的性质a b c d e f 二 不可数集 五 可数集与不可数集 一 可数集 1 定义 与自然数集等势的任何集合称为可数集 其基数用N0 读作阿力夫零 表示 例 A 0 1 4 9 B 0 2 4 6 8 则K A K B N0有限集和可数集称为至多可数集 返回第五节目录 2 可数集判别法 定理1 A为可数 A的全部元素可以排列为 a1 a2 证明 若A a1 a2 将an与自然数n 1对应 则此对应是一个双射 A可数 若A可数 则A与N存在一一映射f 由f得n所对应的元素an 1 A可排列为 a1 an 返回第五节目录 3 可数集的性质 a 任一无限集 必会有可数子集 证明 A为无限集 取出一元素a1 则A a1 仍为无限集 再取一元素a2 如此继续 得A的可数子集 返回第五节目录 3 可数集的性质b 任一无限集M 必与自己的某真子集等势 证明 由a 可得M的可数子集A a1 a2 令M A B 令f M M a1 f an an 1 an A f b b b B 则易证f是一个双射 所以M等势于M a1 证毕 3 可数集的性质c 可数集A的任何无限子集B是可数集 证明 设A a1 a2 从a1开始不断删除不在B中的元素 得集合B ai1 ai2 因为B可列 所以B可数 返回第五节目录 3 可数集的性质d 可数个可数集的并集是可数集 证明 设S1 a11 a12 a13 a1n S2 a21 a22 a23 a2n S3 a31 a32 a33 a3n Sn an1 an2 an3 ann 令B a11 a21 a12 a31 a22 a13 B K 1Sk是可列集 所以B是可数集 3 可数集的性质e N N是可数集 证明 N N N N是可数集 返回第五节目录 3 可数集的性质f 有理数集是可数集 证明 由e 知N N是可数集 在N N删除m n不是互质的序偶得S S是N N的无限子集 S可数 令g S Q g m n 则g是双射 Q 可数 又 Q Q Q Q Q 0 为可数集 返回第五节目录 二 不可数集 例 证 0 1 是不可数集 0 1 的基数记为 N 证明 反证法 设 0 1 可数 0 1 a1 a2 ai 0 1 设a1 0 a11a12a13 a2 0 a21a22a23 aij为数字0 1 9a3 0 a31a32a33 an 0 an1an2an3 构造一个实数r 0 b1b2b3 bi 21aii 1aii 1则r 0 1 但r a1 a2 an 这与 0 1 a1 a2 矛盾 所以 0 1 是不可数集 注 R 0 1 K R N 一 证明基数的方法1 康斯伯定理2 查密勒定理3 康伯定理二 关于基数的一些定理1 2 3 第六节基数的比较 返回总目录 直接证明基数相等比较困难 下面介绍简单证明基数相等法 一 康斯伯定理1 定义 若从集合A到集合B存在一个单射 记K A K B 若从集合A到集合B存在一个单射 但是不存在双射 记K A K B 一 康斯伯定理 返回第六节目录 2 查密勒定理