<p>The answer given is adequate but I'd like to mention that once you reduce a term to normal form, without reflexivity you're out of luck, with reflexivity you've hit a fixed point and thus you can use a fixed point under beta reduction to define the total reduction, as long as you have the nice normalization properties. </p>

CC BY-SA 3.0
2017-03-14T18:42:23.117Z
2017-03-14T18:42:23.117Z
Samuel Schlesinger
<p>The practical reason is that it is very convenient to include also the case "zero steps" in the definition of "many steps" (millennia of mathematical experience have taught us that it is usually a good thing to have a 0 around in our set of natural numbers).</p>

<p>One possible technical exemplification of this (but there are probably dozens more, perhaps more interesting than this one) is that $\to^+$, the transitive closure of reduction, does not satisfy the diamond property  (a.k.a. confluence), whereas $\to^\ast$ satisfies it.  For example, if $I:=\lambda x.x$, there is no way to close the following critical pair by means of $\to^+$:</p>

<p>$$I \leftarrow (\lambda x.I)(II) \to (\lambda x.I)I$$</p>

<p>To close the span, you need to consider the empty reduction $I\to^\ast I$.</p>

CC BY-SA 3.0
2017-03-14T10:35:46.853Z
2017-03-15T13:13:43.617Z
2017-03-15T13:13:43.617Z
Damiano Mazza
<p>I was reading <em><a href="https://dl.dropboxusercontent.com/u/392085/PLLC.pdf" rel="nofollow noreferrer">Programming Languages and Lambda Calculi</a></em>, which defines the multi-step reduction to be the reflexive-transitive closure of the one-step reduction. (Page 15, $\twoheadrightarrow_r$ is the reflexive-transitive closure of $\rightarrow_r$)</p>

<p>A quick search shows that this idea is widely accepted, for example by courses from <a href="https://www.cs.princeton.edu/courses/archive/fall09/cos441/sf/Smallstep.html" rel="nofollow noreferrer">Princeton</a>, <a href="https://www.seas.upenn.edu/~cis500/current/sf/Smallstep.html" rel="nofollow noreferrer">UPenn</a>, <a href="https://www.cs.colorado.edu/~bec/courses/csci3155-s12/recitations/recitation6.pdf" rel="nofollow noreferrer">CU</a>, etc. However, I think the transtivity should be enough to capture the intuition of many steps. So why is reflexivity needed?</p>

CC BY-SA 3.0
2017-03-14T22:18:51.787Z
Because it's more convenient. This isn't about philosophy, but rather about micro-management of technicalities.
Andrej Bauer
<pl.programming-languages><lambda-calculus><semantics>
Why is the multi-step reduction of semantics reflexive?
wlnirvana
# Why is the multi-step reduction of semantics reflexive?

(Asked by: username_0 on 2017-03-14)

I was reading *[Programming Languages and Lambda Calculi](https://dl.dropboxusercontent.com/u/392085/PLLC.pdf)*, which defines the multi-step reduction to be the reflexive-transitive closure of the one-step reduction. (Page 15, $\twoheadrightarrow\_r$ is the reflexive-transitive closure of $\rightarrow\_r$)

A quick search shows that this idea is widely accepted, for example by courses from [Princeton](https://www.cs.princeton.edu/courses/archive/fall09/cos441/sf/Smallstep.html), [UPenn](https://www.seas.upenn.edu/~cis500/current/sf/Smallstep.html), [CU](https://www.cs.colorado.edu/~bec/courses/csci3155-s12/recitations/recitation6.pdf), etc. However, I think the transtivity should be enough to capture the intuition of many steps. So why is reflexivity needed?

**Tags:** pl.programming-languages, lambda-calculus, semantics

> **Comments:**
> **username_1**: Because it's more convenient. This isn't about philosophy, but rather about micro-management of technicalities.  

---

## 2 answers

### Answer by username_3 on 2017-03-14. Score: 10 | Accepted answer

The practical reason is that it is very convenient to include also the case "zero steps" in the definition of "many steps" (millennia of mathematical experience have taught us that it is usually a good thing to have a 0 around in our set of natural numbers).

One possible technical exemplification of this (but there are probably dozens more, perhaps more interesting than this one) is that $\to^+$, the transitive closure of reduction, does not satisfy the diamond property (a.k.a. confluence), whereas $\to^\ast$ satisfies it. For example, if $I:=\lambda x.x$, there is no way to close the following critical pair by means of $\to^+$:

$$I \leftarrow (\lambda x.I)(II) \to (\lambda x.I)I$$

To close the span, you need to consider the empty reduction $I\to^\ast I$.


---

### Answer by username_2 on 2017-03-14. Score: 6

The answer given is adequate but I'd like to mention that once you reduce a term to normal form, without reflexivity you're out of luck, with reflexivity you've hit a fixed point and thus you can use a fixed point under beta reduction to define the total reduction, as long as you have the nice normalization properties.


---

