Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
Samuel J. v. Gool Benjamin Steinberg



This paper provides short proofs of two fundamental theorems of finite semigroup theory whose previous proofs were significantly longer, namely the two-sided Krohn-Rhodes decomposition theorem and Henckell's aperiodic pointlike theorem, using a new algebraic technique that we call the merge decomposition.  A prototypical application of this technique decomposes a semigroup T into a two-sided semidirect product whose components are built from two subsemigroups T_1,T_2, which together generate T, and the subsemigroup generated by their setwise product T_1T_2.  In this sense we decompose T by merging the subsemigroups T_1 and T_2.   More generally, our technique merges semigroup homomorphisms from free semigroups.


Challenges in Inflationary Magnetogenesis: Constraints from Strong Coupling, Backreaction and the Schwinger Effect
    Kandaswamy Subramanian^2
    December 30, 2023
==================================================================================================================





§ INTRODUCTION

Eilenberg's variety theorem <cit.> provides a dictionary between formal language theory and finite semigroup theory.  In particular, membership problems in certain Boolean algebras of regular languages (languages accepted by finite automata) are equivalent to membership problems in varieties of finite semigroups.  Other natural problems in language theory transform into questions about pointlikes with respect to a variety of finite semigroups, a notion introduced by Henckell and Rhodes <cit.>.  An important problem in language theory is the separation problem: given disjoint regular languages, determine whether they can be separated by a language from a given variety of regular languages.  The separation problem is equivalent to decidability of pointlike pairs <cit.>, which is strictly stronger than the membership problem <cit.>.   Decidability of pointlikes can be used to obtain decidability of membership problems of related varieties.  For instance, the second author showed, using the decidability of aperiodic pointlikes and Zelmanov's solution to the restricted Burnside problem, that the join of the variety of aperiodic semigroups with any variety of finite groups of bounded exponent has decidable membership problem, answering a question of Rhodes and Volkov <cit.>.



The first decidability result on pointlikes was Henckell's theorem on the decidability of aperiodic pointlikes <cit.>, which for a long time was considered one of the most difficult results in the subject. Henckell not only provided a decidability algorithm: he also gave an elegant structural description of the aperiodic pointlike sets that we call Henckell's formula.  Henckell's original proof idea is a variation on the holonomy proof  <cit.> of the Krohn-Rhodes theorem <cit.> for  directly decomposing semigroups into wreath products.  
The difficult part of Henckell's proof is to prove that a certain semigroup is aperiodic, which he does by wreath product embeddings.  In <cit.>, Henckell, Rhodes and the second author provided a direct proof that Henckell's semigroup is aperiodic, leading to a simpler and shorter proof of his main theorem.  They also extended the theorem beyond aperiodic pointlikes to the variety of semigroups whose subgroups have prime divisors belonging to a fixed set π of primes (the restriction of this proof to the aperiodic case can be found in <cit.>).  Although simpler than the original proof of Henckell <cit.>, the proof in <cit.> is still non-trivial.



