Discrete Mathematics for Computer Science

(Axiomatic) If \([G; \bullet ]\) is a group, and \(H\) is a subset of \(G\text{,}\) then \(H\) is a subgroup of \(G\) if \([H; \bullet ]\) is a group.

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

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

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

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

(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{?}\)

(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{?}\)

(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{.}\)

(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 \bullet b\) must be an element of \(H\text{.}\) Similarly, \(a \bullet b \in K\text{;}\) therefore, \(a \bullet 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{.}\)

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{.}\)

In \(\mathbb{Z}_{15}\text{,}\) \(\langle 6 \rangle = \{0, 3, 6, 9, 12\}\text{.}\) 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.