Some Properties of Conversion
Alonzo Church, J. B. Rosser · Transactions of the American Mathematical Society · 1936
Our purpose is to establish the properties of conversion which are expressed in Theorems 1 and 2 below.We shall consider first conversion defined by Church's Rules I, II, Ulf and shall then extend our results to several other kinds of-conversion.| 1. Conversion defined by Church's Rules I, II, III.In our study of conversion we are particularly interested in the effects of Rules II and III and consider that applications of Rule I, though often necessary to prevent confusion of free and bound variables, do not essentially change the structure of a formula.Hence we shall omit mention of applications of Rule I whenever it seems that no essential ambiguity will result.Thus when we speak of replacing {\x.M] (iV) § by S^M| it shall be understood that any applications of I are made which are needed to make this substitution an application of II.Also we may write bound variables as unchanged throughout discussions even though tacit applications of I in the discussion may have changed them.A conversion in which III is not used and II is used exactly once will be called a reduction.If II is not used and HI is used exactly once, the conversion will be called an expansion."A imr B," read "A is immediately reducible to B," shall mean that it is possible to go from A to B by a single reduction.11A red B," read "A is reducible to B," shall mean that it is possible to go from A to B by one or more reductions.||"A conv-I B," read "A conv B by applications of I only," shall mean just that (including the case of a zero number of applications)."A conv-I-H B," read "A conv B by applications of I * Presented to the Society, April 20, 1935; received by the editors June 4, 1935.t By Church's rules we shall mean the rules of procedure given in A. Church, A set of postulates for the foundation of logic, Annals of Mathematics, (2), vol.33 (