Skip to main content
Logo image

Applied Discrete Structures

Section 11.5 Subsystems

Subsection 11.5.1 Definition

The subsystem is a fundamental concept of algebra at the universal level.

Definition 11.5.1. Subsystem.

If \(\left[V; *_1, \ldots ,*_n\right]\) is an algebraic system of a certain kind and \(W\) is a subset of \(V\text{,}\) then \(W\) is a subsystem of \(V\) if \(\left[W; *_1, \ldots ,*_n\right]\) is an algebraic system of the same kind as \(V\text{.}\) The usual notation for “\(W\) is a subsystem of \(V\)” is \(W \leq V\text{.}\)
Since the definition of a subsystem is at the universal level, we can cite examples of the concept of subsystems at both the axiomatic and concrete level.
  1. (Axiomatic) If \([G; *]\) is a group, and \(H\) is a subset of \(G\text{,}\) then \(H\) is a subgroup of \(G\) if \([H; *]\) is a group.
  2. (Concrete) \(U = \{-1,1\}\) is a subgroup of \(\left[\mathbb{R}^*;\cdot \right]\text{.}\) Take the time now to write out the multiplication table of \(U\) and convince yourself that \([U;\cdot ]\) is a group.
  3. (Concrete) The even integers, \(2\mathbb{Z} = \{2k : k \textrm{ is} \textrm{ an} \textrm{ integer}\}\) is a subgroup of \([\mathbb{Z}; +]\text{.}\) Convince yourself of this fact.
  4. (Concrete) The set of nonnegative integers is not a subgroup of \([\mathbb{Z}; +]\text{.}\) All of the group axioms are true for this subset except one: no positive integer has a positive additive inverse. Therefore, the inverse property is not true. Note that every group axiom must be true for a subset to be a subgroup.
  5. (Axiomatic) If \(M\) is a monoid and \(P\) is a subset of \(M\text{,}\) then \(P\) is a submonoid of \(M\) if \(P\) is a monoid.
  6. (Concrete) If \(B^*\) is the set of strings of 0’s and 1’s of length zero or more with the operation of concatenation, then two examples of submonoids of \(B^*\) are: (i) the set of strings of even length, and (ii) the set of strings that contain no 0’s. The set of strings of length less than 50 is not a submonoid because it isn’t closed under concatenation. Why isn’t the set of strings of length 50 or more a submonoid of \(B^*\text{?}\)

Subsection 11.5.2 Subgroups

