自然数集N到自身的全体一一映射是不可数的

自然数集合 N 到自身的既单又满的映射全体构成的集合是否可数? 详细证明你的判断.

证：记Xf:f为N到N的一一映射

我认为X是不可数的

可用一个无穷数列表示映射f

ff(0),f(1),,f(n),

假设X可数，则可以已某种方式将所有f列出：

f1f1(0),f1(1),,f1(n),

f2f2(0),f2(1),,f2(n),

……………

fifi(0),fi(1),,fi(n),

……………

如果可找到一个一一映射，没在这个序列里，即证明了X是不可数的 令ff(0),f(1),,f(n),

f(0)min{z:zN{f1(0)}},满足：f(n)min{z:zN{f(0),,f(n1),fn1(n)}},（1）

由于自然数有无限个，故上要求总可以做到

并且可看出f是从N到N的单射。如果是满射，结束。

如果不是满射，必有自然数没被映到，可以证明没被映到的自然数最多只能有一个

如果m没被映到，则n0,nn0,有f(n)m

则mN{f(0),,f(n1),fn1(n)}nn0

即推出fn1(n)m(nn0)(2)

如果有两个自然数没被映到，则根据(1)式可证这两个数相等。

同时可知{f(0)，，f(n01)}中包含了所有小于m的自然数。（3）

此时f不是满射但只有一个数没被映到，为了解决这个问题，需另找一个映射

此时令gnfn(nn0,nn03),gn01fn02,gn02fn01

则{gn}也是一个排列，同（1）的方法可得一个映射g,g是单射

易知g(0)f(0),,g(n01)f(n01)（4）

g(n0)min{z:zN-{g(0),,g(n0-1),gn01(n0)}}

gn01(n0)fn02(n0)mg(n0)m

结合（3）可知g(n0)m

g必为满射，否则有mm没被映到,

可推出n1,nn1,gn1(n)m

可推出nmax{n03,n1},nn,gn1(n)fn1(n)m,据（2）即知mm,矛盾

而g{gn}{fn} 故知gfi,i1,2,

g没在这个序列里，证毕。