Exercise:
A substitution $\theta = \{x_1\leftarrow t_1, \dots, x_n\leftarrow t_n\}$ is idempotent iff $\theta = \theta\theta$. Let $V$ be the set of variables occurring in the terms $\{t_1, \dots, t_n\}$. Prove that $\theta$ is idempotent iff $V \cap \{x_1, \dots , x_n\} = \emptyset$.
Show that the mgu’s produced by the unification algorithm is idempotent.
Proof:
$\leftarrow$
Suppose $\theta$ is idempotent. Then $\theta = \theta\theta$.
Recall that by definition of substitution, for each $t_i$, $t_i\neq x_i; \ i=1,\dots,n$. Hence $V \cap \{x_1, \dots , x_n\} = \emptyset$.
$\rightarrow$
I don't know how this is $\theta\theta$ explicit. I've done composition where both substitutions are different but in this case it's difficult to visualize.
Could somebody please help me? I don't know how to continue.
Suppose that $\theta$ is idempotent.
Intuitively, with substitution $θ$ we put the term $t_i$ in place of every occurrence of $x_i$.
Thus, after substitution, there are no more occurrences of $x_i$, unless some $x_i$ occurs in turn into some $t_j$, in which case the substitution has generated new occurrences of $x_i$.
But idempotency means that the second application of the substitution $\theta$ has no effect.
The way to formalize it is that:
where $V$ is the set of variables occurring in the terms $t_j$.
A simple counterexample will show that the condition $V \cap \{ x_1, \ldots ,x_n \} = \emptyset$ is necessary for idempotency.
Consider the substitution:
We have variables $\{ x,y,z \}$ and $V = \{ y,u \}$; thus: $V \cap \{ x,y,z \} = \{ y \} \ne \emptyset$.
Starting with $\{ x,y,z \}$ and applying $\theta$, we get: $\{ f(y), f(a), u \}$.
Wit a new application of $\theta$ we get: $\{ f(f(a)), f(a), u \}$ and thus $\theta \ne \theta \theta$.
Suppose now that $V \cap \{ x_1, \ldots ,x_n \} = \emptyset$.
This means that $\theta$ cannot introduce new occurrences of the $x_i$'s.
Thus, a new "application" of $\theta$ has no effect, i.e. $\theta \theta = \theta$., that means that $\theta$ is idempotent.