For the remainder of this section, we will concentrate on the properties of subgroups. The first order of business is to establish a systematic way of determining whether a subset of a group is a subgroup.
Our proof consists of verifying that if the three properties above are true, then all the axioms of a group are true for \([H ; *]\text{.}\) By Condition (a), \(*\) can be considered an operation on \(H\text{.}\) The associative, identity, and inverse properties are the axioms that are needed. The identity and inverse properties are true by conditions (b) and (c), respectively, leaving only the associative property. Since, \([G; *]\) is a group, \(a * (b * c) = (a * b) * c\) for all \(a, b, c \in G\text{.}\) Certainly, if this equation is true for all choices of three elements from \(G\text{,}\) it will be true for all choices of three elements from \(H\text{,}\) since \(H\) is a subset of \(G\text{.}\)
For every group with at least two elements, there are at least two subgroups: they are the whole group and \(\{e\}\text{.}\) Since these two are automatic, they are not considered very interesting and are called the improper subgroups of the group; \(\{e\}\) is sometimes referred to as the trivial subgroup. All other subgroups, if there are any, are called proper subgroups.
We can apply Theorem 11.5.3 at both the concrete and axiomatic levels.
  1. (Concrete) We can verify that \(2\mathbb{Z} \leq \mathbb{Z}\text{,}\) as stated in Example 11.5.2. Whenever you want to discuss a subset, you must find some convenient way of describing its elements. An element of \(2\mathbb{Z}\) can be described as 2 times an integer; that is, \(a \in 2\mathbb{Z}\) is equivalent to \((\exists k)_{\mathbb{Z}}(a = 2k)\text{.}\) Now we can verify that the three conditions of Theorem 11.5.3 are true for 2\(\mathbb{Z}\text{.}\) First, if \(a, b \in 2\mathbb{Z}\text{,}\) then there exist \(j, k \in \mathbb{Z}\) such that \(a = 2j\) and \(b = 2k\text{.}\) A common error is to write something like \(a=2j\) and \(b=2j\text{.}\) This would mean that \(a=b\text{,}\) which is not necessarily true. That is why two different variables are needed to describe \(a\) and \(b\text{.}\) Returning to our proof, we can add \(a\) and \(b\text{:}\) \(a + b = 2j + 2k = 2(j + k)\text{.}\) Since \(j + k\) is an integer, \(a + b\) is an element of \(2\mathbb{Z}\text{.}\) Second, the identity, \(0\text{,}\) belongs to 2\(\mathbb{Z}\) (\(0 = 2(0)\)). Finally, if \(a \in 2\mathbb{Z}\) and \(a = 2k, -a = -(2k) = 2(-k)\text{,}\) and \(-k\in \mathbb{Z}\text{,}\) therefore, \(-a \in 2\mathbb{Z}\text{.}\) By Theorem 11.5.3, \(2\mathbb{Z} \leq \mathbb{Z}\text{.}\) How would this argument change if you were asked to prove that \(3\mathbb{Z} \leq \mathbb{Z}\text{?}\) or \(n \mathbb{Z} \leq \mathbb{Z}, n \geq 2\text{?}\)
  2. (Concrete) We can prove that \(H = \{0, 3, 6, 9\}\) is a subgroup of \(\mathbb{Z}_{12}\text{.}\) First, for each ordered pair \((a, b) \in H \times H\text{,}\) \(a +_{12} b\) is in \(H\text{.}\) This can be checked without too much trouble since \(\left| H \times H\right| = 16\text{.}\) Thus we can conclude that \(H\) is closed under \(+_{12}\text{.}\) Second, \(0\in H\text{.}\) Third, \(-0 = 0\text{,}\) \(-3 = 9\text{,}\) \(-6 = 6\text{,}\) and \(-9 = 3\text{.}\) Therefore, the inverse of each element of \(H\) is in \(H\text{.}\)
  3. (Axiomatic) If \(H\) and \(K\) are both subgroups of a group \(G\text{,}\) then \(H \cap K\) is a subgroup of \(G\text{.}\) To justify this statement, we have no concrete information to work with, only the facts that \(H \leq G\) and \(K \leq G\text{.}\) Our proof that \(H \cap K \leq G\) reflects this and is an exercise in applying the definitions of intersection and subgroup, (i) If \(a\) and \(b\) are elements of \(H \cap K\text{,}\) then \(a\) and \(b\) both belong to \(H\text{,}\) and since \(H \leq G\text{,}\) \(a * b\) must be an element of \(H\text{.}\) Similarly, \(a * b \in K\text{;}\) therefore, \(a * b \in H \cap K\text{.}\) (ii) The identity of \(G\) must belong to both \(H\) and \(K\text{;}\) hence it belongs to \(H \cap K\text{.}\) (iii) If \(a \in H \cap K\text{,}\) then \(a \in H\text{,}\) and since \(H \leq G\text{,}\) \(a^{-1}\in H\text{.}\) Similarly, \(a^{-1}\in K\text{.}\) Hence, by the theorem, \(H \cap K \leq G\text{.}\) Now that this fact has been established, we can apply it to any pair of subgroups of any group. For example, since \(2\mathbb{Z}\) and \(3\mathbb{Z}\) are both subgroups of \([\mathbb{Z};+]\text{,}\) \(2\mathbb{Z} \cap 3\mathbb{Z}\) is also a subgroup of \(\mathbb{Z}\text{.}\) Note that if \(a \in 2\mathbb{Z} \cap 3\mathbb{Z}\text{,}\) \(a\) must have a factor of 3; that is, there exists \(k\in \mathbb{Z}\) such that \(a = 3k\text{.}\) In addition, \(a\) must be even, therefore \(k\) must be even. There exists \(j \in \mathbb{Z}\) such that \(k = 2j\text{,}\) therefore \(a = 3(2j)= 6j\text{.}\) This shows that \(2\mathbb{Z}\cap 3\mathbb{Z}\subseteq 6\mathbb{Z}\text{.}\) The opposite containment can easily be established; therefore, \(2\mathbb{Z} \cap 3\mathbb{Z} = 6\mathbb{Z}\text{.}\)
