数理逻辑 课程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.