双射

双射（bijection）是在两个集合之间不重不漏地配对元素的函数。从 $A$ 到 $B$ 的函数 $f$ 若不同输入不会得到同一输出，称单射；若 $B$ 中每个元素都能被某个输入取得，称满射。两项同时成立才是双射。

从配对看定义

令 $A=\{a,b,c\}$、$B=\{1,2,3\}$，规定 $f(a)=2,f(b)=3,f(c)=1$。输出互不重复，故单射；三个输出覆盖 $B$，故满射。逐个倒过来读，可得逆函数 $f^{-1}(1)=c,f^{-1}(2)=a,f^{-1}(3)=b$。一般地，函数存在定义在整个 $B$ 上的逆函数，当且仅当它是双射。

无限集合也能一一配对

在实数上，$f(x)=2x+1$ 是双射。若 $2x+1=2y+1$，消去得到 $x=y$，所以单射；给定任何目标 $z$，取 $x=(z-1)/2$ 就有 $f(x)=z$，所以满射。逆函数由同一计算得到 $f^{-1}(z)=(z-1)/2$。

把定义域改成非负整数，$g(n)=n+1$ 仍单射，却不满射到非负整数：0 没有原像。证明“大小相同”时要写清定义域与陪域，单凭一条没有重复的配对规则不够。有限集合的双射保证元素个数相同；对无限集合，双射仍是比较基数的准确工具，见可数集。

参考资料

• MIT，Mathematics for Computer Science，函数与基数章节。
• MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
• 继续阅读：函数、可数集、幂集。