Given a finite group, we can apply Theorem 11.3.15 to obtain a simpler condition for a subset to be a subgroup.
In this proof, we demonstrate that Conditions (b) and (c) of Theorem 11.5.3 follow from the closure of \(H\) under \(*\text{,}\) which is condition (a) of the theorem. First, select any element of \(H\text{;}\) call it \(\beta\text{.}\) The powers of \(\beta\) : \(\beta ^1\text{,}\) \(\beta ^2\text{,}\) \(\beta^3,\ldots\) are all in \(H\) by the closure property. By Theorem 11.3.15, there exists \(m\text{,}\) \(m\leq \left| G\right|\text{,}\) such that \(\beta ^m = e\text{;}\) hence \(e \in H\text{.}\) To prove that (c) is true, we let \(a\) be any element of \(H\text{.}\) If \(a = e\text{,}\) then \(a^{-1}\) is in \(H\) since \(e^{-1} = e\text{.}\) If \(a\neq e\text{,}\) \(a^q=e\) for some \(q\) between 2 and \(\left| G\right|\) and
\begin{equation*} e = a^q = a ^{q-1} * a \end{equation*}
Therefore, \(a^{-1}= a^{q-1}\) , which belongs to \(H\) since \(q - 1 \geq 1\text{.}\)

Subsection 11.5.3 Sage Note - Applying the condition for a subgroup of a finite group

To determine whether \(H_1= \{0, 5, 10\}\) and \(H_2 = \{0, 4, 8, 12\}\) are subgroups of \(\mathbb{Z}_{15}\text{,}\) we need only write out the addition tables (modulo 15) for these sets. This is easy to do with a bit of Sage code that we include below and then for any modulus and subset, we can generate the body of an addition table. The code is set up for \(H_1\) but can be easily adjusted for \(H_2\text{.}\)
Note that \(H_1\) is a subgroup of \(\mathbb{Z}_{15}\text{.}\) Since the interior of the addition table for \(H_2\) contains elements that are outside of \(H_2\text{,}\) \(H_2\) is not a subgroup of \(\mathbb{Z}_{15}\text{.}\)

Subsection 11.5.4 Cyclic Subgroups

One kind of subgroup that merits special mention due to its simplicity is the cyclic subgroup.

Definition 11.5.6. Cyclic Subgroup.

If \(G\) is a group and \(a \in G\text{,}\) the cyclic subgroup generated by \(a\text{,}\) \(\langle a \rangle\text{,}\) is the set of all powers of \(a\text{:}\)
\begin{equation*} \langle a \rangle = \left\{a^n: n \in \mathbb{Z}\right\}\text{.} \end{equation*}
We refer to \(a\) as a generator of subgroup \(\langle a \rangle\text{.}\)
A subgroup \(H\) of a group \(G\) is cyclic if there exists \(a \in H\) such that \(H = \langle a \rangle\text{.}\)

Definition 11.5.7. Cyclic Group.

A group \(G\) is cyclic if there exists \(\beta \in G\) such that \(\langle \beta \rangle=G\text{.}\)

Note 11.5.8.

If the operation on \(G\) is additive, then \(\langle a \rangle = \{(n)a : n \in \mathbb{Z}\}\text{.}\)

Definition 11.5.9. Order of a Group Element.

