Tag Archives: counterexample

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.

A linear transformation on a finite dimensional vector space which has a stable subspace decomposes as a direct sum

Let V be a finite dimensional vector space over a field F and let \varphi : V \rightarrow V be a linear transformation. A subspace W \subseteq V is called \varphi-stable if \varphi[W] \subseteq W. Prove that if \varphi has a stable subspace W, then \varphi decomposes as a direct sum of linear transformations. Moreover, show that if each summand is nonsingular, then \varphi is nonsingular.

Conversely, prove that if \alpha \oplus \beta is nonsingular over a finite dimensional vector space, then \alpha and \beta are nonsingular. Prove that this statement is not true over an infinite dimensional vector space.

Suppose \varphi[W] \subseteq W. Letting \pi : V \rightarrow V/W denote the natural projection, note that \pi \circ \varphi : V \rightarrow V/W. Moreover, since W is \varphi-stable, we have W \subseteq \mathsf{ker}\ \pi \circ \varphi. By the generalized first isomorphism theorem, we have an induced linear transformation \overline{\varphi} : V/W \rightarrow V/W given by \overline{\varphi}(v+W) = \varphi(v) + W. It is clear that the restriction \varphi|_W : W \rightarrow W is a linear transformation. Recall that V \cong W \oplus V/W via the isomorphism \theta : (w, v+W) = v+w. Evidently, \theta \circ (\varphi|_W \oplus \overline{\varphi}) = \varphi \circ \theta. Thus \varphi decomposes as a direct sum: \theta = \alpha \oplus \beta, where V = A \oplus B.

Suppose \alpha : A \rightarrow A and \beta : B \rightarrow B are nonsingular linear transformations. That is, \mathsf{ker}\ \alpha = \mathsf{ker}\ \beta = 0. Suppose (a,b) \in \mathsf{ker}\ \alpha \oplus \beta; then a \in \mathsf{ker}\ \alpha and b \in \mathsf{ker}\ \beta, and we have (a,b) = 0. Thus \alpha \oplus \beta is nonsingular.

Now suppose V is finite dimensional, W \subseteq V is \varphi-stable for some linear transformation \varphi, and let \varphi|_W : W \rightarrow W and \overline{\varphi} : V/W \rightarrow V/W be the induced maps discussed above. Suppose \varphi is nonsingular. Since V is finite dimensional, in fact \varphi is an isomorphism. This induces the following short exact sequence of vector spaces.

a diagram of vector spaces

Note that \mathsf{ker}\ \varphi|_W \subseteq \mathsf{ker}\ \varphi, so that \varphi|_W is injective (I.e. nonsingular). Again, since W is finite dimensional, \varphi|_W is surjective. Using part (a) to this previous exercise, \overline{\varphi} is injective- that is, nonsingular.

Note that this proof strategy depends essentially on the fact that, on finite dimensional vector spaces, injectivity and surjectivity are equivalent. If we are going to find an infinite dimensional counterexample, then the subspace W must also be infinite dimensional and the induced mapping \varphi|_W must be injective but not surjective.

Consider the vector space V = \bigoplus_\mathbb{N} F. Let \varphi : V \rightarrow V be the “right shift operator” given by \varphi(a)_i = 0 if i = 0 and a_{i-1} otherwise. Let W = 0 \oplus \bigoplus_{\mathbb{N}^+} F; that is, all tuples in V whose first coordinate is 0. Certainly W is a subspace of V, and moreover is stable under \varphi. We also have that V/W \cong F \cong F \oplus \bigoplus_{\mathbb{N}^+} 0. Now \varphi|_W is injective but not surjective. Suppose v+W \in V/W; then \overline{\varphi}(v+W) = \varphi(v)+W. Since \varphi(v) \in W, in fact \overline{\varphi} = 0. So \overline{\varphi} is singular.

A counterexample regarding quotients of an algebraic integer ring

Let \mathcal{O} be an algebraic integer ring with ideals A and B. If \mathcal{O}/A = \{a_i+A\}_{i=1}^n and \mathcal{O}/B = \{b_i+B\}_{i=1}^m, is it necessarily the case that \mathcal{O}/AB = \{a_ib_j\}_{i=1,j=1}^{n,m}?

