离散-2016dm8.2函数复合和可逆

设fg：B→C是两个函数，二元关系f与g的复合，原该记为 例函数复合g∘f关系复合设A={1,2,3B={a,bc,dC={xy g∘f={(1,x),(2,y), f∘g={(1,x),(2,y), 设f

- g:求：f∘g,解：f∘g(x)g∘f:g∘f(x) 定理1设f：A→B，则h∘(g∘f)=(h∘g)(f∘g) 定理设f：Ag：B→则如果f和g均是单射，则g∘f如果f和gg∘f如果f和g均是双射，则g∘f 定理2设f：AB，g：BCf和g均是单射，则g∘f若g∘f(x1)=g∘f(x2),g是单射，所以有f是单射，所以有x1=x2。则g∘f是单射函数。 定理2设f：AB，g：BCf和g均是满射，则g∘f因为g则z=g(f(x))=g∘f(x)。所以g∘f 例A，B，C是三个集合，f是A到B的 ，g是B到C的 若g∘f是A到C的单射，则f是A到B请举出一个g∘f是A到C的单射，但g不是B到C证:用反证法。如果f不是A到B的单射，则存在x1≠x2,使得f(x1)=f(x2)于是g(f(x1))=g(f(x2)),即gf(x1)=gf(x2),这与gf是单射。 例A，B，C是三个集合，f是A到B的 ，g是B到C的 若g∘f是A到C的单射，则f是A到B请举出一个g∘f是A到C的单射，但g不是B到C f：A→g：B→g∘f：A→单单├单├单├单 例A，B，C是三个非空集，f是A到B ①证明：若g∘f是A到C的满射，则g是B到C的满射②给出一个反例，说明g∘fg也是满射，但f证:由g∘f对于任意的c∊C,使得g∘f(a)=cg(f(a))=c。记b=f(a),即有g(b)=c即证得g 例A，B，C是三个非空集，f是A到B ①证明：若g∘f是A到C的满射，则g是B到C的满射②给出一个反例，说明g∘fg也是满射，但f 8.2 f是A到B的g是B到C的。若gg∘f是A到C的满射。证:用反证法。fy∊Bx∊Af(x)再由g的单射性,对于任意x∊Ag(f(x))≠g(y)记z=g(y)∊C,x∊Ag∘f(x) f：A→

g：B→

g∘f：A→ ├满├ ├ ├满 设若存在函数g：B→A，使得则称f是右可逆函数，并称g是f的右逆函数。若存在函数g：B→A，使得g∘f=△A，则说f是可逆函数。 设f：A→B，若f是可逆函数，存在唯一的g：B→Ag∘f=△A证明：由定义知，存在g1：B→A，g2：B→Ag1∘f=△A则g1=g1∘△B=g1∘(f∘g2)=(g1∘f)即存在g：B→A,使得g∘fA，f∘g=△B。 逆函数f-规定若f：A→B则用f-1表示ff-f-1∘f=△A f-1={(x,y)∊B×A│(y,x)注意比较：象源集f-1(B’) 定理

设f：A→Bf是右可逆函数当且仅当f 定理4 证明“”对于任意的使得若存在函数若存在函数g：B→A，使得 定理4 “”

B 定理4 “因为fy∊B,存在x→A,使得f(x)=y。定义一个从B到A的函数g，对于任意的y∊B，g(y)=xy，这里取定xyAy’={x∊A│f(x)=yØ于是对于任意的 f∘g=△B故f 定理42)ff证明“x1，x2∊A,若f(x1)=f(x2),因为存在g：B→Ag∘f 即 故f 定理42)ff“”先看一个例 定理42)ff

若y∉f(A)g(y)=x’x∊A。 只证“”因为f是双射函数，所以对于任意的y∊B，由定义，对于任意的所 g∘f=△A 即f是可逆函数。 例设f：N→N，f(n)=2n+1，对于任意的n∊N问f解：显然，ff n ng：N→N是f的一个左逆函数。这样的函数可以举出无

已知N是自然数集，f:N→N，即f是N到N ？f是否有左 ？若有，请给解：显然，f不是满射，没有右 f是单射，有左 g:N→N，对于 0

xx

对于任意的x，y∊A，若(x，y)∊R当且仅当f(x)=f(y)，则:称函数φ：A→A/R，对于任意的a∊A，φ(a)=[a]R为自然 f:A/R→B，使得f∘φ=f。[a]R→f(a),即 ◆首先必须证明f是函 x∊A，∵f(x)=f(x),x,x∊R。故R是自反的。对于任意的x，y∊Ax，y∊R,∴f(x)=f(y)，即有f(y)=f(x),则(y，x)∊R。对于任意的x，y，z∊A，若(x，y∊R(y，z)∊R，则f(x)=f(y)且f(y)=f(z),即有f(x)=f(z) [a]R→f(a),即◆首先必须证明fa]R=[b]R，要证明f(a)=f(b∵[a]R=[b]R，∴a[b]R，∴(a，b)∊R,f(a)=f(b)。即对于任意的x∊A/R，存在唯一的f(