Monthly Archives: September 2011

Facts about finite cyclic semigroups

Let S be a finite cyclic semigroup. Show that S has a unique maximal subgroup and compute it. Compute the kernel of S. Under what circumstances is S a group? Deduce that every finite semigroup contains an idempotent.


Let S be a finite cyclic subgroup with generator s. Now the map \varphi : \mathbb{N}^+ \rightarrow S given by k \mapsto s^k is a surjective semigroup homomorphism (where \mathbb{N}^+ is a semigroup under +). Since \varphi cannot be injective, there exist pairs of distinct positive natural numbers m+1 > n such that s^{m+1} = s^n. Let (n,m+1) be such that m+1 is minimal among these pairs. (For such m+1, there is a unique n < m+1 with s^n = s^{m+1}, since otherwise m+1 is not minimal.)

We now prove a lemma.

Lemma 1: If n,m \in \mathbb{N}^+ with n \leq m, then there exists a unique d \in \mathbb{N}^+ such that n \leq d(m+1-n) < m+1. Proof: (Existence) Note that m+1-n > 0. By the Division Algorithm in \mathbb{N}, there exist natural numbers (that is, nonnegative integers) q and r such that n = q(m+1-n) + r and 0 \leq r < m+1-n. Letting -t = r - (m+1-n) and d = q+1, we have n = d(m+1-n) - t, so that 0 \leq d(m+1-n) - n = t < m+1-n, and thus n \leq d(m+1-n) < m+1. (Uniqueness) Suppose n \leq d(m+1-n) < m and n \leq e(m+1-n) \leq m, we have (d-e)(m+1-n) = 0, so that d-e = 0, and so d = e. \square

This number d(m+1-n) will turn out to be very special.

Lemma 2: For all i \in \mathbb{N} and k \in \mathbb{N}^+, we have s^{k(m+1-n)}s^{n+i} = s^{n+i}. Proof: We proceed by induction on k. For the base case k = 1, if i = 0, then s^{m+1-n}s^{n+i} = s^{m+1-n+n} = s^{m+1} = s^n = s^{n+i}. If i \neq 0, then s^{m+1-n}s^{n+i} = s^{m+1+i} = s^{m+1}s^i = s^ns^i = s^{n+i}. Now for the inductive step, suppose the result holds for some k. Then s^{(k+1)(m+1-n)}s^{n+i} = s^{m+1-n}s^{k(m+1-n)}s^{n+1} = s^{m+1-n}s^{n+i} = s^{n+i}. So the result holds for all k \geq 1. \square

Corollary 2.1: If a,b \geq n and a \equiv b mod m+1-n, then s^a = s^b. Proof: Without loss of generality, say a > b. Now a-b = q(m+1-n) for some q \geq 1, and thus a = q(m+1-n) + b and b = n+i for some i. \square

Corollary 2.2: If b \geq m+1, then there exists a such that n \leq a < m+1 and s^b = s^a. Proof: It suffices to show that there exists a such that n \leq a < m+1 and a \equiv b mod m+1-n. To that end, let r be the least residue of b-n mod m+1-n. That is, b-n = q(m+1-n) + r, where q and r are nonnegative. Letting a = n+r, we have Then b = q(m+1-n) + a and n \leq a < m+1, so s^b = s^a. \square

Corollary 2.3: S consists of the elements \{s^1,s^2,\ldots,s^n,\ldots,s^m\}, and these are pairwise distinct.

Lemma 3: If a,b \geq n and s^a = s^b, then a \equiv b mod m+1-n. Proof: Since m+1-n \neq 0 and a-n, b-n \geq 0, there exist nonnegative integers q_1,q_2,r_1,r_2 such that a-n = q_1(m+1-n) + r_1, b-n = q_2(m+1-n) + r_2, and 0 \leq r_1,r_2 < m+1-n. Since s^a = s^b, we have s^{q_1(m+1-n)+n+r_1} = s^{q_2(m+1-n)+n+r_2}. Whether q_1 and q_2 are zero (trivially) or not (Lemma 2), we have s^{n+r_1} = s^{n+r_2}. Now r_1,r_2 < m+1-n, so that r_1+n,r_2+n < m+1. By the minimalness of m+1, we have r_1 + n = r_2 + n. Thus a-n \equiv b-n mod m+1-n, and so a \equiv b mod m+1-n. \square

