3.10

证明：对任何 $M, N \in \Lambda$， $M =_\beta N \Leftrightarrow \lambda\beta \vdash M=N$

证明

"$\Rightarrow$"：首先，我们证明：

$\forall M,N \in \Lambda, M \rightarrow_\beta N \Rightarrow \lambda \beta \vdash M = N$

对 $M,N$ 的结构做归纳：

Basis：$(M, N) \in \beta$，$\beta \equiv \{((\lambda x. M) N, M[x := N]) : M, N \in \Lambda \land x \in V\}$，此时有 $\lambda \beta \vdash M = N$

I.H. $(M,N) \in (M', N')$ 的合拍闭包，根据 Basis 有 $\lambda \beta \vdash M' = N'$

$\lambda \beta \vdash M'M' = M'N \quad\cdots (\mu)$

$\lambda \beta \vdash M'M' = N'M'\quad \cdots (\nu)$

$\lambda \beta \vdash \lambda z. M' = \lambda z. N' \quad \cdots (\varepsilon)$

所以 $\lambda \beta$ 对 $(M',N')$ 的合拍闭包封闭，从而 $\lambda \beta \vdash M =_\beta N$，根据习题 (3.9)，$M=_\beta N$，则 $\exists n \geq 0$ 以及 $P_0, \cdots, P_n$ 使得

$P_0 = M$ ，$P_n = N$，$\forall i<n, P_i \rightarrow_\beta P_{i+1}$ 或 $P_{i+1} \rightarrow_\beta P_i$

从而我们有：

$\lambda \beta \vdash P_0 = P_1, \lambda \beta \vdash P_1 = P_2, \cdots \lambda\beta \vdash P_{n-1} = P_n$

由规则 $(\tau)$ 可知，$\lambda \beta \vdash P_0 = P_n$，即 $\lambda \beta \vdash M = N$

“$\Leftarrow$” ：对 $\lambda \beta \vdash P = Q$ 的结构作归纳：

$(\rho)$ 当 $P=Q$ 呈形 $M=M$ 时，易见 $M =_\beta M$，即 $P =_\beta Q$

$(\beta)$ 当 $P = Q$ 呈形 $(\lambda x. M)N = M[x:=N]$ 时，因为 $(\lambda x. M)N =_\beta M[x:=N]$，所以 $P = _\beta Q$

$(\sigma)$ 如果 $\lambda \beta \vdash P = Q$ 且 $P =_\beta Q$，那么 $Q =_\beta P$

$\lambda \beta \vdash P = Q \Rightarrow \lambda \beta \vdash Q = P \Rightarrow Q =_\beta P$

$(\tau)$ 如果 $\lambda \beta \vdash M = N \Rightarrow M =_\beta N, \lambda \beta \vdash N = L \Rightarrow N=_\beta L$，那么 $M =_\beta L$

$\lambda \beta \vdash M = N, \lambda \beta \vdash N = L \Rightarrow \lambda \beta \vdash M = L \Rightarrow M =_\beta L$

对 $(\mu), (\nu), (\xi)$ 同理可验证。