The order of an element \(a\) of group \(G\) is the number of elements in the cyclic subgroup of \(G\) generated by \(a\text{.}\) The order of \(a\) is denoted \(ord(a)\text{.}\)
  1. In \([\mathbb{R}^* ; \cdot ]\text{,}\) \(\langle 2 \rangle = \left\{2^n : n \in \mathbb{Z}\right\} = \left\{\ldots ,\frac{1}{16}, \frac{1}{8} ,\frac{1}{4}, \frac{1}{2}, 1, 2, 4, 8, 16,\ldots \right\}\text{.}\)
  2. In \(\mathbb{Z}_{15}\text{,}\) \(\langle 6 \rangle = \{0, 3, 6, 9, 12\}\text{.}\) Here is why: If \(G\) is finite, you need list only the positive powers (or multiples) of \(a\) up to the first occurrence of the identity to obtain all of \(\langle a \rangle\text{.}\) In \(\mathbb{Z}_{15}\) , the multiples of 6 are 6, \((2)6 = 12\text{,}\) \((3)6=3\text{,}\) \((4)6=9\text{,}\) and \((5)6 = 0\text{.}\) Note that \(\{0, 3, 6, 9, 12\}\) is also \(\langle 3 \rangle\text{,}\)\(\langle 9 \rangle\text{,}\) and \(\langle 12 \rangle\text{.}\) This shows that a cyclic subgroup can have different generators.
If you want to list the cyclic subgroups of a group, the following theorem can save you some time.
This is an easy way of seeing, for example, that \(\langle 9 \rangle\) in \(\mathbb{Z}_{15}\) equals \(\langle 6 \rangle\text{,}\) since \(-6 = 9\text{.}\)

Exercises 11.5.5 Exercises

1.

Which of the following subsets of the real numbers is a subgroup of \([\mathbb{R}; +]\text{?}\)
  1. the rational numbers
  2. the positive real numbers
  3. \(\displaystyle \{k/2 \mid k \textrm{ is} \textrm{ an} \textrm{ integer}\}\)
  4. \(\displaystyle \{2^k \mid k \textrm{ is an integer}\}\)
  5. \(\displaystyle \{x \mid -100 \leq x \leq 100\}\)
Answer.
Only a and c are subgroups.

2.

Describe in simpler terms the following subgroups of \(\mathbb{Z}\text{:}\)
  1. \(\displaystyle 5\mathbb{Z} \cap 4\mathbb{Z}\)
  2. \(4\mathbb{Z} \cap 6\mathbb{Z}\) (be careful)
  3. the only finite subgroup of \(\mathbb{Z}\)

3.

Find at least two proper subgroups of \(R_3\) , the set of \(3\times 3\) rook matrices (see Exercise 11.2.4.5).
Answer.
\(\left\{I,R_1,R_2\right\}\text{,}\) \(\left\{I,F_1\right\}\text{,}\) \(\left\{I,F_2\right\}\text{,}\) and \(\left\{I,F_3\right\}\) are all the proper subgroups of \(R_3\text{.}\)

4.

Let \(H\) and \(K\) be subgroups of \(G\) with elements \(a, x, y \in G\) located in the following Venn diagram. Where should you place the following elements in Figure 11.5.12?
  1. \(\displaystyle e\)
  2. \(\displaystyle a^{-1}\)
  3. \(\displaystyle x * y\)
Figure for exercise 4 of Section 11.5 consisting of a Venn diagram with element \(a\) and \(x\) 	in \(H-K\text{,}\) and \(y\) in \(K-H\text{.}\)
Figure 11.5.12. Figure for exercise 4

5.

  1. List the cyclic subgroups of \(\mathbb{Z}_6\) and draw an ordering diagram for the relation “is a subset of” on these subgroups.
  2. Do the same for \(\mathbb{Z}_{12}\text{.}\)
  3. Do the same for \(\mathbb{Z}_8\text{.}\)
  4. On the basis of your results in parts a, b, and c, what would you expect if you did the same with \(\mathbb{Z}_{24}\text{?}\)
