Last week I got a question that asks me to show that the following statement about Y combinator in LaTeX is correct: where is defined as
The statement about the union originally made me thought in the following way:
both of which are not possible (the one showed in the Wikipedia article shows a syntactic equality not a zero or more beta reduction steps).
I erred in seeing as two separate operations instead of a single relation with the given semantic. Once viewed as a relationship with the given semantic (i.e., ) that means that the relationship holds iff either the left-hand side can beta reduce to the right-hand side or the right-hand side can beta reduce to the left hand side, I can easily understand that the statement is correct as shown below:
In other words, because holds due the given semantic of since Y z can beta reduce to r1 but r1 cannot beta reduce to Y z, and holds due to the same reason since r1 can beta reduce to r2 but r2 cannot beta reduce to r1, and holds due to the same reason since z (Y z) can beta reduce to r2 but r2 cannot beta reduce to z (Y z).