Editing Church–Rosser theorem

{{Short description|Theorem in theoretical computer science}}
[[Image:Confluence.svg|right|200px]]
In [[lambda calculus]], the '''Church–Rosser theorem''' states that, when applying [[Lambda calculus#Reduction|reduction rules]] to [[term (logic)|term]]s,  the ordering in which the reductions are chosen does not make a difference to the eventual result.

More precisely, if there are two distinct reductions or sequences of reductions that can be applied to the same term, then there exists a term that is reachable from both results, by applying (possibly empty) sequences of additional reductions.{{sfnp|Alama|2017}} The theorem was proved in 1936 by [[Alonzo Church]] and [[J. Barkley Rosser]], after whom it is named.

The theorem is symbolized by the adjacent diagram: If term ''a'' can be reduced to both ''b'' and ''c'', then there must be a further term ''d'' (possibly equal to either ''b'' or ''c'') to which both ''b'' and ''c'' can be reduced.
Viewing the lambda calculus as an [[abstract rewriting system]], the Church–Rosser theorem states that the reduction rules of the lambda calculus are [[confluence (abstract rewriting)|confluent]].  As a consequence of the theorem, a term in the [[lambda calculus]] has at most one [[Beta normal form|normal form]], justifying reference to "''the'' normal form" of a given normalizable term.

==History==
In 1936, [[Alonzo Church]] and [[J. Barkley Rosser]] proved that the theorem holds for β-reduction in the λI-calculus (in which every abstracted variable must appear in the term's body). The proof method is known as "finiteness of developments", and it has additional consequences such as the Standardization Theorem, which relates to a method in which reductions can be performed from left to right to reach a normal form (if one exists). The result for the pure untyped lambda calculus was proved by D. E. Schroer in 1965.{{sfnp|Barendregt|1984|p=283}}

==Pure untyped lambda calculus==
One type of reduction in the pure untyped lambda calculus for which the Church–Rosser theorem applies is β-reduction, in which a subterm of the form <math>( \lambda x . t) s</math> is contracted by the substitution <math> t [ x := s]</math>. If β-reduction is denoted by <math> \rightarrow_\beta </math> and its reflexive, transitive closure by <math> \twoheadrightarrow_\beta </math> then the Church–Rosser theorem is that:{{sfnp|Barendregt|1984|p=53–54}}
:<math>\forall M, N_1, N_2 \in \Lambda: \text{if}\ M\twoheadrightarrow_\beta N_1 \ \text{and}\ M\twoheadrightarrow_\beta N_2 \ \text{then}\ \exists X\in \Lambda: N_1\twoheadrightarrow_\beta X \ \text{and}\ N_2\twoheadrightarrow_\beta X</math>

A consequence of this property is that two terms equal in <math>\lambda\beta</math> must reduce to a common term:{{sfnp|Barendregt|1984|p=54}}
:<math>\forall M, N\in \Lambda: \text{if}\ \lambda\beta \vdash M=N \ \text{then}\ \exists X: M \twoheadrightarrow_\beta X \ \text{and}\ N\twoheadrightarrow_\beta X</math>

The theorem also applies to η-reduction, in which a subterm <math>\lambda x.Sx</math> is replaced by <math>S</math>. It also applies to βη-reduction, the union of the two reduction rules.

===Proof===
For β-reduction, one proof method originates from [[William W. Tait]] and [[Per Martin-Löf]].{{sfnp|Barendregt|1984|p=59-62}} Say that a binary relation <math> \rightarrow </math> satisfies the diamond property if:
:<math>\forall M, N_1, N_2 \in \Lambda: \text{if}\ M\rightarrow N_1 \ \text{and}\ M\rightarrow N_2 \ \text{then}\ \exists X\in \Lambda: N_1\rightarrow X \ \text{and}\ N_2\rightarrow X</math>

Then the Church–Rosser property is the statement that <math> \twoheadrightarrow_\beta </math> satisfies the diamond property. We introduce a new reduction <math> \rightarrow_{\|} </math> whose reflexive transitive closure is <math> \twoheadrightarrow_\beta </math> and which satisfies the diamond property. By induction on the number of steps in the reduction, it thus follows that <math> \twoheadrightarrow_\beta </math> satisfies the diamond property.

The relation <math> \rightarrow_{\|} </math> has the formation rules:
*<math>M \rightarrow_{\|} M</math>
*If <math>M \rightarrow_{\|} M'</math> and <math>N \rightarrow_{\|} N'</math> then <math>\lambda x.M \rightarrow_{\|} \lambda x.M'</math> and <math>MN \rightarrow_{\|} M'N'</math> and <math>(\lambda x. M)N \rightarrow_{\|} M'[x:=N']</math>

The η-reduction rule can be proved to be Church–Rosser directly. Then, it can be proved that β-reduction and η-reduction commute in the sense that:{{sfnp|Barendregt|1984|p=64–65}}
:If <math>M \rightarrow_\beta N_1</math> and <math>M \rightarrow_\eta N_2</math> then there exists a term <math>X</math> such that <math>N_1 \rightarrow_\eta X</math> and <math>N_2\rightarrow_\beta X</math>.

Hence we can conclude that βη-reduction is Church–Rosser.{{sfnp|Barendregt|1984|p=66}}

==Variants==
The Church–Rosser theorem also holds for many variants of the lambda calculus, such as the [[simply typed lambda calculus]], many calculi with advanced [[type system]]s, and [[Gordon Plotkin]]'s beta-value calculus. Plotkin also used a Church–Rosser theorem to prove that the evaluation of [[functional program]]s (for both [[lazy evaluation]] and [[eager evaluation]]) is a function from programs to values (a [[subset]] of the lambda terms).

In older research papers, a rewriting system is said to be Church–Rosser, or to have the Church–Rosser property, when it is [[confluence (abstract rewriting)|confluent]].

== Notes ==
{{Reflist}}

==References==
* {{Cite book|url=https://plato.stanford.edu/archives/fall2017/entries/lambda-calculus/|title=The Stanford Encyclopedia of Philosophy|last=Alama|first=Jesse|date=2017|publisher=Metaphysics Research Lab, Stanford University|editor-last=Zalta|editor-first=Edward N.|edition=Fall 2017}}
*{{citation|first1=Alonzo|last1=Church|author1-link=Alonzo Church|first2=J. Barkley|last2=Rosser|author2-link=J. Barkley Rosser|jstor=1989762|title=Some properties of conversion|journal=[[Transactions of the American Mathematical Society]]|volume=39|issue=3|date=May 1936|pages=472–482|doi=10.2307/1989762|url=http://www.ams.org/tran/1936-039-03/S0002-9947-1936-1501858-0/S0002-9947-1936-1501858-0.pdf|doi-access=free}}.
* {{Citation
 |last=Barendregt 
 |first=Hendrik Pieter 
 |author-link=Henk Barendregt
 |title=The Lambda Calculus: Its Syntax and Semantics 
 |publisher=North Holland, Amsterdam
 |year=1984 
 |volume=103 
 |series=Studies in Logic and the Foundations of Mathematics 
 |edition=Revised 
 |url=http://www.elsevier.com/wps/find/bookdescription.cws_home/501727/description 
 |isbn=0-444-87508-5 
 |url-status=dead 
 |archiveurl=https://web.archive.org/web/20040823174002/https://www.elsevier.com/wps/find/bookdescription.cws_home/501727/description 
 |archivedate=2004-08-23
}}. [https://web.archive.org/web/20200819162730/ftp://ftp.cs.ru.nl/pub/CompMath.Found/ErrataLCalculus.pdf Errata].

{{Alonzo Church}}

{{DEFAULTSORT:Church-Rosser theorem}}
[[Category:Lambda calculus]]
[[Category:Theorems in the foundations of mathematics]]
[[Category:Rewriting systems]]