An elementary approach to sofic groupoids
Luiz Cordeiro



We describe sofic groupoids in elementary terms and prove several permanence properties for soficity. We show that soficity can be determined in terms of the full group alone, answering a question by Conley, Kechris and Tucker-Drob.

Keywords: Groupoids, sofic, ultraproducts, full groups.


Complexity Measures of Music
    Bruce J. West^2
    December 30, 2023
============================





§ INTRODUCTION


Sofic groups were first considered by Gromov <cit.> in his work on Symbolic Dynamics (originally under the nable “initially subamenable groups“), and in 2010, Elek and Lippner <cit.> introduced soficity for equivalence relations. Since then, the classes of sofic groups and equivalence relations have been shown to satisfy several important conjectures,see for example <cit.>.

The original definitions of soficity are graph-theoretical, but alternative definitions by Ozawa <cit.> and Pǎunescu <cit.> describe soficity at the level of the so-called full semigroup of R, or in terms of the action of the full group on the measure algebra, which can be immediately generalized to groupoids. We will describe general elementary techniques to deal with (abstract) sofic groupoids.





§ GROUPOIDS


A groupoid is a small category with inverses. More precisely, it consists of a set G together with a partially defined binary operation G^(2)→ G, (g,h)↦ gh, where G^(2)⊆ G× G, called product, satisfying


  (1) If (g,h),(h,k)∈ G^(2) then (gh,k),(g,hk)∈ G^(2) and g(hk)=(gh)k;

  (2) For all g∈ G, there exists g'∈ G such that (g,g'),(g',g)∈ G^(2), and if (g,h),(k,g)∈ G^(2) then g'(gh)=h and (kg)g'=k.

Given g_1,g_2,…,g_n such that (g_i,g_i+1)∈ G^(2), the product g_1⋯ g_n is uniquely determined by (1), and the element g' in (2) is unique – we denote it g^-1 and call it the inverse of g. The source and range of g∈ G are s(g)=g^-1g and r(g)=gg^-1, respectively. The unit space of G is G^(0)=s(G)=r(G). We then obtain G^(2)={(g,h)∈ G× G:s(g)=r(h)}.



A discrete measurable groupoid is a groupoid G with a standard Borel structure for which the product and inverse maps are Borel and s^-1(x) is countable for all x∈ G^(0). In this case the source and range maps are also Borel, and G^(2) and G^(0)={x∈ G:x=s(x)} are Borel subsets of G.

The Borel full semigroup of a discrete measurable groupoid G is the set [[G]]_B of Borel subsets α⊆ G such that the restrictions s|_α and r|_α of the source and range maps are injections, and hence Borel isomorphisms onto their respective images <cit.>. Moreover, a simple application of the Lusin-Novikov Theorem <cit.> implies that G can be covered by countably many elements of [[G]]_B.

[[G]]_B is an inverse monoid[An inverse monoid is a set M with an associative binary operation (x,y)↦ xy, which has a neutral element 1 and such that for each element g∈ M there is an unique element h∈ M satisfying g=ghg and h=hgh, called the inverse of g and denoted h=g^-1.] with the natural product and inverse of sets, namely

    αβ={ab:(a,b)∈ (α×β)∩ G^(2)},    α^-1={a^-1:a∈α}

and G^(0) is the unit of [[G]]_B, which we may instead denote by G^(0)=1 or 1_G. Moreover, [[G]]_B is closed below, i.e., if β⊆α and α∈[[G]]_B then β∈[[G]]_B.

A probability measure-preserving (pmp) groupoid is a discrete measurable grou­poid G with a Borel measure μ on G^(0) satisfying μ(s(α))=μ(r(α)) for all α∈[[G]]_B. 


We write (G,μ) for a pmp groupoid when we need the measure μ to be explicit.

The measure μ induces a pseudometric d_μ on [[G]]_B via

    d_μ(α,β)=μ(s(αβ))=μ(r(αβ)).


The trace of α∈[[G]]_B is defined as tr(α)=μ(α∩ G^(0)). For us, it will be easier to deal with the trace instead of the metric above, which is allowed by Proposition <ref> below.

The following properties of d_μ are useful, and we leave the proof to the interested reader.

Given α,β,γ,δ∈ [[G]]_B;


  * d_μ(α,β)=d_μ(α^-1,β^-1).


  * d_μ(αβ,γδ)≤ d_μ(α,γ)+d_μ(β,δ);

  * d_μ(α,β^-1)≤ d_μ(α,αβα)+d_μ(β,βαβ);




















The (measured) full semigroup of a pmp groupoid (G,μ) is the metric quotient [[G]] (or [[G]]_μ to make μ explicit) of [[G]]_B under the pseudometric d_μ. The proposition above implies that [[G]] is also an inverse monoid with the natural structure.

The Borel full group [G]_B of a discrete measurable groupoid G is the set of those α∈[[G]]_B with s(α)=r(α)=G^(0). If (G,μ) is a pmp groupoid, the image of [G]_B in [[G]] is called the (measured) full group G and is denoted [G] or [G]_μ.

We will not make a distinction between measured and Borel full semigroups and groups, except when necessary.


Let Γ be a countable group acting on a probability space (X,μ) by measure-preserving automorphisms. The transformation groupoid G=Γ⋉ X is defined as Γ× X with product

    (h,gx)(g,x)=(hg,x),   x∈ X,   g,h∈Γ        [row sep=tiny]
    x[r,"g"][rr,bend right,"hg",swap]   gx[r,"h"]   hgx

In this case, the unit space G^(0) can be identified with X.

Subexample 1: If X={*} is a singleton we retrieve the group Γ, in which case [G]=Γ and [[G]] consists of Γ and a zero (absorbing) element.

Subexample 2: If Γ=1 is a trivial group we retrieve X, [[G]] is the measure algebra of X and [G] is the trivial group.




A measure-preserving equivalence relation R on a probability space (X,μ) can be regarded as a groupoid with operation (x,y)(y,z)=(x,z) whenever (x,y),(y,z)∈ R. We can identify the unit space R^(0) as X and [[R]] as the set of all partial Borel automorphisms f:dom(f)→ran(f), where dom(f),ran(f)⊆ X, such that graph(f)⊆ R. Namely, to each such f we associate the element {(f(x),x):x∈dom(f)} of [[R]]. The product becomes the usual composition of partial maps, and the trace becomes tr(f)=μ{x:f(x)=x}.


If {(G_n,μ_n)}_n is a family of pmp groupoids and t_n are non-negative numbers such that ∑_n t_n=1, we construct the convex combination groupoid G=∑ t_n G_n as follows: G is the disjoint union of all G_n, G^(2) is the disjoint union of G_n^(2), the product on G restricts to the product on each G_n, and the measure μ on G is given by μ(A)=∑_n t_nμ_n(A∩ G_n).



  §.§.§ Finite groupoids


Every finite groupoid is a convex combination of groupoids of the form G=Γ× Y^2, where Γ is a (finite) group, Y is a (finite) set and Y^2 is the largest equivalence relation on Y. These are the connected finite groupoids. We see both Γ and Y^2 as groupoids on their own right, and the product has the obvious groupoid structure. In this case, G^(0)=Y, and the only probability measure on Y which makes G pmp is the normalized counting measure, μ_#(A)=|A|/|Y|.

We will analyse the full semigroup [[Y^2]] as in Example <ref>.




  (a) If G is a connected finite pmp groupoid, then there exists a finite set Y and an isometric embedding π:[[G]]→[[Y^2]].

  (b) If G is a finite pmp groupoid and ϵ>0, then there exists a finite set Y and a map π:[[G]]→[[Y^2]] such that d(π(αβ),π(α)π(β))<ϵ and |tr(α)-tr(π(α))|<ϵ for all α∈[[G]].





  (a) Suppose G=Γ× Y^2. For every (g,(y,x))∈ G, set π(g,(y,x))∈[[(H× Y)^2]] by dom(π(g,(y,x)))=H×{x} and π(g,(y,x))(h,x)=(gh,y). Then π:[[G]]→[[(H× Y)^2]], π(α)=⋃_g∈απ(g) has the desired properties.

  (b) Suppose G=tH+(1-t)K, where H,K are connected finite pmp groupoids, and suppose further that t is rational, say t=p/q, p,q∈ℕ. Take finite sets X,Y and isometric embeddings π_H:[[H]]→[[X^2]] and π_K:[[K]]→[[Y^2]]. Let [q]={0,1,…,q-1} be a finite set with q elements, and set π:[[G]]→[[([q]× X× Y)^2]] by

    π(α)(j,x,y)=(j,π_H(α∩ H)x,y)    if j≤ p-1
    
    (j,x,π_K(α∩ K)y)    if p≤ j≤ q-1

(and the domain of π(α) consists of all (j,x,y) for which we can apply the definition above.) Then π is an isometric embedding.

We can iterate the argument above to finite rational convex combinations. In the non-rational case, we approximate the coefficients in the convex combination by rational numbers and obtain approximate embeddings as in the proposition.




















  §.§.§ Ultraproducts

The language of metric ultraproducts is useful for soficity, and we'll describe them briefly here. We refer to <cit.> and <cit.> for the details. Let (M_k,d_k) be a sequence of metric spaces of diameter ≤ 1, and 𝒰 a free ultrafilter on ℕ. The metric ultraproduct of (M_n,d_n) along 𝒰 is the metric quotient of ∏_k M_k under the pseudometric d_𝒰((x_k),(y_k))=lim_k→𝒰d_k(x_k,y_k), and we denote it ∏_𝒰M_k. We denote the class of a sequence (x_k)_k∈∏_k M_k by (x_k)_𝒰.





If (G_k,μ_k) is a family of pmp groupoids, the trace on ∏_𝒰[[G_k]] is given by

    tr(g_k)_𝒰=lim_k→𝒰tr(g_k).

Moreover, by <ref> ∏_𝒰[[G_k]] is an inverse monoid with respect to the canonical product, namely (g_k)_𝒰(h_k)_𝒰=(g_kh_k)_𝒰.












One can avoid ultraproducts when dealing with sofic groupoids as follows: For every n∈ℕ, let Y_n={0,…,n-1} be a finite set with n elements, and denote [[n]]=[[Y_n^2]]. Consider the product space ∏[[n]] endowed with the supremum metric and define an equivalence relation ∼ on ∏[[n]] by setting

    (x_n)∼ (y_n)    iff    lim_n→∞d_#(x_n,y_n)=0.

Denote by ∏^ℓ^∞/c_0[[n]]=∏[[n]]/∼ the quotient. Proposition <ref> also implies that ∏^ℓ^∞/c_0[[n]] is an inverse monoid with the obvious operations.

We can naturally embed [[n]] into [[n+1]] (because Y_n⊆ Y_n+1), and this modifies the metric by at most 1/n+1. Also, [[n]] embeds isometrically into [[kn]] as follows: Given α∈[[n]], set π(α)∈[[kn]] as π(α)(qn+j)=qn+α(j), whenever 0≤ q≤ k-1 and j∈dom(α).

This way, we can embed [[n]] into any p≥ n as follows: if p=qn+r, with 0≤ r<n, embed [[n]] into [[qn]] and then into [[qn+1]],[[qn+2]],…,[[qn+r]. The metric changes by at most 1/qn+r+⋯+1/qn+1≤n/qn=n/p-r≤n/p-n, and this goes to 0 as p→∞. With these embeddings and a couple of diagonal arguments, one easily proves the following:



A separable metric space (semigroup) M embeds isometrically into ∏_𝒰 [[n_k]] (where n_k is a sequence of natural numbers and 𝒰 is an ultrafilter on ℕ) if and only if M embeds into ∏^ℓ^∞/c_0[[n]].


In particular, the choice of free ultrafilter 𝒰 or sequence (n_k) does not matter for the existence of an embedding into ∏_𝒰[[n_k]].


We will be dealing with ultraproducts of full semigroups, and most natural operations extend to ultraproducts. For example, if α,β∈[[G]] are such that β^-1α and βα^-1 are idempotents, then α∪β∈[[G]]. We can consider similar unions in ultraproducts under the same hypotheses. We won't make further reference to these facts during the remainder of the paper.



§ SOFIC GROUPOIDS


We fix, for the remainder of this paper, a free ultrafilter 𝒰 on ℕ.


A pmp groupoid G is sofic if there exists a sequence {G_k}_k of finite pmp groupoids and an isometric embedding π:[[G]]→∏_𝒰[[G_k]].


Equivalently, a pmp groupoid G is sofic if and only if for every ϵ>0 and every finite subset K of [[G]] (or [[G]]_B, for that matter), there exist a finite groupoid H and a map π:[[G]]→[[H]] such that d(π(αβ),π(α)π(β))<ϵ and |tr(α)-tr(π(α))|<ϵ for all α,β∈ K. The map π is called a (K,ϵ)-almost morphism.

This definition differs from the usual one (see <cit.> or <cit.>) on the initial choice of finite models, but Proposition <ref> and Theorem <ref> show that they are equivalent.


An embedding Φ:M→∏_𝒰[[G_k]] from any sub-inverse monoid M of [[G]] is isometric if and only if it preserves the trace.


We simply need to write the distance in terms of the trace and vice versa. First one verifies that if Φ is isometric then Φ(1)=1, since this is the only element of trace 1, and then that

    tr(α)=1-d_μ(s(α),1)-d_μ(s(α),α).

For the converse, one uses

    d_μ(α,β)
    
       =tr(s(α))+tr(s(β))-tr(s(α)s(β))-tr(β^-1α).





If {G_n}_n is an increasing sequence of sofic groupoids, then G=⋃_n=1^∞ G_n is also sofic. Indeed, {[[G_n]]}_n is an increasing sequence of semigroups of [[G]] with dense union, so almost morphisms of each [[G_n]] give us the necessary almost morphisms of [[G]].




§ PERMANENCE PROPERTIES


In this section we will be concerned with permanence properties of the class of sofic groupoids. We will simply say that a measure μ on a discrete measurable groupoid G is sofic if (G,μ) is a (pmp) sofic groupoid.

Given a non-null subgroupoid H of G, denote by μ_H the normalized measure on H^(0), i.e., μ_H(A)=μ(A)/μ(H^(0)) for A⊆ H^(0), and by tr_H for the corresponding trace on [[H]].


Let G be a discrete measurable groupoid.


  * If μ is a strong limit of sofic measures[
Recall that a net {μ_i}_i∈ I of measures on a measurable space (X,ℬ) converges strongly to a measure μ if μ_i(A)→μ(A) for all A∈ℬ.
], then μ is sofic as well..

  * A countable convex combination of sofic measures is sofic.

  * If μ has a disintegration of the form μ=∫_G^(0) p_xdν(x), where ν-a.e. p_x is a probability measure such that (G,p_x) is sofic, then (G,μ) is also sofic. In particular, if a.e. ergodic component of (G,μ) is sofic, so is (G,μ).

  *  If (G,μ) is sofic and H is a non-null subgroupoid of G then (H,μ_H) is sofic.

  * If ν≪μ, where (G,ν) is pmp, and μ is sofic, then ν is sofic.

  * If {H_n} is a countable Borel partition of G by non-null subgroupoids, then G is sofic if and only if each H_n is sofic.




Item 1. is clear since soficity is an approximation property for the measure.


  2. Suppose ν,ρ are sofic measures and μ=tν+(1-t)ρ, 0<t<1. Take sofic embeddings Φ_ν:[[G]]_ν→∏_𝒰[[G_k]] and Φ_ρ:[[G]]_ρ→∏_𝒰[[H_k]]. Set Φ:[[G]]_μ→∏_𝒰[[tG_k+(1-t)H_k]] as

    Φ(α)=(Φ_ν(α))∪ (Φ_ρ(α))

which, it is easy to check, is a sofic embedding. The countable infinite case follows from 1.


  3. From the previous items it suffices to check that μ is a limit of convex combinations of sofic p_x. Let K be a finite collection of Borel subsets of G^(0) and ϵ>0. The maps x↦tr_x(A), A∈ K, take values in [0,1], so by partitioning [0,1] and taking preimages, we can find a finite partition {X_j}_j=1^N of G^(0) for which |p_x(A)-p_y(A)|<ϵ for all A∈ K whenever x and y belong to the same X_j. For each non-null X_j, choose x(j)∈ X_j with p_x(j) sofic. Then for A∈ K,

    μ(A)   =∫_G^(0)p_x(A)dν(x)=∑_j(∫_X_jp_x(j)(A)dν(x))±ϵ
       =(∑_jν(X_j)p_x(j))(A)±ϵ.



  4. Let K⊆[[H]] be a finite subset and ϵ>0. Since [[H]] is contained in [[G]] (as a semigroup, but with a different metric), there exists a (K,ϵ)-almost morphism θ:[[G]]→[[F]] for some finite pmp groupoid F. We may assume that 1_H∈ K, and that θ(1_H) is an idempotent in [[F]]. For α∈[[H]], we have H^(0)α H^(0)=α, so substituting θ(α) by θ(1_H)θ(α)θ(1_H) (and making ϵ smaller) if necessary, we can further assume that θ(α) is contained in F':=θ(1_H)Fθ(1_H), which is a subgroupoid of F. This defines a map θ_H:[[H]]→[[F']].

