复旦大学：《离散数学 Discrete Mathematics（上）》英文课件（赵一鸣）06/30

&Theorem 3.5: Let f be an everywhere function from a to B. Then 令(1)f i)lB°f=f o Proof Concerning(i), let aEA, o IA(a? -fa) g Property (ii) is proved similarly to property ()

❖ Theorem 3.5: Let f be an everywhere function from A to B. Then ❖ (i)f IA =f. ❖ (ii)IB  f = f. ❖ Proof. Concerning(i), let aA, (f  IA)(a) ?=f(a). ❖ Property (ii) is proved similarly to property (i)

Theorem 3.6: Let g be an everywhere function from A to B, and f be an everywhere function from b to c. Then &( fand g are onto, then fo g is also onto 4(2)Iff and g are one to one, then fog is also one to one &3)Iffand g are one-to-one correspondence, then fog is also one-to-one correspondence 令 Proof:(1) for every c∈C, there exists a∈ A such that f°g(a)=c

❖ Theorem 3.6: Let g be an everywhere function from A to B, and f be an everywhere function from B to C. Then ❖ (1)if f and g are onto , then f  g is also onto. ❖ (2)If f and g are one to one, then f  g is also one to one. ❖ (3)If f and g are one-to-one correspondence, then f  g is also one-to-one correspondence ❖ Proof: (1) for every cC, there exists aA such that f  g(a)=c

冷(2)0 ne to one:ifa≠b, thenf。g(a)?≠f。g(b) &3)fand g are one-to-one correspondence, → fand g are onto.By(1),→f° g are onto By(2),→f° g are also one to one. Thus g is also one-to-one correspondence

❖ (2)one to one:if ab，then f  g(a)? f  g(b) ❖ (3)f and g are one-to-one correspondence, f and g are onto. By (1), f  g are onto. ❖ By (2),  f  g are also one to one. Thus f  g is also one-to-one correspondence

.2. Inverse functions ☆ Inverse relation, . 8 Function is a relation ☆ Is the function’ s inverse relation a function? No 今 Example:A={1,2,3},B={a,b},f:A→→B,f k( 1, a), (2, b), 3, b) is a function, but inverse relation f-l=(a, 1), (b, 2), (b, 3) is not a function

❖ 2. Inverse functions ❖ Inverse relation, ❖ Function is a relation ❖ Is the function’s inverse relation a function? No ❖ Example: A={1,2,3},B={a,b}, f:A→B, f ={(1,a),(2,b),(3,b)} is a function, but inverse relation f -1={(a,1),(b,2),(b,3)} is not a function

o Theorem 3.7:: a) Let f be a function from a to B, Inverse relation f- is a function from B to A if only iff is one to one &(b) Let f be an everywhere function from a to B, Inverse relation f-I is an everywhere function from B to A if only if f is one-to-one correspondence. o Proof:(a(1)Iff- is a function, then f is one to one 今 If there exist a,;a2∈ A such that f(a1)=fa2)=b∈B, then a1?=a2 o(2)If f is one to one, then f- is a function 冷∫ is a function Forb∈B, If there exist a1,a2∈ A such that(b,a1)∈f1 and(b, a2)ef-, then a? =a2

❖ Theorem 3.7: :(a) Let f be a function from A to B, Inverse relation f -1 is a function from B to A if only if f is one to one ❖ (b) Let f be an everywhere function from A to B, Inverse relation f -1 is an everywhere function from B to A if only if f is one-to-one correspondence. ❖ Proof: (a)(1)If f –1 is a function, then f is one to one ❖ If there exist a1 ,a2A such that f(a1 )=f(a2 )=bB, then a1?=a2 ❖ (2)If f is one to one，then f –1 is a function ❖ f -1 is a function ❖ For bB，If there exist a1 ,a2A such that (b,a1 )f -1 and (b,a2 ) f -1 ,then a1?=a2

