Proof.We will prove this theorem by induction on n.The assertion that we will prove is:For every integer m such that m >n,if f:{1,...,m{1,...,n,then f is not one-to-one. For the induction step,let nEZ and suppose that if m is an integer greater than n and f is a function f {1,...,m{1,...,n},then f is not one-to-one.We will show that if m >n+1 and f {1,...,m1,...,n+1),then f is not one-to-one. So let us suppose that m >n+1 and we have a map f:{1,…,m}→{1，，n+1} There are three cases to consider:Either f maps nothing to n+1,more than one element to n+1,or exactly one element to n+1