Teorth: New page: Some notes on the algebraic structures underlying words, combinatorial lines, combinatorial subspaces, IP-systems, etc. == Semigroupoid == A '''semigroupoid''' (or '''small category''') ...

2009-02-21T00:59:46Z

New page: Some notes on the algebraic structures underlying words, combinatorial lines, combinatorial subspaces, IP-systems, etc. == Semigroupoid == A '''semigroupoid''' (or '''small category''') ...

New page

Some notes on the algebraic structures underlying words, combinatorial lines, combinatorial subspaces, IP-systems, etc.

== Semigroupoid ==

A '''semigroupoid''' (or '''small category''') G is like a semigroup, except that the operations are only partially defined (or like a groupoid, except that we do not assume invertibility). More formally:

:'''Definition 1''' A ''semigroupoid'' <math>G = (V, (G(w \leftarrow v))_{w,v \in V}, \cdot)</math> consists of the following objects:

:# A ''vertex set'' V;
:# A (possibly empty) collection <math>G( w \leftarrow v )</math> of ''semigroupoid elements'' from v to w for each <math>v, w \in V</math>;
:# A ''multiplication operation'' <math>g, h \mapsto gh</math> from <math>G( w \leftarrow v ) \times G( v \leftarrow u )</math> to <math>G(w \leftarrow u)</math> for all <math>u,v,w \in V</math> which is associative in the sense that <math>(fg)h = f(gh)</math> whenever <math>f \in G(w \leftarrow v), g \in G(w \leftarrow u), h \in G(u \leftarrow t)</math> and <math>u, v, w \in V</math>.

'''Example 1''' Every semigroup <math>G = (G,\cdot)</math> can be viewed as a semigroupoid on a single vertex <math>V = pt</math>.

'''Example 2''' If V is a collection of probability spaces, then we can form a semigroupoid <math>Mes(V)</math> by declaring <math>Mes(V)(w \leftarrow v)</math> to be the collection of measure-preserving transformations from v to w, with the multiplication law being compositions. If we restrict attention to invertible measure-preserving transformations, then the semigroupoid becomes a groupoid <math>InvMes(A)</math>.

'''Example 3''' If V is a collection of Hilbert spaces, then one can form a semigroupoid <math>Unitary(V)</math> by declaring <math>Unitary(V)(w \leftarrow v)</math> to be the collection of all unitary maps from v to w.

'''Example 4''' If A is an alphabet, then we can form a semigroupoid <math>Words(A)</math> by declaring the vertex set to be the natural numbers <math>{\Bbb N} = \{0,1,2,\ldots\}</math>, and <math>Words(A)(i \leftarrow j)</math> to be the space <math>A^{j-i}</math> of words of length j-i if <math>j > i</math>, and to be the empty set otherwise, and with multiplication given by concatenation. It may help to view <math>G(i \leftarrow j)</math> as words of length j, in which the first i positions are "blank", e.g. if A = {1,2,3}, then a typical element of <math>G(2 \leftarrow 5)</math> might be ..231, with multiplication laws such as <math>.3 \cdot ..231 = .3231</math>. Note that this semigroup is generated by the single character words <math>G(i \leftarrow i+1) = \{ .^i a: a \in A \}</math>.

'''Example 5''' If A is an alphabet, and n is a natural number, we can define the semigroupoid <math>Words_n(A)</math> to be the subsemigroupoid of A formed by restricting the vertex set V to just <math>\{0,1,\ldots,n\}</math>.

'''Example 6''' Form the semigroupoid <math>IP</math> by declaring the vertex set to be the natural numbers <math>{\Bbb N}</math>, and <math>IP(i \leftarrow j)</math> to be the collection of all subsets of <math>\{i+1,\ldots,j\}</math> if <math>j > i</math>, and the empty set otherwise, with multiplication given by union. We also form <math>IP_n</math> by restricting the vertex set to <math>\{0,1,\ldots,n\}</math>. Note that as subsets of a set S can be identified with elements of <math>\{0,1\}^S</math>, that IP is isomorphic to <math>Words(\{0,1\})</math>, and similarly <math>IP_n</math> is isomorphic to <math>Words_n(\{0,1\})</math>.