Lemma 4: If a < n and b \in \mathbb{N}^+ such that b \neq a, then s^a \neq s^b. Proof: If b < m+1 and s^b = s^a, we violate the minimalness of m+1. If b \geq m+1, then by Corollary 2.2, there is an integer c with n \leq c < m+1 and s^c = s^b = s^a, again violating the minimalness of m+1. \square

Using Lemmas 3 and 4 and Corollary 2.1, we can now characterize the kernel of \varphi as follows. The equivalence class [a] is \{a\} if 1 \leq a < n, and is \{b \geq n \ |\ b \equiv a\ \mathsf{mod}\ m+1-n\} if a \geq n.

Lemma 5: If s^a is idempotent, with 1 \leq a \leq m, then a = d(m+1-n). (Where d is as defined in Lemma 1.) Proof: If 1 \leq a < n, then we have a = 2a, which has no solution in \mathbb{N}^+. If n \leq a \leq m, then 2a \equiv a mod m+1-n. So a \equiv 0 mod m+1-n, and then a = q(m+1-n) for some q. By Lemma 1, q = d. \square

So S has precisely one idempotent.

Lemma 6: Let S be a semigroup. Let E(S) denote the set of idempotents in S, and let \mathsf{MG}(S) denote the set of maximal subgroups of S. Let \psi : \mathsf{MG}(S) \rightarrow E(S) be defined by G \mapsto 1_G. Then \psi is bijective. Proof: (Surjective) If e \in S is idempotent, then the set G_e = \{a \in S\ |\ ea = ae = a, ab = ba = e\ \mathrm{for\ some}\ b \in S\} is the \subseteq-greatest subgroup of S having identity e by 1.4.11. In particular, G_e is a maximal subgroup, and \psi(G_e) = e. If H \subseteq S is a subgroup with identity e, then H \leq G_e. If H is maximal, then H = G_e. So \psi is injective, and thus bijective. \square

Since our cyclic semigroup S has only one idempotent, it has a unique maximal subgroup. Namely, G_e where e = s^{d(m+1-n)}.

Lemma 7: s^{d(m+1-n)}s^k = s^k if and only if k \geq n. Proof: The (\Leftarrow) direction was proved in Lemma 2. Now suppose s^{d(m+1-n) + k} = s^k. Now d(m+1-n) + k \geq n, so that k \geq n (using our characterization of \mathsf{ker}\ \varphi). \square

Lemma 8: If k \geq n, then there exists \ell \geq n such that s^ks^\ell = s^{d(m+1-n)}. Proof: Choose \ell \geq n such that k+\ell \equiv 0 mod d(m+1-n). \square

Lemmas 7 and 8 demonstrate that G_e = \{s^t\ |\ n \leq t \leq m\}.

In particular, S is a group if and only if n = 1.

Recall now that the kernel of a semigroup is the intersection of its two sided ideals.

Lemma 9: If I \subseteq S is an ideal, then G_e \subseteq I. Proof: Suppose s^a \in I. For all k \geq n, there exists b \geq 1 such that a+b \geq n and a+b \equiv k mod m+1-n; then s^bs^a = s^k. So G_e \subseteq I. \square

Finally, using Corollary 2.2 if necessary, we can see that G_e is itself an ideal of S. Thus the kernel of S is G_e.

Finally, suppose S is a finite semigroup and let s \in S. Now (s) is a cyclic subsemigroup of S, and so must be finite. As we argued above, (s), and thus S, contains an idempotent.

Characterize the left ideal of a semigroup generated by a subset

Let S be a semigroup and let A \subseteq S be a nonempty subset. Recall that the left ideal of S generated by A is the intersection L(A) of all the ideals which contain A, and similarly for right- and two-sided- ideals.

Prove that the left ideal generated by A is A \cup SA and that the two-sided ideal generated by A is A \cup SA \cup AS \cup SAS.


Note that if L is a left ideal containing A, then SA \subseteq L. In particular, A \cup SA is contained in every left ideal which also contains A, and thus is contained in the left ideal generated by A. On the other hand, S(A \cup SA) = SA \cup SSA \subseteq SA \subseteq A \cup SA, and thus A \cup SA is a left ideal of S which certainly contains A. So the left ideal generated by A is contained in A \cup SA, so that L(A) = A \cup SA.

