COMPOSITION OF SUBSTITUTIONS

Let sigma = {f(y)/x, z/y}
     tau = {a/x, b/y, y/z}.
Compute Compose(sigma, tau).

The result, as you should recall, was {f(b)/x, y/z}.

To show that composition of substitutions is not commutative, I asked you to compute Compose(tau, sigma). Here is the solution:

Compose(tau, sigma) =

1. {Subst(sigma, a)/x, Subst(sigma, b)/y, Subst(sigma, y)/z, f(y)/x, z/y}
   = {a/x, b/y, z/z, f(y)/x, z/y}

2. Remove {z/z, f(y)/x, z/y}
   to yield {a/x, b/y}

which is not = Compose(sigma, tau)