Please Login to access more options.


Today

« October 2016 »

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

From Ben: Here's who we'll have present in class:
  • 39 - John, Josh (two different proofs/ compare and contrast)
  • 39.5 - No one, the solution is right under the problem.
  • 41 - Later
  • 42 - Austin
  • 43 - Logan
  • 44 - Colin
  • 45 - Mckay

Problem 39 (The Span Of A Set Of Integers Is Closed)

Let $S$ be a nonempty set of integers. Prove that $\text{span}(S)$ is closed under integer linear combinations.

Problem 39.5 (Function Composition Is Associative)

Let $f:A\to B$, $g:B\to C$, and $h:C\to D$ be functions. Recall that $g\circ f:A\to C$ is a new function defined by $(g\circ f)(x) = g(f(x))$, i.e. first put $x$ into $f$ to obtain $f(x)$ and then put $f(x)$ into $g$ to obtain $g(f(x))$.

Prove that function composition is associative, i.e. show that $h\circ (g\circ f)=(h\circ g)\circ f$.

Remember, to show that two functions $p:X\to Y$ and $q:V\to W$ are equal, you must show that they (1) have the same domains $X=V$, (2) they have the same codomains $Y=W$, and (3) that $p(x)=q(x)$ for each $x\in X$.

Click to see a solution.

First note that $h\circ (g\circ f)$ and $(h\circ g)\circ f$ have the same domain $A$ and codomain $D$. All we must show now is that $(h\circ (g\circ f))(x)=((h\circ g)\circ f)(x)$ for every $x\in A$. Let $x\in A$. We then compute $$(h\circ (g\circ f))(x) = h((g\circ f)(x)) = h(g(f(x))).$$ We can also compute $$((h\circ g)\circ f)(x) = (h\circ g)(f(x)) = h(g(f(x))).$$ This proves that $(h\circ (g\circ f))(x)=((h\circ g)\circ f)(x)$, as desired.

We've talked about automorphisms of graphs and directed graphs. We can similarly define automorphisms of colored directed graphs.

Definition (Automorphism Of A Colored Directed Graph)

Let $\mathcal{G}=(V,C,A)$ be a colored directed graph, where the vertex set is $V$ and the list of colored arrows is $A$, where each arrow in the list $A$ is assigned a unique color from $C$. An automorphism of a directed colored graph is a permutation $\sigma:V\to V$ of the vertex set such that $(x,y)$ is an arrow colored $c\in C$ if and only if $(\sigma(x),\sigma(y))$ is an arrow colored $c$. In other words, it's a permutation of $H$ that preserves the arrow and color structure of the graph.

A Cayley graph is a colored directed graph. We've drawn many Cayley graphs and noticed that they are highly symmetric. Every point has the same number of arrows leaving (and entering). Any pattern we see at one vertex appears at every other vertex. If you were to stand at any vertex and look outwards, the graph would appear the same from every point. This next problem has you show this. You'll show that if $s$ is one of the permutations used to create arrows, then the map $f_s:H\to H$ defined by $f_s(\sigma)=\sigma\circ s$ is an automorphism of the Cayley graph. Once you've shown that the graph looks the same by following one arrow, you can repeatedly apply this process to show that the graph looks the same by following any sequence of arrows.

Problem 41 (Translating By An Arrow In A Cayley Graph Is An Automorphism)

Let $X$ be a set and let $S$ be a set of permutations of $X$. Let $H=\text{span}(S)$ and let $\mathcal{G}$ be the Cayley graph $(H,S)$, so we know $(x,y)$ is an arrow colored $c_t$ where $t\in S$ if and only if $y=t \circ x$. Pick an element $s\in S$ (one of the elements used to create arrows). Prove that the function $f_s:H\to H$ defined by $f_s(\sigma)=\sigma\circ s$ is an automorphism of the Cayley graph. You must show the following three things:

  1. The function $f_s$ is a permutation. (State the inverse and show it is the inverse.)
  2. If $(x,y)$ is an arrow colored $c_t$, then $(f_s(x),f_s(y))$ is an arrow colored $c_t$. In other words, if $t\circ x=y$, then explain why $t\circ f_s(x) = f_s(y)$.
  3. If $(f_s(x),f_s(y))$ is an arrow colored $c_t$, then $(x,y)$ is an arrow colored $c_t$.