:'''Definition 2''' A '''homomorphism''' <math>\phi: G \to H</math> between two semigroupoids <math>G = (V, (G(w \leftarrow v))_{w,v \in V}, \cdot)</math> and <math>H = (W, (H(w \leftarrow v))_{w,v \in W}, \cdot)</math> consists of the following objects:

:# A map <math>\phi: V \to W</math> from the vertex set of G to the vertex set of H;
:# Maps <math>\phi: G( v \leftarrow v' ) \to H( \phi(v) \leftarrow \phi(v') )</math> for each <math>v, v' \in V</math> such that <math>\phi(gh) = \phi(g) \phi(h)</math> whenever <math>g \in G(v \leftarrow v'), h \in G(v' \leftarrow v'')</math> and <math>v, v', v'' \in V</math>.

Of course, the composition of two homomorphisms is again a homomorphism.

'''Example 7''' If A is an alphabet, * is a wildcard not in A, and a is an element of A, then there is a ''substitution map'' <math>\pi_a: Words(A \cup \{*\}) \to Words(A)</math> that preserves the vertex set <math>{\Bbb N}</math> and replaces any occurrence of the wildcard * with a. For instance <math>\pi_2(..2*3**1) = ..223221</math>. This is clearly a homomorphism. One can of course restrict <math>\pi_a</math> to be a homomorphism from <math>Words_n(A \cup \{*\})</math> to <math>Words_n(A)</math> for any n.

'''Example 8''' Let G be a group. Define an '''IP-system''' to be a tuple of group elements <math>u_\alpha \in G</math>, one for each finite set <math>\alpha</math> of natural numbers, such that <math>u_\alpha u_\beta = u_{\alpha \beta}</math> whenever the elements of <math>\alpha</math> all lie to the left of the elements of <math>\beta</math> (in particular, <math>u_\emptyset</math> is the identity, and <math>u_{\{a_1,\ldots,a_n\}} = u_{a_1} \ldots u_{a_n}</math> whenever <math>a_1 < \ldots < a_n</math>). Then one can view this IP system as a homomorphism <math>u: IP \to G</math>, with the property that any copy of the empty set gets mapped to the identity element. Conversely, every homomorphism <math>u: IP \to G</math> that maps every copy of the empty set to the identity element comes from an IP system in this fashion.

:'''Definition 4''' Let G be an semigroupoid. A '''measure-preserving group action''' of G is a homomorphism <math>T: G \to Mes(X)</math> of G to the group of invertible measure-preserving transformations on some probability space X; more generally, a '''measure-preserving groupoid action''' of G is a homomorphism <math>U: G \to Mes({\mathcal X})</math> of G to the groupoid of measure-preserving transformations for some collection <math>{\mathcal X}</math> of probability spaces.

:A '''unitary group representation''' of G is a homomorphism <math>U: G \to Unitary(H)</math> from G to the unitary group of some Hilbert space H. More generally, a '''unitary groupoid representation''' of G is a homomorphism <math>U: G \to Unitary({\mathcal H})</math> from G to the unitary groupoid <math>Unitary({\mathcal H})</math> of some collection <math>{\mathcal H}</math> of Hilbert spaces.

'''Example 9''' Every measure-preserving groupoid action <math>U: G \to Mes({\mathcal X})</math> induces a corresponding unitary groupoid representation <math>U: G \to Unitary({\mathcal H})</math>, where <math>{\mathcal H} := \{ L^2(X): X \in {\mathcal X} \}</math> are the Hilbert spaces associated to <math>{\mathcal X}</math>, and each measure-preserving transformation <math>U(g): X \to Y</math> induces a unitary map <math>U(g): L^2(X) \to L^2(Y)</math> by the formula <math>U(g)f := f \circ U(g)^{-1}</math>. [One can think of this operation as that of composing <math>U: G \to Mes({\mathcal X})</math> with the canonical homomorphism from <math>Mes({\mathcal X})</math> to <math>Unitary({\mathcal H})</math>.]

