Applied Discrete Structures

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

(Concrete) $U=\{-1,1\}$ is a subgroup of $[{\mathbb{R}}^{\ast };\cdot ]\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\text{ is}\text{ an}\text{ 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^{\ast }$ 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^{\ast }$ 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^{\ast }\text{?}$

(Concrete) We can verify that $2\mathbb{Z}\le \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 $(\mathrm{\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}\le \mathbb{Z}\text{.}$ How would this argument change if you were asked to prove that $3\mathbb{Z}\le \mathbb{Z}\text{?}$ or $n\mathbb{Z}\le \mathbb{Z},n\ge 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 $|H\times H|=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\le G$ and $K\le G\text{.}$ Our proof that $H\cap K\le 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\le G\text{,}$ $a\ast b$ must be an element of $H\text{.}$ Similarly, $a\ast b\in K\text{;}$ therefore, $a\ast 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\le G\text{,}$ $a^{-1}\in H\text{.}$ Similarly, $a^{-1}\in K\text{.}$ Hence, by the theorem, $H\cap K\le 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}}^{\ast };\cdot ]\text{,}$ $⟨2⟩=\{2^n:n\in \mathbb{Z}\}=\{\dots ,\frac{1}{16},\frac{1}{8},\frac{1}{4},\frac{1}{2},1,2,4,8,16,\dots \}\text{.}$

In ${\mathbb{Z}}_{15}\text{,}$ $⟨6⟩=\{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 $⟨a⟩\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 $⟨3⟩\text{,}$$⟨9⟩\text{,}$ and $⟨12⟩\text{.}$ This shows that a cyclic subgroup can have different generators.