Discrete Algebraic Methods

□

As the following lemma shows, the division relation between monoids carries over to wreath products.

Lemma 7.30. If M ≺ S and N ≺ T, then M ≀ N ≺ S ≀ T.

Proof: Let σ : S → M and τ : T → N be surjective partial homomorphisms. Let

be the functions in ST which are compatible with σ and τ. For (g, t) ∈ G × T, we define ψ(g, t) = (σ(g), τ(t)) ∈ MN × N by (σ(g))(n) = σ(g(τ−1(n))). By choice of G, the term σ(g(τ−1(n))) defines a unique element in M. For every mapping f : N → M, we can choose an extension fe ∈ G such that fe(t) = s for some s ∈ σ−1(f(τ(t))). If τ(t) is undefined, then fe(t) can be chosen arbitrarily; for instance, we could set fe(