## 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 $k$th entry must be 0 for all $k > N$. But $S$ certainly has elements whose $k$th 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.