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

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.