This should look a lot like the problem Permutations Of $U(n)$. If you find yourself using the associative law and inverses quite a bit, then you're doing this correctly. This problem requires that you use inverses and the associative law, as well as read and use definitions, nothing more. Your solutions on this problem should be quite short. Don't let yourself spend more than 15 minutes on this problem. Move on if you need to.
From Ben:

The following two problems are optional. They provide basically a converse to problem 40. We'll not discuss them in class.

Problem (Closed Under Function Composition)

Suppose that $H$ is a set of permutations of $X$. Suppose also that if $\alpha,\beta\in H$, then we must have $\alpha\circ \beta\in H$. Use induction to prove that for every $n\in \mathbb{N}$, if we know $\sigma_1,\sigma_2,\ldots,\sigma_n\in H$, then we must have $$\sigma_1\circ\sigma_2\circ\cdots\circ\sigma_n\in H.$$

In the previous problem we assumed that if $\alpha,\beta\in H$, then we must have $\alpha\circ \beta\in H$. Any time a set $H$ of permutations satisfies this, we say that the set $H$ is closed under composition. Similarly we say that set is closed under taking inverse if $\alpha\in H$ implies $\alpha^{-1}\in H$. We've been saying that a set of permutations is closed (under composition combinations of permutations) when the set contains any composition combination of permutations in the set. This next problems shows a simpler way to prove that a set is closed, and it requires showing only that the set is closed under composition and closed under taking inverses.

Problem (Characterizing Closed Sets Of Permutations)

Let $H$ be a set of permutations of a set $X$. Suppose that $H$ satisifies the following 4 properties.

  1. The identity function $id_X$ is in $H$.
  2. If $\sigma\in H$, then so is $\sigma^{-1}$.
  3. If $\alpha\in H$ and $\beta\in H$, then so is $\alpha\circ \beta\in H$.
  4. If $\alpha,\beta,\gamma\in H$, then we have $\alpha\circ (\beta\circ \gamma) = (\alpha\circ \beta)\circ \gamma$.

Prove that $H$ is closed.

This problem, together with Properties Of Closed Sets Of Permutations, characterizes precisely when a set of permutations is closed. These 4 properties are the beginnings of group theory.
Definition (Binary Operation)

Let $G$ be a set. A binary operation on $G$ is a way of combining two elements of $G$ to obtain a new element in $G$. Formally, we just say that a binary operation $*$ is function $*:G\times G\to G$, and we use the notation $a*b$ to represent the function notation $*(a,b)$.

You've been using binary operations your whole life.

Problem 39 (Binary Operation Introduction)

In which of the following scenarios do we have a binary operation on a set $G$. Justify your answers.

  1. Addition $a+b$ of integers.
  2. Multiplication $A\cdot B$ of 3 by 3 matrices.
  3. The dot product $\vec u\cdot \vec v$ of two dimensional vectors.
  4. The cross product $\vec u\times \vec v$ of three dimensional vectors.
  5. The scalar product $c\cdot \vec v$.
  6. Composition $f\circ g$ of permutations on the same set $X$.
  7. Composition $f\circ g$ of functions from $X$ to $Y$.

Up to this point in the semester, we've been focusing solely on sets of permutations. Every element was a function, which often required keeping track of a bunch of information that wasn't necessary. Spanning a set of permutations gave us closed sets of permutations. We found that there are 4 key properties of a set of closed permutations. Let's now drop the requirement that we have permutations, and instead focus on sets, together with a binary operation, that satisfy these 4 properties. We call a set with these properties a group.

Definition (Group)

Let $G$ be a nonempty set, and let $*$ be a binary operation on $G$, which means for every $x,y\in G$ we have $x*y\in G$ $\textbf{[Closure]}$. The structure $\mathbb{G} = (G,*)$ is called a $\textdef{group}$ if the following hold.

  1. $\textbf{[Associativity]}$ For all $x,y,z\in G$ we have $(x* y)* z = x* (y* z)$.
  2. $\textbf{[Identity]}$ There is an $e\in G$ such that for all $x\in G$ we have $x * e = e* x = x$.
  3. $\textbf{[Inverses]}$ For all $x\in G$ there is a $y\in G$ such that $x* y = y* x = e$.

We usually simply write $G$ when referring to the entire structure $\mathbb{G}=(G,*)$. The element $e$ from the second point is called the $\textdef{identity}$. The element $y$ from the third point is called the $\textdef{inverse}$ of $x$ and is usually denoted $x^{-1}$. One often simply writes $xy$ in place of $x*y$, and for every positive integer $n$, we'll write $x^n$ as shorthand for $x* x* \cdots * x$ ($n$ times).

