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.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: