4.偏序集合中的几个特殊元素 定义：设(A,≤)是一个偏序集合, BA,若存在一个元素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的最大元.

Presentation on theme: "4.偏序集合中的几个特殊元素 定义：设(A,≤)是一个偏序集合, BA,若存在一个元素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的最大元."— Presentation transcript:

1 4.偏序集合中的几个特殊元素 定义：设(A,≤)是一个偏序集合, BA,若存在一个元素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的最大元无。

2 A2={2,3,6,12,24,36},(A2,|) A2既无最小元，也无最大元。 偏序集或它的子集不一定存在最小元(最大元) 偏序集存在最小元(最大元)，它的子集也不一定存在最小元(最大元) 定理：在(A,≤)中，BA，若B存在最大元(最小元)，则必唯一。 证明：假设B有两个最大元a1,a2,

3 对任何非空有限子集，极大元、极小元一定存在 若子集B有最大元(最小元)，则B的极大元(极小元)唯一
定义：设(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,|) 这些说明： 极大元(极小元)不唯一 最大元(最小元)必是极大元(极小元) 对任何非空有限子集，极大元、极小元一定存在 若子集B有最大元(最小元)，则B的极大元(极小元)唯一

4 定义：设(A,≤)是一个偏序集合, BA,若存在一个元素aA, 对所有b'B都有b'≤a, 则称a是B的上界；对所有b'B都有 a≤b', 则称a是B的下界。
注意最大元(最小元)与上界(下界)的区别 最大元(最小元)要求最大元(最小元)B,而上界(下界)无此要求 例:A2={2,3,6,12,24,36},(A2,|) P={2,3,6}, B={2,3},

5 上界(下界)可能存在，也可能不存在。 上界(下界)不一定唯一。 上界(下界)可以是B中的元素，也可以不是 定义：设(A,≤)是一个偏序集合, BA，若aA是B的上界且对B中每个上界a'都有a≤a', 则称a为B的上确界(或称最小上界)；若aA是B的下界且对B中每个下界a'都有a'≤a,则称a为B的下确界(或称最大下界)。

6 例:A2={2,3,6,12,24,36},(A2,|) P={2,3,6},P的上界{6,12,24,36}， B={2.3}, 例:A3={6,9,36,54},(A3,|) B={6,9}, 上确界(下确界)唯一 上确界(下确界)可以是B中的元素，也可以不是 存在上界(下界)，上确界(下确界)不一定存在。

7 RA×B,R为A到B的二元关系，DomRA。
若DomR=A,且规定对每个aA,有唯一的b与之对应，即不允许出现(a,c),(a,b)R出现。 满足这两条的称为函数。

8 第三章 函数 3.1 函数的基本概念