%o Proof:(b)(1)Iff- is an everywhere function, then f Is one-to-one correspondence. ☆( if is onto For any b∈B, there exists a∈ A such that f(a)=2b ☆(i) f is one to one ☆ If there exist a1;a2∈ A such that f(a1)f(a2)=b∈B, then a,?=a 2 4(2)ffis one-to-one correspondence, then f-lis a everywhere function %- is an everywhere function, for any beB, there exists one and only a∈ A so that(b,a)∈f1. For any b∈B, there exists a∈ A such that(ba)∈?f1 Forb∈B, If there exist a1,a2∈ A such that(b,a1)∈f1 and(b, a2)ef-, then a1?=a2

❖ Proof: (b)(1)If f –1 is an everywhere function, then f is one-to-one correspondence. ❖ (i)f is onto. ❖ For any bB，there exists aA such that f (a)=?b ❖ (ii)f is one to one. ❖ If there exist a1 ,a2A such that f (a1 )=f (a2 )=bB, then a1?=a2 ❖ (2)If f is one-to-one correspondence，then f –1 is a everywhere function ❖ f -1 is an everywhere function, for any bB，there exists one and only aA so that (b,a) f -1 . ❖ For any bB, there exists aA such that (b,a)?f -1 . ❖ For bB，If there exist a1 ,a2A such that (b,a1 )f -1 and (b,a2 ) f -1 ,then a1?=a2

Definition 3.5: Let f be one-to-one correspondence between A and B We say that inverse relation f-l is the everywhere inverse function of f. We denoted f B-A And iff(a)=b then f-(b)=a &o Theorem 3.8: Letf be one-to-one correspondence between A and B. Then the inverse function f-lis also one-to-one correspondence. 8 Proof: (1)f-is onto(f- is a function from B to A For any a∈A, there exists b∈ B such that f(b=a) 冷(2f- is one to one For any b1,b2∈B,ifb1≠b2 then f1(b1)≠f1(b2) 冷IffA→ B is one-to-0 ne correspondence, then f1 B-A is also one-to-one correspondence. The function f is called invertible

❖ Definition 3.5: Let f be one-to-one correspondence between A and B. We say that inverse relation f -1 is the everywhere inverse function of f. We denoted f -1：B→A. And if f (a)=b then f -1 (b)=a. ❖ Theorem 3.8: Let f be one-to-one correspondence between A and B. Then the inverse function f -1 is also one-to-one correspondence. ❖ Proof: (1) f –1 is onto (f –1 is a function from B to A ❖ For any aA,there exists bB such that f -1 (b)=a) ❖ (2)f –1 is one to one ❖ For any b1 ,b2B, if b1b2 then f -1 (b1 ) f -1 (b2 ). ❖ If f:A→B is one-to-one correspondence, then f -1： B→A is also one-to-one correspondence. The function f is called invertible

Theorem 3.9: Let f be one-to-one correspondence between A and B 8 Then 冷(1)f1)=f 冷(2f1户=IA 冷(3)f°f1=IB 冷Pro0f:(1)f1)l=f 冷(2f1=IA 令Letf:A→ B and g:B→A, %Is g the inverse function off? 令∫g?= IB andg of?=IA

❖ Theorem 3.9: Let f be one-to-one correspondence between A and B. ❖ Then ❖ (1)(f -1 ) -1= f ❖ (2)f -1  f=IA ❖ (3)f  f -1=IB ❖ Proof: (1)(f -1 ) -1= f ❖ (2)f -1  f=IA ❖ Let f:A→B and g:B→A， ❖ Is g the inverse function of f ? ❖ f g?=IB and g  f ?=IA

o Theorem 3.10: Let be one-to-one correspondence between A and B, andf be one-to-one correspondence between B and c Then ()-=gl of-I o Proof: By Theorem 3.6,f og is one-to-one correspondence from A to C o Similarly, By theorem 3.7, 3.8, 8- is a one-to one correspondence function from B to A, and f-l is a one-to-one correspondence function firom c to B

❖ Theorem 3.10：Let g be one-to-one correspondence between A and B, and f be one-to-one correspondence between B and C. Then (fg) -1= g -1 f -1 ❖ Proof: By Theorem 3.6, f g is one-to-one correspondence from A to C ❖ Similarly, By theorem 3.7, 3.8, g -1 is a one-to￾one correspondence function from B to A, and f –1 is a one-to-one correspondence function from C to B

.8 Theorem 3.11: let a and b be two finite set with AFBl, and let f be an everywhere function from a to B. Then 8(1)Iff is one to one, then f is onto. 令(2川 ifis onto, then f is one to one. . The prove are left your exercises

❖ Theorem 3.11: Let A and B be two finite set with |A|=|B|, and let f be an everywhere function from A to B. Then ❖ (1)If f is one to one, then f is onto. ❖ (2)If f is onto, then f is one to one. ❖ The prove are left your exercises