Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-25T03:49:21.414Z Has data issue: false hasContentIssue false
  • English
  • Français

An abstract Church-Rosser theorem. II: Applications

Published online by Cambridge University Press:  12 March 2014

R. Hindley
R. Hindley*
Affiliation:
University College, Swansea SA2 8PP, Wales
Get access Rights & Permissions [Opens in a new window]

Extract

This paper is a continuation of An abstract form of the Church-Rosser theorem. I (this Journal, vol. 35 (1969), pp. 545–560). In Part I, the Church-Rosser property was deduced from abstract premises (A1)–(A8). The original draft of Part II contained some applications of this result, and a fairly simple abstract result by which the Church-Rosser property could be extended from λβ-reduction to λβη-reduction (Curry's notation [3, Chapter 3]). But since this draft was written, these results have been obtained independently and improved by other workers, and a simple and natural new proof for λβ-reduction has been discovered by W. W. Tait and P. Martin-Löf (see §11 later, and [17, §2.4.3]).

So the main purpose of the present Part II is merely to justify the claim in Part I that the abstract theorem does cover the case of λβ-reduction (and various modifications). I shall also include a summary of the main kinds of Church-Rosser proofs. The paragraph and theorem numbers in Part II will continue from those of Part I.

In §§5 and 6 below, Theorem 1 will be specialised to reductions defined by replacements of parts of expressions by others (Theorems 2 and 2A). At the end of §6 an important subclass of such reductions will be treated (Theorem 3).

In §7, Theorem 3 will be applied to prove the Church-Rosser property for combinatory weak reduction [10, §11B], with or without type-restrictions and extra “arithmetical” reduction-rules (Theorems 4 and 5). (In the original draft Theorem 5 was deduced directly from Theorem 2A; the present intervening Theorem 3 is an independent result of B. Rosen [7].)

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 39 , Issue 1 , March 1974 , pp. 1 - 21
Copyright
Copyright © Association for Symbolic Logic 1974

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., A new proof of the Church-Rosser Theorem, Koninklijke Nederlandse Akademie van Wetenschappen. Proceedings. Series A, vol. 55 (1952), pp. 16–22.Google Scholar
[2]Church, A., The calculi of Lambda-conversion, Princeton University Press, Princeton, N.J., 1941.Google Scholar
[3]Curry, H. B. and Feys, R., Combinatory logic, Volume I, North-Holland, Amsterdam, 1958.Google Scholar
[4]Newman, M. H. A., On theories with a combinatorial definition of “equivalence”, Annals of Mathematics, vol. 43 (1942), pp. 223–243.CrossRefGoogle Scholar
[5]Rosser, J. B., Review of “A new proof of the Church-Rosser Theorem”, this Journal, vol. 24 (1956), p. 377.Google Scholar
[6]Schroer, D. E., The Church-Rosser theorem, Ph.D. thesis, Cornell University, Ithaca, N.Y., 1965.Google Scholar
[7]Rosen, B., Tree-manipulating systems and Church-Rosser theorems, Journal of the Association for Computing Machinery, vol. 20 (1973), p. 160.CrossRefGoogle Scholar
[8]Mitschke, G., Ein algebraischer Beweis für das Church-Rosser Theorem, Archiv für mathematische Logik, vol. 15 (1973), pp. 146–157.CrossRefGoogle Scholar
[9]Rosser, J. B., A mathematical logic without variables, Annals of Mathematics, vol. 36 (1935), pp. 127–150.CrossRefGoogle Scholar
[10]Curry, H. B., Hindley, R. and Seldin, J. P., Combinatory Logic, Volume II, North-Holland, Amsterdam, 1972.Google Scholar
[11]Church, A., A formulation of the simple theory of types, this Journal, vol. 5 (1940), pp. 56–68.Google Scholar
[12]Sanchis, L. E., Functionals defined by recursion, Notre Dame Journal of Formal Logic, vol. 8 (1967), pp. 161–174.CrossRefGoogle Scholar
[13]Church, A. and Rosser, J. B., Some properties of conversion, Transactions of the American Mathematical Society, vol. 39 (1936), pp. 472–482.CrossRefGoogle Scholar
[14]Tait, W., Intensional interpretations of functionals of finite type. I, this Journal, vol. 32 (1967), pp. 198–212.Google Scholar
[15]Kleene, S. C., λ-definable functionals of finite type, Fundament a Mathematica, vol. 50 (1962), pp. 281–303.CrossRefGoogle Scholar
[16]Hindley, R., Lercher, B. and Seldin, J., Introduction to combinatory logic, London Mathematical Society Lecture Notes Series, Cambridge University Press, 1972.Google Scholar
[17]Martin-Löf, P., An intuitionistic theory of types, manuscript, University of Stockholm, 1972.Google Scholar
[18]Stenlund, S., Combinators, λ-terms and proof theory, Reidel, Dordrecht, 1972.CrossRefGoogle Scholar