We've already seen many groups throughout the semester. In the problem Characterizing Closed Sets Of Permutations, we showed that any closed set of permutations is a group. Since the span of any set of permutations is closed, then every time we span a set of permutations, we end up with a group. All of the patterns you have discovered about simple shift permutations, automorphisms of graphs, and more, we will be able to transfer to your understanding of abstract groups. Let's look an example, namely a group of matrices that we used before to encrypt messages.

Problem 40 (General Linear Group Introduction)

We've used matrices mod $5$ to encrypt a simple message. The set of possible 2 by 2 matrices mod $5$ that we can use as an encryption key is an important set in cryptography. It's called a general linear group and written $\text{GL}(2,\mathbb{Z}_5)$. We can generalize this to $m$ by $m$ matrices mod $n$ and write $\text{GL}(m,\mathbb{Z}_n)$, though generally we require that $n$ be a prime. With each of the problems below, a single sentence or two is enough to answer the question.

  1. If we want $A$ to serve as a valid matrix for encryption, what must we require about $A$? One sentence is fine.
  2. If $A\in \text{GL}(2,\mathbb{Z}_5)$, show that $A^{-1}\in \text{GL}(2,\mathbb{Z}_5)$.
  3. If $A\in \text{GL}(2,\mathbb{Z}_5)$ and $B\in \text{GL}(2,\mathbb{Z}_5)$, why is $AB\in \text{GL}(2,\mathbb{Z}_5)$?
  4. Prove that if we know for some integer $k$ that $A_1,A_2,A_3,\ldots,A_k \in \text{GL}(2,\mathbb{Z}_5)$, then we know $A_1A_2A_3\cdots A_k\in \text{GL}(2,\mathbb{Z}_5)$.
  5. Is $\text{GL}(2,\mathbb{Z}_5)$ a group? (Which of the group properties did we not show above? Are they true?)
  6. Do your arguments above hold when considering $\text{GL}(m,\mathbb{Z}_n)$ for every $m,n \in \mathbb{N}$ such that $n\geq 2$? A conjecture with a reasonable justification (not a complete a proof) is fine in this part.
In linear algebra we showed that $\det (AB)=\det(A)\cdot \det(B)$ when working with real numbers (not mod $n$). However, since we've shown that we can perform addition and multiplication either before or after we compute remainders, and the determinant is defined entirely in terms of sums and products, then this fact is true for matrices mod $n$ as well. Similarly, we know that a matrix has an inverse if and only if the determinant is not zero. You may use these facts without proof.

In the definition of a group, it said that there exists an element $e\in G$ such that $ex=xe=e$ for each $x\in G$. It refers to this element as the identity. Could there be two such elements? Similarly, could an element have two inverses? The next problem has you show that the identity and inverses are unique.

Problem 41 (The Identity And Inverses Are Unique)

Suppose that $(G,\cdot)$ is a group.

  1. Prove that the identity of the group is unique.
  2. Prove that if $x\in G$, then the inverse of $x$ is unique.
Your first proof should start something like this.
Suppose $e_1,e_2\in G$ are both identities. This means that for every $x\in G$ we have $x e_1 = e_1 x = x$ and also $x e_2 = e_2 x = x$.

You then need to show why $e_1=e_2$. Your second proof is similar.

Problem 42 (The GCD Theorem Proof)

Prove the GCD Theorem.

Theorem (The GCD Theorem)

Let $a$ and $b$ be nonzero integers. The greatest common divisor of $a$ and $b$ is an integer linear combination of $a$ and $b$, or symbolically we have $\gcd(a,b)\in\text{span}(a,b)$. In addition, the smallest positive integer linear combination of $a$ and $b$ is $\gcd(a,b)$.

Hint: If you intersect $\text{span}(a,b)$ with the natural numbers, then you can apply the well ordering principle to get the smallest positive element $d$ of this intersection. You then just have to show that this smallest positive element $d$ is the greatest common divisor. This requires that you show

  1. that $d$ is a common divisor, and
  2. that $d$ is the greatest common divisor.

Showing that $d$ divides both $a$ and $b$ is the trickiest bit. First, we know that their span is closed. When we use the division algorithm to obtain $a=qd+r$, so in particular $r=a-qd$, show that $r$ is in the span of $a$ and $b$. Once you've done this, you should be able to explain why the remainder must be zero (how large is the remainder in relation to $d$, and what did you define $d$ as?).

