一對一與映成

函數 $f: A\to B$ 的兩個關鍵性質:一對一 (injective) 不同輸入給不同輸出($f(a) = f(b)\Rightarrow a = b$);映成 (surjective) 對應域每個元素都被打到。兩者都滿足叫雙射 (bijective),此時反函數存在,且 $|A| = |B|$。

判斷訣竅:一對一看「會不會撞」(水平線測試),映成看「有沒有漏」。$f(x) = x^2$ 在 $\mathbb{R}\to\mathbb{R}$ 兩者皆非,但改定義域為 $[0,\infty)$ 就一對一、改對應域為 $[0,\infty)$ 就映成——性質取決於定義域與對應域,不只看公式。

計數:$|A| = m$、$|B| = n$,函數 $n^m$ 個,一對一函數在 $m\le n$ 時有 $P(n,m)$ 個($m>n$ 時 0 個),雙射 $n!$ 個($m = n$)。

雙射是「兩個集合一樣大」的定義,Cantor 用它比較無窮集合;一對一函數是編碼無損、雜湊無碰撞的數學條件。