Answer.
  1. \(\langle 1\rangle = \langle 5\rangle = \mathbb{Z}_6\text{,}\) \(\quad\)\(\langle 2\rangle = \langle 4\rangle = \{2, 4, 0\}\text{,}\) \(\langle 3\rangle = \{3, 0\}\text{,}\) \(\langle 0\rangle = \{0\}\)
  2. \(\langle 1\rangle = \langle 5\rangle = \langle 7\rangle = \langle 11\rangle =\mathbb{Z}_{12}\text{,}\) \(\langle 2\rangle = \langle 10\rangle = \{2, 4, 6, 8, 10, 0\}\text{,}\) \(\langle 3\rangle = \langle 9\rangle = \{3, 6, 9, 0\}\text{,}\) \(\langle 4\rangle = \langle 8 \rangle = \{ 4 , 8, 0\}\text{,}\) \(\langle 6\rangle = \{6, 0\}\text{,}\) \(\langle 0\rangle = \{0\}\)
  3. \(\langle 1\rangle = \langle 3\rangle = \langle 5 \rangle = \langle 7\rangle = \mathbb{Z}_8\text{,}\) \(\langle 2\rangle = \langle 6\rangle = \{2, 4, 6, 0\}\text{,}\) \(\langle 4\rangle = \{4, 0\}\text{,}\) \(\langle 0\rangle = \{0\}\)
  4. Based on the ordering diagrams for parts a through c in Figure 11.5.13, we would expect to see an ordering diagram similar to the one for divides on \(\{1, 2, 3, 4, 6, 8, 12, 24\}\) (the divisors of 24) if we were to examine the subgroups of \(\mathbb{Z}_{24}\text{.}\) This is indeed the case.
Figure for exercise 5 of Section 11.5
Figure 11.5.13. Figure for exercise 5

6. Subgroups generated by subsets of a group.

The concept of a cyclic subgroup is a special case of the concept that we will discuss here. Let \([G; * ]\) be a group and \(S\) a nonempty subset of \(G\text{.}\) Define the set \(\langle S \rangle\) recursively by:
  • If \(a\in S\text{,}\) then \(a\in \langle S \rangle\text{.}\)
  • If \(a, b \in \langle S \rangle\text{,}\) then \(a * b \in \langle S \rangle\text{,}\) and
  • If \(a \in \langle S \rangle\text{,}\) then \(a^{-1}\in \langle S \rangle\text{.}\)
  1. By its definition, \(\langle S \rangle\) has all of the properties needed to be a subgroup of \(G\text{.}\) The only thing that isn’t obvious is that the identity of \(G\) is in \(\langle S \rangle\text{.}\) Prove that the identity of \(G\) is in \(\langle S \rangle\text{.}\)
  2. What is \(\langle\{9, 15\}\rangle\) in\([\mathbb{Z}; +]\text{?}\)
  3. Prove that if \(H \leq G\) and \(S \subseteq H\text{,}\) then \(\langle S \rangle\leq H\text{.}\) This proves that \(\langle S \rangle\) is contained in every subgroup of \(G\) that contains \(S\text{;}\) that is, \(\langle S \rangle =\underset{S\subseteq H, H\leq G}{\cap }H\text{.}\)
  4. Describe \(\langle \{0.5, 3\}\rangle \) in \(\left[ \mathbb{R}^+;\cdot \right]\) and in \([\mathbb{R}; +]\text{.}\)
  5. If \(j, k \in \mathbb{Z}\text{,}\) \(\langle\{j,k\}\rangle\) is a cyclic subgroup of \(\mathbb{Z}\text{.}\) In terms of \(j\) and \(k\text{,}\) what is a generator of \(\langle \{j, k\}\rangle \text{?}\)

7.

Prove that if \(H,K \leq G\text{,}\) and \(H\cup K=G\text{,}\) then \(H = G\) or \(K = G\text{.}\)
Hint.
Use an indirect argument.
Answer.
Assume that \(H\) and \(K\) are subgroups of group \(G\text{,}\) and that, as in Figure 11.5.12, there are elements \(x \in H - K\) and \(y \in K - H\text{.}\) Consider the product \(x * y\text{.}\) Where could it be placed in the Venn diagram? If we can prove that it must lie in the outer region, \(H^c \cap K^c=(H \cup K)^c\text{,}\) then we have proven that \(H \cup K\) is not closed under \(*\) and cannot be a subgroup of \(G\text{,}\) Assume that \(x*y\in H\text{.}\) Since \(x\) is in \(H\text{,}\) \(x^{-1}\) is in \(H\) and so by closure \(x^{-1}*(x * y )= y \in H\) which is a contradiction. Similarly, \(x*y \notin K\text{.}\)
One way to interpret this theorem is that no group is the union of two groups.

8.

Prove that the order of an element, \(a\) of a group is the least positive integer, \(k\text{,}\) such that \(a^k\) is the identity of the group.