We've spent quite a bit of time looking at modular multiplicative inverses and the sets $\mathbb{Z}_n$ and $U(n)$. Let's take a minute and explore an encryption problem that uses these sets.

Definition (Affine Encryption Key)

Suppose we have an alphabet with $n$ letters. Set up a 1-1 correspondence between the letters in your alphabet and the integers 0 to $n-1$. As an example, we could let $n=27$ for the standard alphabet with 26 letters and a space (the 27th letter which we'll number 0), and then use the correspondence in the table below.

 abcdefghijklmnopqrstuvwxyz
01234567891011121314151617181920212223242526

Pick an integer $m\geq n$. Then an affine encryption key is an invertible function \( f:\mathbb{Z}_m \to \mathbb{Z}_m\) defined by $$f(x)=ax+b\pmod {m}$$ for some $a,b\in\mathbb{Z}_m$.

Problem 43 (Affine Encryption Key Introduction)

If we let $m=31$, then we can use the function $f(x)=5x+12\pmod m$ to encrypt the message "save them" by (1) swapping the letters to the numbers (19,1,22,5,0,20,8,5,13) and then (2) applying $f(x)$ to each letter to obtain the encrypted numbers (14, 17, 29, 6, 12, 19, 21, 6, 15).

  1. Find $c,d\in \mathbb{Z}_{31}$ so that the inverse of $f$ is $f^{-1}(x)=cx+d$ where $c,d\in \mathbb{Z}_{31}$.
  2. If instead we let $m=27$, then find the inverses of $f(x)=2x+17\pmod{27}$ or explain why it cannot be done.
  3. Give an example of nonzero $a,b\in \mathbb{Z}_{27}$ so that $f(x)=ax+b\pmod{27}$ is not invertible.

You've been studying groups since you started adding integers back in grade school. Just about every idea we've encountered since the start of the semester has also been a group. Now that we have isolated the key properties that make up a group, we need to become comfortable with showing that sets with a binary operation are groups, i.e. we need to become comfortable with checking the four properties of closure, associativity, identity, and inverses.

Let's practice showing that some sets are groups by showing that $\mathbb{Z}_n$ and $U(n)$ are groups. If we already showed a key fact in a previous problem, feel free to refer to problem by name and state the fact that was proved there. We have already shown most of the reasons why the sets below are groups.

Problem 44 ($\mathbb{Z}_n$ and $U(n)$ are groups)

Show the following. You need to briefly explain why the set together with its binary operation satisfies the definition of a group.

  1. For each $n\geq 1$, the set $\mathbb{Z}_n$ is a group under addition mod $n$.
  2. For each $n\geq 2$, prove that $U(n)$ is a group under multiplication mod $n$.

Try to solve the problems above without looking up the definition of a group.

If you need to, click here to show the definition of a group.

Definition (Group)

Let $G$ be a nonempty set, and let $*$ be a binary operation on $G$, which means for every $x,y\in G$ we have $x*y\in G$ $\textbf{[Closure]}$. The structure $\mathbb{G} = (G,*)$ is called a $\textdef{group}$ if the following hold.

  1. $\textbf{[Associativity]}$ For all $x,y,z\in G$ we have $(x* y)* z = x* (y* z)$.
  2. $\textbf{[Identity]}$ There is an $e\in G$ such that for all $x\in G$ we have $x * e = e* x = x$.
  3. $\textbf{[Inverses]}$ For all $x\in G$ there is a $y\in G$ such that $x* y = y* x = e$.

We usually simply write $G$ when referring to the entire structure $\mathbb{G}=(G,*)$. The element $e$ from the second point is called the $\textdef{identity}$. The element $y$ from the third point is called the $\textdef{inverse}$ of $x$ and is usually denoted $x^{-1}$. One often simply writes $xy$ in place of $x*y$, and for every positive integer $n$, we'll write $x^n$ as shorthand for $x* x* \cdots * x$ ($n$ times).

Because of how we defined groups, anytime we span a collection of permutations of a set $X$ we should get a group. The next problem has you show this. Each question can be answered by referring to things we have already shown. Feel free to look at the pages September 2016 and October 2016 for a list of all the problems we have solved each day. If you have not yet printed the work we are doing, I would suggest that you print a copy for reference as you work on new problems.

Problem 45 (Spans Of Permutations Are Subgroups)

Let $X=\{1,2,3,\ldots,n\}$. Let $S_n$ be the set of all permutations of $X$ (so we know there are $n!$ such permutations).

  1. Show that $S_n$ is a group under function composition $\circ$.
  2. If $H$ is a subset of $S_n$ that is closed (under composition combinations of permutations), prove that $H$ is a group under function composition.
  3. Let $S$ be a nonempty subset of $S_n$. Show that $\text{span}(S)$ is a group under function composition.

In the previous problem, we saw if $S\subseteq S_n$ then $\text{span}(S)$ is a not only just a subset of the group $S_n$, but is itself a group. The operation we use in the smaller group $(\text{span}(S),\circ)$ comes from the operation we used in the larger group $(S_n,\circ)$. Because of this close connection, we call $\text{span}(S)$ a subgroup of $S_n$ and write $\text{span}(S)\leq S_n$. Let's now make a formal definition.

Definition (Subgroup)

Let $(G,\cdot)$ be a group, and let $H$ be a nonempty subset of $G$. Then $H$ is called a $\textdef{subgroup}$ of $G$ if the following hold:

  1. $\textbf{[Closure]}$ for all $h,k\in H$ we have $h\cdot k\in H$, and
  2. $(H,\cdot)$ is a group.

When $H$ is a subgroup of $G$, we write $H\le G$. Any subgroup of $G$ that is not equal to $G$ itself we call a $\textdef{proper subgroup}$. The subset of $G$ consisting of just the identity we call the $\textdef{trivial subgroup}$.

In the proof of problem Characterizing Closed Sets Of Permutations, we did not need to use the first and fourth properties listed to show that the set of permutations $H$ was closed. The next problem replicates this, but now in terms of subgroups instead of in terms of closed sets of permutations.

Problem 46 (The Subgroup Test - Subgroups Are Subsets That Are Closed Under Products And Taking Inverses)

Suppose that $G$ is a
group
Definition (Group)

Let $G$ be a nonempty set, and let $*$ be a binary operation on $G$, which means for every $x,y\in G$ we have $x*y\in G$ $\textbf{[Closure]}$. The structure $\mathbb{G} = (G,*)$ is called a $\textdef{group}$ if the following hold.

  1. $\textbf{[Associativity]}$ For all $x,y,z\in G$ we have $(x* y)* z = x* (y* z)$.
  2. $\textbf{[Identity]}$ There is an $e\in G$ such that for all $x\in G$ we have $x * e = e* x = x$.
  3. $\textbf{[Inverses]}$ For all $x\in G$ there is a $y\in G$ such that $x* y = y* x = e$.

We usually simply write $G$ when referring to the entire structure $\mathbb{G}=(G,*)$. The element $e$ from the second point is called the $\textdef{identity}$. The element $y$ from the third point is called the $\textdef{inverse}$ of $x$ and is usually denoted $x^{-1}$. One often simply writes $xy$ in place of $x*y$, and for every positive integer $n$, we'll write $x^n$ as shorthand for $x* x* \cdots * x$ ($n$ times).

and $H$ is a nonempty subset of $G$ that satisfies the following properites:
  1. If $a,b\in H$, then $ab\in H$. (We say $H$ is closed under the group operation.)
  2. If $a\in H$, then $a^{-1}\in H$. (We say $H$ is closed under taking inverses.)
Prove that $H$ is a
subgroup
Definition (Subgroup)

Let $(G,\cdot)$ be a group, and let $H$ be a nonempty subset of $G$. Then $H$ is called a $\textdef{subgroup}$ of $G$ if the following hold:

  1. $\textbf{[Closure]}$ for all $h,k\in H$ we have $h\cdot k\in H$, and
  2. $(H,\cdot)$ is a group.

When $H$ is a subgroup of $G$, we write $H\le G$. Any subgroup of $G$ that is not equal to $G$ itself we call a $\textdef{proper subgroup}$. The subset of $G$ consisting of just the identity we call the $\textdef{trivial subgroup}$.

of $G$.

The following problem again asks you to make sure you are comfortable with the definitions of a binary operation and a group.

Problem 47 (Can We Use Division To Create A Group)

Let $G=\mathbb{R}$ and $H=\mathbb{R}\setminus \{0\}$.

  1. Show that division $a\div b$ is not a
    binary operation
    Definition (Binary Operation)

    Let $G$ be a set. A binary operation on $G$ is a way of combining two elements of $G$ to obtain a new element in $G$. Formally, we just say that a binary operation $*$ is function $*:G\times G\to G$, and we use the notation $a*b$ to represent the function notation $*(a,b)$.

    on $G$.
  2. Show that division $a\div b$ is a binary operation on $H$.
  3. Since division is a binary operation on $H$, determine if $(H,\div)$ is a
    group
    Definition (Group)

    Let $G$ be a nonempty set, and let $*$ be a binary operation on $G$, which means for every $x,y\in G$ we have $x*y\in G$ $\textbf{[Closure]}$. The structure $\mathbb{G} = (G,*)$ is called a $\textdef{group}$ if the following hold.

    1. $\textbf{[Associativity]}$ For all $x,y,z\in G$ we have $(x* y)* z = x* (y* z)$.
    2. $\textbf{[Identity]}$ There is an $e\in G$ such that for all $x\in G$ we have $x * e = e* x = x$.
    3. $\textbf{[Inverses]}$ For all $x\in G$ there is a $y\in G$ such that $x* y = y* x = e$.

    We usually simply write $G$ when referring to the entire structure $\mathbb{G}=(G,*)$. The element $e$ from the second point is called the $\textdef{identity}$. The element $y$ from the third point is called the $\textdef{inverse}$ of $x$ and is usually denoted $x^{-1}$. One often simply writes $xy$ in place of $x*y$, and for every positive integer $n$, we'll write $x^n$ as shorthand for $x* x* \cdots * x$ ($n$ times).

    .
    • Does $e=1$ satisfy the property of being an identity?
    • If $x\in H$, find an inverse $x^{-1}\in H$ or explain why none exists.
    • Is the operation $\div$ associative?

Just as we spanned sets of permutations, we can span subsets of a group. After defining this, we'll show that spanning a subset of a group always gets you a subgroup of the group. This should be analogous to the fact that spanning a subset of permutations leads to a closed set of permutations.

Definition (The Subgroup Generated By A Subset)

Let $G$ be a group. Suppose that $S$ is a subset of $G$.

  1. A word from the alphabet $S$ is a product of the form $$x=s_1s_2\cdots s_k$$ where for each $i$ either $s_i\in S$ or $s_i^{-1}\in S$.
  2. The subgroup generated by $S$ is the set of words from the alphabet $S$, namely $$\left<S\right> = \{s_1s_2\cdots s_k\mid k\in \mathbb{N} \text{ and either $s_i\in S$ or $s_i^{-1}\in S$ for each } i\in\{1,2,\ldots, k\}\}.$$
  3. If $H=\left<S\right>$, then we say that $H$ is the subgroup generated by $S$, or that $S$ is a generating set for $H$.
  4. If $S=\{a\}$, then we'll write $\left<a\right>$ instead of $\left<\{a\}\right>$. We call $\left<a\right>$ the subgroup generated by $a$.
We'll be using this notation to develop the game of scoring for groups. We'll call the game "Generate/Don't Generate."

We call $\left<S\right>$ the subgroup of $G$ generated by $S$, but we have not yet shown this is in fact a subgroup. The next problem has you verify this, so that we can definitely refer to $\langle S\rangle$ as a subgroup.

Problem 51 (The Subgroup Generated By S Is Actually A Subgroup)

Let $G$ be a group and $S$ be a nonempty subset of $G$. Prove that $\left<S\right>$ is a subgroup of $G$.

Any time you want to show something is a subgroup, the subgroup test (see problem (Subgroups Are Subsets That Are Closed Under Products And Inverses)) will simplify your work. So you just need to show that $\left<S\right>$ is a nonempty subset of $G$ and if $a,b\in \left<S\right>$, then both $ab\in \left<S\right>$ and $a^{-1}\in \left<S\right>$.
Any time you want to show something is a subgroup, the subgroup test (see problem (Subgroups Are Subsets That Are Closed Under Products And Inverses)) will simplify your work.
Definition ($|a|$ and $|G|$ - Order For Elements and Groups)

Let $G$ be a group with identity $e$, and let $g\in G$.

  • The $\textdef{order}$ of $G$, denoted $|G|$, is the cardinality of $G$.
  • The $\textdef{order}$ of $g$, denoted $|g|$, is the smallest positive integer $n$ such that $g^n = e$, if such an $n$ exists. If no such $n$ exists, we say $g$ has infinite order.

For more problems, see AllProblems