Recently, Place and Zeitoun <cit.> gave a new proof of the decidability of aperiodic pointlikes, which, unlike the previous proofs, is inductive.  They use a language theoretic reformulation of the problem of computing pointlike sets and the McNaughton-Schützenberger theorem that the aperiodic languages are precisely the first order definable languages <cit.>. 
The Place-Zeitoun approach follows the inductive proof scheme of the Krohn-Rhodes theorem (the so-called `V∪ T' argument <cit.>) later used by Wilke in the logic context <cit.>, but done in the power set of the semigroup.


This paper introduces a new algebraic tool, that we call the merge decomposition, in Section <ref>. 
In Section <ref>, we use this tool to give a short proof of the inductive step of the two-sided Krohn-Rhodes decomposition theorem (cf. <cit.>). Then, in Section <ref>, we use the merge decomposition in the inductive step of the Place-Zeitoun inductive scheme to give a short algebraic proof of Henckell's formula for the aperiodic pointlikes.  We feel that our approach has several advantages over previous approaches <cit.>.  First of all, it leads to a significantly shorter proof than the previous ones.   Secondly, we obtain the best known bound on the length of a two-sided Krohn-Rhodes decomposition of the aperiodic semigroup witnessing pointlikes (or, equivalently, quantifier-depth of the first order formula giving separation).

 An advantage of our approach is that it is potentially extendable beyond the realm of first order logic on words.  For instance, decidability of pointlikes for some larger varieties than aperiodics is obtained in <cit.>.  We leave this to future work.

  











§ PRELIMINARIES

We assume familiarity with notions from the theory of semigroups, in particular, relational morphisms and divisions, the wreath product (denoted ≀), and the two-sided semidirect product of semigroups (denoted ⋈) and of varieties of finite semigroups (denoted ∗∗); see, e.g., <cit.>. Throughout the paper, we call `variety' what is called `pseudovariety' in <cit.>.





  §.§.§ Augmented semigroups

Let T be a finite semigroup. Let T^I be the monoid obtained by adjoining a new identity, I, to T and T^0 the semigroup obtained by adjoining a new zero to T.

We denote by  the variety of finite semilattices and by U_1 the two-element semilattice.

If a variety  contains T and , then T^0 ∈. If a variety  contains T, , and is generated by monoids, then T^I ∈.


The first statement is true because T^0 is a homomorphic image of T × U_1 <cit.>. For the second statement, we distinguish two cases. If T is a monoid, then T^I embeds in T × U_1, where U_1 denotes the two-element semilattice <cit.>. If T is not a monoid, then T divides some monoid M ∈, and since T is not a monoid, it follows that T^I divides the same monoid M.


The semigroup T acts faithfully on T^I by multiplication on the right, and thus T embeds into the semigroup of total functions on T^I; we identify every element t ∈ T with the corresponding right multiplication map. Further, for every t ∈ T^I, we denote by t^♯ the function with constant value t. We define T^♯ := T ∪{t^♯ :  t ∈ T^I}, the semigroup consisting of the right multiplication maps and the constant maps. Thus, T^♯ naturally acts on T on the right.[Note that our definition of T^♯ for a semigroup T deviates slightly from the definition of M^♯ for a monoid M in <cit.>.]  Dually, T^♭ denotes the semigroup consisting of left multiplication maps for every t ∈ T and constant maps t^♭ for every t ∈ T^I. Note that T^♭ = ((T^)^♯)^, and T^♭ acts on T on the left.


For any finite semigroup T, let T denote the monoid obtained from T by adjoining an identity and a zero and let M be any monoid with |M| > |T|. Then T^♭ embeds in M ≀T.


Fix a bijection t ↦ m_t between T and a subset of M ∖{1_M}.
We define a function i  T^♭→ M ≀T.
For every t ∈ T, define i(t) := (c_1, t), where c_1∈ M^T denotes the function with constant value 1_M, the identity of M, and i(t^♭) := (f_t, 0), where f_t ∈ M^T denotes the function defined by f_t(0) := 1_M and f_t(t') := m_t't for all t' ∈ T^I. It is straightforward to verify that i is an injective homomorphism.




  §.§.§ Triple product

Let (S,+) be a (not necessarily commutative) semigroup equipped with two actions on it, a left action of a semigroup (S_L,·) and a right action of a semigroup (S_R,·), which commute. The triple product[We follow the notation of <cit.>; note the positions of the semigroups acting on the left and on the right. Also note that the multiplication can be viewed as matrix multiplication, if we represent an element (s_R, s, s_L) by the lower triangular matrix [ [ s_R   0;   s s_L ]].]  T = (S_R,S,S_L) is the semigroup of triples (s_R, s, s_L), with multiplication defined by (s_R, s, s_L) · (s_R',s',s_L') := (s_Rs_R',ss_R'+s_Ls', s_Ls_L').


If S ∈ and S_L, S_R ∈, then (S_R,S,S_L) ∈.


Define an action of S_L × S_R on S by ⟨ s_L,s_R ⟩ s := s_Ls and s ⟨ s_L,s_R ⟩ := ss_R. Then T is isomorphic to the two-sided semidirect product S ⋈ (S_L × S_R). (Cf., e.g., <cit.>.)




§ THE MERGE DECOMPOSITION

Throughout this section, we fix:

	
  * a finite alphabet A and two disjoint subalphabets A_1, A_2 such that A = A_1 ∪ A_2;
	
  * two homomorphisms ψ_1  A_1^+ → T_1 and ψ_2  A_2^+ → T_2, with T_1 and T_2 finite;
	
  * a homomorphism χ (T_1 × T_2)^+ → T_0.

For any w_1 ∈ A_1^+, w_2 ∈ A_2^+, define μ(w_1w_2) := (ψ_1(w_1),ψ_2(w_2)) ∈ T_1 × T_2. Since the subsemigroup (A_1^+A_2^+)^+ of A^+ is freely generated by the infinite set of generators A_1^+A_2^+, the function μ extends uniquely to a homomorphism μ (A_1^+A_2^+)^+ → (T_1 × T_2)^+. We define ψ_0  (A_1^+A_2^+)^+ → T_0 to be the composition χ∘μ.

For i = 0, 1, 2, we denote the external identity of T_i^I by I_i, and we also denote by ψ_i the homomorphism from the corresponding free monoid to the finite monoid T_i^I; i.e., ψ_i() := I_i.

For any word w in A^+, uniquely write w = v_2 u v_1, with v_2 ∈ A_2^*, u ∈ (A_1^+A_2^+)^*, and v_1 ∈ A_1^*, and define τ(w) := (ψ_2(v_2),ψ_0(u),ψ_1(v_1)). The function τ A^+ → T_2^I × T_0^I × T_1^I is not a homomorphism in general. The aim in this section is to show that the kernel of τ can be refined to a semigroup congruence of  finite index in a well-controlled variety.

To this end, we will define a semigroup T_M and a homomorphism ψ_M  A^+ → T_M. Let S:= (T_0^I)^T_1^I × T_2^I, with the pointwise product of T_0^I, written additively. We define a left action of T_1^♯ and a right action of T_2^♭ on S. For s ∈ S, s_L ∈ T_1^♯ and s_R ∈ T_2^♭, let s_L s s_R ∈ S be defined by [s_L s s_R](t_1,t_2) := s(t_1s_L,s_Rt_2) for every (t_1,t_2) ∈ T_1^I × T_2^I. Let T_M := (T_2^♭,S,T_1^♯) be the triple product; we call T_M the merge semigroup associated to ψ_1, ψ_2 and χ.


Let  be a variety, and  a variety generated by monoids and containing . If T_0 ∈ , T_1, T_2 ∈, and T_M is any triple product of T_2^♭, (T_0^I)^T_1^I × T_2^I, and T_1^♯, then T_M ∈ ().


Applying Fact <ref> with M a semilattice (e.g., a chain) with |T_2| + 1 elements and using T_2∈ by Fact <ref> yields T_2^♭∈. Similarly, T_1^♯∈. Fact <ref> gives the result.


For any w_1 ∈ A_1^+, we define an element s_w_1∈ S by s_w_1(t_1,I_2) := I_0 and s_w_1(t_1,t_2) := χ(t_1ψ_1(w_1),t_2), for all t_1 ∈ T_1^I and t_2 ∈ T_2.
Now let ψ_M  A^+ → T_M be the unique homomorphism defined by

    ψ_M(a_1) :=
    (I_2^♭, s_a_1, ψ_1(a_1))
     for  a_1 ∈ A_1,
      ψ_M(a_2) :=
    (ψ_2(a_2), i_0, I_1^♯)
     for  a_2 ∈ A_2,

where i_0 denotes the identity of S, i.e., the function with constant value I_0. We call the homomorphism ψ_M  A^+ → T_M the merge decomposition of A^+ along χ, ψ_1 and ψ_2.

The crucial property of the merge decomposition is the following.

There exists a function f  T_M → T_2^I × T_0^I × T_1^I such that f ∘ψ_M = τ.


For any (t_2,s,t_1) ∈ T_M, define f(t_2,s,t_1) := (t_2 I_2, s(I_1,I_2), I_1 t_1). We show f ∘ψ_M = τ.

We first prove, for all w_1 ∈ A_1^+,
ψ_M(w_1) = (I_2^♭, s_w_1, ψ_1(w_1)).
By induction, assume that this holds for all shorter words in A_1^+. Then, writing w_1 = a_1w_1', the left and right coordinates are clearly as stated, and the middle coordinate of ψ_M(w_1) = ψ_M(a_1)ψ_M(w_1') is s_a_1I_2^♭ + ψ_1(a_1)s_w_1'. From the definition of the right action and of s_a_1 we get that s_a_1I_2^♭ = i_0. From the definition of the left action and of s_w_1' and s_w_1, we get that ψ_1(a_1)s_w_1' = s_w_1.

For w_2 ∈ A_2^+, we easily obtain
ψ_M(w_2) = (ψ_2(w_2), i_0, I_1^♯),
since s_L i_0 s_R = i_0 for all s_L, s_R, because i_0 is a constant map.

Multiplying these two results, for any w_1 ∈ A_1^+ and w_2 ∈ A_2^+,
ψ_M(w_1w_2) = (I_2^♭, s_w_1w_2, I_1^♯),
where
s_w_1w_2(I_1,I_2) = s_w_1(I_1,ψ_2(w_2)) = χ(ψ_1(w_1),ψ_2(w_2)) = ψ_0(w_1w_2).

We next prove, by induction on the length of u ∈ (A_1^+A_2^+)^+ as a word in the free semigroup generated by A_1^+A_2^+, that
ψ_M(u) =  (I_2^♭, s_u, I_1^♯),
where s_u(I_1,I_2) = ψ_0(u). We have already established the base case. If u = (w_1w_2)u' for some w_1 ∈ A_1^+ and w_2 ∈ A_2^+ with u' ∈ (A_1^+A_2^+)^+, then, for the middle coordinate s_u of ψ_M(u) = ψ_M(w_1w_2)ψ_M(u'), we have

    s_u(I_1,I_2) = [s_w_1w_2I_2^♭ + I_1^♯ s_u'](I_1,I_2) = ψ_0(w_1w_2) ·ψ_0(u') = ψ_0(u).


Finally, to prove that f ∘ψ_M = τ, let w ∈ A^+. Suppose that w = v_2 u v_1 with u ∈ (A_1^+A_2^+)^+, v_1 ∈ A_1^+ and v_2 ∈ A_2^+. Then, using our previous calculations, we get

    ψ_M(v_2uv_1) = (ψ_2(v_2),i_0, I_1^♯) · (I_2^♭, s_u, I_1^♯) · (I_2^♭, s_v_1,ψ_1(v_1)) = (ψ_2(v_2)^♭, s, ψ_1(v_1)^♯),

where

    s(I_1,I_2) = ( (i_0 I_2^♭ + I_1^♯ s_u) I_2^♭ + I_1^♯ s_v_1)(I_1,I_2) = I_0 · s_u(I_1,I_2) · I_0 = ψ_0(u).

Thus, in this case, f(ψ_M(w)) = τ(w). If one or more of the factors in the factorization w = v_2 u v_1 are empty, then the proof is similar but simpler.


We end with a prototypical application of the technique, to be used in the next section.

Let S be a finite semigroup and let T_1, T_2 be subsemigroups of S such that T_1 ∪ T_2 generates S. Denote by T_0 := T_1T_2, the subsemigroup generated by T_1T_2. Then the semigroup S divides a triple product of T_2^♭, (T_0^I)^T_1^I × T_2^I, and T_1^♯.


Let A_i := T_i ×{i} for i = 1,2 and A := A_1 ∪ A_2. Denote by ψ A^+  S the surjective homomorphism defined on generators (t_i,i) ∈ A by ψ(t_i,i) := t_i. For i = 1,2, let ψ_i be the restriction of ψ to A_i^+, and let χ (T_1 × T_2)^+ → T_0 be the homomorphism defined by χ(t_1,t_2) := t_1t_2 for (t_1,t_2) ∈ T_1 × T_2. Note that ψ_0, as defined above, in this case turns out to be the restriction of ψ to (A_1^+A_2^+)^+. Hence, writing m  T_2^I × T_0^I × T_1^I → T^I for the multiplication map m(t_2,t_0,t_1) := t_2t_0t_1, we have ψ = m ∘τ. Let ψ_M  A^+ → T_M be the merge decomposition along χ, ψ_1, and ψ_2. By Proposition <ref>, pick f  T_M → T_2^I × T_0^I × T_1^I such that τ = f ∘ψ_M. Then ψ = m ∘ f ∘ψ_M, so S divides T_M since ψ is surjective.





§ TWO-SIDED KROHN-RHODES THEOREM

In this section, we apply the merge decomposition technique of Section <ref> to give a short proof of the crucial step in the two-sided Krohn-Rhodes theorem.

For any finite semigroup S, define _S to be the smallest variety which is closed under two-sided semidirect products, and which contains  and all simple groups that divide S.

Let S be a finite semigroup. Then S ∈_S.


By induction on |S|.

Case 1. S is a group. Any finite group embeds in an iterated wreath product of its simple group divisors, cf., e.g., <cit.>.

Case 2. S is cyclic. Any finite cyclic semigroup divides an iterated wreath product of a subgroup and copies of U_1, cf., e.g., <cit.>.

Case 3. S is not a group and S is not cyclic. Let A be a minimal generating set for S and note that |A|≥ 2. Since S is not a group, without loss of generality, S is not right simple (cf., e.g., <cit.>). Therefore, there exists a ∈ A such that aS ⊊ S. Let A_1 := {a}, A_2 := A ∖ A_1, T_i := A_i for i = 1,2, and T_0 := T_1T_2.
By minimality of A, T_1 and T_2 are strictly contained in S. By the induction hypothesis, T_i ∈_T_i, which is contained in _S, since any simple group dividing T_i also divides S.

Moreover, T_0 ⊆ aS, so T_0 is also strictly contained in S. By the induction hypothesis again, T_0 ∈_T_0⊆_S. Since T_1 ∪ T_2 generates S, by Corollary <ref>, S divides a triple product of T_2^♭, (T_0^I)^T_1^I × T_2^I, and T_1^♯. Hence, by Fact <ref>, S ∈_S  (_S _S) = _S.




§ HENCKELL'S THEOREM ON APERIODIC POINTLIKES

Recall that any element s in a finite semigroup S has a unique idempotent power, s^ω. A semigroup S is called aperiodic if every subgroup of S is trivial, or, equivalently, s^ω s = s^ω for every s ∈ S.

For k ≥ 1, define ^k+1 := ^k.

A semigroup S is aperiodic if, and only if, S ∈^k for some k; indeed, the necessity follows from Theorem <ref>.[A finite semigroup S lies in ^k if, and only if, every language recognized by S can be defined by a first-order sentence of quantifier depth ≤ k; this result is contained in <cit.>, and relates our work in Section <ref> to the logical approach of <cit.>.]




For any m, n ≥ 1, ^m ^n ⊆^m+n.


By induction on m. The case m = 1 is true by definition. By the lax associativity of double semidirect product <cit.>, (^m-1) ^n ⊆ (^m-1^n). By the induction hypothesis, (^m-1^n) ⊆^m + n - 1 = ^m+n.




Let  be a variety. A subset X of a finite semigroup S is called -pointlike if, for any relational morphism ρ S  T with T ∈, X ⊆ρ^-1(t) for some t ∈ T.

Any singleton set is -pointlike, and the collection of -pointlike subsets of a semigroup S forms a downward closed subsemigroup, _(S), of the power semigroup 2^S, partially ordered by inclusion, and with multiplication of subsets of S.

The following observation is specific to the variety  of aperiodic semigroups: if X is an -pointlike set in S, then so is the set

X^ω + ∗ := ⋃_n ≥ 0 X^ω X^n.

Indeed, for any ρ S  T with T aperiodic, X ⊆ρ^-1(t) for some t ∈ T, which gives X^m ⊆ρ^-1(t^m) for all m ≥ 1. Aperiodicity of T then yields X^ωX^n ⊆ρ^-1(t^ω) for all n ≥ 0.

We will call a subset U of 2^S saturated, if it is a subsemigroup that is closed downward in the inclusion order and closed under the operation X ↦ X^ω + ∗. Clearly, any subset U of 2^S is contained in a smallest saturated set, which we call its saturation, and denote by (U).

We will need the following lemma, which was essentially already in <cit.>; see also <cit.>.

Let G be a subgroup of 2^S. Then ⋃ G ∈(G).


Let C_1, …, C_k be an exhaustive list of the cyclic subgroups of G. Note that, for any generator X of C_i, X^ω + ∗ = ⋃ C_i, so ⋃ C_i ∈(G) for every i. Also note that G = C_1 ⋯ C_k. Therefore, since multiplication distributes over union, ⋃ G = (⋃ C_1) ⋯(⋃ C_k) ∈(G).


We will use the merge decomposition (Section <ref>) to give a short proof of the following theorem.

Let S be a semigroup. The set _(S) is the saturation of the set of singletons in 2^S. Moreover, if A is a generating set for S, then _(S) = _^k(S), where k = (|A|-1)2^|S|2 + 2^|A| - 1.




Throughout the proof, for any finite alphabet A, semigroup S, and homomorphism ϕ A^+ → 2^S, define U_ϕ := (ϕ), S_ϕ := ⋃ U_ϕ, and k(ϕ) := (|ϕ(A)|-1)2^^|S_ϕ|2 + 2^|S_ϕ| - 1.


For any homomorphism ϕ A^+ → 2^S∖{∅}, there exists a homomorphism ψ A^+ → T with T ∈^k(ϕ) and ⋃ϕ(ψ^-1 t) ∈(U_ϕ) for every t ∈ T.


The construction of ψ A^+ → T with T ∈^k(ϕ) is by induction on the parameter (|S_ϕ|,|ϕ(A)|) in ℕ^2, ordered lexicographically.


Case 1. For every a ∈ A, ϕ(a)S_ϕ = S_ϕ = S_ϕϕ(a).

 
Let e = ϕ(w) be an idempotent in the minimal ideal of U_ϕ. Then G := e U_ϕ e is a subgroup of U_ϕ, see, e.g., <cit.>. By Lemma <ref>, ⋃ G lies in (e U_ϕ e), and hence also in (U_ϕ), since e U_ϕ e ⊆ U_ϕ. Using the assumption in this case and the fact that multiplication distributes over union, we have

    S_ϕ = ϕ(w) S_ϕϕ(w) = e (⋃ U_ϕ) e  = ⋃ G.

Thus, S_ϕ lies in (U_ϕ), and we choose ψ to be the trivial homomorphism A^+ →{1}∈.


Case 2. |ϕ(A)| = 1.


Denote the unique element of ϕ(A) by X. Since U_ϕ is a finite cyclic semigroup, pick m ≤ |U_ϕ| such that X^m is idempotent, i.e., X^m = X^ω. Let T := x  |  x^m = x^m+1, the finite aperiodic cyclic semigroup of order m, and let ψ A^+ → T be the homomorphism defined by a ↦ x for every letter a ∈ A. Note that T ∈^m <cit.>, and, since U_ϕ⊆ 2^S_ϕ∖{∅}, we have m ≤ |U_ϕ| ≤ 2^|S_ϕ| - 1 = k(ϕ).
From the definitions, note that, for 1 ≤ i < m, ⋃ϕ(ψ^-1 x^i) = X^i, which lies in U_ϕ, and for i ≥ m, ⋃ϕ(ψ^-1 x^i) = X^ω + ∗, which lies in (U_ϕ).


Case 3. |ϕ(A)| ≥ 2, and there is a_0 ∈ A such that ϕ(a_0)S_ϕ⊊ S_ϕ or S_ϕϕ(a_0) ⊊ S_ϕ.


 Without loss of generality, we may assume ϕ(a_0)S_ϕ⊊ S_ϕ.
Let A_1 := { a ∈ A  |  ϕ(a) = ϕ(a_0)}, and A_2 := A ∖ A_1. Note that, since |ϕ(A)| ≥ 2, ϕ(A_1) and ϕ(A_2) are non-empty proper subsets of ϕ(A). For i = 1,2, denote by ϕ_i the restriction of ϕ to A_i^+, and pick ψ_i  A_i^+ → T_i with T_i ∈^k(ϕ_i) and ⋃ϕ(ψ_i^-1 t) = ⋃ϕ_i(ψ_i^-1 t) ∈(U_ϕ_i) ⊆(U_ϕ), for all t ∈ T_i.  Without loss of generality, we may assume the ψ_i are surjective.

Let ϕ_0  (T_1 × T_2)^+ → 2^S∖{∅} be the unique homomorphism defined, for (t_1,t_2) ∈ T_1 × T_2, by ϕ_0(t_1,t_2) := ⋃ϕ(ψ_1^-1t_1 ·ψ_2^-1t_2). Note that S_ϕ_0⊆ϕ(a_0) S_ϕ, since any w ∈ψ_1^-1t_1 ·ψ_2^-1t_2 starts with a letter from the subalphabet A_1. Since ϕ(a_0) S_ϕ⊊ S_ϕ by assumption, |S_ϕ_0| < |S_ϕ|, so the induction hypothesis applies to ϕ_0: pick a homomorphism χ (T_1 × T_2)^+ → T_0 with T_0 ∈^k(ϕ_0) such that ⋃ϕ_0(χ^-1(t)) ∈(U_ϕ_0) ⊆(U_ϕ), for every t ∈ T_0.

Define μ (A_1^+A_2^+)^+ → (T_1 × T_2)^+ and ψ_0 := χ∘μ, as in Section <ref>.
Note that, for any w_1 ∈ A_1^+, w_2 ∈ A_2^+, we have ϕ(w_1w_2) ⊆ϕ_0(μ(w_1w_2)), and, hence, ϕ(w) ⊆ϕ_0(μ(w)) for all w ∈ (A_1^+A_2^+)^+. Therefore, by the definition of ψ_0, ⋃ϕ(ψ_0^-1t) ⊆⋃ϕ_0(χ^-1t) for all t ∈ T_0, so also ⋃ϕ(ψ_0^-1t) ∈(U_ϕ).

Applying the construction of Section <ref>, let ψ_M  A^+ → T_M be the merge homomorphism, and pick f  T_M → T_2^I × T_0^I × T_1^I such that f ∘ψ_M = τ. Let t ∈ T_M, and write f(t) = (t_2,t_0,t_1) ∈ T_2^I × T_0^I × T_1^I. If (t_2,t_0,t_1) ∈ T_2 × T_0 × T_1, then

    ⋃ϕ(ψ_M^-1t) ⊆⋃ϕ(τ^-1(t_2,t_0,t_1)) =
    ⋃ϕ(ψ_2^-1t_2) ·⋃ϕ(ψ_0^-1t_0) ·⋃ϕ(ψ_1^-1t_1) ∈(U_ϕ),

and, if t_i = I_i for one or more i ∈{0,1,2}, a similar inclusion holds, omitting the corresponding factors ⋃ϕ(ψ_i^-1t_i) from the final product.

Let us write m := |S_ϕ|. Note that, since S_ϕ_0 is strictly contained in S_ϕ and ϕ_0(T_1 × T_2) is contained in 2^S_ϕ_0∖{∅}, we have

    k(ϕ_0) ≤ (2^m-1-2)2^m-12 + 2^m-1 - 1 = 2^m2 - 2^m-12+1 + 2^m-1-1 ≤ 2^m2 - 1,

using that m2 = m-1 + m-12 and 2^m-1≤ 2^m-12+1.

By Facts <ref> and <ref>, T_M ∈^k, where k = k(ϕ_0) + max{k(ϕ_1),k(ϕ_2)} + 1. Using that |ϕ(A_i)| < |ϕ(A)|, we have

    k(ϕ_0) + max{k(ϕ_1),k(ϕ_2)} + 1 ≤(2^m2 - 1) + ((|ϕ(A)| - 2) 2^m2 + 2^m - 1) + 1 = k(ϕ).



Now, to prove the theorem, let A be a generating set for S, define ϕ A^+ → 2^S by ϕ(a) := {a} for a ∈ A, and pick ψ A^+ → T as in the claim. Then U_ϕ is the set of singletons, |ϕ(A)| = |A|, and S_ϕ = S, so that k(ϕ) = (|A|-1)2^|S|2+2^|S| - 1=:k. Define the relational morphism ρ S  T by ρ^-1(t) := ⋃ϕ(ψ^-1 t). Then, for any ^k-pointlike X ⊆ S, we have X ⊆ρ^-1(t) for some t ∈ T, and therefore, since ρ^-1(t) lies in (U_ϕ) by the claim, so does X. We have proved that _^k(S) ⊆(U_ϕ), while the remarks at the beginning of this section imply (U_ϕ) ⊆_(S), which is clearly contained in _^k(S), since ^k ⊆. Thus, _^k(S) = (U_ϕ) = _(S).




§ ACKNOWLEDGEMENTS

In an earlier version of the proof of Theorem <ref>, we proved the claim for k(ϕ) := |ϕ(A)|2^^|S_ϕ|2. We acknowledge the help of MathOverflow <cit.> for guiding us to the slightly better bound given in the paper.
amsplain