Similarly, if I is an ideal of S containing A, then A \cup SA \cup AS \cup SAS \subseteq I. So A \cup SA \cup AS \cup SAS is contained in the ideal \langle A \rangle generated by A. And on the other hand, since S(A \cup SA \cup AS \cup SAS) \subseteq A \cup SA \cup AS \cup SAS, this set is a left ideal, and likewise a right ideal. So A \cup SA \cup AS \cup SAS is a two sided ideal containing A. Hence \langle A \rangle = A \cup SA \cup AS \cup SAS.

Groups are precisely those semigroups which are both left and right simple

Prove that a semigroup S is a group if and only if it is both left and right simple. Exhibit a left simple semigroup which is not right simple.


We begin with a lemma.

Lemma: Let S be a semigroup. Then S is left simple (right simple) [simple] if and only if Sa = S (aS = S) [SaS = S] for all a \in S. Proof: Suppose S is left simple, and let a \in S. Certainly SSa \subseteq Sa, so that Sa is a left ideal. Thus Sa = S for all a \in S. Conversely, suppose Sa = S for all a \in S, and let L \subseteq S be a left ideal. Now L is nonempty by definition; say a \in L. Then Sa \subseteq L, and so S \subseteq L. Thus L = S, and in fact S is the only left ideal of S. So S is left simple. The proofs for right simple and simple are similar. \square

Now let S be a group and let a \in S. If x \in S, then we have x = xe = xa^{-1}a; in particular, x \in Sa. So S = Sa for all a. By the lemma, S is left simple. Similarly, S is right simple.

Now suppose the semigroup S is both left and right simple. Let a \in S. Since Sa = S, there exists an element e \in S such that ea = a. Now let b \in S be arbitrary. Since aS = S, there exists c \in S such that b = ac. Now b = ac = eac = eb, so in fact e is a left identity element of S. Similarly, there is a right identity element f, and we have e = ef = f, so that e is a two-sided identity.

Now let a \in S be arbitrary. Since Sa = aS = S, there exist elements b,c \in S such that ba = ac = e. Now b = be = bac = ec = c, and we have b = c. Thus a has a two sided inverse with respect to e. Since a was arbitrary, every element has an inverse, and so S is a group.

Now consider the semigroup S = \{a,b\} with xy = x for all x,y \in S. (That is, S is the left zero semigroup on two elements.) Suppose T \subseteq S is a left ideal. Now for all x \in S and y \in T, we have xy = x \in T. Thus T = S, and so S is left simple. However, S is not a group, and so (by the previous argument) cannot be right simple.

The semigroup of nonempty subsets of a semigroup

Let S be a semigroup, and let P(S) denote the set of all nonempty subsets of S. Show that P(S) is a semigroup under the operation AB = \{ab \ |\ a \in A, b \in B\}. Which of the basic properties of S are preserved by P(S)?


We need only show that this operator is associative. Indeed, (AB)C = \{ab\ |\ a \in A, b \in B\}C = \{(ab)c\ |\ a \in A, b \in B, c \in C\} = \{a(bc)\ |\ a \in A, b \in B, c \in C\} = A\{bc\ |\ b \in B, c \in C\} = A(BC).

Suppose S has a left identity e. Then for all A \in P(S), we have \{e\}A = \{ea \ |\ a \in A\} = \{a \ |\ a \in A\} = A. That is, \{e\} is a left identity in P(S). Similarly if e is a right identity in S, then \{e\} is a right identity in P(S). Then if e is an identity in S, \{e\} is an identity in P(S).

Suppose S has a left zero z. Then for all A \in P(S), we have \{z\}A = \{za\ |\ a \in A\} = \{z\ |\ a \in A\} = \{z\}. Thus \{z\} is a left zero in P(S). Similarly, if z is a right zero in S then \{z\} is a right zero in P(S), and if z is a zero in S then \{z\} is a zero in P(S).

If S is commutative, then for all A,B \in P(S) we have AB = \{ab \ |\ a \in A, b \in B\} = \{ba \ |\ b \in B, a \in A\} = BA. Thus P(S) is also commutative.

Suppose e \in S is an identity element and u \in S is a unit, with uv = vu = e. Then \{u\}\{v\} = \{v\}\{u\} = \{e\}, so that \{u\} is a unit in P(S).