'''Example 10''' Let <math>U: G \to Unitary({\mathcal H})</math> be a unitary groupoid representation, and let V be the vertex set of G. If H_0 is another Hilbert space, and one has unitary maps <math>R_v: H_0 \to Unitary(v)</math> for every <math>v \in V</math>, then we can ''conjugate'' U by R to obtain a unitary group representation <math>U^R: G \to Unitary(H_0)</math>, defined by the formula
:<math>U^R(g) := R_{v}^{-1} U(g) R_{w}</math>
for all <math>g \in G(w \leftarrow v)</math> (thus U(g) is a unitary map from <math>U(v)</math> to <math>U(w)</math>). One easily verifies that this is still a homomorphism. [R here is essentially playing the role of a ''natural transformation'' in category theory.]

'''Example 11''' One application of the renormalisation construction in Example 10 arises when considering a unitary groupoid representation <math>U: IP \to Unitary({\mathcal H})</math> of IP. We set <math>H_0 := U(0)</math> and define <math>R_n: H_0 \to U(n)</math> for every natural number n by the formula <math>R_n := U( \emptyset_{n \leftarrow 0} )</math>, where <math>\emptyset_{n \leftarrow 0} \in IP(n \leftarrow 0)</math> is the copy of the empty set in <math>IP(n \leftarrow 0)</math>, then the unitary group representation <math>U^R: IP \to Unitary(H_0)</math> maps every copy of the empty set to the identity, and so <math>U^R</math> is essentially an IP system in <math>Unitary(H_0)</math>.

:'''Definition 3''' Let A be an alphabet. An '''A-semigroupoid''' <math>G = (G, G^*, (\pi_a)_{a \in A})</math> is a semigroupoid <math>G^*</math>, together with a subsemigroupoid <math>G^*</math> (with the same vertex set V as <math>G^*</math>), together with morphisms <math>\pi_a: G^* \to G</math> for each <math>a \in A</math>, which are the identity on the vertex set V, and which are the identity on G. An '''A-homomorphism''' <math>\phi: G \to H</math> between two A-semigroupoids <math>G = (G, G^*, (\pi^G_a)_{a \in A}), H = (H, H^*, (\pi^H_a)_{a \in A})</math> is a homomorphism <math>\phi: G^* \to H^*</math> which restricts to a homomorphism <math>\phi: G \to H</math>, and also maps <math>G^* \backslash G</math> to <math>H^* \backslash H</math>, and is such that <math>\pi^H_a \circ \phi = \phi \circ \pi^G_a</math> for all <math>a \in A</math>.

'''Example 12''' Example 7 shows that <math>Words(A)</math> and <math>Words_n(A)</math> are A-semigroupoids, with <math>Words(A)^* = Words(A \cup \{*\})</math> and <math>Words_n(A)^* = Words_n(A \cup \{*\})</math>.

'''Example 13''' Suppose we have an A-homomorphism <math>\phi: Words_m(A) \to Words_n(A)</math>, which maps the vertices <math>0,1,\ldots,m</math> to <math>j_0=0,j_1,\ldots,j_m = n</math>. Then we must have <math>j_0 < j_1 < \ldots < j_m</math> (and hence <math>m \leq n</math>), and <math>\phi</math> maps each wildcard generator <math>.^i *</math> to some word <math>.^{j_i} w_i</math>, with <math>w_i</a> having length <math>j_{i+1} - j_i</math> and containing at least one wildcard, and one has
:<math>\phi( .^i a_{i+1} \ldots a_{i'} ) = .^{j_i} \pi_{a_{i+1}}(w_{i+1}) \ldots \pi_{a_{i'}}(w_i).</math>
Thus the image <math>\phi(Words_m(A))</math> is essentially an m-dimensional [[combinatorial subspace]] of <math>A^n</math>, with the property that the positions of the <math>(i+1)^{th}</math> wildcard all lie to the right of the positions of the <math>i^{th}</math> wildcard. Conversely, any combinatorial subspace with this wildcard ordering property can be represented as an A-homomorphism.

Word algebra - Revision history

Teorth: New page: Some notes on the algebraic structures underlying words, combinatorial lines, combinatorial subspaces, IP-systems, etc. == Semigroupoid == A '''semigroupoid''' (or '''small category''') ...