
606 Lassez, Mäher, and Marriott
PROPOSITION
15
Substitution μ is an mgu iff ν Ε αοηιαΐη(μ) Π range{\i) =^>
E(JC
— ν) Ε μ .
Proof:
Let θ be an equivalent idempotent mgu, then μ = θοα where α =
{JC—
χμ:χ Ε domain^), χ ^ domain^)}. Now, ν Ε άοηιαΐη(μ) Π range{p) implies
that ν Ε range(a). There are two cases: If ν £ rangera) then, since ν Ε
domain(\L),
we must have ν Ε domain(a). Thus, the ν in ranged) does not
contribute to μ, and so ν Ε range(a). If ν ^ range(Q) then, since ν E
range(\L),
we must have ν Ε range(a). From the previous proposition, α has the form {x
x
Vj,...,jc
m
v
m
} and so
3(JC
*-v)6a and hence
3(JC
ν) Ε μ. •
Consequently not al ...