Suppose I \subseteq S is a left ideal. Now let A \subseteq S and B \subseteq I be nonempty subsets. Now AB = \{ab \ |\ a \in A, b \in B\} \subseteq I, since B \subseteq I, and moreover this set is nonempty since A and B are nonempty. That is to say, AB \in P(I). So P(I) \subseteq P(S) is a left ideal. Likewise if I is a right ideal in S, then P(I) is a right ideal in P(S), and if I is a two-sided ideal in S, then P(I) is a two-sided ideal in P(S). More generally, if T \subseteq S is a subsemigroup, then P(T) \subseteq P(S) is a subsemigroup.

Suppose S is a left zero semigroup. That is, ab = a for all a,b \in S. If A,B \in P(S), then AB = \{ab \ |\ a \in A, b \in B\} = \{a \ |\ a \in A, b \in B\} = A. That is, P(S) is also a left zero semigroup. Similarly, if S is a right zero semigroup then so is P(S). Suppose now that S has a zero element 0, and that S is a zero semigroup. Now \{0\} is a zero in P(S), and for all A,B \in P(S), we have AB = \{ab \ |\ a \in A, b \in B\} = \{0 \ |\ a \in A, b \in B\} = \{0\}. So P(S) is also a zero semigroup.

If S is simple, P(S) need not be simple, as we show. Consider the group G = Z_2 = \{1,x\}. We can easily verify that the only two-sided ideal in G is G itself, so that G is simple as a semigroup. Now P(Z_2) = \{\{1\}, \{x\}, Z_2\}, and evidently, \{Z_2\} is an ideal in P(Z_2), so that P(Z_2) is not simple.

Every square matrix over a Euclidean domain can be diagonalized by elementary row and column operations

Show that if A is a matrix over a Euclidean domain R, then there is a sequence of elementary row and column operations (as described here and here) which, when performed on A, result in a matrix \begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix} such that D = [d_{i,j}] is square and diagonal and if d_{1,1},\ldots, d_{k,k} are the nonzero diagonal entries of D (k \leq n), we have d_{i,i} | d_{j,j} whenever i \leq j.

Conclude that if M is a finitely generated R-module with relations matrix A (see here for a discussion of relations matrices) then M \cong R^{n-k} \oplus \bigoplus_{i=1}^k R/(d_i).


Let N : R \rightarrow \mathbb{N} denote the Euclidean norm on R.

Note first that if A = 0, there is nothing to show. If A \neq 0, we proceed by induction on the number m of rows of A.

For the base case m = 1, say A = [a_{1,1}\ a_{1,2}\ \cdots\ a_{1,n}]. If n = 1 there is nothing to show, so we assume n \geq 2. We now proceed by induction on \sum_{i=2}^n N(a_{1,i}). For the base case, if \sum_{i=2}^n N(a_{1,i}) = 0, then a_{1,i} = 0 for each 2 \leq i \leq n, and so A = [a_{1,1} | 0] has the desired form. For the inductive step, suppose that for all 1 \times n matrices B = [b_{1,1}\ b_{1,2}\ \cdots\ b_{1,n}] such that \sum_{i=2}^n N(b_{1,i}) \leq K, B can be diagonalized by some sequence of elementary row and column operations. Now suppose \sum_{i=2}^n N(a_{1,i}) = K+1. Using column operation 1 (swap two columns), rearrange the columns of A so that a_{1,1} has minimal norm. By the Division Algorithm, there exist q_i and r_i such that a_{1,i} = q_ia_{1,1} + r_i and either r_i = 0 or N(r_i) < N(a_{1,1}) for each 2 \leq i \leq n. Using column operation 2 (add a multiple of one column to a different one) n-1 times, one for each column after the first, we can put A in the form [a_{1,1}\ r_2\ \cdots\ r_n]. Now \sum_{i=2}^n N(r_i) < \sum_{i=2}^n N(a_{1,1}) \leq \sum_{i=2}^n N(a_{1,i}). By the inductive hypothesis, there is a sequence of elementary row and column operations which diagonalize this new matrix, and so there is a sequence of elementary row and column operations which diagonalizes A. This proves our base case, where A has one row.

Suppose now that the result holds for every matrix having at most m rows, and let A be an (m+1) \times n matrix. Say A = \begin{bmatrix} a_{1,1} & R_1 \\ C_1 & A_1 \end{bmatrix}, where R_1 = [r_{1,2}\ cdots\ r_{1,n}] and C_1 = [c_{2,1}\ \cdots\ c_{m+1,1}]^\mathsf{T}.

