[Solved]: What is beta equivalence?

Problem Detail: 

In the script I am currently reading on the lambda calculus, beta equivalence is defined as this:

The $\beta$-equivalence $\equiv_\beta$ is the smallest equivalence that contains $\rightarrow_\beta$.

I have no idea what that means. Can someone explain it in simpler terms? Maybe with an example?

I need it for a lemma following from the Church-Russer theorem, saying

If M $\equiv_\beta$ N then there is a L with M $\twoheadrightarrow_\beta$ L and N $\twoheadrightarrow_\beta$ L.

Asked By : atticae

Answered By : Dave Clarke

$\to_\beta$ is the one-step relation between terms in the $\lambda$-calculus. This relation is neither reflexive, symmetric, or transitive. The equivalence relation $\equiv_\beta$ is the reflexive, symmetric, transitive closure of $\to_\beta$. This means

1. If $M\to_\beta M'$ then $M\equiv_\beta M'$.
2. For all terms $M$, $M\equiv_\beta M$ holds.
3. If $M\equiv_\beta M'$, then $M'\equiv_\beta M$.
4. If $M\equiv_\beta M'$ and $M'\equiv_\beta M''$, then $M\equiv_\beta M''$.
5. $\equiv_\beta$ is the smallest relation satisfying conditions 1-4.

More constructively, first apply rules 1 and 2, then repeat rules $3$ and $4$ over and over until they add no new elements to the relation.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/634