Question

证明一个有限集合到它自身的满射一定是双射

Answer 1

设A和B是任意两个集合，函数f:A→B是一个满射。则值域{f(a)}=B，对于任意b，b∈B，至少存在一个a，a∈A使得f(a)=b。
反证法：
设一个有限集合A到它自身的满射不一定是双射。既存在函数f：A→A是满射且不是单射，至少对于函数f的值域A的某个元素a，有b≠c且都属于函数f的定义域A的两个元素，使得f(b)=a=f(c)。[aj]是函数f的值的一个标记，它满足：J是一个集合，函数g使得函数f的任何值f(x)，都有g(f(x))=j（j∈J）是单射，既如果g(f(x1))=g(f(x2))=j，则f(x1)=f(x2)，x1未必等于x2。标记[aj]，其中a=f(x)，j=g(f(x))。任何a∈A，在函数f下，f(a)都有标记[aj]，对于b和c这种情形的元素，它们的标记是同一个[aj]。
在A中存在不被标记的元素，因为f的反函数可以把任何标记[aj]在A找到一个本象a,对于形同f(b)=a=f(c)的，只选取其中的一个本象b。那么由本象组成的集合A'显然不等于A，这是因为，如果A'=A，那么c也是一个本象了，既除了f(c)=a=f(b)的那个标记[aj]外，还有另外一个标记[ej]使得f(c)=e，并且a≠e。可见f不是一个函数。被标记的元素组成的集合和集合A'已经存在一个一一映射了。那么现在可以得到矛盾了：函数f：A→A不是满射。因为A有不被标记的元素。假设不成立。证完。