Extensionnalité des modèles de calcul lambda

Je traduis un livre sur LISP et naturellement il touche certains éléments de -calculus. Ainsi, une notion d'extensionnalité y est mentionnée aux côtés de certains modèles de -calculus, à savoir: et D ^ \ infty (oui, avec l'infini en haut). Et on dit que \ mathcal {P} _ \ omega est extensionnel tandis que D ^ \ infty ne l'est pas.λ P ω D $\lambda$$\lambda$$\mathcal{P}_\omega$$D^\infty$D $\mathcal{P}_\omega$$D^\infty$

Mais ... Je regardais à travers le calcul Lambda de Barendregt , It's Syntax and Semantics , et (espérons-le, correctement) y lire exactement le contraire: $\mathcal{P}_\omega$ n'est pas extensionnel, $D_\infty$ est.

Quelqu'un connaît-il cet étrange modèle $D^\infty$ ? Serait-ce juste le même modèle que $D_\infty$ , mais écrit par erreur? Ai-je raison sur l'extensionnalité des modèles?

Merci.

Je suppose que par extensionnalité, vous entendez la loi Si c'est ce que vous voulez dire, le modèle de graphique n'est pas extensionnel, tandis que Dana Scott l' est (je suppose que est le modèle de Dana Scott du - calcul).P ω D ∞ D ∞ β ξ η

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

Pour voir cela, rappelez-vous que est un réseau algébrique avec la propriété que son espace de cartes continues est un retrait correct de , c'est-à-dire qu'il existe des cartes continues et telle sorte que mais . Étant donné , l'application est interprétée comme . Maintenant, prends[ P ω → P ω ] P ω Λ : P ω → [ P ω → P ω ] Γ : [ P ω → P ω ] → ) u u ′ u ≠ u $\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]$$ Λ ∘ Γ = i d Γ ∘ Λ ≠ i d u , v ∈ P ω u v Λ ( u ) ( $$\Gamma : [\mathcal{P}\omega \to \mathcal{P}\omega] \to \mathcal{P}\omega$$ $\Lambda \circ \Gamma = \mathrm{id}$$\Gamma \circ \Lambda \neq \mathrm{id}$$u, v \in \mathcal{P}\omega$$u v$$\Lambda(u)(v)$$u$et tels que mais (ceux-ci existent parce que ). Alors pour tout on a encore . L'extensionnalité est violée.$u'$$u \neq u'$Γ ∘ Λ ≠ i d v u v = u v ′ u ≠ u $\Lambda(u) = \Lambda(v)$$\Gamma \circ \Lambda \neq \mathrm{id}$$v$$u v = u v'$$u \neq u'$

En revanche, est isomorphe à , c'est-à-dire qu'il existe des cartes continues et qui sont inverses les uns des autres. Considérez donc tout et supposez que pour tout . Cela signifie que pour tous les , donc et donc . L'extensionnalité est établie.D ∞ Λ : D ∞ → [ D ∞ → D ∞ ] Γ : [ D ∞ → D ∞ ] → D ∞ ′ ) ( v ) v ∈ D $[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 v = u ′ v v ∈ D ∞ Λ ( u ) ( v ) = Λ ( $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'$

Nous voyons que l'extensionnalité est une conséquence de . À quoi sert l'autre équation ? Pour cela, nous devons nous rappeler comment -abstraction est interprétée: En mots, une expression avec une variable peut être interprétée comme une carte qui prend à . Ensuite, le -abstraction est interprété comme l'image de cette fonction. Maintenant, à partir de nous obtenons $\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)$$ qui est juste -reduction.$\beta$