数理逻辑 课程XI
数理逻辑 课程XI
第山章函数 上一章研究了关系的自反,传递、对称等 性质,并针对这些性质研究了一些特殊的 关系,如等价关系、偏序关系.这一章研 究的各类函数是另外一些特殊的关系,这 是从它们的单值性、定义域和值域的性质 来讨论的.函数是一个基本的数学概 念.通常的实函数是在实数集合上讨 的.这里推广了实函数概念,讨论在任意 集合上的函数
第11章 函 数 • 上一章研究了关系的自反，传递、对称等 性质，并针对这些性质研究了—些特殊的 关系，如等价关系、偏序关系．这一章研 究的各类函数是另外一些特殊的关系，这 是从它们的单值性、定义域和值域的性质 来讨论的．函数是一个基本的数学概 念．通常的实函数是在实数集合上讨论 的．这里推广了实函数概念，讨论在任意 集合上的函数．
LL.1函数和选择公理 ⊥111函数定义 定义11.1.1对集合A到集合B的关系f,若满足下列条件: 1)对任意的x∈dom(f,存在唯一的y∈ran(f),使xy成 (2)dom(f)=A 则称f从A到B的函数,或称f把A映射到B(有的书称f为全 函数、映射、变换 0一个从A到B的函数f,可以写成f:A→B,这时若xy,则 一可记作f:x→y或f(×)=y °若A到B的关系f只满足条件(1),且有dom(f)<A,则称f为 从A到B的部分函数(有的书上称f为函数)
11．1 函数和选择公理 11.1.1 函数定义 • 定义11.1.1 对集合A到集合B的关系f，若满足下列条件： (1)对任意的x∈dom(f)，存在唯一的y∈ran(f)，使xfy成 立； (2)dom(f)=A 则称f为从A到B的函数，或称f把A映射到B(有的书称f为全 函数、映射、变换) • 一个从A到B的函数f，可以写成f：A→B，这时若xfy，则 可记作f：x|→y或f(x)=y. • 若A到B的关系f只满足条件(1)，且有dom(f)A，则称f为 从A到B的部分函数(有的书上称f为函数)
函数的两个条件可以写成 1)×(y1)(Vy2)(xhy1^xy2)→y1=y2), (2(×)(×∈A→(y)(y∈B^xfy) 函数的第一个条件是单值性,定义域中任一x与B中唯一的 y关系,因此,可以用f(x)表示这唯一的y.第二个条件 是A为定义域,A中任X都与B中某个y有关系注意不能把 单值性倒过来,对A到B的函数f,当xf且x2成立时,不 定X1=x2;因此,函数的逆关系不一定是函数 ●如果一个关系是函数,则它的关系矩阵中每行恰好有一个 1,其余为0。它的关系图中每个A中的顶点恰好发出一条 有向边
• 函数的两个条件可以写成 (1)(x)(y1)(y2)((xfy1^xfy2)→y1=y2)， (2)(x)(x∈A→(y)(y∈B^xfy))． • 函数的第—个条件是单值性，定义域中任一x与B中唯一的 y有关系，因此，可以用f(x)表示这唯一的y．第二个条件 是A为定义域，A中任一x都与B中某个y有关系.注意不能把 单值性倒过来，对A到B的函数f，当x1fy且x2fy成立时，不 一定x1=x2；因此，函数的逆关系不一定是函数． • 如果一个关系是函数，则它的关系矩阵中每行恰好有一个 1，其余为0。它的关系图中每个A中的顶点恰好发出一条 有向边．
例1对实数集R,R上的关系千为 f={×,y>|y 是从R到R的函数,记作f:R→R,并记作f:X→×3或f(x) 例2集合A={1,2,3}上的两个关系 g=,,,} 都不是从A到A的函数. 因为g没有单值性,即∈g且有∈g,而对 关系h,dom(h)={1,2}≠A.但是,h是从{1,2}到A的函
• 例1 对实数集R，R上的关系f为 f＝{|y=x3} f是从R到R的函数，记作f：R→R，并记作f：x|→x 3或f(x) ＝x 3． • 例2 集合A={1，2，3}上的两个关系 g＝{，，，} 和 h={，} 都不是从A到A的函数． • 因为g没有单值性，即∈g且有∈g，而对 关系h，dom(h)={1，2}≠A．但是，h是从{1，2}到A的函 数．
定义11,1.2对集合A和B,从A到B的所有函数的集合记为A有的书记 ff:A→B} 例3对A={1,2,3},B={a,b}.从A到B的函数有8个: ={,,} f2={,,} f={,} 阵={,, 5=区1,b>,,} f6={,,} 7={,,} f8={,,} 于是AB={f1,f2,f3,…,f8}
• 定义11.1.2 对集合A和B，从A到B的所有函数的集合记为AB (有的书记 为B A)．于是，AB＝{f|f：A→B}． • 例3 对A＝{1，2，3}，B＝{a，b}．从A到B的函数有8个： f1={，，} f2={，，} f3={，，} f4={，，} f5={，，} f6={，，} f7={，，} f8={，，} 于是 AB＝{f1，f2，f3，…，f8}
若A和B是有限集合,且|A|=m,|B|=n, 则AB|=m.从Φ到Φ的函数只有f=①,从 ①到B的函数只有f一Φ.若A≠,从A到Φ的 函数不存在,因此,Φa=ΦB={},A= (对A≠①)
• 若A和B是有限集合，且|A|＝m，|B|＝n， 则|AB|＝n m．从到的函数只有f＝，从 到B的函数只有f＝．若A≠，从A到的 函数不存在．因此，=B={}，A ＝ (对A≠)．
定义11.1.3设f:A→B,A1A,定义A1在f下的 象代A山为A1]=(x)(x∈A^y=f×),把fA 为函数的象, )设BB,定义B1在f下的完全原象f1B1]为 fB1={×X∈A^f(x)∈B1} 注意,在上一章f1表示f的逆关系.这个定义中的 f[B1表示完全原象,可以认为其中的f1是f的逆 关系,因为函数的逆关系不一定是函数,所以f1 表示逆关系,不是逆函数(除非特别说
• 定义11.1.3 设f：A→B，A1A，定义A1在f下的 象f[A1]为f[A1]={y|(x)(x∈A1^y=f(x))}，把f[A] 称为函数的象， • 设B1B，定义B1在f下的完全原象f -1 [B1]为 f -1 [B1]＝{x|x∈A^f(x)∈B1} • 注意，在上—章f -1表示f的逆关系．这个定义中的 f -1 [B1]表示完全原象，可以认为其中的f -1是f的逆 关系，因为函数的逆关系不一定是函数，所以f -1 一般只表示逆关系，不是逆函数(除非特别说 明)．
例4f:Z→Z定义为 当x为偶数 f(x) 斗x为奇数 fN]=N,f{-1,0,1」={-1,0} -[:2,3}=〈4,5,6,7 特别地 [的]=f[必]=
L112特殊的函数 等价关系利函数都是特殊的关系,同样可以定义一些特殊 的函数,它们是具有某种性质的函数, 定义11.1.4设f:A→B )ran(f)=B,则称f是满射的,或称f是A到B上的, (2若对任意的×1,x2∈A,X1#x2,都有f(×1)(X2),则称f 是单射的,或内射的,或一对一的, (3)若f是满射的又是单射的,则称f是双射的,或一对一A到B 的.简称双射 如果f:A→B是满射的,则对任意的y∈B,存在x∈A,使 f(x)=y.如果f:A→B是单射的,则对任意的y∈ran(f), 存在唯一的x∈A,使fx)=y
11.1. 2 特殊的函数 • 等价关系利函数都是特殊的关系．同样可以定义一些特殊 的函数，它们是具有某种性质的函数， • 定义11．1．4 设f：A→B． (1)若ran(f)＝B，则称f是满射的，或称f是A到B上的， (2)若对任意的x1，x2∈A，x1≠x2，都有f(x1)≠f(x2)，则称f 是单射的，或内射的，或—对一的， (3)若f是满射的又是单射的，则称f是双射的，或一对一A到B 上的．简称双射． • 如果f：A→B是满射的，则对任意的y∈B，存在x∈A，使 f(x)＝y．如果f：A→B是单射的，则对任意的y∈ran(f)， 存在唯一的x∈A，使f(x)＝y．