We next claim that there is a sequence of elementary row and column operations which transforms A into a matrix of the form \begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix}. To prove this, we proceed by induction on \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}). (Note that it may be the case that n = 1. In this case the sum over the r is empty and thus 0. However, the sum over the c is not empty.) If \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = 0, then we have c_{i,1} = r_{1,j} = 0 for each 2 \leq i \leq m+1 and 2 \leq j \leq n, and so A = \begin{bmatrix} a_{1,1} & 0 \\ 0 & A_1 \end{bmatrix} has the desired form. For the induction hypothesis, suppose that for some K \in \mathbb{N}, every matrix B can be put in the desired form provided \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) \leq K, and suppose that for our A we have \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1. Now among the entries of our matrix, choose a nonzero element of minimal norm and use elementary row and column operations of type 1 (swap) to put this entry in position (1,1). (If no such entry exists, then A = 0 and there is nothing to show.) Now by the Division Algorithm in R, there exist q_i,t_j,u_i,v_j such that r_{1,i} = q_ia_{1,1} + u_i, c_{j,1} = t_ja_{1,1} + v_j, 0 \leq N(u_i) < N(a_{1,1}), and 0 \leq N(v_j) < N(a_{1,1}). Using elementary row and column operations of type 2 (add a multiple of one row/column to a different row/column) we can replace r_{1,i} with u_i and likewise replace c_{j,1} by v_j. Note now that \sum_{i=2}^{m+1} N(v_j) + \sum_{i=2}^n N(u_i) < \sum_{i=2}^{m+1} N(a_{1,1}) + \sum_{i=2}^n N(a_{1,1}) \leq \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1. By the induction hypothesis, there is a sequence of elementary row and column operations which puts the new A in the desired form, and so (performing these one after the other) we can put the original matrix A in the desired form.

Now A can be put in the form \begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix} by elementary row and column operations. Note that any row or column operation we perform on A_1, when performed analogously on A, does not change the entry a_1 or introduce new nonzero elements to row and column 1. Since (as we assume by the induction hypothesis) the matrix A_1 can be diagonalized, then A can also be diagonalized by elementary row and column operations.

We have thus shown by induction that every matrix A over a Euclidean domain can be diagonalized. It remains to be seen that these diagonal entries can be ordered by divisibility. We can assume that our matrix D is square and has all nonzero entries on the main diagonal. We proceed by induction on the dimension of D. For the base case, where D has dimension 1 \times 1, there is nothing to show. Suppose now that every square diagonal matrix D of dimension n can have its diagonal entries divisibility-ordered by elementary row and column operations and let D = \begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix} be a square diagonal matrix of dimension n+1. We claim that d_1 can be replaced by the greatest common divisor of all the d_i, and that each remaining d_i can be replaced by a linear combination of the d_is, via elementary row and column operations. We will show this for one d_i. Note that if D is diagonal, then row and column operations which only operate on two rows and columns (say a and b) do not affect the rest of the matrix. For this reason we can focus on a 2 \times 2 matrix, say \begin{bmatrix} d_1 & 0 \\ 0 & d_i \end{bmatrix}. Since R is a Euclidean domain, using the extended Euclidean Algorithm we can find x and y such that \mathsf{gcd}(d_1,d_i) = xd_1 + yd_i. Using a column/row operation of type 2, we can obtain \begin{bmatrix} d_1 & xd_1 + yd_i \\ 0 & d_i \end{bmatrix}. Swapping rows (or columns), we have \begin{bmatrix} \mathsf{gcd}(d_1,d_i) & d_1 \\ d_i & 0 \end{bmatrix}. If d_1 = a_1\mathsf{gcd}(d_1,d_i), then again we can obtain \begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ d_i & a_1d_i \end{bmatrix}, and so \begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ 0 & a_1d_i \end{bmatrix}. Repeating this procedure for each diagonal entry (except the first), and since greatest common divisor is associative, we have a diagonal matrix \begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix} where d_1 divides each diagonal entry of D_1. By induction, D is row/column equivalent to a diagonal matrices whose diagonal entries are ordered by divisibility.

