Prove the Equivalence Lemma 4.2. Call a derivation maximal if it is finite and cannot be extended to a longer derivation or it is infinite. Call a derivation fair if it is infinite and every rule is applied in it infinitely often or it is finite. Consider a CSP P with finite domains and a finite set of domain reduction rules.

Prove that every derivation starting in P, in which each rule application is relevant, is finite. Conclude that every maximal derivation of this type is stabilising.

Prove that every maximal and fair derivation has a prefix that is a stabilising derivation.