9 一、函数的定义及其表示 定义3.1：设A和B是两个任意集合, f是从A到B的二元关系。若f具有性质: (1)f的定义域Domf=A； (2)如果(a,b),(a,b')f, 则b=b'。 则称关系f是从A到B的函数,记为f:A→B,称b为a的象,a为b的原象,记为b= f(a)。f的值域记为Rf。又称f为从A到B的映射。 (1)由DomRA变为DomR=A,即定义域有区别。 (2)对于关系允许(a,b),(a,b')R,而函数则是不允许的除非b=b'。

10 例：设A={1,2,3,4},B={a,b,c},从A到B的关系:
R1={(1,a),(2,b),(3,c)}, R2={(1,a),(1,b),(2,b),(3,c),(4,c)}, R3={(1,a),(2,b),(3,b),(4,a)} DR1={1,2,3}A,不是函数。 DR2={1,2,3,4}=A,但(1,a),(1,b)R2,故不是函数。 R3是函数

11 定义：设函数f:A→B, 若存在bB，使得对所有aA,有f(a)=b,则称f为常值函数。
定义 3.6：设函数f:A→A, 若对所有aA,有f(a)=a,则称f为A上的恒等函数,记为IA。 下面讨论函数象集的运算。 二、函数的象 定义3.2：设函数f:A→B,XA,YB,定义:f(X)={f(a)|aX}，称f(X)是在f 下X的象。f -1(Y)={aA|f(a)Y},称f -1(Y)是在f下Y的原象。

12 定理(一)：设函数f:A→B, (1)设XA,则X,当且仅当f(X) (2)对每个aA, f({a})={ f(a)} 对于a.f(a),a的象f(a). {a}的象{ f(a)} 定理(二)：设函数f:A→B, A1,A2为A的子集， (1)若A1A2,则f(A1) f(A2) (2) f(A1∩A2) f(A1)∩f(A2) (3) f(A1∪A2)= f(A1)∪f(A2) (4) f(A1)- f(A2) f(A1-A2) 要注意(2),(4)等式不一定成立

13 证明：(3) f(A1)∪f (A2) f(A1∪A2)
f(A1∪A2) f(A1)∪f (A2) 因此f(A1∪A2)= f(A1)∪f(A2) (4)对任意y f(A)-f(B)，目标y f(A-B) 要注意的是等式不成立

14 定理(三)：设函数f:A→B, AiA (y=1,2,…n)，

15 三、不同函数的个数 下面我们来讨论集合A到集合B可以定义多少个不同的函数。 从关系来讲，A×B的子集都是A到B的关系，故集合A到集合B的二元关系个数是2|A||B|，而根据函数定义，A×B的子集不一定是A到B的函数。 设|A|=m,|B|=n, A到B的函数有nm个， 用BA表示A到B的函数全体所组成的集合，则|BA|=nm

16 四、几类特殊的函数 这里要介绍在函数中常要讨论的几个特殊函数：满射，内射和双射。 定义3.3：(1)设函数f:A→B,若Rf=B,则称f为满射或称f为到上的。 (2)设函数f:A→B, 若a1,a2A,a1a2有f(a1)f(a2),则称f为内射或称f为一对一的。 (3)设函数f:A→B, 若f是满射,且内射, 则称f为双射,或称f为一一对应的。

17 定义：设函数f、g:A→B,若对任意aA,有f(a)=g(a)，则称函数f和g相等，记为f=g。 例：在实数范围内，
例:设函数f1:R(实数集)→C(复数集), f1(a)=i|a|; f1不是内射,不是满射。 设函数f2:R(实数集)→C(复数集), f2(a)=ia; f2为内射,不是满射。 设函数f:Z→Zm={0,1,…m-1}, f(a)=a mod m 满射,不是内射。 定义：设函数f、g:A→B,若对任意aA,有f(a)=g(a)，则称函数f和g相等，记为f=g。 例：在实数范围内， f(x)=x+1,g(x)= x(x+1)/x 两个函数是否相等必须考察它们的定义域是否相同。

18 3.2 逆函数与复合函数 一、复合函数 定理：设函数g:A→B,f:B→C,则A到C的复合关系gf是A到C的函数。
3.2 逆函数与复合函数 一、复合函数 定理：设函数g:A→B,f:B→C,则A到C的复合关系gf是A到C的函数。 证明：先证明对A中任一元素,都有C中元素与之对应,然后证明对A中每个元素,都只对应C中一个元素 (1)对A中任一元素a,都有C中元素与之对应 (2)对A中每个元素,都只对应C中一个元素 即证明对A中元素a，若有x,yC，使得(a,x)gf，(a,y)gf，必有x=y。

19 定义3.5：设函数g:A→B,f:B→C,称复合关系gf是从A到C的复合函数,记为fg:A→C。对aA,有(fg)(a)= f(g(a))。
注意：这里采用复合函数习惯记法,目的是为了将变元放在函数记号的右侧，使(fg)(a)= f(g(a)),所以用记号(fg)，而不用gf。 例：A={1,2,3}, f、g是集合A到A的函数。 g={(1,2),(2,1),(3,3)}, f={(1,2),(2,3),(3,1)} 一般fg≠gf

20 定理3.3：设函数g:A→B,f:B→C,h:C→D,则(hf )g=h(fg)
证明：函数是特殊的关系,关系的复合运算满足结合律,则函数的复合运算自然满足结合律

21 定理 3.4：设函数g:A→B,f:B→C, fg: A→C, 则 (1)若f和g是满射,则fg是满射。
证明：(1)要证明fg满射，就是证明对C中每个元素都有A中元素与之对应。 (2)所谓内射就是要证明当ab时，fg(a) fg(b) (3)f和g是双射,所以f和g当然满射, 内射， 所以fg是双射。

22 注意定理 3.4的逆是不一定成立的，请考虑原因 但是fg是满射，f必定满射；fg内射，g必定内射。 fg双射，则f必定满射，g必定内射。 二、逆函数 例:A={1,2,3},B={a,b}, f:A→B, f={(1,a),(2,b),(3,b)}是函数，但其逆关系f-1 ={(a,1),(b,2),(b,3)}, 不符合函数的定义，不是函数。

23 定理：设函数f:A→B, 则f的逆关系是函数当且仅当f是双射。 证明：(1)若f -1是函数，则f是双射
(i)先证明f是满射。 对于任意bB，找aA,使得(a,b) f ， (ii) f内射。 若存在a1,a2A，有f(a1)= f(a2)=bB,目标证明 a1=a2。 (2)若f是双射，则f -1是函数 分析：要证明f-1是函数即证明对任意bB，存在唯一的aA，使得(b,a) f-1, 存在性,对任意bB，找aA，使得(b,a) f-1, 唯一性 若对于bB，存在a1,a2A，有(b,a1) f-1 (b,a2) f-1,目标证明a1=a2。

24 作业:p45 36,42, 44,45 P52 5,6,7,15,16,20,21(2),22,23, 24, 25 说明:这里自然数集N是包含0的,即N是非负整数集