Once again, let \(S\) denote the collection of finite subsets of \(\N\). Interestingly, the partial order graph \((S, \subseteq)\) studied in Section 1 is the graph of a positive semigroup. Constructing the semigroup requires a bit of work.
We identify a nonempty subset \(x\) of \(\N_{+}\) with the function given by \[x(i) = i\text{th smallest element of } x\] with domain \(D(x) = \{1, 2, \ldots, \#(x)\}\) if \(x\) is finite and with domain \(\N_+\) if \(x\) is infinite. We will sometimes refer to \(x(i)\) as the element of rank \(i\) in \(x\).
Note that \(\#(x) \le \max(x)\) for every \(x\).
If \(x\) and \(y\) are nonempty subsets of \(\N_{+}\) with \(\max(y) \le \#(x)\), let \(x \circ y\) denote the subset of \(\N_+\) whose function is the composition of \(x\) and \(y\): \[(x \circ y)(i) = x[y(i)], \quad i \in D(y)\] We also define \(x \circ \emptyset = \emptyset\) for any \(x \subseteq \N_+\).
Note that \(x \circ y\) is always defined when \(x\) is infinite.
Suppose that \(x\) and \(y\) are subsets of \(\N_+\) with \(\max(y) \le \#(x)\). Then
Parts (a), (b), and (c) are clear since \(x \circ y\) consists of the elements of \(x\) that are indexed by the elements of \(y\). Suppose that \(x \subseteq \N_+\) is infinite, so that \(x \circ y\) is defined for every \(y \subseteq \N_+\). For part (d), note that by definition an element \(j \notin x \circ y\) if and only if either \(j \notin x\) or \(j \in x\), but \(j\) is not indexed by an element of \(y\) and hence is indexed by an element of \(y^c\).
Suppose that \(x\), \(y\), and \(z\) are subsets of \(\N_+\). Assuming that the operations are defined,
Part (a) is the associate law for composition. In general, of course, the composition of functions is associative when the compositions make sense. Part (b) is the left distributive law for composition over union; and part (c) is the left distributive law for composition over intersection. Finally, part (d) is the left cancellation law. Note that the right distributive laws cannot possibly hold; \((x \cup y) \circ z\) and \((x \circ z) \cup (y \circ z)\) do not even have the same cardinality in general, and neither do \((x \cap y) \circ z\) and \((x \circ z) \cap (y \circ z)\). Similarly, the right cancellation law does not hold: if \(x \circ z = y \circ z\), we cannot even conclude that \(\#(x) = \#(y)\), let alone that \(x = y\). Note that \(\N_+\) is a left identity: \(\N_+ \circ x = x\) for any \(x \subseteq \N_+\).
Let \(x = \{2, 5, 6, 8, 12, 13, 25\}\), \(y = \{1, 4, 7\}\), \(z = \{1, 3, 4, 6\}\). Find each of the following sets directly from the definition:
Let \(x\) denote the set of odd positive integers and \(y\) the set of even positive integers. Find each of the following sets:
We can now define semigroup of interest.
Define the binary operation \(\cdot\) on \(S\) by \[x y = x \cup (x^c \circ y) = x \cup \{i\text{th smallest element of } x^c: i \in y\}\] Then \((S, \cdot)\) is a positive semigroup with associated graph \((S, \subseteq)\).
Note that the operation is well defined since \(x^c\) is infinite for \(x \in S\). Essentially, \(x y\) is constructed by adding to \(x\) those elements of \(x^c\) that are indexed by \(y\) (in a sense those elements form a copy of \(y\) that is disjoint from \(x\)). The associative rule holds, and in fact for \(x, \, y, \, z \in S\), \[x (y z) = (x y) z = x \cup (x^c \circ y) \cup (x^c \circ y^c \circ z)\] The empty set is the identity: If \(x \in S\) then \begin{align*} x \emptyset &= x \cup (x^c \circ \emptyset) = x \cup \emptyset = x \\ \emptyset x &= \emptyset \cup (\N_+ \circ x) = \emptyset \cup x = x \end{align*} The left cancellation law holds: Suppose that \(x, \, y, \, z \in S\) and that \(x y = x z\). Then \(x \cup (x^c \circ y) = x \cup (x^c \circ z)\) by definition and hence \(x^c \circ y = x^c \circ z\) since the pairs of sets in each union are disjoint. But then \(y = z\). There are no non-trivial inverses: If \(x, \, y \in S\) and \(x y = \emptyset\) then \(x \cup (x^c \circ y) = \emptyset\). Hence we must have \(x = \emptyset\) and therefore also \(x^c \circ y = \N_+ \circ y = y = \emptyset\). Finally, the associated partial order is the subset order. Suppose first that \(x, \, u, \, y \in S\) and that \(x u = y\). Then \(x \cup (x^c \circ u) = y\) so \(x \subseteq y\). Conversely, suppose that \(x, \, y \in S\) and that \(x \subseteq y\). Let \(u = \{i \in \N_+: x^c(i) \in y\}\). Then \(u \in S\) and \(x \cup (x^c \circ u) = y\) so \(x u = y\).
With our usual notation, \(S_+ = \{x \in S: x \ne \emptyset\}\), so that \((S_+, \cdot)\) is the corresponding strict positive semigroup. The irreducible elements of \((S,\,\cdot)\) are the singletons \(\{i\}\) where \(i \in \N_+\). Here are some simple examples:
For \(i \in \N_+\),
Comparing (b) and (c) in example we see that the semigroup is not commutative, and comparing (a) and (b) we see that the right cancellation law does not held. Thus, \((S, \cdot)\) just satisfies the minimal algebraic assumptions of a positive semigroup; in particular, \(S\) cannot be embedded in a group. Here are a couple of other facts of interest:
Suppose that \(n \in \N_+\).
Some computational exercises are next:
Let \(x = \{2, 3, 10\}\) and \(y = \{4, 7\}\). Find each of the following:
We can give another formulation of the semigroup by identifying a finite subset \(x \subset \N_+\) with its indicator function or equivalently a bit string in the usual way: \(x = (x_1, x_2, \ldots)\) where \(x_i = 1\) means that \(i \in x\) and \(x_i = 0\) means \(i \notin x\), for each \(i \in \N_+\).
Let \(S\) denote the collection of infinite bit strings \(x = (x_1, x_2, \ldots)\) so that \(x_i \in \{0, 1\}\) for each \(i \in \N_+\) and with the restriction that \(x_i = 0\) for all but finitely many \(i \in \N_+\). For \(x, \, y \in S\), define \(x y\) to be the bit string in \(S\) obtained by putting the bits of \(y\), in order, in the 0s of \(x\). Then \((S, \cdot)\) is equivalent to the semigroup formulated above.
Technically, the spaces are isomorphic under the isomorphism that takes a set to its indicator function. By definition, the 1s of \(x\) are also 1s of \(x y\). Putting the bits of \(y\), in order, in the 0s of \(x\) is equivalent to adding (by means of union) \(x^c \circ y\) to \(x\).
This is a very different operation on bit strings than the concatenation operation we saw with free semigroups in Chapter 5.
Repeat exercise in the notation of bit strings.
The notation \(0^*\) means an infinite string of 0s. So \(x = 01100000010^*\) and \(y = 00010010^*\)
The other relations of interest can also be defined in terms of the semigroup operator. Let \(x, \, y \in S\). Then \(x \subset y\) if and only if \(x z = y\) for some \(z \in S_+\). Next, \(x \uparrow y\) if and only if \(y = x \{i\}\) for some \(i \in \N_+\). Finally, \(x \Upa y\) if and only if \(x = y\) or \(y = x \{i\}\) for some \(i \in \N_+\).
If \(\varphi\) is a homomorphism from \((S, \cdot)\) into \((\R, +)\), then \(\varphi = c \#\) for some \(c \in \R\). In particular, \(\dim(S, \cdot) = 1\).
Suppose that \(\varphi\) is a homomorphism from \((S, \cdot)\) into \((\R, +)\). Then \(\varphi(\{i\}\{i\}) = \varphi(\{i + 1\}\{i\})\) and hence \(\varphi(\{i\}) + \varphi(\{i\}) = \varphi(\{i + 1\}) + \varphi(\{i\})\). It follows that \(\varphi(\{i + 1\}) = \varphi(\{i\})\) for \(i \in \N_+\) and so \(\varphi(\{i\}) = \varphi(\{1\})\) for \(i \in \N_+\). Let \(c = \varphi(\{1\})\). If \(n \in \N_+\) and \(i_1 \lt i_2 \lt \cdots \lt i_n\) are positive integers then \begin{align*} \varphi(\{i_1, i_2, \ldots, i_n\}) & = \varphi(\{i_n\} \{i_{n-1}\} \cdots \{i_1\}) \\ & = \varphi(\{i_n\}) + \varphi(\{i_{n - 1}\}) + \cdots + \varphi(\{i_1\}) = c n \end{align*} So \(\varphi(x) = c \#(x)\) for \(x \in S\). In particular, if \(\varphi(\{1\}) = 0\) then \(\varphi(x) = 0\) for all \(x \in S\). On the other hand, if \(c \ne 0\) then \(c \#\) is a non-trivial homomorphism.
For \(x, \, y \in S\),
In particular, if \(x \in S\) and \(i \in \N_+\) then \[ \max(x \{i\}) = \begin{cases} \max(x), &\text{ if } i \le \max(x) - \#(x)\\ \#(x) + i, &\text{ if } i \gt \max(x) - \#(x) \end{cases} \] From Section 1, we know that the partial order graph \((S, \subseteq)\) is uniform. In terms of the semigroup, \(x \in S_+\) can be factored into singletons \[x = u_1 u_2 \cdots u_n\] where \(n = \#(x) \in \N_+\) and \(\#(u_i) = 1\) for \(i \in \{1, 2, \ldots, n\}\). Moreover, we know the number of such factorings.
If \(x \in S_+\) with \(\#(x) = n\) then there are \(n!\) factorings of \(x\) into irreducible elements (singletons).
The proof is by induction on \(n\). The result is trivially true when \(n = 1\) since \(x\) itself would be a singleton. Suppose that the result holds for a given \(n\) and suppose that \(x \in S\) with \(\#(x) = n + 1\). Note that in general, if \(y, \, z \in S\), \(i \in \N_+\) and \(z = \{i\} y\) then \(i \in z\). So an algorithm for constructing a factoring of \(x\) is as follows: Select \(i \in x\) and select a factoring of \(\{i\}^{-1}x\). The first step can be performed in \(n + 1\) ways, and by the induction hypothesis, the second step can be performed in \(n!\) ways. Hence the number of factorings of \(x\) is \((n + 1) n! = (n + 1)!\).
We can also give an explicit algorithm for the factorings. Let \(x = \{i_1, i_2, \ldots, i_n\} \in S_+\). Let \((j_1, j_2, \ldots, j_n)\) be a permutation of \((i_1, i_2, \ldots, i_n)\). For each \(m \in \{1, 2, \ldots, n\}\), let \(k_m = \#\{j \in \{j_1, \ldots, j_{m - 1}\}: j_m \gt j\}\). Then the factoring of \(x\) coresponding to the given permutation is \(\prod_{m=1}^n \{j_m - k_m\}\). Of course, there are \(n!\) permutations of the elements of \(x\).
Here are a couple of simple examples illustrating :
Suppose that \(i, \, j, \, k \in \N_+\) with \(i \lt j \lt k\).
Here are some computational examples illustrating the algorithm in the details of :
Let \(x = \{2, 3, 5, 12, 17\} \in S\). Give the factoring of \(x\) into singletons corresponding to the following permutations:
The semigroup \((S, \, \cdot)\) has an interesting structure, as we will see next. From Section 1, recall the sets \( S_k = \{x \in S: \max(x) - \#(x) = k\} \) for \(k \in \N\). If \(x \in S_+\) then \(\{1, 2, \ldots, \max(x)\} - x\) is the set of gaps
of \(x\) relative to \(\{1, 2, \ldots, \max(x)\}\) and so \(\max(x) - \#(x)\) is the cardinality of this set of gaps. Here is the main result:
\((S_k, \cdot)\) is a complete sub-semigroup of \((S, \cdot)\) for each \(k \in \N\).
We first need to show that \(x y \in S_k\) for \(x, \, y \in S_k\). The result is trivial if \(x = \emptyset\) or \(y = \emptyset\) (which is only possible if \(k = 0\)), so we will assume that \(x\) and \(y\) are nonempty. Then \(\max(y) > \max(x) - \#(x)\), since the left side is \(k + \#(y)\) and the right side is \(k\). By proposition , \(\max(x y) = \max(y) + \#(x)\). Hence \[\max(x y) - \#(x y) = [\max(y) + \#(x)] - [\#(x) + \#(y)] = \max(y) - \#(y) = k\] Therefore \(x y \in S_k\).
To show completeness, suppose that \(x, \, y \in S_k\) and \(x \subset y\) so that \(x u = y\) for some \(u \in S_+\). If \(\max(u) \le k\) then from proposition again, \(\max(y) = \max(x)\) and \(\#(y) = \#(x) + \#(u)\), so \(\max(y) - \#(y) = k - \#(u) \lt k\), a contradiction. Thus, \(\max(u) > k\). From proposition yet again, \(\max(u) = \max(y) - \#(x)\) and \(\#(u) = \#(y) - \#(x)\), so \(\max(u) - \#(u) = \max(y) - \#(y) = k\). Thus, \(u \in S_k\).
Properties of the sub-semigroups:
Finally note that the collection \(\{S_k: k \in \N\}\) is disjoint. The set of irreducible elements of \((S_k, \cdot)\) for \(k \in \N\) is the set \(M_k\) of minimal elements of \((S_k, \subseteq)\) that we characterized in Section 1: \[M_k = \{x \in S_k: x(i) \le k \text{ for all } i \lt \#(x)\}\] Recall that \(M_k\) has \(2^k\) elements. The irreducible elements will be important in our study of exponential distributions in Section 5. For \(k \in \N_+\), the number of elements in a factoring of an element in \(S_k\) into irreducible elements is not necessarily unique so \((S_k, \cdot)\) is not uniform. Here is an example.
If \(k \in \N_+\) then \(\{k + 1\}, \, \{k, k + 2\} \in M_k\) and \[\{k, k + 2\} \{k, k + 2\} = \{k + 1\} \{k + 1\} \{k , k + 2\} = \{k, k + 1, k + 2, k + 4\}\]
Although the structure of the irreducible elements is more complicated, the sub-semigroups all have dimension 1, like the parent semigroup.
Let \(k \in \N\). If \(\varphi\) is a homomorphism from \((S_k, \cdot)\) into \((\R, +)\), then \(\varphi = c \#\) for some \(c \in \R\). In particular, \(\dim(S_k, \cdot) = 1\).
Suppose that \(\varphi\) is a homomorphism from \((S_k, \cdot)\) into \((\R, +)\). We will show by induction on \(\#(x)\) that \(\varphi(x) = c {\#(x)}\) where \(c = \varphi(\{k + 1\})\). The result is trivially true if \(\#(x) = 1\), since the only such \(x \in S_k\) is \(x = \{k + 1\}\). Suppose now that \(\varphi(x) = c \#(x)\) for all \(x \in S_k\) with \(\#(x) \le n\). Let \(x \in S_k\) with \(\#(x) = n + 1\). If \(x\) is not an irreducible element, then \(x = u v\) where \(u, \, v \in S_k\), \(\#(u) \le n\), \(\#(v) \le n\), and \(\#(u) + \#(v) = \#(x)\). In this case, \[\varphi(x) = \varphi(u) + \varphi(v) = c \#(u) + c \#(v) = c \#(x)\] On the other hand, if \(x\) is irreducible, let \(j = \min\{i \in x: i + 1 \notin x\}\). Note that \(j \lt \#(x)\) since \(\max(x) = \#(x) + k\). Now let \(y \in S_k\) be obtained from \(x\) by replacing \(j\) with \(j + 1\). Note that \(\#(y) = \#(x)\) and moreover, \(y^c\) can be obtained from \(x^c\) by replacing \(j + 1\) with \(j\). We claim that \(x x = y x\); that is, \(x \cup (x^c \circ x) = y \cup (y^c \circ x)\). To see this, note first that if \(i \neq j\) and \(i \neq j + 1\), then \(i \in x\) if and only if \(i \in y\), and \(i \in x^c\) if and only if \(i \in y^c\). On the other hand, \(j \in x\) and \(j \in y^c \circ x\) since \(j = y^c[x(1)]\) (by definition, there are \(x(1) - 1\) elements less than \(x(1)\) in \(y^c\); the next element in \(y^c\) is \(j\)). Similarly, \(j + 1 \in y\) and \(j + 1 \in x^c \circ x\) since \(j + 1 = x^c[x(1)]\). Since \(x x = y x\), it follows that \(\varphi(x) = \varphi(y)\). Continuing this process, we find that \(\varphi(x) = \varphi(y)\) for some \(y \in S_k\) that is not irreducible, but with \(\#(y) = \#(x)\). It then follows that \(\varphi(x) = \varphi(y) = c \#(y) = c \#(x)\) and the proof is complete.
The following example illustrates the construction in the details of :
Let \(x = \{3, 4, 5, 8, 15\}\), so that \(x \in S_{10}\). Then \(j = 5\), \(y = \{3, 4, 6, 8, 15\}\) and \[x x = y x = \{3, 4, 5, 6, 7, 8, 9, 12, 15, 20\}\]
For \(k \in \N\), let \(T_k = S_k \cup \{\emptyset\}\), so that \((T_k, \cdot)\) is a positive sub-semigroup of \((S, \cdot)\). Of course, \(T_0 = S_0\). Our next discussion concerns the corresponding quotient spaces in the sense of Section 2.8.
For \(k \in \N\), the quotient space of \((S, \cdot)\) corresponding to \((T_k, \cdot)\) is \[S / T_k = \{z \in S: t \not \subseteq z \text{ for all } t \in M_k\}\]
In particular, \(S / S_0 = \{z \in S: 1 \notin z\}\). In this case, the basic assumption for the decomposition of \(S\) over \(S_0\) and \(S / S_0\) is satisfied:
For \(x \in S\) with \(1 \in x\) (so tht \(x \notin S / S_0\)), let \(j_x = \max\{j \in \N_+: \{1, 2, \ldots j\} \subseteq x\}\). Then \(x\) can be factored uniquely as \(x = y z\) where \begin{align*} y &= \{1, 2, \ldots, j_x\} \in S_0 \\ z &= \{j - j_x: j \in x, \, j \gt j_x\} \in S / S_0 \end{align*}
If \(k \in \N_+\) then the basic assumption for the decomposition over \(T_k\) and \(S / T_k\) is not satsifed. Here is an example
Let \(x = \{1, 2, \ldots, k + 2\} \in S_0\). The subsets of \(x\) that are in \(T_k\) are \(\{k + 1\}\) and \(\{j, k + 2\}\) for \(j \in \{1, 2, \ldots, k + 1\}\). (Note that no subsets of \(x\) of cardinality greater than 2 are in \(T_k\).) So all of the sets \(y = \{j, k + 2\}\) for \(j \in \{1, 2, \ldots, k + 1\}\) are maximal elements of \(S_k\) with \(y \subseteq x\).