已知条件有a1?a2且c1?c2，进而(a1,c1)?(a2,c2)，因此h是单射.

任意(b,d)?B?D，则b?B,d?D，由于f是A到B的双射且g是C到D的双射，于是存在a?A,c?C使得f(a)?b,g(c)?d，因此

h(a,c)?(f(a),g(c))?(b,d)，所以h是满射.

故h是双射.

13.设f:A?B,g:B?C,h:C?A，若f?g?h?IA，g?h?f?IB，

h?f?g?IC，则f,g,h均可逆，并求出f?1,g?1,h?1.

证 因为恒等映射是双射，多次使用定理6即可得结论.

由于f?g?h?IA，所以f是单射且h是满射. 由于g?h?f?IB，所以g是单射且f是满射. 由于h?f?g?IC，所以h是单射且g是满射. 于是f,g,h是双射，因此f,g,h均可逆.

由于f?g?h?IA，所以f?1?g?h且h?1?f?g，进而g?1?h?f.

14.已知Ackermann函数A:N?N?N的定义为 (1)A(0,n)?n?1,n?0; (2)A(m,0)?A(m?1,1),m?0;

(3)A(m,n)?A(m?1,A(m,n?1)),m?0,n?0. 分别计算A(2,3)和A(3,2).

解 由已知条件有A(0,1)?2，A(1,0)?A(0,1)?2，于是

A(1,1)?A(0,A(1,0))?A(0,2)?2?1?3， A(1,2)?A(0,A(1,1))?A(0,3)?3?1?4，

由此可进一步得出

A(1,n)?n?2， A(2,0)?A(1,1)?3，

A(2,1)?A(1,A(2,0))?A(1,3)?3?2?5，

A(2,2)?A(1,A(2,1))?A(1,5)?5?2?7， A(2,3)?A(1,A(2,2))?A(1,7)?7?2?9.

因此有

A(2,n)?2n?3，

A(3,0)?A(2,1)?2?1?3?5，

A(3,1)?A(2,A(3,0))?A(2,5)?2?5?3?13， A(3,2)?A(2,A(2,2))?A(2,13)?2?13?3?29.

所以有A(2,3)?9,A(3,2)?29.