Simplified Reducibility Proofs of Church-Rosser for β- and βη-reduction

The simplest proofs of the Church Rosser Property are usually done by the syntactic method of parallel reduction. On the other hand, reducibility is a semantic method which has been used to prove a number of properties in the ?-calculus and is well known to offer on one hand very general proofs which can be applied to a number of instantiations, and on the other hand, to be quite mysterious and inflexible. In this paper, we concentrate on simplifying a semantic method based on reducibility for proving Church-Rosser for both ß- and ß?-reduction. Interestingly, this simplification results in a syntactic method (so the semantic aspect disappears) which is nonetheless projectable into a semantic method. Our contributions are as follows:•We give a simplification of a semantic proof of CR for ß-reduction which unlike some common proofs in the literature, avoids any type machinery and is solely carried out in a completely untyped setting.•We give a new proof of CR for ß?-reduction which is a generalisation of our simple proof for ß-reduction.•Our simplification of the semantic proof results into a syntactic proof which is projectable into a semantic method and can hence be used as a bridge between syntactic and semantic methods. Crown Copyright © 2009.