Finally, suppose we have a finitely generated R-module M, with (say) a generating set of cardinality n and corresponding surjective homomorphism \varphi : R^n \rightarrow M. By the preceding result, there exists a basis B = \{e_1, \ldots, e_n\} for R^n and a generating set E = \{e_1,\ldots,e_m\} for \mathsf{ker}\ \varphi such that the corresponding relations matrix is of the form \begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}, D is square of dimension k \leq n and has no zero diagonal entries, and the diagonal entries of D are ordered by divisibility. In particular, we have \mathsf{ker}\ \varphi = Rd_1 + \cdots Rd_k = (d_1) \oplus \cdots \oplus (d_k) \oplus 0^{n-k}. Then by this previous exercise, M \cong R/\mathsf{ker}\ \varphi \cong R/(d_1) \oplus \cdots \oplus R/(d_k) \oplus R^{n-k}. Note that if any d_i are units, then the corresponding quotient R/(d_i) is trivial.

By the uniqueness portion of the Fundamental Theorem of Finitely Generated Modules over a PID, the (nonunit) d_i are precisely the invariant factors of M.

Characterize the ideals and congruences on the semigroup of natural numbers under max

Characterize the ideals and congruences on the semigroup \mathbb{N} of natural numbers under the \mathsf{max} operator. (I.e., a\ \mathsf{max}\ b = a if a \geq b, b otherwise.)


First we will make some definitions.

Definition: A subset I \subseteq \mathbb{N} is called an interval if, whenever a \leq c \leq b and a,b \in I, c \in I.

Lemma 1: Every nonempty interval in \mathbb{N} has the form [a,b] = \{c \ |\ a \leq c \leq b\} for some a,b or [a,\infty) = \{c \ |\ a \leq c\}. Proof: Every nonempty interval on \mathbb{N} has a least element by the well-ordering property of natural numbers. If a nonempty interval I has a greatest element b, then c \in I for all a \leq c \leq b, and so we have I = [a,b]. If I does not have a greatest element, then for every c \geq a, there exists b \in I with a \leq c \leq b, and thus c \in I. So we have I = [a,\infty). \square

Lemma 2: If I and J are disjoint intervals and there exist a \in I and b \in J such that a \leq b, then for all x \in I and y \in J we have x \leq y. Proof: Suppose to the contrary that there exist x \in I and y \in J with y \leq x. There are six possible orderings for \{a,b,x,y\} which preserve a \leq b and y \leq x. Specifically, these are a \leq b \leq y \leq x, a \leq y \leq b \leq x, a \leq y \leq x \leq b, y \leq a \leq b \leq x, y \leq a \leq x \leq b, and y \leq x \leq a \leq b. In each case, I \cap J is not empty. \square

Next we consider the ideals on \mathbb{N}. To that end, let I \subseteq \mathbb{N} be a subset.

Suppose that I is an ideal under the \mathsf{max} operator. If I is nonempty (as we insist our ideals to be), then it has a least element a by the well-ordering property of the natural numbers. If b \geq a, then \mathsf{max}(a,b) = b \in I, and if b < a, then b \notin I since a is minimal. Thus I = [a,\infty).

Conversely, suppose I = [a,\infty) for some a \in \mathbb{N}. If t \in I and s \in \mathbb{N}, then we have t \geq a. So \mathsf{max}(s,t) \geq a, and thus \mathsf{max}(s,t) \in I. So I is an ideal.

Hence the ideals of (\mathbb{N}, \mathsf{max}) are precisely the intervals [a,\infty) where a \in \mathbb{N}.

Now we will consider the congruences on \mathbb{N}. To that end, let \sigma \subseteq \mathbb{N} \times \mathbb{N} be an equivalence relation.

Suppose \sigma is a congruence, and let A \subseteq \mathbb{N} be a \sigma-class. We claim that A is an interval. To that end, let a,b \in A and suppose a \leq c \leq b. Now a \sigma b and c \sigma c, so that (since \sigma is a congruence) ac \sigma bc, and thus c \sigma b. So c \in A. Thus A is an interval (by our definition above). Thus if \sigma is a congruence on \mathbb{N} under \mathsf{max}, then the classes of \sigma are pairwise disjoint intervals.

Conversely, suppose the classes of the equivalence relation \sigma are pairwise disjoint intervals. We claim that \sigma is a congruence. To that end, suppose a \sigma b and c \sigma d, and suppose without loss of generality that a \leq c. By Lemma 2, we have b \leq d. So ac = c \sigma d = bd. Thus \sigma is a congruence.

