O'Reilly logo

Lambda Calculus with Types by Richard Statman, Wil Dekkers, Henk Barendregt

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

4

Definability, unification and matching

4.1 Undecidability of lambda-definability

The finite standard models

Recall that the full type structure over a set X, written imageX, is defined in Definition 2.4.18 as follows:

image

Note that if X is finite then all the X(A) are finite. In that case we can represent each element of imageX by a finite piece of data and hence (through Gödel numbering) by a natural number. For instance for X = {0, 1} we can represent the four ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required