## Tag Archives: generating set

### A generating set for the kernel of a given module homomorphism

Let $V$, $T$, $A$, et cetera be as in this previous exercise.

Show that $\mathsf{ker}\ \varphi$ is generated by $D = \{\omega_1,\ldots,\omega_n\}$.

Let $\zeta \in \mathsf{ker}\ \varphi$. Now $\varphi(\zeta) = 0$, and by this previous exercise, we have $\zeta \in \mathsf{span}_{F[x]}(\omega_1,\ldots,\omega_n) + \mathsf{span}_F(\xi_1,\ldots,\xi_n)$. Recall that the $\omega_i$ are in $\mathsf{ker}\ \varphi$, so that $0 = \varphi(\zeta) = \sum b_i v_i$ for some $b_i \in F$. Since the $v_i$ are a basis for $V$ over $F$, we have $b_i = 0$ for all $i$. Thus $\mathsf{ker}\ \varphi \subseteq \mathsf{span}_{F[x]}(\omega_1,\ldots,\omega_n)$. The reverse inclusion is immediate, and so the $\omega_i$ are a generating set for $\mathsf{ker}\ \varphi$ over $F[x]$.

### 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$.

### 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.

### Characterization of the subsemigroup generated by a subset

Let $S$ be a semigroup and let $A \subseteq S$ be a nonempty subset. Recall that the subsemigroup of $S$ generated by $A$ is the set $(A) = \{\prod a_i\ |\ a:n \rightarrow A\ \mathrm{for\ some}\ n \in \mathbb{N}^+\}$. (Since $S$ is associative, the $\prod$ notation is unambiguous provided we insist that $\prod_{i=1}^n a_i = a_1a_2 \cdots a_n$.) Let $B_A(S)$ denote the set of all subsemigroups of $S$ which contain $A$. (Note that $I_A(S)$ is nonempty since it contains $S$.) Prove that $(A) = \bigcap B_A(S)$.

Note that if $T \subseteq S$ is a subsemigroup containing $A$, then in particular we have $\prod a_i \in T$ for all $a: n \rightarrow A$ and $n \in \mathbb{N}^+$. (We can see this by using induction on $n$.) So $(A) \subseteq T$, and thus $(A) \subseteq \bigcap B_A(S)$.

Note also that $(A)$ is itself a subsemigroup of $S$, by generalized associativity. That is, if $\prod_{i=1}^n a_i, \prod_{j=1}^m b_j \in (A)$, then $(\prod a_i)(\prod b_i) = \prod_{k=1}^{n+m} c_i$ where $c_k = a_k$ for $1 \leq k \leq n$ and $c_k = b_{k-n}$ for $n+1 \leq k \leq n+m$. So $\bigcap B_A(S) \subseteq (A)$.

### 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)$.

### Given an element a of an ideal in an algebraic integer ring, give a two element generating set containing a

Find $\alpha$ such that $(180) = (\alpha, 16200)$ in $\mathbb{Z}$. Find $\alpha$ such that $(3, 1+2\sqrt{-5}) = (9,\alpha)$ in $\mathbb{Z}[\sqrt{-5}]$.

Note that $(160)(90) = (16200)$. Using Theorem 9.3, it suffices to find an element $\alpha \in (180)$ and an ideal $C$ such that $(180)C = (\alpha)$ and $(C, (90)) = (1)$. To that end, note that $(90)$ factors into prime ideals as $(90) = (2)(3)^2(5)$, with distinct factors $(2)$, $(3)$, and $(5)$. Let $A_1 = (180)(3)(5) = (2700)$, $A_2 = (180)(2)(5) = (1800)$, and $A_3 = (180)(2)(3) = (1080)$. Now let $\alpha_1 = 8100$, $\alpha_2 = 3600$, and $\alpha_3 = 2160$. Evidently, $A_1(3) = (8100)$, $A_2(2) = (3600)$, and $A_3(2) = (2160)$, and $(3,2) = (2,5) = (3,5) = (1)$. Following the proof of Theorem 9.3, let $\alpha = \alpha_1 + \alpha_2 + \alpha_3 = 13860$. Then $(13860,16200) = (180)$. Indeed, we have $180 = -7 \cdot 13860 + 6 \cdot 16200$, $13860 = 180 \cdot 77$, and $16200 = 180 \cdot 90$.

We first need to find an ideal $D$ such that $(3,1+2\sqrt{-5})D = (9)$. In a previous exercise we found that $D = (9, 3-6\sqrt{-5})$ is such an ideal. Next we wish to find the prime factorization of $D$. To this end, we note that $D = (3)(3,1-2\sqrt{-5})$ $= (3,1+2\sqrt{-5})(3,1-2\sqrt{-5})^2$ (since $(1+2\sqrt{-5})(1+2\sqrt{-5}) - 2 \cdot 3 \cdot 3 = 3$).

Claim: $(3,1+2\sqrt{-5})$ is proper. Proof of claim: Suppose to the contrary that this ideal contains 1. THen we have $1 = 3(a+b\sqrt{-5}) + (1+2\sqrt{-5})(h+k\sqrt{-5})$, so that $1 = 3a + h - 10k$ and $0 = 3b + 2h + k$. This leads to a contradiction mod 3, so that $(3,1+2\sqrt{-5})$ is proper.