Hence the congruences on (\mathbb{N}, \mathsf{max}) are precisely the paritions of \mathbb{N} which consist of intervals.

Exhibit a subsemigroup of a cyclic semigroup which is not cyclic

Exhibit a subsemigroup of a cyclic semigroup which is not cyclic.


Consider the semigroup \mathbb{N} of natural numbers under addition. Certainly \mathbb{N} is cyclic with generator 1. Define T \subseteq \mathbb{N} by T = \{2a+3b\ |\ a,b \in \mathbb{N}\}.

Certainly T is nonempty, since 0 = 2\cdot 0 + 3 \cdot 0 \in T. Moreover, if 2a_1 + 3b_1, 2a_2 + 3b_2 \in T, then (2a_1+3b_1) + (2a_2 + 3b_2) = 2(a_1+a_2) + 3(b_1+b_2) \in T. So T \subseteq \mathbb{N} is a subsemigroup of a cyclic semigroup.

Now suppose T is cyclic, with generator 2a_0 + 3b_0. Now 2 = 2 \cdot 1 + 3 \cdot 0 \in T, so 2 = k(2a_0 + 3b_0) for some k \in \mathbb{N}. Certainly k \neq 0. If b_0 \neq 0, then we have 2 = k(2a_0+3b_0) \geq 3kb_0 \geq 3 > 2, a contradiction. So b_0 = 0, and we have 2 = 2ka_0. So 1 = ka_0, and thus a_0 = 1. That is, T is generated by 2 \cdot 1 + 3 \cdot 0 = 2. But we also have 3 = 2 \cdot 0 + 3 \cdot 1 \in T, so that 3 = 2k for some k \in \mathbb{N}, a contradiction.

So T is not cyclic.

Exhibit a semigroup which is not finitely generated and a semigroup which is finitely generated but not cyclic

Exhibit a semigroup which is not finitely generated and a semigroup which is finitely generated but not cyclic.


We begin with some lemmas of a more general nature.

Lemma 1: Let I be a set and let \{S_i\}_I be a family of semigroups indexed by I. Then the usual cartesian product of sets \prod_I S_i is a semigroup under the induced operation (s_i) \cdot (t_i) = (s_it_i). Moreover, if each S_i is a monoid with identity e_i, then \prod_I S_i is a monoid with identity (e_i), and if each S_i is commutative, then \prod_I S_i is commutative. Proof: We need only show that this operator is associative. Indeed, ((s_i) \cdot (t_i)) \cdot (u_i) = (s_it_i) \cdot (u_i) = ((s_it_i)u_i) = (s_i(t_iu_i)) = (s_i) \cdot (t_iu_i) = (s_i) \cdot ((t_i) \cdot (u_i)) for all (s_i). (t_i), (u_i) \in \prod_I S_i as desired. Now if e_i is an identity in S_i for each i \in I, then given (s_i) \in \prod_I S_i, we have (e_i) \cdot (s_i) = (e_is_i) = (s_i) and likewise (s_i) \cdot (e_i) = (s_i). Finally, if each S_i is commutative, then (s_i) \cdot (t_i) = (s_it_i) = (t_is_i) = (t_i) \cdot (s_i). \square

Lemma 2: Let I be a set and let \{S_i\} be a family of monoids (with identity e_i \in S_i) indexed by I. Then the set \{(s_i) \in \prod_I S_i \ |\ s_i = e_i\ \mathrm{for\ all\ but\ finitely\ many}\ i \in I\} is a subsemigroup of \prod_I S_i, which we denote \bigoplus_I S_i. Proof: In view of Lemma 1, we need only show that this set is closed under multiplication. Indeed, if (s_i), (t_i) \in \bigoplus_I S_i, then there exist finite sets A,B \subseteq I such that, if i \notin A, then s_i = e_i, and if i \notin B, then t_i = e_i. In particular, if i \notin A \cup B, then s_it_i = e_i. Now A \cup B \subseteq I is finite, and thus (s_i) \cdot (t_i) \in \bigoplus_I S_i. So \bigoplus_I S_i is a subsemigroup of \prod_I S_i. \square

