3.8

证明：对任意 P,Q∈ΛP, Q \in \Lambda，若 P↠βQP \twoheadrightarrow_\beta Q，则 λz.P↠βλz.Q\lambda z. P \twoheadrightarrow_\beta \lambda z. Q

证明

即证明 ↠β\twoheadrightarrow_\beta 的合拍性，由习题 (3.7) 知 P≡P0→βP1→β⋯→βPn−1→βPn≡QP \equiv P_0 \rightarrow_\beta P_1 \rightarrow_\beta \cdots \rightarrow_\beta P_{n-1} \rightarrow_\beta P_n \equiv Q

根据 →β\rightarrow_\beta 和合拍性，有 ∀i<n,Pi→βPi+1⟹λz.Pi→βλz.Pi+1\forall i<n, P_i \rightarrow_\beta P_{i+1} \Longrightarrow \lambda z. P_i \rightarrow_\beta \lambda z. P_{i+1}

从而，λz.P≡λz.P0→βλz.P1→β⋯→βλz.Pn≡λz.Q\lambda z. P \equiv \lambda z. P_0 \rightarrow_\beta \lambda z. P_1 \rightarrow_\beta \cdots \rightarrow_\beta \lambda z. P_n \equiv \lambda z. Q，即 λz.P↠βλz.Q\lambda z. P\twoheadrightarrow_\beta \lambda z. Q