No. If A = B is nontrivial, then the set pairwise products of representatives of \mathcal{O}/A is not large enough.

The division algorithm does not hold in the ring of integers of QQ(sqrt(-D)) with respect to the field norm when D is at most -15

Let D \leq -15 be a squarefree integer, let K = \mathbb{Q}(\sqrt{D}), and let \mathcal{O} be the ring of integers in K. Show that the division algorithm does not hold in \mathcal{O} with respect to the field norm on K.

We wish to find \alpha, \beta \in \mathcal{O} such that, whenever \alpha = \gamma\beta + \delta, we have N(\delta) \geq N(\beta).

If D \not\equiv 1 mod 4, then \mathcal{O} = \{a+b\sqrt{D} \ |\ a,b \in \mathbb{Z}\}. Let \alpha = 2+\sqrt{D} and \beta = 2, and suppose there exist \gamma = a+b\sqrt{D} and \delta = h+k\sqrt{D} such that \alpha = \beta\gamma + \delta and N(\delta) < N(\beta). Then we have h^2 - Dk^2 < 4. Note that if k \neq 0, then N(\delta) is too large; thus k = 0 and h^2 < 4. In fact, h = \pm 1, so that 2+\sqrt{D} = (2a \pm 1) + 2b\sqrt{D}. Comparing coefficients, we have a contradiction mod 2. So no such \gamma and \delta exist.

If D \equiv 1 mod 4, then \mathcal{O} = \{\frac{a}{2} + \frac{b}{2}\sqrt{D} \ |\ a,b \in \mathbb{Z}, a \equiv b \mod 2\}. Let \alpha = \frac{3}{2} + \frac{1}{2}\sqrt{D} and \beta = 2. Suppose there exist \gamma = \frac{a}{2}+\frac{b}{2}\sqrt{D} and \delta = \frac{h}{2}+\frac{k}{2}\sqrt{D} such that \alpha = \beta\gamma + \delta and N(\delta) < N(\beta). Now h^2 - Dk^2 < 16. Since D \leq -15, we have (h,k) \in \{(0,\pm 1), (\pm 1,0), (\pm 2,0), (\pm 3,0)\}. Since h \equiv k mod 2, (h,k) = (\pm 2,0). Now \beta = 1/2, a contradiction.

While every ideal in an algebraic integer ring is generated by two elements, an arbitrary generating set need not contain a two-element generating set

Exhibit an ideal A \subseteq \mathbb{Z} such that A = (a,b,c) but A is not equal to any of (a,b), (a,c), and (b,c).

Consider (6,10,15) = (1), and note that (6,10) = (2), (6,15) = (3), and (10,15) = (5).

In an algebraic integer ring, two ideals whose intersection contains 3 may be comaximal

Let K be an algebraic number field with ring of integers \mathcal{O}, and let A,B \subseteq \mathcal{O} be nontrivial ideals. If 3 \in A \cap B, must it be the case that (A,B) \neq (1)?

Consider K = \mathbb{Q}(\sqrt{-2}), so that \mathcal{O} = \mathbb{Z}[\sqrt{-2}]. Consider A = (1+\sqrt{-2}) and B = (1-\sqrt{-2}). Now AB = (3), so that 3 \in A \cap B. However, note that 1 = (1+\sqrt{-2})(1-\sqrt{-2}) - (1+\sqrt{-2}) - (1-\sqrt{-2}) = (A,B), so that (A,B) = (1).

Principal ideals generated by irreducible elements need not be prime

Suppose \pi is an irreducible element in an algebraic integer ring \mathcal{O}. Must (\pi) be prime as an ideal in \mathcal{O}?

Recall that 1+\sqrt{-5} is irreducible in \mathcal{O}_K, where K = \mathbb{Q}(\sqrt{-5}), since no element in this ring has norm 3. Moreover, 1 - \sqrt{-5} \notin (1+\sqrt{-5}), as we show. If to the contrary we have (a+b\sqrt{-5})(1+\sqrt{-5}) = 1 - \sqrt{-5}, then comparing coefficients we have a-5b = 1 and a+b = -1, so that 3b = -2 for some b \in \mathbb{Z}, a contradiction. Using this previous exercise, we have (1+\sqrt{-5}) \subsetneq (1+\sqrt{-5}, 1-\sqrt{-5}) \subsetneq \mathcal{O}. In particular, 1+\sqrt{-5} is irreducible, but (1+\sqrt{-5}) is not maximal and thus not prime.

