Graph model of lambda calculus ($P\omega$)

Let $P\omega =\mathcal{P}(\mathbb{N})$ ordered by subset. Encode a finite subset $u$ and output $n$ by a natural number $⟨u,n⟩$. Define $a\cdot b=\{n:\exists u\subseteq b\text{ finite},⟨u,n⟩\in a\}$ and $e(f)=\{⟨u,n⟩:n\in f(u)\}$. Every Scott continuous map satisfies $f(b)={\bigcup }_{u\subseteq b\text{ finite}}f(u)$, proving that application is the projection of a retraction. Lambda abstraction has graph $\{⟨u,n⟩:n\in [[M{]]}_{\rho [x:=u]}\}$.

The interpretation of a lambda term in the graph model of lambda calculus is the union of the interpretations of all its finite Böhm approximants. Every finite indexed interpretation reduces monotonically to an indexed normal approximant. Taking the union over all occurrence indices gives one inclusion; replacing subterms by bottom and using beta soundness gives the other. This identifies denotational information with finite observable parts of a Böhm tree.

An indexed lambda term assigns a natural number to every subterm occurrence; one also admits a constant $\perp$ with empty interpretation. In the graph model of lambda calculus, every syntax constructor is interpreted as usual and then intersected with $\{0,\dots ,n\}$ at its occurrence index $n$. All indexed interpretations are finite subsets of the unindexed interpretation, and their directed union recovers that interpretation.

Use the binary finite-set encoding $e_k$ and Cantor code $⟨k,t⟩$. Contracting $(\lambda x.P^n{)}^{m+1}{Q}^p$ gives the substituted body with its root index lowered by taking the minimum with $\min (m,n)$, replacing each occurrence $x^r$ by a copy of $Q$ with root index $\min (m,p,r)$. A zero-indexed abstraction instead substitutes $\perp$ and gives the body root index zero. Indices strictly budget the argument information that can be used by application. Finite-witness inequalities for the pairing code prove that indexed reduction increases the interpretation, although it can decrease the underlying Böhm tree.