Now consider \mathbb{N} as a semigroup under addition and let S = \bigoplus_\mathbb{N} \mathbb{N}. We claim that S is not finitely generated. To see this, suppose to the contrary that S has a finite generating set A = \{\alpha_1, \ldots, \alpha_k\}, where \alpha_j = (a_{j,i}) and a_{j,i} \in S_i for each i \in \mathbb{N}. Now for each j, the set of all indices i such that a_{j,i} \neq 0 is finite- in particular, it has a largest element with respect to the usual order on \mathbb{N}. Let this number be N_j. Now let N = \mathsf{max}_j N_j. For any index k > N, we have a_{j,i} = 0.

Since (as we suppose) S is generated by A, every element of S can be written as a finite product (or sum, as it were, since S is commutative) of elements from A. But in any such sum, the kth entry must be 0 for all k > N. But S certainly has elements whose kth entry is not zero, and so we have a contradiction. So S is not finitely generated.

Now consider T = \mathbb{N} \times \mathbb{N}, where again we consider \mathbb{N} to be a semigroup under addition. Using additive notation, T is evidently generated by \{(0,1), (1,0)\} since (a,b) = a(1,0) + b(0,1). Suppose now that T is cyclic- say T is generated by (a_0,b_0). Now every element of T has the form k(a_0,b_0) = (ka_0,kb_0) for some k. For example, (1,1) = (ka_0,kb_0), so 1 = ka_0 and 1 = kb_0. In \mathbb{N}, we then have a_0 = b_0 = 1. But then (1,2) = k(1,1) = (k,k), so that 1 = k = 2– a contradiction. Thus \mathbb{N} is not finitely generated.

Every infinite cyclic semigroup is isomorphic to the positive natural numbers under addition

Prove that every infinite cyclic semigroup is isomorphic to the semigroup (\mathbb{N}^+, +) of positive natural numbers under addition.


First, let’s clarify some terminology. If S is a semigroup and s \in S, then there is a semigroup homomorphism \varphi : \mathbb{N}^+ \rightarrow S given by k \mapsto s^k. The image of \varphi is called the cyclic subsemigroup of S generated by s, and if \varphi is surjective, then we say S is cyclic with s as a generator. If S has an (unique) identity element e, then the homomorphism \varphi extends to a mapping \psi : \mathbb{N} \rightarrow S by 0 \mapsto e and this is also a semigroup homomorphism. The image of \psi is called the cyclic submonoid of S generated by s.

First, it is clear that (\mathbb{N}^+, +) is an infinite cyclic semigroup.

Suppose now that S is an infinite cyclic semigroup with s a generator. Now \varphi : \mathbb{N}^+ \rightarrow S given by k \mapsto s^k is a surjective semigroup homomorphism. We only need to show that \varphi is injective. To that end, suppose we have \varphi(a) = \varphi(b) for some a,b \in \mathbb{N}^+, so that s^a = s^b. Suppose, without loss of generality, that a < b; say b = a+k, so that s^{a+k} = s^{a}. But now for all t \geq 0, by the division algorithm we have t = qk + r for some q and 0 \leq r < k. Then s^{a+t} = s^{a+qk+r} = s^{a+r}. Indeed, for all positive natural numbers \ell, we have \varphi(\ell) \in \{s^1, s^2, \ldots, s^a, s^{a+1}, \ldots, s^{a+k-1}\}. In particular, \mathsf{im}\ \varphi, hence S, is finite- a contradiction. Thus a = b, and so \varphi is injective. So S \cong \mathbb{N}^+.

Properties of the rows of a relations matrix

Let R, M, \varphi, x_j, y_i, and A be defined as in this previous exercise.

  1. Show that interchanging the generators y_a and y_b has the effect of interchanging the ath and bth rows of the relations matrix A.
  2. Show that, for any r \in R, replacing y_a by y_a + ry_b a \neq b) gives another generating set S^\prime for \mathsf{ker}\ \varphi. Show further that the matrix with respect to this generating set is obtained from A by adding r times the bth row to the a th row.

It is clear that interchanging y_a and y_b in S interchanges the ath and bth rows of A, since the ith row of A is merely the B-expansion of y_i.

Our proof in the previous exercise that adding a multiple of one element in a generating set to another element does not change the generated submodule holds here as well, so the altered set S^\prime = \{y_1, \ldots, y_a + ry_b, \ldots, y_b, \ldots, y_m\} is indeed a generating set for \mathsf{ker}\ \varphi. Moreover, it is clear that the new ath row is just the old ath row plus r times the old bth row.