Claim: $(3,1+2\sqrt{-5})$ is maximal. Proof of claim: Let $a+b\sqrt{-5} \in \mathbb{Z}[\sqrt{-5}]$, and say $b = 2b_1 + b_0$ and $a-b_1 = 3a_1 + a_0$ where $b_0 \in \{0,1\}$ and $a_0 \in \{0,1,2\}$. Mod $(3,1+2\sqrt{-5})$, we have $a+b\sqrt{-5} \equiv a_0 + b_0 \sqrt{-5}$. Now $2+\sqrt{-5} \equiv (2+\sqrt{-5}) + (1+2\sqrt{-5})$ $\equiv 3(1+\sqrt{-5}) \equiv 0$ mod $(3,1+2\sqrt{-5})$. Thus $\sqrt{-5} \equiv 1$ and $1+\sqrt{-5} \equiv 2$. In particular, $\mathcal{O}/(3,1+2\sqrt{-5}) = \{ \overline{0}, \overline{1}, \overline{2} \}$. Now $1 \not\equiv 0$ since this ideal is proper, and so also $2 \not\equiv 1$. If $2 \equiv 0$, then $3-2 = 1 \in (3,1+2\sqrt{-5})$, a contradiction. So $\mathcal{O}/(3,1+2\sqrt{-5}) \cong \mathbb{Z}/(3)$ is a field, and thus $(3,1+2\sqrt{-5})$ is maximal.

We can show very similarly that $(3,1-2\sqrt{-5})$ is proper and also maximal. Here we can show that $2-\sqrt{-5} \equiv 0$.

Thus we have the prime factorization of $D$, with distinct factors $P_1 = (3,1+2\sqrt{-5})$ and $P_2 = (3,1-2\sqrt{-5})$. Let $A_1 = P_1P_2$ and $A_2 = P_1^2$. We see that $A_1 = (3)$ and $A_2 = (9,1-4\sqrt{-5})$.

Next we find $\alpha_1 \in A_1$ and $\alpha_2 \in A_2$ such that $((\alpha_1)/A_1, (3,1+2\sqrt{-5})) = ((\alpha_2)/A_2, (3,1-2\sqrt{-5})) = (1)$. By our proof of Theorem 9.2, it suffices to exhibit $\alpha_1 \in A_1 \setminus A_1(3,1+2\sqrt{-5})$, and likewise for $\alpha_2$. Noting that $A_2(3,1-2\sqrt{-5}) = (9,3+6\sqrt{-5})$, we see that $\alpha_1 = 3$ and $\alpha_2 = 1-4\sqrt{-5}$ are such elements. Let $\alpha = \alpha_1 + \alpha_2 = 4-4\sqrt{-5}$. By the proof of Theorem 9.3 in TAN, $(3,1+2\sqrt{-5}) = (9,4-4\sqrt{-5})$.

We can verify this by noting that $3 = 9(-1-4\sqrt{-5}) + (4-4\sqrt{-5})(-7+2\sqrt{-5})$, $1+2\sqrt{-5} = 9(-3-2\sqrt{-5}) + (4-4\sqrt{-5})(-3+2\sqrt{-5})$, $9 = 3 \cdot 3$, and $4-4\sqrt{-5} = 3(-5) + (1+2\sqrt{-5})(-1-2\sqrt{-5})$.

### An equivalent characterization of ideal products

In TAN, we defined the product of (finitely generated) ideals $I = (A)$ and $J = (B)$ to be $I \star J = (ab \ |\ a \in A, b \in B)$. We can also define an ideal product $IJ = \{\sum_T x_iy_i \ |\ T\ \mathrm{finite}, x_i \in I, y_i \in J\}$. Prove that $IJ = I \star J$.

We did this previously.

### (A) is contained in I if and only if A is contained in I

Let $R$ be a commutative ring, let $I \subseteq R$ be an ideal, and let $A \subseteq R$ be a subset. Prove that $(A) \subseteq I$ if and only if $A \subseteq I$.

Certainly if $(A) \subseteq I$ then $A \subseteq I$. Suppose conversely that $A \subseteq I$. Now $(A)$ consists of all finite $R$-linear combinations of elements from $A$. Since $A \subseteq I$ and $I$ is an ideal, $(A) \subseteq I$.

### Show that a given generating set is a basis for an ideal in a quadratic integer ring

Show that $B = \{5+i, 2+3i\}$ is a basis for the ideal $(2+3i)$ in $\mathbb{Z}[i]$.

First we wish to show that $(5+i,2+3i)_\mathbb{Z} = (2+3i)$; the $(\supseteq)$ direction is clear. Now suppose $\zeta = a(5+i) + b(2+3i) = (5a+2b) + (a+3b)i$; note that $\zeta = (2+3i)(a+b-ai) \in (2+3i)$, as desired.

Now suppose we have integers $a,b \in \mathbb{Z}$ such that $(5+1)a + (2+3i)b = 0$. Comparing coefficients, we have $5a+2b = 0$ and $a+3b = 0$. Evidently this system has only the solution $a = b = 0$, so that $B$ is $\mathbb{Z}$-linearly independent. Hence $B$ is a basis for $(2+3i)$.

### A fact about finitely generated field extensions

Let $F$ be a field and let $E$ be an extension of $F$. Suppose $E$ is finitely generated as an $F$-vector space; say by $B = \{b_i\}_{i=1}^n$. ($B$ need not be a basis.) Prove that $E$ is a finite extension of $F$. What can we say about the degree of $E$ over $F$?

Recall that every finite generating set of a vector space contains a basis. Thus there is a subset $B^\prime \subseteq B$ which is a basis for $E$ over $F$. In particular, $E$ has finite dimension as an $F$-vector space. Moreover, the dimension of $E$ (i.e. its degree over $F$) is at most $n$.