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.
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_+\).
For \(i \in \N_+\),
Comparing (b) and (c) in example we see that the semigroup is not commutative, and comparing (a) and (b) we wee 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_+\).
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} \] Since the cardinality function is a homomorphism, the partial order graph \((S, \subseteq)\) is uniform. That is, if \(x \in S\) can be factored into singletons \[x = u_1 u_2 \cdots u_n\] where \(n \in \N_+\) and \(\#(u_i) = 1\) for \(i \in \{1, 2, \ldots, n\}\), then \(n = \#(x)\). 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\).
Suppose that \(i, \, j, \, k \in \N_+\) with \(i \lt j \lt k\).
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. In particular, it can be partitioned into sub-semigroups where the difference between the maximum element and the cardinality is constant.
Let \(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.
Properties
Parts (a) and (b) are clear from the definitions. For part (c) follows since \(x \in S_{n,k}\) must contain the element \(n + k\) and \(n - 1\) elements from \(\{1, 2, \ldots, n + k - 1\}\).
Suppose that \(x \in S_{n,k}\) and \(y \in S_{m,j}\) where \(j, \, k \in \N\) and \(m, \, n \in \N_+\).
In particular, suppose that \(x \in S_{n, k}\) where \(n \in \N_+\) and \(k \in \N\) and that \(i \in \N_+\). If \(i \le k\) then \(x \{i\} \in S_{n + 1, k - 1}\) while if \(i \gt k\) then \(x \{i\} \in S_{n + 1, i - 1}\).
\((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-hand side is \(k + \#(y)\) and the right-hand 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. To characterize the exponential distributions on \((S_k, \cdot)\) for \(k \in \N\) which we will do in Section 3, we must first characterize the irreducible elements. For \(k \in \N_+\), the irreducible elements are also the minimal elements.
For \(k \in \N\), the set of irreducible elements of \((S_k, \cdot)\) is \[M_k = \{x \in S_k: x(i) \le k \text{ for all } i \lt \#(x)\}\] There are \(2^k\) minimal elements.
First we show that if \(x \in S_k\) is not an irreducible element of \((S_k, \cdot)\) then \(x \notin M_k\). Thus, suppose that \(x = u v\) where \(u, \, v \in S_k\) are nonempty. Then \(\max(u) > k\) and \(\max(u) \in u \subseteq u v = x\). Moreover, \(\max(u) \lt \max(x)\), so the rank of \(\max(u)\) in \(x\) is less than \(\#(x) = \#(u) + \#(v)\). Therefore \(x \notin M_k\).
Next we show that if \(x \in S_k - M_k\) then \(x\) is not an irreducible element of \((S_k, \cdot)\). Thus, suppose that \(x \in S_k\) and \(x(i) > k\) for some \(i \lt \#(x)\). Construct \(u \in S\) as follows: \(x(i) \in u\) and \(u\) contains \(x(i) - k - 1\) elements of \(x\) that are smaller than \(x(i)\). This can be done since \(x(i) - i \le k\), and hence \(x(i) - k - 1 \le i - 1\), and by definition, \(x\) contains \(i - 1\) elements smaller than \(x(i)\). Now note that \(\max(u) - \#(u)\) = \(x(i) - [x(i) - k] = k\) so \(u \in S_k\). By construction, \(u \subseteq x\) so there exists \(v \in S\) such that \(u v = x\). Recall that \(v\) is the set of ranks of the elements of \(x - u\) in \(u^c\). But \(u^c\) contains \(k\) elements less than \(x(i)\) together with the elements \(x(i) + 1, x(i) + 2, \ldots\). The largest element of \(x - u\) is \(\max(x) = \#(x) + k\) which has rank greater than \(k\) in \(u^c\). Therefore \(\max(v) > k = \max(u) - \#(u)\) so by proposition , \(\max(x) = \max(v) + \#(u)\). Therefore \[\max(v) - \#(v) = [\max(x) - \#(u)] - [\#(x) - \#(u)] = \max(x) - \#(x) = k\] so \(v \in S_k\). Therefore \(x\) is not an irreducible element of \(S_k\).
Next, note that if \(x \in S_k\) and \(\#(x) \ge k + 2\), then \(x \notin M_k\), since one of the \(k + 1\) elements of \(x\) of rank less than \(\#(x)\) must be at least \(k + 1\). For \(n \le k + 1\), the number of elements \(x \in M_k\) with \(\#(x) = n\) is \(\binom{k}{n - 1}\), since \(x\) must contain \(n + k\) and \(n - 1\) elements in \(\{1, 2, \ldots, k\}\). Hence \[\#(M_k) = \sum_{n=1}^{k+1} \binom{k}{n - 1} = 2^k\]
Explicitly give the set of irreducible elements of \((S_k, \cdot)\) for \(k \in \{0, 1, 2, 3\}\).
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.
To illustrate 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\).
Our next discussion concerns the path function of the graph corresponding to the semigroup \((S_k, \cdot)\) for \(k \in \N\). When \(k = 0\) the result is trivial since this semigroup is isomorphic to \((\N, +)\). For \(k \in \N_+\) the result is unknown.
The path function of order \(n \in \N\) for \((S_0, \subseteq)\) is \[\gamma_{0,n}(x) = \binom{\#(x) + n}{n}, \quad x \in S_0\]
Find the path functions for \((S_k, \subset)\) when \(k \in \N_+\).
There are also sub-semigroups of \((S, \cdot)\) based on the minimum.
For \(k \in \N_+\), let \(U_k = \{x \in S: \min(x) = k\}\) and \(V_k = \{x \in S: \min(x) \ge k\}\).
Trivially \(U_k\) and \(V_k\) are closed under \(\cdot\) since \(\min(x y) = \min\{\min(x), \min(y)\}\) for \(x, \, y \in S\). So all that remains is to show that \((V_k, \cdot)\) is complete. Thus, suppose that \(x, \, y \in V_k\), \(z \in S\), and that \(y = x z\). If \(y = x\) then \(z = \emptyset \in V_k\) (recall that \(\min(\emptyset) = \infty\)). Next, suppose that \(y \ne x\) so that \(x \subset y\) and \(z \ne \emptyset\). Let \(i = \min(z)\). If \(i \lt k\) then, since \(\min(x) \ge k\), \(y\) contains the element \(x^c(i) = i\). But this is a contradiction since \(\min(y) \ge k\) so we must have \(i \ge k\).
Here are some simple proprties of these sub-semigroups:
Properties
The sub-semigroup \((U_k, \cdot)\) is not complete for \(k \in \N_+\) as the next example shows.
If \(k \in \N_+\) then \(\{k\}\{k + 1\} = \{k, k + 2\}\). Note that \(\{k\}, \, \{k, k + 2\} \in U_k\) but \(\{k + 1\} \notin U_k\).
In fact, as the next proposition states, \(\{k\}\) and \(\{k, k + 2\}\) are irreducible in \((U_k, \cdot)\)
Let \(k \in \N_+\).
Let \(k \in \N_+\).
The sub-semigroup \((V_k, \cdot)\) is uniform for \(k \in \N_+\).
If \(x \in V_k\) with \(\#(x) = n \in \N_+\) then \(x\) can be factored into irreducible elements. Since these are singletons, the number of factors must be \(n\).
On the other hand, the sub-semigroup \((U_k, \cdot)\) is not uniform for \(k \in \N_+\).
Let \(k \in N_+\). Then \(\{k\}\) and \(\{k, k + 2\}\) are irreducible in \((U_k, \cdot)\) but \[\{k, k + 2\}\{k\} = \{k\}^3 = \{k, k + 1, k + 2\}\]
The next proposition shows that it suffices just to consider \((U_1, \cdot)\) and \((V_1, \cdot)\). Moreover, as noted earlier, \((V_1, \cdot)\) is the same as the strict positive semigroup \((S_+, \cdot)\) which we have already considered. So really, only \((U_1, \cdot)\) is new.
Let \(k \in \N_+\).
For \(x \in S\) define \(\phi_k(x) = \{i + (k - 1): i \in x\}\). It's easy to see that \(\phi_k\) is one-to-one. Moreover, \(\phi_k\) maps \(V_1\) onto \(V_k\) and \(U_1\) onto \(U_k\). Finally, tracing through the definitions, we see that \(\phi_k(x \cdot y) = \phi_k(x) \cdot \phi_k(y)\) for \(x, \, y \in S\).
Let \(\rta\) denote the relation associated with \((U_1, \cdot)\), so that for \(x, \, y \in U_1\), \(x \rta y\) if and only if \(y = x z\) for some \(z \in U_1\). Since \((U_1, \cdot)\) is not complete, \(\rta\) is not simply the subset relation. That is, for \(x, \, y \in U_1\), \(x \rta y\) implies \(x \subset y\), but not conversely. But \(\rta\) is easy to express with the help of a new function.
Define \(u: U_1 \to \N_+\) by \[u(x) = \max\{k \in \N_+: \{1, 2, \ldots, k\} \subseteq x\}, \quad x \in U_1\]
Note that \(u(x)\) is well defined for \(x \in U_1\) since \(x\) is finite and \(1 \in x\).
For \(x, \, y \in U_1\), \(x \rta y\) if and only if \(x \subset y\) and \(u(x) \lt u(y)\).
Suppose that \(x, \, y \in U_1\) and \(x \rta y\). Then by definition, \(y = x z\) for some \(z \in U_1\). But then \(x \subset y\) (strict, since \(z \ne \emptyset\)), and since \(1 \in z\), \(y\) contains the first element in \(x^c\), which by definition is \(u(x) + 1\). Hence \(u(y) \ge u(x) + 1\). Conversely, suppose that \(x, \, y \in U_1\) and that \(x \subset y\) and \(u(x) \lt u(y)\). We know there exists \(z \in S\) such that \(x z = y\), so it just remains to show that \(1 \in z\). But since \(u(y) \ge u(x) + 1\), we must have \(u(x) + 1 \in y\). But this is the element of rank 1 in \(x^c\) so it follows that \(1 \in z\).
The following proposition parallels Proposition
Suppose that \(\varphi\) is a homomorphism from \((U_1, \cdot)\) into \((\R, +)\). The \(\varphi = c \#\) for some \(c \in \R\). In particular, \(\dim(U_1, \cdot) = 1\).
We prove that \(\varphi(x) = \varphi(\{1\}) \#(x)\) for \(x \in U_1\) by induction on \(\#(x)\). The result is trivial when \(\#(x) = 1\) since \(x = \{1\}\). Suppose that the result holds for every \(x \in U_1\) with \(\#(x) = n\), for some \(n \in \N_+\). Suppose that \(x \in U_1\) with \(\#(x) = n + 1\). If \(2 \in x\) then \(x = \{1\}y\) for some \(y \in U_1\) with \(\#(y) = n\). But then by the homomorphism property and the induction hypothesis, \[\varphi(x) = \varphi(\{1\}) + \varphi(y) = \varphi(\{1\}) (n + 1)\] Suppose \(2 \notin x\) so that \(x\) is irreducible. Let \(y = \{1\} \cup \{i - 1: i \in x, \, i \gt 1\}\). Then \[\{1\} x = y \{1\} = \{1\} \cup \{i + 1: i \in x\}\] Note that \(\#(y) = \#(x) = n + 1\) and from the homomorphism property \(\varphi(x) = \varphi(y)\). Repeating the procedure but with \(y\) replacing \(x\) we eventually have \(\varphi(x) = \varphi(z)\) for some \(z \in U_1\) with \(2 \in z\). But then just as before, \(z = \{1\} w\) with \(w \in U_1\) and \(\#(w) = n\), so \(\varphi(x) = \varphi(\{1\}) (n + 1)\).
Let \(T = U_1 \cup \{\emptyset\}\). The quotient space of \((S, \cdot)\) with respect to the positive sub-semigroup \((T, \cdot)\) is \[S / T = \{z \in S: 1 \notin z\} = V_2\]
The basic assumption for the decomposition of \(S\) over \(T\) and \(S / T\) is trivially satisfied, since if \(x \in S\) then either \(x \in T\) or \(x \in S / T\).