So it need not be the case that (\pi) is prime if \pi is irreducible.

Exhibit a pair of algebraic integers in QQ(sqrt(-5)) which are relatively prime but for which Bezout’s identity does not hold

Show that 3 and 1 + \sqrt{-5} are relatively prime as algebraic integers in \mathbb{Q}(\sqrt{-5}), but that there do not exist algebraic integers \lambda,\mu \in \mathbb{Q}(\sqrt{-5}) such that 3\lambda + (1+\sqrt{-5})\mu = 1.

Let a+b\sqrt{-5} be an arbitrary integer in \mathbb{Q}(\sqrt{-5}). Since -5 \equiv 3 \not\equiv 1 mod 4, a and b are integers. Note that N(a+b\sqrt{-5}) = a^2 + 5b^2. If this element has norm 3, then taking this equation mod 5 we have a^2 \equiv 3. Note, however, that the squares mod 5 are 0, 1, and 4. In particular, no algebraic integer in \mathbb{Q}(\sqrt{-5}) has norm 3.

Now N(3) = 9 and N(1+\sqrt{-5}) = 6; if these elements have a factorization, then some factor must be a unit. Thus both 3 and 1 + \sqrt{-5} are irreducible as integers in \mathbb{Q}(\sqrt{-5}). By Theorem 7.7 in TAN, the units in this ring are precisely \pm 1, so that 3 and 1 + \sqrt{-5} are not associates.

If \delta|3 and \delta|(1+\sqrt{-5}), then since N(\delta) \neq 3, N(\delta) = \pm 1, and thus by Lemma 7.3 in TAN \delta is a unit. That is, every common divisor of 3 and 1+\sqrt{-5} is a unit, so that these elements are relatively prime.

Suppose now that there are integers a,b,c,d such that, with \lambda = a+b\sqrt{-5} and \mu = c+d\sqrt{-5}, we have 3\lambda + (1+\sqrt{5})\mu = 1.Comparing coefficients, we have 3a+c-5d = 1 and 3b+c+d = 0. Mod 3, these equations reduce to c+d \equiv 1 and c+d \equiv 0, a contradiction. So no such \lambda and \mu exist.

The dual of the free ZZ-module with a countably infinite basis is not projective

Prove that the dual of the free \mathbb{Z}-module having a countable basis is not free. Show also that it is not projective. (You may assume that any submodule of a free \mathbb{Z}-module is free.)

Note that M = \bigoplus_\mathbb{N} \mathbb{Z} is a free \mathbb{Z}-module having a countably infinite basis. As described in this previous exercise, the dual of an R-module M is the abelian group \mathsf{Hom}_R(M,R) equipped with a particular right R-action. Now we saw in this prior exercise that \mathsf{Hom}_\mathbb{Z}(\bigoplus_\mathbb{N} \mathbb{Z}, \mathbb{Z}) \cong \prod_\mathbb{N} \mathsf{Hom}_\mathbb{Z}(\mathbb{Z},\mathbb{Z}) \cong \prod_\mathbb{N} \mathbb{Z}. (The final conguence is proven here.) Note that since \mathbb{Z} is commutative, right and left \mathbb{Z}-modules are the same. We saw in this prior exercise that \prod_\mathbb{N} \mathbb{Z} is not free. In particular, the dual module to \bigoplus_\mathbb{N} \mathbb{Z} is not free.

Now if \mathsf{Hom}_\mathbb{Z}(M,\mathbb{Z}) is projective as a \mathbb{Z}-module, then there exists a module N such that \mathsf{Hom}_\mathbb{Z}(M,\mathbb{Z}) \oplus N is free. But \mathsf{Hom}_\mathbb{Z}(M,\mathbb{Z}) is naturally a submodule of this direct sum, and thus (by our permitted assumption) must be free- a contradiction. So the dual module of M is not projective.