For the first case,n+1 is not in the range of f,so f actually defines a map f:{1,...,m{1,...n).Since m >n+1 >n,our induction hypothesis tells us that f is not one-to-one,and we are done in this case. In case two,there exist j,k e{1,...,m with jtk,and f(j)=n+1=f(k). Then f is not one-to-one,and we are done in this case,too. For the last case,we may assume that je{1,...,m is the only integer for which f(j)=n+1.We now define the function g:{1,...,m{1,...,m that inter- changes m with j and leaves all other elements of {1,...,m fixed: 2 3 kfk≠j,m 23 3 3 (f。g)l1m-1 maps{1,…,m-1} 8(k) j ifk=m tof1,....n};By H,(fg)l(1..m-1)is 44 not one-to-one. m ifk=j m m n+1 Then (fog)cannot be one-to-one; Asg is one-to-one,So f cannot be (f°g)(m)=f(g(m)=n+1. one-to-one;123…j …m 123…q…n+1 1 g f 23…j …m