To see that θ_H approximately preserves the trace, note that the trace on [[H]] and the trace on [[F']] are given respectively by

    tr_H(α)=tr_μ(α)/tr_μ(1_H)    and    tr_F'(θ_H(α))=tr_F(θ(α))/tr_F(θ(1_H)),

and these numbers are as close as necessary if ϵ is small enough. Products are dealt with similarly, so θ_H is an approximate morphism as necessary.


  5. Let ϵ>0. Let f=dν/dμ. Take a countable partition X_1,X_2,… of G^(0) such that |f(x)-f(y)|<ϵ whenever x and y belong to the same X_j, and fix points x(j)∈ X_j. Then for all A⊆ X,

    ν(A)=∑_j∫_X_j∩ Af(x(j))dμ(x)±ϵ=∑_jf(x(j))μ(X_j)μ_j(A)±ϵ,

where μ_j is the normalized measure on X_j. Since 1=ν(X)=∑_j f(x_j)μ(X_j)±ϵ, it is not hard to obtain

    ν(A)=∑_j(f(x_j)μ(X_j)/∑_i f(x_i)μ(X_i))μ_j(A)±2ϵ/1±ϵ

Each μ_j is sofic by item 4., so items 1. and 2. imply that ν is sofic.

  6. Apply items 4. and 2. with the fact that G=∑_j μ(H_j)H_j.



Now we will deal with finite-index subgroupoids.

A subgroupoid H⊆ G is said to have finite index in G if there exist ψ_1,…,ψ_n∈[G] such that {ψ_iH:i=1… n} is a partition of G. We will call ψ_1,…,ψ_n left transversals of H in G.

This definition restricts to the usual notions of finite index subgroups and equivalence relations, as defined in <cit.>, in the ergodic case. Note that if H⊆ G is of finite index then H^(0)=G^(0).

























Suppose H⊆ G is of finite index. If H is sofic, so is G.


Suppose that ψ_1,…,ψ_N are left transversals for H⊆ G. For each α∈ [[G]], let α_i,j=ψ_i^-1αψ_j∩ H. Note that α_i,j∈[[H]] and that α_i,j^-1=α_j,i. Moreover, α_i,jα_k,l=∅ whenever j≠ l. Let Y be a set with N elements. Given (i,j)∈ Y^2, let E_i,j={(i,j)}∈[[Y^2]] (as a partial transformation on Y, E_i,j is simply defined by E_i,j(j)=i.

Given k and γ∈[[G_k]], set γ⊗ E_i,j=γ× E_i,j∈[[G_k× Y^2]], and then define Ξ:[[G]]→∏_𝒰[[G_k× Y^2]] by

    Ξ(α)=⋃_i,jΦ(α_i,j)⊗ E_i,j


First let's show that Ξ is well-defined, or more precisely that the terms in the right-hand side have disjoint sources and ranges: Let (i,j) and (k,l) be given. Then

    (Φ(α_i,j)⊗ E_i,j)(Φ(α_k,l)⊗ E_k,l)^-1=Φ(α_i,jα_l,k)⊗(E_i,jE_l,k)

If j≠ l the right-hand side is empty, so assume j=l. Then

    α_i,jα_j,k=(ψ_i^-1αψ_j∩ H)(ψ_j^-1αψ_k∩ H)1

If this product is nonempty, then we have p_i∈ψ_i, p_j,q_j∈ψ_j, q_k∈ψ_k and g,h∈α such that the product (p_i^-1gp_j)(q_j^-1hq_k) is defined, and both terms belong to H. But in particular s(p_j)=r(q_j^-1)=s(q_j), so p_j=q_j. Similarly g=h, and so p_i^-1q_k∈ H, thus q_k∈ψ_i H∩ψ_k H, which implies i=k.

This proves that the ranges of the terms in the definition of Ξ(α) are disjoint. The sources are dealt with similarly, and so Ξ is well-defined.

Now we need to show that Ξ is a morphism. Suppose α,β∈[[G]]. We have

    Ξ(α)Ξ(β)=⋃_i,j,k,lΦ(α_i,jβ_k,l)⊗ (E_i,jE_k,l)=⋃_i,j,lΦ(α_i,jβ_j,l)⊗ E_i,l.

On the other hand Ξ(αβ)=⋃_i,lΦ((αβ)_i,l)⊗ E_i,l, so we are done if we show that for given i,l,

    ⋃_jα_i,jβ_j,l=(αβ)_i,l.


The inclusion ⊆ is quite straightforward, using a similar argument to the one right after (1) above. For the converse, suppose p_i^-1abp_l∈(αβ)_i,l, where p_i∈ψ_i, p_l∈ψ_l, a∈α and b∈β. Choose j such that bp_l∈ψ_j H, so there is a unique p_j∈ψ_j such that the product p_j^-1bp_l is defined and in H. Therefore 



    p_i^-1abp_l=(p_i^-1a p_j)(p_j^-1bp_l)∈α_i,jβ_j,l.






Finally, we need to show that Ξ is trace-preserving. Note that

    trΞ(α)=1/N∑_i=1^Ntr(α_i,i),

so we are done if we prove that tr(α_i,i)=tr(α).

Let's show that α_i,i∩ G^(0)=s{g∈ψ_i:r(g)∈α∩ G^(0)}. An element of α_i,i∩ G^(0) has the form x=p_i^-1ap_i for a∈α and p_i∈ψ_i. It follows that x=s(p_i), so r(p_i)=a∈α∩ G^(0). Conversely, if x=s(g), where g∈ψ_i and r(g)∈α∩ G^(0), then x=g^-1r(g)g∈ψ_i^-1αψ_i∩ G^(0).

Finally, we obtain

    tr(α_i,i)   =μ(ψ_i^-1αψ_i∩ G^(0))=μ(s(ψ_i∩ r^-1(α∩ G^(0))))=μ(r(ψ_i∩ r^-1(α∩ G^(0))))
       =μ(α∩ G^(0))=tr(α),

because r|_ψ_i:ψ_i→ G^(0) is surjective.

We will say that a pmp groupoid G is periodic if s^-1(x) is finite for all x∈ G^(0), and that G is hyperfinite if it is an increasing union of subgroupoids with finite fibers (this is the measured analogue of the AF groupoids introduced in <cit.>)


Every hyperfinite groupoid is sofic.


First note that every measure space (X,μ), seen as a trivial groupoid (i.e., X=X^(0)), is sofic. Indeed, μ=∫_Xδ_xμ(x), where δ_x is the point-mass measure on x, and (X,δ_x), as a pmp groupoid, is isomorphic to a singleton, hence finite and sofic.

Suppose G has finite fibers. Let G_n={g∈ G:|s^-1(s(g))|=n}. Then the G_n are subgroupoids of G with G=⋃_nG_n, so it suffices to show that each G_n is sofic. An application of Lusin-Novikov implies that the subgroupoid G_n^(0), which is simply a measure space, has finite index in G_n, which is therefore finite. The general case follows from the remark after Proposition <ref>.


Two pmp groupoids (G,μ) and (H,ν) are sofic if and only if (G× H,μ×ν) is sofic.


One direction is clear, since [[G]] embeds isometrically into [[G× H]] via α↦α× H^(0), and similarly for [[H]].

Let M be the submonoid of [[G× H]] of elements of the form ⋃_i=1^nα_i×β_i, where α_i∈[[G]], β_i∈[[H]], and for i≠ j, s(α_i)∩ s(α_j)=∅ or s(β_i)∩ s(β_j)=∅, and r(α_i)∩ r(α_j)=∅ or r(β_i)∩ r(β_j)=∅. Let's show that M is dense in [[G× H]].

Let ϕ∈[[G× H]] and ϵ>0. We can take α_i∈[[G]] and β_i∈[[H]] such that (μ⊗ν)(ϕ(⋃α_i×β_i))<ϵ, and with the α_i×β_i disjoint. For i≠ j, let 

    h_i,j=s|_α_i×β_i^-1(s(α_j×β_j))=α_is(α_j)×β_is(β_j)    and     h_i=⋃_j≠ ih_i,j.


Let x∈ h_i,j∩ϕ, so s(x)=s(a_j,b_j) for some (a_j,b_j)∈α_j×β_j. If (a_j,b_j)∈ϕ, we'd obtain (a_j,b_j)=x∈α_i×β_i, which happens only if i=j. This proves that

    s(⋃_i(h_i∩ϕ))⊆ s(⋃_j(α_j×β_j)∖ϕ)

In particular, d(ϕ,ϕ∖⋃_ih_i)<ϵ, from which follows that d(⋃_i(α_i×β_i∖ h_i),ϕ)<2ϵ.

Since each h_i is a rectangle, we can rewrite ⋃_i(α_i×β_i∖ h_i) as a union of disjoint rectangles with the desired property for the source map. To deal with the range map one can apply the same argument to ϕ^-1 and take intersections. 

So given sofic embeddings Φ:[[G]]→∏_𝒰[[G_n]] and Ψ:[[H]]→∏_𝒰[[H_n]] set Φ⊗Ψ:M→[[G_n× H_n]] by

    Φ⊗Ψ(⋃α_i×β_i)=⋃Φ(α_i)×Ψ(β_i),

where the α_i and β_i satisfy the condition in the definition of M.

The element in the right-hand side is well-defined and doesn't depend on the choice of α_i and β_i since sofic embeddings preserve sources, ranges, and intersections. Φ⊗Ψ is then an trace-preserving embedding of M, and hence extends uniquely to a isometric embeddings of [[G× H]].



§ SOFICITY AND THE FULL GROUP


Let's fix some notation here as well. Given a probability space X, we denote its measure algebra (i.e., the algebra of measurable subsets of X modulo null sets) by MAlg(X). Given a pmp groupoid (G,μ), the set of idempotents of [[G]] (i.e., elements α such that α^2=α) is precisely MAlg(G^(0)).

Given α∈[[G]], define fixα=α∩ G^(0) and suppα=s(α)∖fixα. These defines maps fix,supp:[[G]]→MAlg(G^(0)), and we can extend these maps to ultraproducts of these semigroups.

Again, for each n∈ℕ, fix Y_n a set with n elements, consider the full equivalence relation Y_n^2, whose full group [Y_n^2] can be identified as the permutation group 𝔖_n on n elements, as in Example <ref>. We denote the measure algebra of Y_n by MAlg(n).

A well-known theorem of Dye <cit.> states that when R is an aperiodic equivalence relation, the full group [R] completely determines R. With this in mind, we prove that a pmp groupoid G is sofic if and only if [G] embeds isometrically into ∏_𝒰𝔖_n, as long as G doesn't contain “trivial parts”. This solves a question posed by Conley, Kechris and Tucker-Drob in <cit.> in this case.


A metric group (Γ,d) is metrically sofic if it embeds isometrically into ∏_𝒰𝔖_n.


We will need a few technical lemmas relating the full group [G], the measure algebra MAlg(G^(0)) and the full semigroup [[G]].


Let θ:[G]→∏_𝒰𝔖_n be an isometric embedding and α,β∈[G].


  *  suppα=fixβ if and only if supp(θ(α))=fix(θ(β)).

  *  suppα∩suppβ=∅ if and only if suppθ(α) ∩suppθ(β)=∅





  * Simply note that suppα=fixβ is equivalent to

    d_μ(α,β)=1    and    tr(α)+tr(β)=1,

and the same condition applies to ultraproducts.

  * We have suppα∩suppβ=∅ if and only if d_μ(α,β)=d_μ(1,α)+d_μ(1,β), and this condition is preserved by θ.


We will say that a groupoid G is aperiodic if |s^-1(x)|=∞ for all x∈ G^(0).


Suppose (G,μ) is an aperiodic groupoid. Then for all A∈MAlg(G^(0)), there exists α∈[G] such that suppα=A.


We can decompose G as G=H+K, where H and K are subgroupoids, |r(s^-1(x))|=∞ for all x∈ H^(0) and for every x∈ K^(0), K^x_x=s^-1(x)∩ r^-1(x) is infinite.

The equivalence relation R(H)=(r,s)(H) on H^(0) is aperiodic, in the usual sense, so if A⊆ H^(0), <cit.> allows us to take f∈[[R(H)]] with supp(f)=A, and f lifts to an element of [[H]].

If A⊆ K^(0), we use the fact that K is covered by countably many elements of [[K]], and it is easy to construct α∈[K] with s(g)=r(g) for all g∈α and α∩ K^(0)=K^(0)∖ A.


If γ∈[[G]], then there exists γ∈[G] with γ⊆γ.


Let γ_0=γ, and for all n≥ 1, set

    γ_n={g∈γ^-n:s(g)∉s(γ), r(g)∉r(γ)}

One shows that s(γ_n)∩ s(γ_m)=r(γ_n)∩ r(γ_m)=∅ for n≠ m, and that ⋃_n s(γ_n) and ⋃_n r(γ_n) are both contained and conull in s(γ)∪ r(γ). Therefore γ=⋃_nγ_n∪(G^(0)∖(s(γ)∪ r(γ)) has the desired properties.

If Γ_1 and Γ_2 are groups acting on sets X_1 and X_2, respectively, θ:Γ_1→Γ_2 is a homomorphism and ϕ:X_1→ X_2 is a function, we say that the pair (θ,ϕ) is covariant if ϕ(γ x)=θ(γ)ϕ(x) for all γ∈Γ_1 and x∈ X_1.

Given α∈[G] and A∈MAlg(G^(0)), define α· A=r(s|_α^-1(A)). This defines an (isometric, order-preserving) action of [G] on MAlg(G^(0)). This action also extends to ultraproducts of full groups and measure algebras.


An aperiodic pmp groupoid G is sofic if and only if the full group [G] is metrically sofic. More precisely, every isometric embedding of [G] into an ultraproduct ∏_𝒰𝔖_n extends uniquely to an isometric embedding of [[G]].


Let's deal with uniqueness first: If θ:[[G]]→∏_𝒰𝔖_n is an isometric embedding, then for every α∈ [[G]] choose, by Lemmas <ref> and <ref>, α,β∈ [G] with suppβ=s(α) and α⊆α. Then θ(α)=θ(α)suppθ(β), so θ is uniquely determined by its restriction to [G].

Now suppose θ:[G]→∏_𝒰𝔖_n is an isometric embedding, and let's use the ideas above to extend it to [[G]].

Given A∈MAlg(G^(0)), choose α∈[G] with supp(α)=A and define ϕ(A)=supp(θ(α)). We need several steps to finish this proof, namely,



  *  ϕ is well-defined, i.e., ϕ(A) does not depend on the choice of α with supp(α)=A:

Suppose α,α'∈[G] satisfy suppα=suppα'=A. Consider any β∈[G] with suppβ=G^(0)∖ A. By Lemma <ref>.<ref>, supp(θ(α))=fix(θ(β))=supp(θ(α)).














  * ϕ preserves intersections:

Let A,B∈MAlg(G^(0)), and consider α,β,γ∈[R] with supp(α)=A∩ B, supp(β)=A∖ B and supp(γ)=B∖ A. By Lemma <ref>.<ref>, the supports of θ(α) and θ(β) are disjoint, so supp(θ(αβ))=supp(θ(α)θ(β))=supp(θ(α))∪supp(θ(β)), and similarly for α and γ. Also, supp(αβ)=A and supp(αγ)=B, so again by Lemma <ref>.<ref>,

    ϕ(A)∩ϕ(B)   =supp(θ(αβ))∩supp(θ(αγ))
       =(supp(θ(α))∪supp(θ(β)))∩(supp(θ(α))∪supp(θ(γ)))
       =supp(θ(α))=ϕ(A∩ B).



  * ϕ preserves measure:

By Proposition <ref>, θ is trace-preserving, so ϕ preserves measure.


  * If α∈[G], then ϕ(fixα)=fix(θ(α)):

We need just to verify that ϕ preserves complements. Given A∈MAlg(G^(0)), the complement B=G^(0)∖ A is the unique element disjoint with A and such that μ(A)+μ(B)=1, and all of this is preserved by ϕ.


  * (θ,ϕ) is covariant:

Let A∈MAlg(G^(0)) and α∈[G]. Take β∈[G] with suppβ=A. Then supp(αβα^-1)=α· A, and

    ϕ(α· A)   =supp(θ(αβα^-1))=supp(θ(α)θ(β)θ(α)^-1)=θ(α)·supp(θ(β))
       =θ(α)·ϕ(A).



For every α∈[[G]], set Φ(α)=θ(α')ϕ(s(α)), where α'∈[G] is such that α⊆α' (which exists by Lemma <ref>). Using the definition of ϕ and the fact that it preserves the order, it is not hard to see that Φ is also well-defined. Note that Φ extends both θ and ϕ.

Let's show that Φ is a sofic embedding. Suppose α=α'A, β=β'B, where α,β∈[[G]], α',β'∈[G] and A,B∈MAlg(G^(0)). Then

    αβ=α'β'(B∩β^-1· A)

Since the same kind of formula holds on ultraproducts and (θ,ϕ) is a covariant pair of morphisms, we obtain Φ(αβ)=Φ(α)Φ(β).

It remains only to see that Φ is trace-preserving. Let α∈[[G]]. If we show that fixΦ(α)=ϕ(fixα) we are done because ϕ is isometric.

Let α'∈[G] with α⊆α'. Let A=fixα and B=fixα'∖ A. Note that A=fixα'∩ s(α), so 
    ϕ(A)=fixθ(α')∩ s(Φ(α)).

Since Φ(α)=θ(α')ϕ(s(α))⊆θ(α'), we have fix(Φ(α))=fix(θ(α'))∩ s(Φ(α)). Thus we are done.


Now we extend this result to when G has periodic points, but no singleton classes. Set Per_≥ 2(G)={x∈ G^(0):2≤|s^-1(x)|<∞}.


There exists α∈ [G] with suppα=Per_≥ 2(G).


This follows easily from the existence of a transversal for periodic relations (<cit.>) and an argument similar to the proof of Lemma <ref>.


Suppose that for all x∈ G^(0), |s^-1(x)|≥ 2. Then G is sofic if and only if [G] is metrically sofic.


Let P=Per_≥ 2(G) and Aper=G^(0)∖ P, and consider the subgroupoid H=GAper of G. By previous results, it suffices to show that [H] is metrically sofic. Fix any ρ∈[G] with suppρ=P. Let θ:[G]→∏_𝒰𝔖_n_k be an isometric embedding.

Consider the embedding [H]→[G], α↦α=α∪ P. This embedding modifies distances by a multiplicative factor of μ(Aper). By Lemma <ref>.<ref>, suppθ(α)⊆fixθ(ρ). We can then restrict θ(α) to fixθ(ρ) (similarly to how we did in Theorem <ref>.<ref>.) and obtain a new embedding η:[H]→∏_𝒰𝔖_m_k (where m_k≤ n_k). This new embedding modifies distances by a multiplicative factor of

    d(θ(ρ),1)^-1=d(ρ,1)^-1=μ(Aper)^-1

so η is in fact isometric.

abbrv


