Definition. Computability model of lambda terms [math-FJTC]

The set of lambda terms Λ/∼\Lambda / _\sim with α\alpha and β\beta equivalence form a computability model.

weak product [local-0]

See weak product.

pair:=λxyz.zxyfst:=λp.p(λxy.x)snd:=λp.p(λxy.y)\text{pair} := \lambda xyz. zxy \\ \text{fst} := \lambda p.p(\lambda xy.x) \\ \text{snd} := \lambda p.p(\lambda xy.y)

Check that fst(pair M N)∼M\text{fst}(\text{pair}\ M\ N) \sim M and snd(pair M N)∼N\text{snd}(\text{pair}\ M\ N) \sim N

weak terminal [local-1]

Any element can play the role of a weak terminal: λx.i\lambda x. i for all i∈Λ/∼i \in \Lambda / _\sim

weak cartesian closed [local-2]

Let ⋅\cdot be given by application, if M∈ΛM \in \Lambda induces an operation in [L⋈L,L][L \bowtie L, L] representing some f:L×L→Lf : L \times L \to L then λxy.M(pair x y)\lambda xy. M(\text{pair}\ x\ y) induces the corresponding operation in L,L⇒LL, L \Rightarrow L; conversely, if NN induces an operation in [L,L⇒L][L, L \Rightarrow L], then λz.N(fst z)(snd z)\lambda z. N (\text{fst}\ z) (\text{snd}\ z) induces the corresponding one in [L⋈L,L][L \bowtie L, L].

Definition closed terms [local-3]

There is a submodel Λ0/∼\Lambda^0/_\sim for closed terms.

Notation Use β\beta-equivalence [local-4]

Use β\beta-equivalence then we denote Λ/=β\Lambda / _{=_\beta}.