1.6

设 $f: \mathbb{N} \rightarrow \mathbb{N}$，证明：$f$ 可以作为配对函数的左函数当且仅当对任何 $i \in \mathbb{N}$， $|\ \{\ x\in \mathbb{N}: f(x)=i\ \}\ | = \aleph_0.$ 关于 $\aleph_0$ 的通俗解释，可以参考视频“怎样数到无限之后？”

证明

• "$\Rightarrow$"，设 $f$ 为配对函数 $pg(x,y)$ 的左函数

  $\because f(pg(i, j)) = i$ for all $j$

  从而对任何 $i \in \mathbb{N}$，$\therefore \{\ x\ |\ f(x) = i\ \} \supseteq \{\ pg(i,j) \ |\ j \in \mathbb{N}\ \} \sim \{\ j \ | \ j \in \mathbb{N}\ \} \sim \mathbb{N}$

  因此，$\{\ x\ |\ f(x) = i\ \}$ 无穷。

• “$\Leftarrow$”，设任何 $i \in \mathbb{N}$，$f^{-1}[\{i\}]$ 无穷，

  $\because \mathbb{N}$ 良序，

  $\therefore$ 可设 $f^{-1}[\{i\}] = \{\ a_{ij}\ |\ j \in \mathbb{N}\ \}$

  $g: \mathbb{N} \rightarrow \mathbb{N}$ 定义如下： $g(x) = \left\{ \begin{array}{ll} j, & \text{if } x = a_{ij} \\ 0, & \text{else} \end{array} \right.$ 从而对任何 $i,j \in \mathbb{N}$，$f(a_{ij}) = i$，$g(a_{ij}) = j$，

  令 $pg(i, j) = a_{ij}$，$f$ 即为左函数。

  ​