Rozległość modeli rachunku lambda

Tłumaczę książkę na temat LISP i oczywiście dotyka ona niektórych elementów rachunku. Zatem wzmiankowane jest pojęcie ekstensywności wraz z niektórymi modelami λ- rachunku, a mianowicie: P ω i D ∞ (tak, z nieskończonością u góry). I mówi się, że P ω jest ekstensjonalny podczas D ∞ nie jest.$\lambda$$\lambda$$\mathcal{P}_\omega$$D^\infty$$\mathcal{P}_\omega$$D^\infty$

Ale ... Patrzyłem na rachunek Lambda Barendregta , jego składnię i semantykę , i (mam nadzieję, poprawnie) przeczytałem dokładnie odwrotnie: nie jest ekstensywne, D ∞ jest.$\mathcal{P}_\omega$$D_\infty$

Czy ktoś wie o tym dziwnym modelu ? Czy może to być ten sam model co D ∞ , ale błędnie napisany? Czy mam rację co do ekstensywności modeli?$D^\infty$$D_\infty$

Dzięki.

Zakładam, że przez ekstensywność rozumiesz prawo Jeśli to jest to, co masz na myśli następnie model wykres P ω jestnieekstensjonalny, natomiast Dana Scotta D ∞ jest (jak mniemam D ∞ jest modelem Dana Scotta z beta Ę r | X -calculus).

$$(\forall x . f x = g x) \implies f = g.$$ $\mathcal{P}\omega$$D_\infty$$D^\infty$$\beta\xi\eta\lambda$

Aby to zobaczyć, przypomnij sobie, że jest siecią algebraiczną z tą właściwością, że jej przestrzeń ciągłych map [ P ω → P ω ] jest właściwym wycofaniem P ω , tzn. Istnieją ciągłe mapy Λ : P ω → [ P ω → P ω ] i Γ : [ P ω → P ω ] → P ω tak, że Λ ∘ Γ = i d ale $\mathcal{P}\omega$$[\mathcal{P}\omega \to \mathcal{P}\omega]$$\mathcal{P}\omega$

$$\Lambda : \mathcal{P}\omega \to [\mathcal{P}\omega \to \mathcal{P}\omega]$$ $$\Gamma : [\mathcal{P}\omega \to \mathcal{P}\omega] \to \mathcal{P}\omega$$ $\Lambda \circ \Gamma = \mathrm{id}$ . Biorąc pod uwagę u , v ∈ P ω , aplikacja u v jest interpretowana jako Λ ( u ) ( v ) . Teraz weź u i u ′ tak, że u ≠ u ′, ale Λ ( u ) = Λ ( v ) (istnieją, ponieważ Γ ∘ Λ ≠ i d ). Zatem dla wszystkich v mamy$\Gamma \circ \Lambda \neq \mathrm{id}$$u, v \in \mathcal{P}\omega$$u v$$\Lambda(u)(v)$$u$$u'$$u \neq u'$$\Lambda(u) = \Lambda(v)$$\Gamma \circ \Lambda \neq \mathrm{id}$$v$ jeszcze u ≠ u ′ . Przestępczość jest naruszona.$u v = u v'$$u \neq u'$

$[D_\infty \to D_\infty]$$D_\infty$

$$\Lambda : D_\infty \to [D_\infty \to D_\infty]$$ $$\Gamma : [D_\infty \to D_\infty] \to D_\infty$$ $u, u' \in D_\infty$$u v = u' v$$v \in D_\infty$$\Lambda(u)(v) = \Lambda(u')(v)$$v \in D_\infty$$\Lambda(u) = \Lambda(u')$$u = \Gamma(\Lambda(u)) = \Gamma(\Lambda(u')) = u'$

$\Gamma \circ \Lambda = \mathrm{id}$$\Lambda \circ \Gamma = \mathrm{id}$$\lambda$

$$\lambda X. u(X) = \Gamma (v \mapsto u(v))$$ $u(X)$$X$$v$$u(v)$$\lambda$$\lambda X . u(X)$$\Gamma$$\Lambda \circ \Gamma = \mathrm{id}$ $$(\lambda X . u(X)) w = \Lambda (\Gamma (v \mapsto u(v))) (w) = (v \mapsto u(v))(w) = u(w)$$ $\beta$