Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-07T17:29:17.487Z Has data issue: false hasContentIssue false
  • English
  • Français

Completeness, invariance and λ-definability

Published online by Cambridge University Press:  12 March 2014

R. Statman
R. Statman*
Affiliation:
Rutgers University, New Brunswick, New Jersey 08903
Get access Rights & Permissions [Opens in a new window]

Extract

In [4] Gordon Plotkin considers the problem of characterizing the λ-definable functionals in full type structures. A plausible, but, as we shall see, quite false, conjecture is that a functional is λ-definable ⇔ it is invariant in the sense of Fraenkel and Mostowski. A better guess might be that the set of λ-definable functionals of type σ has a uniform (in σ) definition in type theory over all full type structures (Plotkin explicitly considers a certain sort of definition by means of “logical relations”). More or less generally, one may ask if the following question is decidable.

Given: a functional F in a full type structure over a finite ground domain.

Question: is Fλ-definable?

We call the statement that this question is decidable Plotkin's λ-definability conjecture. We do not know if Plotkin's conjecture is true.

In this note we consider several questions which quickly arise from Plotkin's conjecture. In §1, we ask which type structures satisfy λ-definability = invariance. We construct for each consistent set of equations a model satisfying this equality. From consideration of these models we obtain a number of syntactic corollaries including a reduction of βη-conversion to βη-conversion at a single type (Theorem 3), an “ω-rule” for βη-conversion (Proposition 6) and consistency with βη-conversion (Proposition 8), definability and indefinability results for versions of Kronecker's δ (Propositions 10 and 11), and a decidability result for the problem of inter-definability among combinators.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 1 , March 1982 , pp. 17 - 26
Copyright
Copyright © Association for Symbolic Logic 1982

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Curry, H. B. and Feys, R., Combinatory logic, Vol. 1, North-Holland, Amsterdam, 1968.Google Scholar
[2]Friedman, H., Equality between functions, Lecture Notes in Mathematics (Parikh, R., Editor), vol. 453, Springer-Verlag, Berlin and New York, 1975, pp. 22–37.Google Scholar
[3]Jacopini, G., A condition for identifying two elements of whatever model of combinatory logic, Lecture Notes in Computer Science (Böhm, C., Editor), vol. 37, Springer-Verlag, Berlin and New York, 1975, pp. 213–220.Google Scholar
[4]Plotkin, G. D., λ-definability and logical relations, Memorandum SAI-RM-4, School of Artificial Intelligence, University of Edinburgh, 10, 1973.Google Scholar
[5]Statman, R., The typed λ-calculus is not elementary recursive, Theoretical Computer Science, vol. 9(1979), pp. 73–81.CrossRefGoogle Scholar
[6]Troelstra, A. S., Mathematical investigation of intuitionistic arithmetic and analysis, Lecture Notes in Mathematics, vol. 344, Springer-Verlag, Berlin and New York, 1973, pp. 123–124.Google Scholar
[7]Jensen, D. C. and Pietrzykowski, T., Mechanizing ω-order type theory through unification, Theoretical Computer Science, vol. 3 (1976), pp. 123–171.CrossRefGoogle Scholar
[8]Prawitz, D., Natural deduction, Almqvist and Wiksell, Stockholm, 1965.Google Scholar
[9]Barendregt, H., The type free lambda calculus, Handbook of Mathematical Logic (Barwise, Jon, Editor), North-Holland, Amsterdam, 1977, pp. 1091–1132.CrossRefGoogle Scholar