Midterm

W1D1: Jan. 3rd, 2022

Discussed Chapter 1 (literally).

• 16th - 18th century math competitions

• looking to solve polynomials

• cant solve polynomial greater than 5

• we will see groups of permutations in chapter 7

• don’t do Galois thoery in this course (is in 345 and at the end of the book)

  • fun but hard

We are going to prove things with only three rules (in the beginning).

Appendix A - Set Theory

A set is an un-ordered collection of objects. The objects are called elements.

• set of students , set of real numbers

We use capital letters (A,B, …,G, H, K,…) for sets.

• call group G, and more than one group G, H, K

We use lover case for elements.

If \(x\) is an elements of A, we write \(x\in A\).

• this is read “x is an element of A” or “x is in A”

• \(x\notin A\), x is not an element of A

Ex : Let \(A = \{1,4,3,5\}\). Then \(3\in A\), but \(b\notin A\).

• culry brackets indicate that order doesn’t matter.

Ex : Let B be the set of letters of the alphabet. Then the elements \(B=\{a,b,c,...,x,y,z\}\).

Common examples of sets

1. The empty set \(\emptyset=\{\}\).

2. The natural numebrs \(\mathbb{N}=\{1,2,3,...\}\)

3. The integers \(\mathbb{Z}=\{...-3,-2,-1,0,1,2,3,...\}\)

• Number Theory deal a lot with integers

4. The rational numbers \(\mathbb{Q}=\{\frac{m}{n}|m,n\in\mathbb{Z}\text{ and }n\ne0\}\).

• set builder notation, tell the elements and what restrictions on those elements

• could “;” instead of “|”

• bar read “such that”

5. The set of real numbers \(\mathbb{R}\)

6. The complex numbers \(\mathbb{C}=\{a+bi|a,b\in\mathbb{R}\text{ and }i^2=-1\}\)

• wont be on test, but are good for showing examples in class

Placing an asterisk in the superscript means delete zero : \(\mathbb{R}^*=\{x\in\mathbb{R}|x\ne 0\}\).

Placing a + in the superscript means the set only contains \(\mathbb{R}^+=\{x\in\mathbb{R}|x>0\}\).

W1D2: Jan. 5th, 2022

Definitions

1. A set B is a subset of A, denoted \(B\subseteq A\), if every element of B is an element of B is an element of A.

• Ex: \(\mathbb{Z\subseteq Q}\) and \(\mathbb{Q\subseteq R}\)

2. The union of two sets A and B, denoted \(A\cup B\), is the \[A\cup B=\{x|x\in A\text{ or } x\in B\text{ or both}\}\]

3. The intersection of A and B, denoted \(A\cap B\), is the set \[A\cap B=\{x|x\in A \text{ and } x\in B\}\]

4. The Cartesian product of A and B, denoted \(A\times B\), is the set \[A\times B=\{(a,b)|a\in A \text{ and } b\in B\}\]

• Ex : Let \(A=\{1,2\}\) and \(B=\{2,3,4\}\), then \[A\times B=\{(1,2),(1,3),(1,4),(2,2),(2,3),(2,4)\}\]

Other notations

1. \(\Rightarrow\) means “implies”

• Ex : \(x=2\Rightarrow x^2=4\)

2. \(\Leftrightarrow\) means “if and only if”

• Ex : \(x=\pm 2\Leftrightarrow x^2=4\)

• The statements on either side of \(\Leftrightarrow\) are equivalents.

\(\square\) : means end of proof (so does Q.E.D.)

\(\forall\) : means for all

\(\exists\) : means there exists

s.t. : such that

w.r.t. : with respect to

WLOG : without loss of generality

TFAE : the following are equivalent

Operations

An operation * on a set A is a rule which assigns to each ordered pair (a,b) of elements of A exactly one element \(a*b\) of A.

• needs to work for each ordered pair.

• output comes from the same set we started with, A.

Common Examples (and nonexamples) :

1. • is an operation on \(\mathbb{Z,Q,R,C}\)
2. • isn’t an operation on \(\mathbb{R}*\), because 1, \(-1\in \mathbb{R}*\) but \(1+(-1)=0\notin\mathbb{R}^*\)

3. \(\cdot\) is an operation on \(\mathbb{Z, Q, R, R^*}\), ect.

4. • is not an operation on \(\mathbb{N}=\{1,2,3,4,...\}\) since \(2,5\in\mathbb{N}\) but \(2-5=-3\notin\mathbb{N}\)

5. \(\div\) is not an operation on \(\mathbb{Z}\), since \(0\in\mathbb{Z}\) and we can’t divide by sero.

6. Matrix addition and multiplication are operations on the set of \(2\times 2\) matrices with real entries.

7. Compositions is an operation on sets of functions.

Operation Tables

Suppose * is an operation on \(A=\{a,b,c\}\).

• Ex : Let \(A=\{0,1,2\}\). Define an operation + on A, called addition mod 3, as follows :

To compute \(1+2\), start at 1 on the circle and move 2 spaces clockwise.

So, \(1+2=0\) in A. Similarly \(2+2=1\) in A. Another way to think about this ”

In the integers \(2+2=4\), and 4 is 1 more than 3.

Here’s the operation table:

Notice the table has the property that every element of A appears exactly once in each row and column.

• Sudoku property

Properties of Opertations

Let \(*\) be an operation on a set A.

1. \(*\) is commutative if \(a\ne b=b\ne a\forall a,b\in A\).

Ex :

1. \(+\) and \(\cdot\) of numbers are commutative operations.

2. matrix multiplication is \(\underline{\text{not}}\) commutative :

\[(\begin{smallmatrix} 1 & 1 \\ 1 & 0\end{smallmatrix})(\begin{smallmatrix} 1 & 1 \\ 0 & 1\end{smallmatrix})\ne(\begin{smallmatrix} 1 & 1 \\ 0 & 1\end{smallmatrix})(\begin{smallmatrix} 1 & 1 \\ 1 & 0\end{smallmatrix})\]

3. \(-\) and \(\div\) are \(\underline{\text{not}}\) commutative :

\[1-2\ne 2-1\quad\text{and}\quad\frac{1}{2}\ne\frac{2}{1}\]

4. function composition \(\underline{\text{isn't}}\) commutative :

Let \(f(x)=x^2\) and \(g(x)=x+1\).

Then \((f\circ g)(x)=f(g(x))=(x+1)^2\), but \((g\circ f)(x)=g(f(x))=x^2+1\).

W1D3: Jan. 7th, 2022

Ch. 2 - Operations, Cont.

Let A be a set. An \(\underline{\text{operation}}\) * on A is a rule which assigns to each ordered pair of elements of A exactly one element \(a*b\in A\).

Remarks :

1. a*b must be defined for every choice of \(a,b\in A\).

2. For each choice of a and b in A, \(a*b\) can only equal one element. (We can’t have something like \(a*b=\pm 3\).)

3. For each choice of a and b in A, a*b must also be in the set A.

Properties of Operations

1. We say * is \(\underline{\text{commutative}}\) if \(a*b=b*a\) for all \(a,b\in A\)

2. We say * is \(\underline{\text{associative}}\) if \((a*b)*c=a*(b*c)\forall a,b,c\in A\).

Examples :

• \(+\) is associative.

• Multiplication of numbers and square matrices are associative perations.

• Subtraction of numbers \(\underline{\text{isn't}}\) associative :

  • \((1-2)-3=-1-3=-4\)

  • \(1-(2-3)=1-(-1)=2\)

  • NOT EQUAL !!

3. If there exists \(e\in A\) such that \(e*a=a*e=a\) for all \(a\in A\) we call e the \(\underline{\text{identity element}}\) in A with respect to *.

Examples :

• zero is the identity w.r.t addition.

• \(1\in \mathbb{R}\) is the identy w.r.t. multiplication of numebrs

• zero isn’t the identity w.r.t. subtraction, since 0-b=-b instead of b.

4. If \(e\in A\) is the identity w.r.t. * and \(a,b\in A\) are such that \[a*b=b*a=e\], we call a and b \(\underline{\text{inverses}}\) of one another.

\(\underline{\text{Notation: }}\) \(a=b^{-1}\quad\) and \(b=a^{-1}\)

Examples :

• The inverese of \(a\in \mathbb{R}\) w.r.t. + and -a, since \(a+(-a)=(-a)+a=0\).

• The inverse of \(a\in \mathbb{R}^*\) w.r.t. multiplication is \(\frac{1}{a}\) since \[a\cdot\frac{1}{a}=\frac{1}{a}\cdot a=1\]

Example 1: (Similar to #2, 3 on HW 1)

Define * on \(\mathbb{R}\) by \(a*b=a+2b+4\).

• “First # plus two times the second # plus 4”

For example, \(3*7=3+2\cdot 7+4=21\) and \(7*3=7+2\cdot3+4=17\)

1. Since \(3*7\ne7*3\), the operation * is not commutative.

2. Is * associative?

\[\begin{equation} \label{d3 b1} \begin{split} (a*b)*c &= (a+2b+4)*c\\ &=a+2b+4+2c+4\\ &=a+2b+2c+8 \end{split} \end{equation}\]

• think of (a+2b+4) is first # and c is the 2nd #

\[\begin{equation} \label{d3 b2} \begin{split} a*(b*c) &= a*(b+2c+4)\\ &=a+2(b+2c+4)+4\\ &=a+2b+4c+12 \end{split} \end{equation}\]

Since \((a*b)*c\ne a*(b*c)\), * isn’t associative.

3. Is there an identity \(e\in\mathbb{R}\) wrt *?

The process : Pretend \(e\in\mathbb{R}\) exists. This means \(e*a=a\forall a\in\mathbb{R}\).

Rewrite this equation, then solve for e. If we find a solution for \(e\in\mathbb{R}\), check if \[e*a=a\]

If so, then this value of e is the identity. If not, there is no identity.

\[\begin{equation} \label{d3 c} \begin{split} e*a = a &\Rightarrow a+2e+4=a\\ &\Rightarrow 2e+4=0\\ &\Rightarrow e=-2 \end{split} \end{equation}\]

“When solving for e, the answer must be a constant element of the set, i.e. Can’t involve variables.”

Check other order:

\[e*a=-2*a=-2+2a+4=2a+2\]

Since \(-2*a\ne a\), then no there is no identity in \(\mathbb{R}\) w.r.t. *.

Example 2:

Define * on \(\mathbb{R}\) by \(a*b=a+b+ab\)

1. Show that * is commutative :

\[\begin{equation} \label{d3 2a} \begin{split} a*b &= a+b+ab\\ &= b+a+ab\quad\text{ since + is commutative}\\ &= b+a+ba\quad\text{since }\cdot\text{ is commutative}\\ &= b*a \end{split} \end{equation}\]

2. skip associativity for time

3. Is there an identity w.r.t. *? Yes, lets show \(0\in\mathbb{R}\) is the identity: \(a*0=a+0+a\cdot 0=a\)

Why must it be true that \(0*a=a\) as well? We already showed * is commutative.

4. Which elements \(a\in\mathbb{R}\) have inverses w.r.t. *?

Process :

Suppose \(b=a^{-1}\). Then \(a*b=0\). (Identity found in part (c))

Try to solve this equation for b.

Once we solve for b, check if \(b*a=0\) as well.

\[\begin{equation} \label{d3 2c} \begin{split} a*b=0 &\Rightarrow a+b+ab=0\\ &\Rightarrow b(1+a)=-a\\ &\Rightarrow b =\frac{-a}{1+a} \end{split} \end{equation}\]

So every \(a\in\mathbb{R}\) except -1 has an inverse given by \[a^{-1}=\frac{-a}{1+a}\].

Note: We didn’t need to check that when \(\frac{-a}{1+a}\), \(b*a=0\) as well, since we know * is commutative.

W2D4: Jan. 10th, 2022

Ch.3 - The Definition of a Group

Let G be a set and * an operation on G. Suppose

1. * is associative (i.e. \((a*b)*c=a*(b*c))\forall a,b,c\in G\).

2. There is an identity element \(e\in G\). (Recall, \(e*a=a*e=a\forall a\in G\))

3. Every element \(a\in G\) has an inverse \(a^{-1}\in G\). (Recall, \(a*a^{-1}=a^{-1}*a=e\).)

Then we call \(\langle G,*\rangle\) a \(\underline{\text{group}}\).

If, in addition, * is commutative we call \(\langle G,*\rangle\) an \(\underline{\text{abelian group}}\).

Examples of Infinite Groups (and nonexamples)

1. \(\langle \mathbb{Z},+\rangle\) , \(\langle\mathbb{Q},+\rangle\), and \(\langle\mathbb{R},+\rangle\) are abelian groups (the identity is e=0 [addititve identity] and the inverse of a is \(-a\) [additive inverse or negative]

2. \(\langle\mathbb{Z},\cdot\rangle\) isn’t a group since \(2\in\mathbb{Z}\) but the multiplicative inverse of 2, which is \(\frac{1}{2}\), isn’t in \(\mathbb{Z}\).

3. \(\langle \mathbb{N},+\rangle\) isn’t a group since the additive identity, 0, isn’t in \(\mathbb{N}\).

4. \(\langle\mathbb{Q}^*,\cdot\rangle\), \(\langle\mathbb{R}^*,\cdot\rangle\), \(\langle\mathbb{Q}^+,\cdot\rangle\), \(\langle\mathbb{R}^+,\cdot\rangle\) are abelian grops. (the identity is e=1 and the inverse of a is \(\frac{1}{a}\))

---

We call a group \(\langle G,*\rangle\) a \(\underline{\text{finite group}}\) if \(|G|<\infty\), i.e. the # of elements in G is finite. We call \(|G|\) the \(\underline{\text{order}}\) (size) of G.

Examples of finite group:

Define \(\mathbb{Z}_6=\{0,1,2,3,4,5\}\), called the \(\underline{\text{integers mod 6}}\).

Define an operation +, called addition mod 6 as follows :

To Compute \(4+5\): start at 4 and move 5 spaces clockwise. So in \(\mathbb{Z}_6\)

\[4+5=3\]

• note : we can also think that \(4+5=9-6=3\).

The identity element in \(\mathbb{Z}_6\) is zero. What’s the inverse of 4 in \(\mathbb{Z}\)?

Think of it this way: what needs to be added to 4 to get 0?

In \(\mathbb{Z}\), \(4+2=0\), so 2 is the inverse of 4.

---

For any \(n\geq 2\), define \(\mathbb{Z}_n=\{0,1,2,3,...,n-1\}\). With addition mod n this forms a finite abelian group.

The inverse of 0 is 0. For any nonzero \(a\in\mathbb{Z}_n\), the inverse of a is \(n-a\), since in \(\mathbb{Z}_n\)

\[a+(n-a)=0\]

Ex: In \(\mathbb{Z}_8\), 7+5=4 (since 12 is 4 more than 8 in \(\mathbb{Z}\)).

HW 1 #4

Let \(G=\{(x,y)\in\mathbb{R}\times\mathbb{R}|x\ne0\}\). Define * on G by \[(a,b)*(c,d)=(ac,ad+bc)\]

In this problem, show \(\langle G,*\rangle\) is an abelian group.

For example,

\((1,3)*(5,2)=(1\cdot 5, 1\cdot 2+3\cdot 5)=(5,17)\).

“Look at Ch. 3 B for similar problems.”

Lets show * is associative :

\[\begin{equation} \label{d4e1} \begin{split} ((a,b)*(c,d))*(f,g) &= (ac,ad+bc)*(f,g)\\ &= (acf,acg+(ad+bc)f)\\ &= (acf, acg+adf+bcf) \end{split} \end{equation}\]

\[\begin{equation} \label{d4e2} \begin{split} (a,b)*((c,d)*(f,g)) &= (a,b)*(af,cg+df)\\ &= (acf,a(cg+df)+bcf)\\ &= (acf, acg+adf+bcf) \end{split} \end{equation}\]

Identity : Solve \((a,b)*(e_1,e_2)=(a,b)\) for \(e_1,e_2\in\mathbb{R}\).

• \(e_1\) and \(e_2\) are the identities

Examples of nonabelian group

The \(\underline{\text{dihedral group}}\) of degree 3, \(D_3\), is the group of symmetries of an equilateral triangle.

The group has 6 elements : \(D_3=\{1,r,r^2,s,sr,sr^2\}\) , where, for example sr means rotate first then reflect. (Why are we going right to left? We will view this group’s operation as function composition starting in Ch. 7.)

• 6 is the smallest size nonabelian, dihedral group

Why isn’t \(r^3\) in the set? We consider \(r^3=1\) since the triangle looks the same after \(360^o\) rotation. Similarly, \(s^2=1\).

To see that \(D_3\) is nonabelian, check that \(sr\ne rs\).

Before Wednesday, consider rs using triangles.

• rs : the operation goes right to left, so rs means reflect first then rotate.

W2D5: Jan. 12th, 2022

Let G be a set and * be an operation on G. We call \(\langle G,*\rangle\) a \(\underline{\text{group}}\) if

1. * is associative

2. $$ identity element \(e\in G\).

3. \(\forall\) elements \(a\in G\) has an inverse \(a^{-1}\in G\).

\(\underline{\text{Comment on notation:}}\) We’ll write G instead of \(\langle G, *\rangle\) when there is no confusion about what the operation * is.

Ch.4 - Properties of Groups

Proposition 1

Let G be a group. Then G has exactly one identity element.

\(\underline{\text{Proof}}\): Suppose \(e_1,e_2\in G\) are identity elements.

Since \(e\in G\) is an identity, \[e_1*e_2=e_2.\]

Similarly, since \(e_2\in G\) is an identity, \[e_1*e_2=e_1.\]

Combining, we get \[e_2=e_1*e_2=e_1\quad\Rightarrow\quad e_2=e_1.\]

So, G has exactly one identity element. \(\square\)

Proposition 2

Every element of G has exactly one inverse.

\(\underline{\text{Proof:}}\) Let \(a\in G\). Suppose \(b_1,b_2\in G\) are inverses of a. By definition \[b_1*(a*b_2)=b_1*e=b_1.\]

Similarly, \[(b_1*a)*b_2=e*b_2=b_2\]

By associativity, \(b_1*(a*b_2)=(b_1*a)*b_2\), implying \(b_1=b_2\). Hence, the element \(a\in G\) has exactly one inverse in G. Since \(a\in G\) was arbitrary, every element of G has exactly one inverse. \(\square\).

\(\underline{\text{Comment about notation:}}\) In arbitrary groups, we’ll write ab instead of \(a*b\). We’ll call ab the \(\underline{\text{product}}\) of a and b in G (even if the operation isn’t multiplication).

• “can’t assume inverse”

Theorem 1 (Cancellation Law)

Let G be a group and let \(a,b,c\in G\) Then

1. \(ab=ac\quad\Rightarrow\quad b=c\)

2. \(ba=ca\quad\Rightarrow\quad b=c\)

\(\underline{\text{Warning}}\) In an arbitrary group, \(ab=ca\) doesn’t imply that \(b=c\).

\(\underline{\text{Ex}}\) : Recall \(D_3=\{1,r,r^2,s,sr,sr^2\}\) is the group of symmetries of an equilateral triangle.

In \(D_3\), you can show that \(sr=r^2s\). However, \(r\ne r^2\). So, we can’t cancel the s’s in the equation \(sr=r^2s\).

Proof of part (iii) of the Cacellation Theorem

Assume that \(ba=ca\). We know the element \(a\in G\) has an inverse \(a^{-1}\in G\). Let’s “multiply” by \(a^{-1}\) on the right:

\[\begin{equation} \label{cancellation (iii)} \begin{split} ba=ca &\Rightarrow (ba)a^{-1}=(ca)a^{-1}\\ &\Rightarrow b(aa^{-1})=c(aa^{-1})\text{ ,by associativity}\\ &\Rightarrow be=ce\quad\text{, since }aa^{-1}=e\\ &\Rightarrow b=c \end{split} \end{equation}\]

\(\underline{\text{Ex}}\): Let G be a group and let \(a,b,c,x\in G\). Solve the following for x:

\[\begin{equation} \label{d5e solve for x} \begin{split} x^2b=xa^{-1}c &\Rightarrow xxb=xa^{-1}c\\ &\Rightarrow xb=a^{-1}c\quad\text{by left cancellation}\\ &\Rightarrow xbb^{-1}=a^{-1}cb^{-1}\\ &\Rightarrow x=a^{-1}cb^{-1} \end{split} \end{equation}\]

Note: HW problem about division, “the side matters”

\(\underline{\text{Ex}}\): Solve this system of equations for x: \(ax^2=b\) and \(x^3=e\)

\[\begin{equation} \label{d5e solve soe} \begin{split} ax^2=b &\Rightarrow ax^2x=bx\\ &\Rightarrow ax^3=bx\\ &\Rightarrow ae=bx\text{ , since }x^3=e\\ &\Rightarrow a=bx\text{ , since }e\text{ is the identity}\\ &\Rightarrow b^{-1}a=b^{-1}bx\\ &\Rightarrow x=b^{-1}a \end{split} \end{equation}\]

Theorem 2

Let G be a group and let \(a,b\in G\). If \(ab=e\), then a and b are inverses, i.e. \(a=b^{-1}\) and \(b=a^{-1}\).

(Note: we don’t ahve to check if \(ba=e\) as well.)

\(\underline{\text{Proof:}}\) Suppose \(ab=e\). Let’s show that \(a=b^{-1}\).

\[\begin{equation} \label{T2 Proof} \begin{split} ab=e &\Rightarrow ab=b^{-1}b\text{ , since }b^{-1}b=e\\ &\Rightarrow a=b^{-1} \end{split} \end{equation}\]

When solving equations or simplifying expressions in an arbitrary group, we can:

1. use left or right cancellation

2. “Multiply” both sides of an equation by the same element, as long as we’re consistent with placing the element on the left or right.

3. Take the inverse of both sides of an equation.

Theorem 3

Let G be a group and let \(a,b\in G\).

1. (Socks and Shoes) \[(ab)^{-1}=b^{-1}a^{-1}\]

2. \((a^{-1})^{-1}=a\)

\(\underline{\text{Proof:}}\)

1. We want to show that \(ab\) and \(b^{-1}a^{-1}\) are inverses of one another. By Theorem 2, we just need to show their product is e:

\[\begin{equation} \label{T3 Proof} \begin{split} (ab)(b^{-1}a^{-1})&=a(bb^{-1})a^{-1}\text{ , by associativity}\\ &= aea^{-1} \quad\text{, since }bb^{-1}=e\\ &= aa^{-1}\quad\text{, since }ae=a\\ &= e\quad\text{, since } aa^{-1}. \end{split} \end{equation}\]

So, by Theorem 2, \(ab\) and \(b^{-1}a^{-1}\) are inverses, i.e. \[(ab)^{-1}=b^{-1}a^{-1}.\]

2. We want to show that the inverse of \(a^{-1}\) is a. By Theorem 2, we just need to consider their product:

\[a^{-1}a=e\quad\Rightarrow\quad(a^{-1})^{-1}=a.\quad\quad\quad\quad\quad\square\]

\(\underline{\text{Note: }}(abc)^{-1}=c^{-1}b^{-1}a^{-1}\) and \((abcd)^{-1}=d^{-1}c^{-1}b^{-1}a^{-1}\), ect.

W2D6: Jan. 14th, 2022

Reminder : PSU closed Monday 1/17, so there’s no class

Homework 2 will be posted over the weekend.

Ch 4. Continued

Let G be a finite group.

\(\underline{\text{Fact}}\): Every row and column of G’s operation table contains each element of G exactly once.

Let \(x,g\in G\). Show that g appears in the row for the element x.

• “x times what will be equal to g?”

Now lets show g can’t appear twice in x’s row:

This contradicts the way we make operation tables. (We list each element above the table only once.) So g appears only once in x’s row.

Examples

\(\underline{\text{Ex}}\): Consider \(\mathbb{Z}_4=\{0,1,2,3\}\), with addition mod 4.

\(\underline{\text{Ex}}\): Let \(G=\{e,a,b,c\}\) be a group of size 4 such that \[a^2=b^2=c^2=e.\]

(This group is called the Klein 4 Group)

There is only one way to fill out the operation table :

Direct Product of Groups (Ch 4 G Problems)

Let \(\langle G,*_G\rangle\) and \(\langle H,*_H\rangle\) be groups. The \(\underline{\text{direct product}}\) of G and H is the set \[G\times H=\{(g,h)|g\in G\text{ and } h\in H\}\]

with operation \[(g_1,h)(g_2,h_2)=(g_1*_Gg_2,h_1*_Hh_2)=\underline{(g_1g_2,h_1h_2)}\quad\leftarrow\text{ simplifying notation}\]

Identity in \(G\times H\): \(e_G,e_H\)

Inverses in \(G\times H\): \((g,h)^{-1}=(g^{-1},h^{-1})\)

Examples

\(\underline{\text{Ex}}\): List the elements of \(\mathbb{Z}_2\times\mathbb{Z}_3\).

\[\mathbb{Z}_2\times\mathbb{Z}_3=\{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)\}\]

In this group : \((1,1)+(1,1)=(1+1,1+1)=(0,2)\)

and the invese of \((1,1)\) is \((1,2)\), since \((1,1)+(1+2)=(0,0)\).

\(\underline{\text{Ex}}\): Another group size 4 : \(\mathbb{Z}_2\times \mathbb{Z}_2=\{(0,0),(0,1),(0,2),(1,0), (1,1), (1,2),(2,0),(2,1),(2,2)\}\)

This group has the property that any element added to itself is the idenity : \[(0,1)+(0,1)=(0+0,1+1)=(0,0)\]

\(\underline{\text{Ex}}\): This group has the property that any element added to itself is the identity:

For example, \((0,1)+(0,1)=(0+0,1+1)=(0,0)\)

Ch.5 - Subgroups

Let G be a group. A subset \(H\subseteq G\) is called a \(\underline{\text{subgroup}}\) of G if :

1. \(e\in H\) (Note : e is the identity from the group G.)

2. For all \(a,b\in H\) , \(ab \in H\) (We say H is closed under the operation)

3. For all \(a\in H\) , \(a^{-1}\in H\). (We say H is closed under inverses)

Note: If H is a subgroup of G, H and G must have the same operation.

What does this definition look like if the operation is +?

1. \(0\in H\)

2. \(\forall a,b\in H\) , \(a+b\in H\).

3. \(\forall a\in H\) , \(-a\in H\).

Ex: Subgroups of \(\langle\mathbb{Z},+\rangle\)

1. Why isn’t \(\mathbb{Z}_4\) a subgroup of \(\mathbb{Z}\)? These groups have different operations (addition vs. addition mod 4).

2. \(\{0\}\) is called a trivial subgroup of \(\mathbb{Z}\).

3. \(\emptyset=\{\}\) isn’t a subgroup because it doesn’t contain the identity.

4. The even integers \(2\mathbb{Z}=\{...,-4,-2,0,2,4,6,...\}\) are a subgroup of \(\mathbb{Z}\).

Proof :

1. \(0\in 2\mathbb{Z}\) because \(0=2\cdot0\)

2. Let \(a,b\in\mathbb{Z}\). Then \(a=2m\) and \(b=2n\), for some \(m,n\in\mathbb{Z}\). So, \[a+b=2m+2n=2(m+n)\in2\mathbb{Z}\], since \(m+n\in\mathbb{Z}\). Therefore \(2\mathbb{Z}\) is colsed under +.

3. Let \(a\in\mathbb{Z}\). Then \(a=2m\) for some \(m\in\mathbb{Z}\). So, \[-a=-2m=2(-m)\in2\mathbb{Z}\quad\quad \square\]

5. For any fixed integer \(k\in\mathbb{Z}\), \[k\mathbb{Z}=\{...,-2k,-k,0,k,2k,3k,...\}\] is a subgroup of \(\mathbb{Z}\).

Example

Show \(H=\{0,3,6,9\}\) is a subgroup of \(\mathbb{Z}_{12}\) (with the operation of addition mod 12).

Make the operation table for H :

Note : we don’t know if H is a group yet, so we can’t use sudoku property (hence green writing).

2. H is closed under + since all elements in the table are in H.

3. Since every row and column contains zero, H is closed under inverses. (For example, the highlighted row and column above show that the inverse of 9 in H is 3. )

W3D7: Jan. 19th, 2022

Ch. 5 Continued

Let G be a group. We call a subset \(h\subseteq G\) a \(\underline{\text{subgroup}}\) of G if

1. the identity of e is in H

2. for all \(a,b\in H\) , \(ab\in H\)

3. for all \(a\in H\) , \(a^{-1}\in H\)

\(\underline{\text{Note:}}\) If H is a subgroup of G. H and G have the same operation.

• don’t have to check associativity because it is assumed becasue G is a group.

\(\underline{\text{Notation:}}\) \(H\leq G\)

Example: not a subgroup

Let \(G=\mathbb{Z}_5=\{0,1,2,3,4\}\). Why isn’t \(H=\{0,2,4\}\) a subgroup of G?

One reason : \(2,4\in H\) , but \(2+4=1\in H\) (we’er using the operation from \(\mathbb{Z}\)’s).

Another reason : \(4\in H\) , but the inverse of 4 in \(\mathbb{Z}\)’s (which is 1) isn’t in H.

Example: cyclic subgroup

Subgroups of \(\langle\mathbb{R}^*,\cdot\rangle\)

One way we can generate subgroups of \(\mathbb{R}^*\) is to take a fixed element, say 7, and form the \(\underline{\text{cyclic subgroup}}\) generated by 7: \[\langle 7\rangle=\{...,\frac{1}{7^3},\frac{1}{7^2},\frac{1}{7},1,7,7^2,7^3,7^4,...\}=\{7^n|n\in\mathbb{Z}\}.\]

\(\underline{\text{Note:}}\) This is the smallest subgroup of \(\mathbb{R^*}\) that contains 7.

Example: cyclic subgroups

List the cyclic subgroups of \(\mathbb{Z}_6=\{0,1,2,3,4,5\}\).

\(\langle 0\rangle=\{0\}\)

\(\langle 1\rangle=\{0,1,2,3,4,5\}=\mathbb{Z}_6\)

\(\langle 2\rangle=\{0,2,4\}\)

\(\langle 3\rangle=\{0,3\}\)

You can show that \(\langle 4\rangle=\{0,4,2\}=\langle 2\rangle\) and \(\langle 5\rangle=\{0,5,4,3,2,1\}=\mathbb{Z}_6\). We will see more about subgroups of \(\mathbb{Z}_n\) in Ch. 11.

Since \(\mathbb{Z}_6=\langle 1\rangle\), we call \(\mathbb{Z_6}\) a \(\underline{\text{cyclic group}}\) with generator 1.

Example: \(H\leq\mathbb{R}\times\mathbb{R}\)

Let \(H=\{(x,y)\in\mathbb{R}\times\mathbb{R}|y=4x\}\). Show \(H\leq\mathbb{R}\times\mathbb{R}\quad\quad\leftarrow\) The operation is coordinate - wise addition.

(Examples of elements of H: (0,0), (1,4), (2,8), etc. )

1. Since \(0=4\cdot 0\), the identity \((0,0)\) is in H.

2. Let \((a_1,a_2), (b_1,b_2)\in H\). Then, by definition, \[a_2=4a,\quad\text{and}\quad b_2=4b_1\]

So,

\[\begin{equation} \label{D7a} \begin{split} (a_1,a_2)+(b_1+b_2) &= (a_1+b_1,a_2+b_2)\\ &= (a_1+b_1,4a_1+4ab_1)\\ &= (a_1+b_1,y(a_1+b_1))\\ &\in H \end{split} \end{equation}\]

\(\Rightarrow\) H is closed under coordinate-wise addition.

3. Let \((a_1,a_2)\in H\). Then \(a_2=4a\). So, \[-(a_1,a_2)=(-a_1,-a_2)=(-a_1,-4a_1)=(-a_1,4(-a_1))\in H.\]

\(\Rightarrow\) H is closed under inverses. Completing the proof that \(H\leq\mathbb{R}\times\mathbb{R}\quad\quad\square\).

Example: (similar to the Ch.5 C problems)

Let G be an abelian group and let \[H=\{x\in G|x^2=e\}.\]

Recall, \(x^2=xx\)

Prove \(H\leq G\).

Proof:

1. Since \(e^2=ee=e\), the identity e is in H.

2. Let \(a, b\in H\). Then \(a^2=e\) and \(b^2=e\).

(We want to show that \(ab\in H\). To do this, we must show that \((ab)^2=e\).)

\[\begin{equation} \label{D7b} \begin{split} \text{So,}\quad (ab)^2 &= abab\\ &=aabb\quad\text{, since G is abelian}\\ &= a^2b^2\\ &= ee\\ &=e \end{split} \end{equation}\]

implying that \(ab\in H\).

3. let \(a\in H\). Then \(a^2=e\).

(We want to show \(a^{-1}\in H\). To do this, we need to show \((a^{-1})^2=e\).

\[\begin{equation} \label{D7c} \begin{split} (a^{-1})^2 &= a^{-1}a^{-1}\\ &= a^{-1}a^{-1}e\\ &= a^{-1}a^{-1}a^2\quad\text{, since }a^2=e\\ &= a^{-1}a^{-1}aa\\ &= a^{-1}(a^{-1}a)a\\ &= a^{-1}a\\ &=e. \end{split} \end{equation}\]

\[\begin{equation} \label{D7d} \begin{split} \text{Another way: } (a^{-1})^2 &= a^{-1}a^{-1}\\ &= (aa)^{-1}\quad\text{ by Theorem 4(i) from Ch3}\\ &= (a^2)^{-1}\\ &= e^{-1}\quad\text{, since }a^2=e\\ &=e. \end{split} \end{equation}\]

This implies \(a^{-1}\in H\), proving that \(H\leq G\quad\quad\square\).

---

\(\underline{\text{A few things we saw in this proof:}}\)

1. If G is abelian, \[(ab)^n=a^nb^n\] for all \(n\in\mathbb{N}\).

2. In any group, \((a^{-1})^n=(a^n)^{-1}\forall n\in\mathbb{N}\).

3. In any group, \(e^{-1}=e\).

---

Example from the book:

The Group \(\mathcal{F}(\mathbb{R})\) is the group of all functions from \(\mathbb{R}\) to \(\mathbb{R}\) with the operation of function addition.

Subgroups of \(\mathcal{F}(\mathbb{R})\):

1. continuous functions : if f and g are continuous, so are \(f+g\) and \(-f\)

2. polynomial functions (of the form \(f(x)=a_nx^n+...a_2x^2+a_1x+a_0\))

3. all functions whose graphs go through the origin:

If \(f(0)=0\) and \(g(0)=0\). Then \((f+g)(0)=f(0)+g(0)=0+0=0\) and \(-f(0)=-0=0\).

Two-step subgroup test:

Let G be a group. A subset \(H\subseteq G\) is a \(\underline{\text{subgroup}}\) of G if:

1. \(e\in H\)

2. for all \(a,b\in H\) , \(ab^{-1}\in H\). (this combines parts two and three of our first definition of a subgroup)

What does this look like if the operation in G is addition?

\(H\subseteq G\) is a \(\underline{\text{subgroup}}\) of G if.

1. \(0\in H\)

2. for all \(a,b\in H\) , \(a+(-b)=a-b\in H\).

W3D8: Jan. 21st, 2022

\(\underline{\text{Equivalent definition of a subgroup:}}\)

A subset H of group G is a subgorup of G if

1. \(e\in H\)

2. For all \(a,b\in H\), \(ab^{-1}\in H\).

Example : Show a set is a subgroup

Let G be an abelian group, and let H and K be subgroups of G.

Show that the set \[HK=\{hk|h\in H,k\in K\}\] is also a subgroup of G.

\(\underline{\text{Proof:}}\)

1. Since \(H,K\leq G\), \(e\in H\) and \(e\in K\). So \[e=ee\in HK\]

2. Let \(a,b\in HK\). Then \(a=h_1k_1\) and \(b=h_2k_2\) fro some \(h_1,h_2\in H\) and \(j_1,k_2\in K\). So,

\[\begin{equation}\label{d8a} \begin{split} ab^{-1} &= (h_1k_1)(h_2k_2)^{-1}\\ &=h_1k_1k_2^{-1}h_2^{-1}\quad\quad\quad\text{by T.3(i) from CH. 4}\\ &=h_1h_2^{-1}k_1k_2^{-1}\quad\quad\quad\text{since G is abelian} \end{split} \end{equation}\]

\(\Rightarrow ab^{-1}\in HK\)

\(\Rightarrow HK\leq G\)

\(\square\)

Note :

• \(h_1h_2^{-1}\) is in H because H is a subgroup of G.

• \(k_1k_2^{-1}\) is in K because K is a subgroup of G

Ch. 6 - Functions:

Let A and B be sets. A \(\underline{\text{function}}\) f from A to B is a rule that assigns to each element \(a\in A\) exactly one element in \(f(a)\in B\).

\(\underline{\text{Notation:}}\) \(f: A\rightarrow B\)

The set A is called the \(\underline{\text{domain}}\) and the set B is called the \(\underline{\text{codomain}}\).

The \(\underline{\text{range}}\) of \(f:A\rightarrow B\) is the set \[ran(f)=\{f(a)|a\in A\}\subseteq B.\]

Example : Diagrams

We can describe functions using diagrams:

We can also decsribe this function as follows : \[f=(\begin{smallmatrix} 1 & 2 & 3\\ a & b&b\end{smallmatrix})\]

• top line is inputs

• bottom line is corresponding outputs

Definitions

1. A function \(f:A\rightarrow B\) is called \(\underline{\text{injective}}\) or \(\underline{\text{one-to-one}}\) if \[f(x_1)=f(x_2)\quad\Rightarrow\quad x_1=x_2\]

2. \(f:A\rightarrow B\) is \(\underline{\text{surjective}}\) or \(\underline{\text{onto}}\) if for all \(y\in B\) there exists \(x\in A\) such that \[f(x)=y.\]

\(\underline{\text{Ex:}}f=(\begin{smallmatrix} 1 & 2 & 3\\ a & b&b\end{smallmatrix})\) from \(A=\{1,2,3\}\) to \(B=\{a,b,c\}\) is neither one-to-one nor onto (since there is a repetition in the second row and \(c\in B\) doesn’t appear in the second row)

3. If \(A\Rightarrow B\) is both one-to-one and onto, we call \(f\) a \(\underline{\text{bijection}}\) or \(\underline{\text{bijective}}\).

Example : Show f is a bijection

Let G be a group and let \(a\in G\) be constant. Define \(f: G\rightarrow G\) by \[f(x)=a\times a^{-1}\]

(note: that this, \(a^{-1}\), is called conjugation by a)

Let’s show \(f\) is a bijection.

1. Suppose that for some \(x_1\),\(x_2\in G\), \(f(x_1)=f(x_2)\).

\[f(x_1)=f(x_2)\Rightarrow ax_1a^{-1}=ax_2a^{-1}\Rightarrow x_1=x_2.\]

So, \(f\) is one-to-one.

2 Take any \(y\in G\). We need to find \(x\in G\) such that \(f(x)=y\).

\[\begin{equation}\label{d8b} \begin{split} f(x)=y &\Rightarrow axa^{-1}=y \\ &\Rightarrow a^{-1}axa^{-1}a=a^{-1}ya\\ &\Rightarrow x=a^{-1}ya \end{split} \end{equation}\]

Check : If \(x=a^{-1}ya\), \[f(x)=f(a^{-1}ya)=aa^{-1}yaa^{-1}=y\]

So, f is also onto.

Composition

Let \(f: A\rightarrow B\) and \(a:B\rightarrow C\). The \(\underline{\text{compostion}}\) of f with g is the function \(g\circ f:A\rightarrow C\) defined by

\(\underline{\text{Ex:}}\) Let \(f:G\rightarrow G\) be given by \(f(x)=axa^{-1}\).

Define \(g:G\rightarrow G\) by \(g(x)=bxb^{-1}\), for some constant \(b\in G\).

Find a formula for \(f\circ g\):

\[(f\circ g)(x)=f(g(x))=f(bxb^{-1})=ab\times b^{-1}a^{-1}=ab(ab)^{-1}\]

Note : conjugation by ab

Inverse

The \(\underline{\text{inverse}}\) of a function \(f:A\rightarrow B\) (if it exists) is the function \(f^{-1}:B\rightarrow A\) satisfying:

\(\underline{\text{Comment:}}\) If \(f:A\rightarrow B\) has an inverse, then for all \(x\in A\) and \(y\in B\), \[(f^{-1}\circ f)(x)=x\quad\text{and}\quad(f\circ f^{-1})(y)=y.\]

\(\underline{\text{Fact:}}\) A function \(f:A\rightarrow B\) has an inverse \(f^{-1}:B\rightarrow A\) if and only if f is bisjective.

Why? Suppose f isn’t one-to-one. Then \(\exists\) \(x_1\ne x_2\) such that \(f(x_1)=f(x_2)\)

Now suppose \(f\) isn’t onto. Then there is \(y]in B\) that isn’t in \(\text{ran}(f)\).

\(\underline{\text{Ex:}}\) Let \(f:G\rightarrow G\) be define by \(f(x)=axa^{-1}\). Find \(f^{-1}\).

1. Write \(y=f(x)\).

2. Solve the above equation for x.

3. Switch the x’s to y’s to get formula for \(f^{-1}\).

\[\begin{equation}\label{d8c} \begin{split} y=f(x) &\Rightarrow y=axa^{-1} \\ &\Rightarrow x=a^{-1}axa^{-1}a\quad\quad\text{see earlier example}\\ &\Rightarrow f^{-1}(x)=a^{-1}ya \end{split} \end{equation}\]

W4D9: Jan. 24th, 2022

\(\mathbb{R}\times\mathbb{R}=\{(x,y)|x,y\in \mathbb{R}\}=\mathbb{R}^2\)

operation in \(\mathbb{R}\times\mathbb{R}\) : \((a,b)+(c,d)=(a+c,b+d)\)

Ch. 6 - Functions

We’re going to define a group whose elements are bijections from a set A to itself.

\(\underline{\text{Facts}}\): Let \(f:A\rightarrow A\) and \(g:A\rightarrow A\) be bijections.

1. Since f and g are ont-to-one, so \(g\circ f\).

2. Since f and g are onto, so \(g\circ f\).

Proof

1. Suppose \((g\circ f)(x_1)=(g\circ f)(x_2)\). Then

\[\begin{equation}\label{d9a} \begin{split} g(f(x_1))=g(f(x_2)) &\Rightarrow f(x_1)=f(x_2)\quad\quad\text{since g is 1-1}\\ &\Rightarrow x_1=x_2\quad\quad\text{since f is 1-1} \end{split} \end{equation}\]

Hence by definition, \(g\circ f\) is one-to-one.

2. Take any \(y\in A\). Find an \(x\in A\) such that \((g\circ f)(x)=y\).

Since g is onto \(\exists a\in A\) such that \(g(a)=y\). Similarly, since \(f\) is onto \(\exists x\in A\) such that \(f(x)=a\).

\(\Rightarrow (g\circ f)(x)=g(f(x))=g(a)=y\).

Hence, \(g\circ f\) is onto. \(\quad\quad\square\)

As a consequence, the composition of two bijections is a bijections.

Ch.7 - Permutation Groups

A \(\underline{\text{permutation}}\) of a set A is a bijection from A to A.

Example : Permutation

Let \(A=\{1,2,3\}\). Then function \(f=(\begin{smallmatrix} 1 & 2 & 3\\ 3 & 2 & 1\end{smallmatrix})\) is a permutation of A.

Another is \(g=(\begin{smallmatrix}1 & 2 & 3\\2 & 3 & 1\end{smallmatrix})\). Let’s compute \(g^{-1}\). To do this just switch the rows :

\[g^{-1}=(\begin{smallmatrix}2 & 3 & 1 \\1 & 2&3\end{smallmatrix})=(\begin{smallmatrix}1 & 2 & 3 \\3 & 1 & 2\end{smallmatrix}).\]

How many permutations of \(A=\{1,2,3\}\) are there?

\(\Rightarrow\) There are \(3!=3\cdot 2\cdot 1=6\) permutations of \(A=\{1,2,3\}\).

Symmetric Group

Let A be a set. The \(\underline{\text{symmetric group}}\) on A, denoted \(S_A\), is the group of all permutations of A with the operation of function composition.

Lets show function composition is associative.

Let f, g, h \(\in S_A\forall x\in A\).

\[(f\circ (g\circ h))(x)=f((g\circ h)(x))=f(g(h(x)))\]

\[\updownarrow\text{the same}\updownarrow\]

\[((f\circ g)\circ h)(x)=(f\circ h)(h(x))=f(g(h(x)))\]

The identity function in \(S_A\) is \(\epsilon :A\rightarrow A\) defined by \[\epsilon (x)=x.\]

Check :

\[(f\circ \epsilon)(x)=f(\epsilon(x))=f(x)\quad\Rightarrow \quad f\circ \epsilon =f\]

\[(\epsilon\circ f)(x)=\epsilon(f(x))=f(x)\quad\Rightarrow\quad\epsilon\circ f=f\]

Examples - Symmetric Groups

\(\underline{\text{Ex}}\): Let \(A=\mathbb{R}\). Then \(\epsilon :\mathbb{R}\rightarrow\mathbb{R}\) is the function whose graph is the line \(y=x\):

\(\underline{\text{Ex}}\): Let \(A=\{1,2,3\}\). Then \(\epsilon = (\begin{smallmatrix} 1 & 2 & 3 \\ 1 & 2 &3\end{smallmatrix})\).

Permutation Group

A \(\underline{\text{permutation group}}\) is any symmetric group or any subgroup of a symmetric group.

When \(A=\{1,2,3,...,n\}\), we call the group of all permutations of A the \(\underline{\text{symmetric group on n elements}}\) and denote it by \(S_n\).

Example - \(S_3\)

\(S_3\) contains 6 elements (the operation table and description are on page 71-72). Let \(f = (\begin{smallmatrix} 1 & 2 & 3 \\ 3 & 2 &1\end{smallmatrix})\) and \(g = (\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 3 &1\end{smallmatrix})\). Lets find \(f\circ g\) and \(g\circ f\):

Hence, \(f\circ g\ne g\circ g\). Therefore, the group \(S_3\) is not commutative or nonabelian.

\(\underline{\text{Fact}}\): \(S_A\) is nonabelian whenever \(|A|\geq 3\). (all symmetric groups greater than or equal to 3)

Example - Dihedral Group

Let’s return to the dihedral group \(D_3=\{1,r,r^2,s,sr,sr^2\}\).

We can view \(D_3\) as \(S_3\) “in disguise”. We do this by labeling the verticies.

\[r=(\begin{smallmatrix}1 & 2 & 3 \\ 2 & 3 & 1 \end{smallmatrix})\quad\text{and}\quad s=(\begin{smallmatrix}1 & 2 & 3 \\ 3 & 2 & 1\end{smallmatrix})\]

Example - Square

Consider the symmetries of a square.

\(\underline{\text{Note}}\): The group \(S_4\) contains all permutations of \(\{1,2,3,4\}\). So, \(|S_4|=4\cdot 3\cdot 2\cdot 1=24\). Not all 24 of these elements in \(S_4\) correspond to a symmetry of a square. For example, \(f=(\begin{smallmatrix} 1 & 2 & 3& 4\\ 2 & 1 & 3 & 4\end{smallmatrix})\) (twisting the top of the square but leaving the bottom) doesn’t represent a symmetry of a square. The group \(D_4\) (of the symmetries of the square) has only 8 elements.

W4D10: Jan. 26th, 2022

Ch.7 Permutation Groups, Cont.

Let A be a set. A \(\underline{\text{permutation}}\) of A is a bijections (one-to-one and onto) from A to A.

The \(\underline{\text{symmetric group}}\) on A, denoted \(S_A\), is the set of all permutations of A with the operation of function composition.

The identity permutation is the function \(\epsilon : A\rightarrow A\) defined by \[\epsilon(x)=x.\]

The inverse of \(f\in S_A\) is defined as follows: \[f(x)=y\quad\Rightarrow\quad f^{-1}(y)=x.\]

Ex. Symmetries of a Square (Permutation Group)

Last class we considered the group symmetries:

There are 8 symmetries of the square. This set forms an 8 element subgroup of \(S_4\). (Recall, \(|S_4|=24\).)

Let H be the group of symmetries of the square. Since everything from H can be obtained from \(r,s\in S_4\), we write: \[H=\langle(\begin{smallmatrix}1&2&3&4\\2&3&4&1\end{smallmatrix}),(\begin{smallmatrix}1&2&3&4\\4&3&2&1\end{smallmatrix})\rangle\]

Ex: Prove H (a subgroup) is a subgroup of the \(S_{\mathbb{Z}}\text{ }\) (another subgroup)

(Similar to problem on Homework 2)

In this example, we’re going to find a subgroup of \(S_{\mathbb{Z}}\). \(\forall n\in \mathbb{Z}\) define \(f_n:\mathbb{Z}\rightarrow\mathbb{Z}\) by \(f_n(x)=n+x\).

We’ll show \(H=\{f_n|n\in\mathbb{Z}\}\) is a subgroup of \(S_{\mathbb{Z}}\).

i) Show that \(H\subseteq S_{\mathbb{Z}}\), i.e. \(f_n\in S_\mathbb{Z}\forall n\in \mathbb{Z}\).

(show one-to-one and onto)

First, suppose \(f_n(x_1)=f_n(x_2)\) for some \(x_1,x_2\in\mathbb{Z}\).

\[\begin{equation}\label{D10P1i} \begin{split} f_n(x_1)=f_n(x_2) &\Rightarrow n+x_1=n+x_2\\ &\Rightarrow x_1 = x_2 \end{split} \end{equation}\]

So, by definition, \(f_n\) is one-to-one.

Now take any \(y\in\mathbb{Z}\) and let \(x=y-n\in\mathbb{Z}\). Then \[f_n(x)=f_n(y-n)=n+y-n=y.\]

Thus, \(f_n\) is onto.

(ii) No, we’ll show that \(\epsilon\in H=\{...,f_{-2}, f_{-1},f_{0},f_{1},f_{2},...\}\).

Since \(f_0(x)=0+x=x\), \(f_0=\epsilon\) (\(\epsilon\) is the identity permutation). Hence, \(\epsilon\in H\).

(iii) Now take any \(f_n\) and \(f_m\) in H. For all \(x\in\mathbb{Z}\), \[(f_n\circ f_m)(x)=f_n(f_m(x))=f_n(m+x)=n+m+x.\]

Since, \(f_{n+m}(x)=n+m+x\) as well, \(f_n\circ f_m = f_{n+m}\in H\).

(iv) Now we need to show that H is closed under inverses.

I claim that the inverse of \(f_n\) is \(f_{-n}\): \[f_n\circ f_{-n}=f_{n+(-n)}=f_0=\epsilon\]

So by Theorem 2 from Ch. 4, \((f_n)^{-1}=f_{-n}\in H\).

Since \(H\subseteq S_{\mathbb{Z}}\) contains the idenety, is closed under \(\circ\) (composition), and closed under inverses, \(H\leq S_{\mathbb{Z}}\).

Ch.8 Permutations of a Finite Set

If \(A=\{1,2,3,...n\}\), for some \(n\geq 1\), we use \(S_n\) to denote the symmetric group on A.

Ex. Cycle function \(\in S_5\)

Let \(f=(\begin{smallmatrix}1&2&3&4&5\\3&4&1&1&5\end{smallmatrix})\in S_5\).

This function is called a \(\underline{\text{cycle}}\):

We’ll rewrite f using cycle notation:

We write \(f=(1\quad3\quad2\quad4)\)

• note: closing parentheses indicates that the last number is sent to the beginning of the cycle.

Ex. Cycle Decomposition \(\in S_7\)

Let \(g=(\begin{smallmatrix}1&2&3&4&5&6&7\\5&3&1&7&2&6&4\end{smallmatrix})\in S_7\)

\(\Rightarrow g=(1523)(47)\)

This is called the \(\underline{\text{cycle decomposition}}\) of g.

Def. Disjoint

We call two cycles \(\underline{\text{disjoint}}\) if they have no numbers in common.

\(\underline{\text{Fact}}\): disjoint cycles in \(S_n\) commute.

Ex. Rewritting Cycle Decompositions

Let \(g=(1523)(47)\in S_7\). We can also write this as follows:

\[\begin{equation}\label{d10 example3} \begin{split} g &= (47)(1523)\\ &= (74)(1523)\\ &= (74)(3152)\\ &\quad\quad \vdots \end{split} \end{equation}\]

\(\underline{\text{Fact}}\): Cycles that aren’t disjoint don’t necessary commute.

Ex. Composition of non-disjoint cycles

Let \(f=(12)\) and \(g=(23)\) in \(S_3\).

Let’s compute \(f\circ g\) and \(g\circ f\).

Ex. Find the inverse of a cycle

How can we find the inverse of \(h=(1432)\in S_4\)?

We can find \(h^{-1}\) by writing the numbers in h backwards: \[h^{-1}=(2341)=(1234)\]

W4D11: Jan. 28th, 2022

Ch.8 Permutations of Finite Set, continued:

\(S_n\) denotes the group of permutations of the set \(\{1,2,3,...,n\}\).

A cycle in \(S_n\) is a permutation of the form \(f=(a_1,a_2,a_3,...a_k)\) where \(f(a_i)=a_{i+1}\forall 1\leq i\leq k-1\) (any number but 1) and \(f(a_k)=a_1\).

Any number not appearing in the cycle \((a_1\quad a_2\quad a_3\quad\dots\quad a_k)\) is fixed by f. 

Th. 8.1: Permutations in \(S_n\)

Every permutation in \(S_n\) is either the identity, a cycle or a composition (the book will say “product” here instead) of dijoint cycles.

Ex. Permutation \(\in S_8\)

Let \(f=(\begin{smallmatrix}1&2&3&4&5&6&7&8\\8&4&5&1&6&3&7&2\end{smallmatrix})\in S_8\)

\(f=(1824)(356)\)

We can also write this as \(f=(356)(1824)\), etc.

Def. Length and Transposition

The number of integers in a cycle is called its \(\underline{\text{length}}\).

A cycle of length 2 is called a \(\underline{\text{transposition}}\).

Ex. \(\epsilon =f\circ f\text{ }\) for \(\text{ }f=(12)\in S_3\)

Let \(f=(12)\in S_3\). What is \(f\circ f\)? Since f switches 1 and 2, composing with f will switch them back.

\(\Rightarrow f\circ f=\epsilon\)

\(\Rightarrow f=f^{-1}\)

\(\underline{\text{Fact}}\): Every transposition in \(S_n\) is equal to its own inverse. Equivalently, every transposition composed with itself gives the identity permutation \(\epsilon\).

\(\underline{\text{Fact}}\): Every permutation in \(S_n\) can be written as a composition of transpositions.

Ex. Rewrite \(g=(127643)\in S_7\)

Let \(g=(127643)\in S_7\). We can write g as follows: \[g=(12)(27)(76)(64)(43)\]

Here’s another way: \[g=(34)(36)(37)(32)(31)\]

Th. 8.2: Parity of transpositions is unique

When writing a permutation as a composition of transpositions, the parity (even/odd) of the number of transpositions is unique.

For example, we can’t write a permutation as a composition of 3 transposition and also as a composition of 4 transpositions (because one is odd and one is even).

Ex. Number of transpositions changes but stays even

In \(S_3\), \((123)=(12)(23)=(13)(23)(12)(13)\)

A permutation in \(S_n\) is called \(\underline{\text{even/odd}}\) if it can be written as a composition of an even / odd number of transpositions.

\(\underline{\text{Fact}}\): There are the same # of even permutations and odd permutations in \(S_n\).

Def. Alternating Group

The set of all even permutations in \(S_n\) is a subgroup called the \(\underline{\text{alternating group}}\), which is denoted \(A_n\).

Ex. Even length implies odd permutation

Let \(g=(127643)\in S_7\). The length of g is even. But \[g=(12)(27)(76)(64)(43),\]

implying g is an odd permutation.

\(\underline{\text{Facts}}\):

1. If the length of a cycle is even, then the cycle is an odd permutation.

2. If the length of a cycle is odd, then the cycle is an even permutation.

Ex. Even plus odd permutation

Is \(h=(158)(2346)\in S_8\) an even or odd permutation?

Since even+odd=odd, the permutaion h is odd.

Ex. Composition of two even permutations | Proof that \(A_n\) is a subgroup of \(S_n\)

(i) What happens if we compose two even permutations?

The result will be an even permutation since

even + even = even.

(ii) If f is an even/ odd permutation, then so is \(f^{-1}\).

For example, if \(h=(158)(2346)\), then

These imply that \(A_n\) (the set of even permutations in \(S_n\)) is closed under composition and inverses.

The identity \(\epsilon\) is even since \(\epsilon = (12)(12)\). So \(\epsilon \in A_n\), completing the proof that \(A_n\) is a subgroup of \(S_n\).

Ex. \(S_3\) (non-abelian group) is NOT a subgroup of H

In Ch.5, we showed that if G is abelian then \[H=\{x\in G|x^2=e\}\] is a subgroup of G.

If G is nonabelian, this set H is not necessarily a subgroup.

Let’s consider \(G=S_n=\{\epsilon, (12), (13), (123), (132)\}\).

Then \(\alpha = (12)\) and \(\beta=(13)\) are in the set H, since \[\alpha^2=\alpha\circ\alpha=\epsilon\quad\text{and}\quad \beta^2=\beta\circ\beta=\epsilon.\]

But \(\alpha\circ \beta=(12)(13)=(132)\) and \((132)(132)=(123)\ne\epsilon\).

(Right to left)

We’ve shown that in \(S_3\), the set \(H=\{x\in H|x^2=\epsilon\}\) is not a subgroup because \(\alpha\), \(\beta\in H\), but \(\alpha\circ\beta\notin H\).

Question for Ch. 10

A question we’ll answer in Ch.10:

What is the least positive \(n\in \mathbb{N}\) such that \(a^n=e?\)

\(\underline{\text{Ex}}\): Let \(\alpha =(1324)\in S_4\).

You can check that \(\alpha^4=\alpha\circ\alpha\circ\alpha\circ\alpha=\epsilon\).

W5D12: Jan. 31st, 2022

Ch. 9 - Isomorphism

In CH4, we made the operation table for a group \(G_1=\{e,a,b,c\}\) of size 4 with the property \(e^2=a^2=b^2=c^2=e\).

Another group of size 4 with this property is \(G_2=\mathbb{Z}_2\times \mathbb{Z}_2\).

The function \(f:G_1\rightarrow G_2\) given by

transforms the table for \(G_1\) into the table for \(G_2\). This function is called an \(\underline{\text{isomorphism}}\) from \(G_1\) to \(G_2\).

An isopmorphism from a group \(G_1\) to \(G_2\) will have to be a bijection. What does it mean for \(f\) to “transform” the table for \(G_1\) into the table for \(G_2\)?

\(\forall a,b,\in G\) we want f to take \(ab\in G\) to the element \(f(a)f(b)\in G_2\).

Def. Isomorphism

A function \(f:G_1\rightarrow G_2\) is called an \(\underline{\text{isomorphism}}\) if f is a bijection and for all \(a,b\in G\), \[\text{operation in }G_1\rightarrow\quad f(ab)=f(a)f(b)\quad\leftarrow\text{operation in }G_2\]

If the operation in \(G_1\) and / or \(G_2\) is “+”, the above equation might look like \(f(a+b)=f(a)f(b)\), \(f(ab)=f(a)+f(b)\), or \(f(a+b)=f(a)+f(b)\). (Left side might use addition, right side might use addition, both sides might use addition)

If f is an isomorphism from \(G_1\) to \(G_2\), we call \(G_1\) and \(G_2\) \(\underline{\text{isomorphic}}\) and we write \(G_1\cong G_2\).

Ex. Show \(\langle\mathbb{R},+\rangle\cong\langle\mathbb{R},\cdot\rangle\)

I claim \(f(x)=10^x\) is an isomorphism from \(\mathbb{R}\) to \(\mathbb{R}^+\).

This is a bijection:

\[\begin{equation}\label{D121} \begin{split} f(x_1)=f(x_2) &\Rightarrow 10^{x_1}=10^{x_2}\\ &\Rightarrow log(10^{x_1})=log(10^{x_2})\\ &\Rightarrow x_1=x_2 \end{split} \end{equation}\]

So, f is one-to-one.

Now let \(y\in \mathbb{R}^+\) and \(x=log(y)\in \mathbb{R}\). Then \[f(x)=10^x=10^{log(y)}=y,\]

proving f is onto.

Last, take any \(a,b\in\mathbb{R}\). Then \[f(a+b)=10^{a+b}=10^a10^b=f(a)f(b)\].

Hence, \(\langle\mathbb{R},+\rangle\cong\langle\mathbb{R},\cdot\rangle\).

Ex. Show that \(\langle\mathbb{Z},+\rangle\cong\langle7\mathbb{Z},+\rangle\)

Note: Integers will always be under addition.

Recall, \(7\mathbb{Z}=\{...,-14,-7, 0, 7, 14, 28, ...\}\)

Define \(f:\mathbb{Z}\rightarrow 7\mathbb{Z}\), by \(f(n)=7n\). (You can check this is a bijection.)

Take \(a,b\in \mathbb{Z}\), then \[f(a+b)=7(a+b)=7a+yb=f(a)+f(b)\]

So \(\mathbb{Z}\cong 7\mathbb{Z}\).

Ex. Construct an isomorphism

Let \(G_1=\mathbb{Z}_4=\{0,1,2,3\}=\langle 1\rangle\).

\(\rightarrow\) all elements of \(\mathbb{Z}_4\) can be obtained from 1 using repeated addition mod 4.

Let \(G_2=\{1,-1,i,-i\}\subseteq\mathbb{C}\) with the operation of complex multiplication.

Since \(i^2=-1\), \(i^3=-i\), and \(i^4=1\), then \(G_2=\langle i\rangle\).

We’ll construct an isomorphism \(f:G_1\rightarrow G_2\) by specifying that \(f(1)=i\).

Then,

\[f(2)=f(1+1)=f(1)f(1)=i^2=-1\]

\[f(3)=f(1+2)=f(1)f(2)=i(-1)=-i\]

\[f(0)=f(1+3)=f(1)f(3)=i(-i)=1\]

(Note: \(f(0)=f(2+2)=f(2)f(2)=(-1)(-1)=1\).)

So, we constructed an isomorphism \(f:\mathbb{Z}_4\rightarrow G_2\):

\[f=(\begin{smallmatrix} 0 & 1 & 2 & 3\\ 1 & i & -1 & -i\end{smallmatrix})\]

Notice: 1 and 3 are inverses in \(\mathbb{Z}_4\). Similarly, i and \(-i\) are inverses in \(G_2\).

(This is enough for cyclic groups)

Also Notice: Identity elements are always paired (0 paired with 1). Two inverses paired up in the first group will be paired up with the inverses in the second.

Prop. 1: True for any isomorphic group

Let \(f:G_1\rightarrow G_2\) be an isomorphism. Then

1. \(f(e_1)=e_2\)

2. \(\forall a\in G\), \(f(a)\) and \(f(a^{-1})\) are inverses in \(G_2\), i.e. \[f(a^{-1)}=[f(a)]^{-1}\]

3. If \(G_1=\langle a\rangle\), then \(G_2=\langle f(a)\rangle\).

(If the first group )

Proof of Prop. 1

1. Let \(e_1\) and \(e_2\) be the identites in \(G_1\) and \(G_2\), respectively. Then

\[\begin{equation}\label{D12,2} \begin{split} f(e_1)e_2 &= f(e_1)\\ &= f(e_1e_1)\\ &= f(e_1)f(e_1)\quad\text{since f is an isomorphism} \end{split} \end{equation}\]

\(\Rightarrow e_2=f(e_1)\), by left cancellation.

2. To show \(f(a)\) and \(f(a^{-1})\) are inverses, let’s show their product is the identity \(e_2\in G\):

\[\begin{equation}\label{12,3} \begin{split} f(a)f(a^{-1}) &= f(aa^{-1})\\ &=f(e_1)\\ &= e_2\quad\text{ by part(i)} \end{split} \end{equation}\]

Therefore, \(f(a^{-1})=(f(a))^{-1}\) by Theorem 2 from Ch. 4.

W5D13: Feb. 2nd, 2022

Ch. 9 - Isomorphism

A function \(f:G_1\rightarrow G_2\) is called an \(\underline{\text{isomorphism}}\) if f is a bijection and for all \(a,b\in G\), \[f(ab)=f(a)f(b).\]

Ex. Show matrix \(G\cong \langle \mathbb{Z},+\rangle\)

Let \(G\{(\begin{smallmatrix} 1 & n \\ 0 & 1\end{smallmatrix})|n\in \mathbb{Z}\}\) with the operation of matrix multiplication. Let’s show \(G\cong \langle \mathbb{Z},+\rangle\).

First, why is G a group?

1. identity = \((\begin{smallmatrix} 1 & 0 \\ 0 & 1\end{smallmatrix})\in G\)

2. \((\begin{smallmatrix} 1 & a \\ 0 & 1\end{smallmatrix})(\begin{smallmatrix} 1 & b \\ 0 & 1\end{smallmatrix})=(\begin{smallmatrix} 1\cdot 1 + a\cdot 0 & 1\cdot b+a\cdot 1 \\ 0\cdot 1+1\cdot 0 & 0\cdot b+1\cdot 1\end{smallmatrix})=(\begin{smallmatrix} 1 & a+b \\ 0 & 1\end{smallmatrix})\in G\).

3. \((\begin{smallmatrix} 1 & a \\ 0 & 1\end{smallmatrix})^{-1}=(\begin{smallmatrix} 1 & -a \\ 0 & 1\end{smallmatrix})\in G\)

Now let’s show \(G\cong\mathbb{Z}\). Define \(f:\mathbb{Z}\rightarrow G\) by \[f(n)=(\begin{smallmatrix} 1 & n \\ 0 & 1\end{smallmatrix}).\]

One-to-one:

Suppose \(f(n_1)=f(n_2)\) for some \(n_1,n_2\in\mathbb{Z}\). Then \[(\begin{smallmatrix} 1 & n_1 \\ 0 & 1\end{smallmatrix})=(\begin{smallmatrix} 1 & n_2 \\ 0 & 1\end{smallmatrix})\quad\Rightarrow\quad n_1=n_2.\]

Onto:

Take any \((\begin{smallmatrix} 1 & n \\ 0 & 1\end{smallmatrix})\in G\). Then \(n\in\mathbb{Z}\) and \(f(n)=(\begin{smallmatrix} 1 & n \\ 0 & 1\end{smallmatrix})\). Take any \(a,b\in\mathbb{Z}\). Then \[f(a+b)=(\begin{smallmatrix} 1 & a+b \\ 0 & 1\end{smallmatrix})=(\begin{smallmatrix} 1 & a \\ 0 & 1\end{smallmatrix})(\begin{smallmatrix} 1 & b \\ 0 & 1\end{smallmatrix})=f(a)f(b).\]

Groups that are isomorphic have the same algebraic properties

Suppose that \(G_1\cong G_2\). Then

1. \(|G_1|=|G_2|\) (they have the same size)

2. \(G_1\) is abelian if and only if \(G_2\) is abelian.

3. \(G_1\) is cyclic if and only if \(G_2\) is cyclic.

4. \(G_1\) has the property that every element squared equals e if and only if \(G_2\) has the same property.

5. Every subgroup of \(G_1\) is isomorphic to a subgroup of \(G_2\).

\(\vdots\)

Ex. \(\mathbb{Z}_4\ncong \mathbb{Z}_2\times \mathbb{Z}_2\)

Show that \(\mathbb{Z}_4=\{0,1,2,3\}\) is not isomorphic to \(\mathbb{Z}_2\times \mathbb{Z}_2\).

The group \(\mathbb{Z}_4\langle 1\rangle\) is cyclic. The group \(\mathbb{Z}_2\times \mathbb{Z}_2\) is not, since

Another way to show \(\mathbb{Z}_4\ncong \mathbb{Z}_2\times \mathbb{Z}_2\):

\(\mathbb{Z}_2\times \mathbb{Z}_2\) has the property that every element added to itself is the identity. The group \(\mathbb{Z}_4\) doesn’t have this property:

\[1+1=2\ne 0\in \mathbb{Z}_4\]

\(\underline{\text{Fact}}\): (We’ll prove this in ch. 11): Every group of size 4 is isomorphic to \(\mathbb{Z}_4\) or \(\mathbb{Z}_2\times\mathbb{Z}_2\). (This is either one or the other since we just showed these are not isomorphic to each other)

Ex. Symetries of a square \(\cong \mathbb{Z}_2\times \mathbb{Z}_2\)

Let G be the group of symmetries of a (non-square) rectangle. Then \(G=\{1,R,S_1,S_2\}\):

Any element of G times itself is the identity, so \(G\cong \mathbb{Z}_2\times \mathbb{Z}_2\).

We could also show that this isn’t cyclic so it wouldn’t be in \(\mathbb{Z}_4\), so therefore it is isomorphic to \(\mathbb{Z}_2\times\mathbb{Z}_2\) (by fact above).

Ex. Show \(\langle \mathbb{R},+\rangle \ncong \langle \mathbb{R}^*,\cdot\rangle\)

The group \(\mathbb{R}^*\) has a cyclic subgroup of size 2: \(\langle -1\rangle =\{1,-1\}\).

The group \(\mathbb{R}\) does not have a cyclic subgroup of size 2. The only finite cyclic subgroup of \(\mathbb{R}\) is \(\langle 0\rangle =\{0\}\), since \(a\ne 0\), \[\langle a\rangle =\{...,-2a,-a,0,a,2a,3a,...\},\]

which is infinite.

Alternatively, \(\langle \mathbb{R}^*, \cdot \rangle\) has two elements that are their own inverse (1 and \(-1\)). In \(\langle \mathbb{R}^*, + \rangle\) there is only one element that is its own inverse (the identity 0).

Ex. Show \(\langle\mathbb{C}^*,\cdot\rangle\ncong\langle \mathbb{R}^*,\cdot\rangle\)

The group \(\mathbb{C}^*\) has a cyclic subgroup of size 4: \(\langle i\rangle=\{1,-1,i,-i\}\) but \(\mathbb{R}^*\) doesn’t have a subgroup of size 4.

Ex. Show \(\langle\mathbb{C},+\rangle\ncong\langle \mathbb{R}\times\mathbb{R},+\rangle\)

\[\begin{equation}\label{D13} \begin{split} f((a_1+b_1i)+(a_2+b_2i)) &= f(a_1+a_2+(b_1+b_2)i)\\ &= (a_1+a_2,b_1+b_2)\\ &= (a_1,b_1) + (a_2,b_2)\\ &= f(a_1+b_1i)+f(a_2+b_2i) \end{split} \end{equation}\]

Cayley’s Theorem (1854)

Every group is isomorphic to a permutation group. (Like $S_4, \(S_5\) …)

\(\underline{\text{Proof}}\): Let G be any group. For every \(a\in G\), define a function \(f_a:G\rightarrow G\) by \[f_a(x)=ax.\]

Let \(H=\{F_a|a\in G\}\). We’ll show that H is a subgroup of \(S_G\) (all permutations of G), and that \(G\cong H\).

In Hw 2, you showed:

1. Each function \(f_a\) is a bijection, i.e. \(H\subseteq S_G\).

2. \(f_a\circ f_b=f_{ab}\), i.e. H is closed under composition.

3. \((f_a)^{-1}=f_{a^{-1}}\), i.e. H is closed under inverses.

Note that \(f_e\), “left multiplication by e”, is the identity permutation, since \[f_e(x)=ex=x=\epsilon(x).\]

So H contains the identity permmutation. Hence, \(H\leq S_G\), i.e. H is a permutation group.

Now let’s show that \(G\cong H\). Define a function \(\alpha:G\rightarrow H\) by \[\alpha(a)=f_a.\]

Then \(\forall a,b\in G\), \[\alpha(ab)=f_{ab}=f_a\circ f_b=\alpha(a)\circ\alpha(b).\]

(See the book for the proof that \(\alpha\) is a bijection.) Hence, \(\alpha\) is an isomorphism, proving \(G\cong H\). \(\quad\quad\square\)

W5D14: Feb. 4th, 2022

One more example from CH9:

Ex. Show \(G_2\) also has same property as \(G_1\)

Suppose \(G_1\cong G_2\) and that \(G_1\) has the property that every element squared equals the identity \(e_1\). Show \(G_2\) must also have this property.

\(\underline{\text{Proof}}\):

Since \(G_1\cong G_2\) there is an isormorphism \(f:G_1\rightarrow G_2\).

Take any \(y\in G_2\). (We want to show \(y^2=e_2\).)

Since f is onto, there exists \(x\in G_1\), such that \(f(x)=y\).

Hence,

\[\begin{equation}\label{D14e1} \begin{split} y^2=(f(x))^2 &= f(x)f(x)\\ &= f(xx)\quad\quad\text{, since f is an isomorphism}\\ &= f(x^2)\\ &= f(e_1)\quad\quad\text{, since the square of every element of G, equals e}\\ &= e_2 \end{split} \end{equation}\]

\(\Rightarrow\) Every element of \(G_2\) squared equales the identity. \(\quad\quad\square\)

“isomorphisms take the identity (e) from the first group to the second group.”

Ch. 10 - The Order of Group Elements

• not on HW or the midterm

• “ordr is related to a size but the two are different things”

Let G be a group and let \(a\in G\). For any \(n>0\)

Exponent Laws for Groups

For all \(m,n\in \mathbb{Z}\),

1. \(a^{m+n}=a^ma^n\)

2. \(a^{mn}=(a^m)^n\)

3. \(a^{-n}=(a^{-1})^n=(a^n)^{-1}\)

The exponent law we can’t necessarily use: \((ab)^n=a^nb^n\).

Def. Order

Let \(a\in G\). The \(\underline{\text{order}}\) of a, denoted \(ord(a)\) or \(|a|\), is the least positive integer n such that \[a^n=e.\]

If \(a^n\ne e\) for all poisitve integers n, we say \(ord(a)=\infty\).

Let’s rewrite the definition using +:

\(ord(a)\) is the least positive \(n\in\mathbb{Z}\) such that

Ex. Find the orders of all elements of \(\mathbb{Z}_6=\{0,1,2,3,4,5\}.\)

• Additive

• “How many a’s do you need to add together to get 6.”

• “For four you are finding a multiple of six, which is why it’s ord(4)=3 since 4+4+4=0.”

• “Multiples of 6 work for the integers”

\(\underline{\text{Comment}}\): Supppose every element of G squared equals the identity. This is equivalent to saying that every non-identity element of G has order 2.

10 Examples

1. Whats the order of 12 in \(\mathbb{Z}_{20}\)?

We need a sum of 12’s that is a multiple of 20. The least common multiple (lcm) of 12 and 20 is 60. We need to add 5 to 12’s to get 60, so \[ord(12)=\frac{lcm(12,20)}{12}=\frac{60}{12}=5\]

2. If \(k\in \mathbb{Z}_n=\{0,1,2,...,n-1\}\) is nonzero, \[ord(k)=\frac{lcm(k,n)}{k}.\]

3. Find the order of \(f=(132)\in S_3\).

• “To compose these cycles start are the right with 1. 1 goes to three and then three goes to two, so 1 goes to 2. Starting on the right again, 2 goes to 1 which goes to three. So 2 goes to three.”

4. Find the order of \(g=(125786)\in S_8\).

The order of a cycle in \(S_n\) is equal to its length. So, \[ord(g)=6.\]

• “Notice the previous example has 3 elements, and 3 arrows.”

• “We would get six different things until \(f^6\)”

5. Whats the order of \(h=(14)(2356)\in S_6\)?

For any \(n>0\),

\[\begin{equation}\label{D14e5} \begin{split} h^n=[(14)(2356)]^n &= (14)(2356)(14)(2356)...(14)(2356)\\ &= (14)^n(2356)^n\quad\quad\text{, since disjoint cycles commute} \end{split} \end{equation}\]

We need n to be a multiple of 2 so that \((14)^n=\epsilon\).

We need n to be a multiple of 4 so that \((2356)^n=\epsilon\).

Since \(4=lcm(2,4)\), the order of \(h=(14)(2356)\) is 4.

6. The order of a composition of disjoint cycles in \(S_n\) is the lcm of the lengths of the cycles. \[\text{Ex:}\quad ord((2364)(157))=lcm(4,3)=12\]

7. The group \(S_4\) has no elements of order 6 (even though 6 is a divisor of \(|S_4|=24\)).

Since \(S_4\) is the group of permutations of \(\{1,2,3,4\}\) it has no cycles of length 6.

Similarly, no element of \(S_4\) can be written as a composition of two disjoint cycles with lengths 2 and 3.

8. What is the order of \((4,8)\in\mathbb{Z}_6\times\mathbb{Z}_{12}\)?

We need to add three 4’s to get 0 in \(\mathbb{Z}_6\). Similarly,

we need to add three 8’s to get 0 in \(\mathbb{Z}_{12}\).

So, \((4,8)+(4,8)+(4,8)=(4+4+4,8+8+8)=(0,0)\)

\(\Rightarrow ord((4,8))=3\).

9. What is the order of \((4,6)\in \mathbb{Z}_6\times\mathbb{Z}_{12}\)?

We need to add two 6’s to get 0 in \(\mathbb{Z}_{12}\). Since we need to add three 4’s to get 0 in \(\mathbb{Z}_6\),

10. In \(G\times H\), the order of (g,h) is \[lcm (ord(g),ord(h))\].

W6D15: Feb. 7th, 2022

Ch. 10 Continued

The \(\underline{\text{order}}\) of an element a in a group G is the least positive integer n such that \(a^n=e\) (or a+a+a…(for n a’s)…+a=0) if the operation is +).

If no such \(n>0\) exists, we say the order of a is \(\infty\).

Ex. In \(\mathbb{Z}\), ord(1)=\(\infty\)

Because no sum of 1’s is equal to 0.

Ex. Suppose \(a\in G\) has order 4.

(Then \(a^4=e\) and none of a,\(a^2\), or \(a^3\) equal e.)

Consider \(a^{19}\in G\). Then

\[\begin{equation}\label{D15e1} \begin{split} a^{19}=a^{4\cdot 4+3}&=(a^4)^4a^3\\ &= e^4a^3\quad\quad\text{, since }a^4=e\\ &=a^3\quad\quad\text{, since }e^4=e \end{split} \end{equation}\]

Similarly,

\[\begin{equation}\label{D15e1.2} \begin{split} a^{-10} = a^{4(-3)+2} &= (a^4)^{-3}a^2\\ &= e^{-3}a^2\quad\quad\text{, since }a^4=e\\ &= a^2\quad\quad\text{, since } e^{-3}=e. \end{split} \end{equation}\]

The Division Algorithm

Let m,n \(\in\mathbb{Z}\) and \(n>0\). Then there exists q (quotient),r (remainder) \(\in \mathbb{Z}\) such that \[\frac{m}{n}=q+\frac{r}{n}\quad\quad\text{and}\quad\quad0\leq\frac{r}{n}<1\]

\[\Leftrightarrow m=nq+r\quad\quad\text{and}\quad\quad0\leq r<n.\]

Ex. Suppose ord(b)=7. Rewrite the element \(b^{26}\).

Using the Division Algorithm,

\(26=7\cdot 3+5\)

\(\Rightarrow b^{26}=b^{7\cdot 3+5}=(b^7)^3b^5=e^3b^5=b^5\).

Theorem 3

Let G be a group and let \(a\in G\) have order \(n<\infty\). Then every power of a is equal to exactly one \[e,a,a^2,a^3,...,a^{n-1}.\]

\(\underline{\text{Proof}}\):

Lets see why \(e,a,a^2,a^3,...,a^{n-1}\) are distinct elements.

Suppose that \(a^i=a^j\) for some \(0\leq i\leq j\leq n-1.\)

\[\begin{equation}\label{d15prooft3} \begin{split} a^i=a^j &\Rightarrow a^ja^{-i}=a^ja^{-i}\\ &\Rightarrow e=a^{j-i}. \end{split} \end{equation}\]

Since \(0<j-i<n\), the fact that \(a^{j-i}=e\) contradicts that ord(a)=n is the \(\underline{\text{least}}\) positive integer such that \(a^n=e\).

(n should be the smallest value in order, but we just showed j-i exists and is smaller than n)

Therefore, the elements \(e,a,a^2,...,a^{n-1}\) are distinct.

Now take any element \(a^m\). By the Division Algorithm \(\exists\) q,r \(\in \mathbb{Z}\) such that \(m=nq+r\) and \(0\leq r<n\). So, \[a^m=a^{nq+r}=(a^n)^qa^r=e^qa^r=a^r.\]

Since \(0\leq r< n\), \(a^r\) is one of e, a, \(a^2\), …, \(a^{n-1}\).

Corollary

Let ord(a)=n<\(\infty\). Then the cyclic group gemerated by a has n elements:

\[\begin{equation}\label{d15ex3} \begin{split} \langle a\rangle &=\{..., a^{-2}, a^{-1}, e, a, a^2, a^3\}\\ &= \{e,a,a^2,...,a^{n-1}\}. \end{split} \end{equation}\]

Theorem 4

Let ord(a)=\(\infty\). Then for all i,j \(\in\mathbb{Z}\), if \(i\in j\) then \(a^i\ne a^j\).

(no power of a gives us the identity, and no power of a is the same)

\(\underline{\text{Proof}}\):

Suppose \(a^i=a^j\) for some \(i<j\). Then \(a^{j-i}=e\).

Since \(j-i\ne 0\), this contradicts that ord(a)=\(\infty\). Hence if \(i\ne j\), then \(a^i\ne a^j\).

Corollary

If ord(a)=\(\infty\), the cyclic group generated by a has infinitely many elements: \[\langle a\rangle =\{...,a^{-2},a^{-1},e,a,a^2\}\]

Ex. Suppose \(a\in G\) has order 6. What other powers of a are equal to e?

Suppose \(a\in G\) has order 6. (Then \(a^6=e\) and none of a, \(a^2\), \(a^3\), \(a^4\), \(a^5\) equals e.)

What other powers of a are equal to e? We need the exponent to be a multiple of 6. For example, \[a^{-24}=a^{6(-4)}=(a^6)^{-4}=e^{-4}=e.\]

Theorem 5

Let \(a\in G\) have order \(n<\infty\). Then \(a^m=e\) if and only if m is a multiple of n. 

\(\underline{\text{Proof}}\):

(\(\Leftarrow\)) Suppose m is a multiple of n. Then \(m=nq\) for some \(q\in \mathbb{Z}\). Hence, \[a^m=a^{nq}=(a^n)^q=e^q=e.\]

\(\Rightarrow\) Now suppose that \(a^m=e\). By the Division Algorithm, we can write \[m=nq+r,\] where \(0\leq r< n\). Therefore,

\[\begin{equation}\label{d1prooft5} \begin{split} a^m=e &\Rightarrow a^{nq+r}=e\\ &\Rightarrow (a^n)^qa^r=e\\ &\Rightarrow a^r=e\quad\quad\text{, since }a^n=e. \end{split} \end{equation}\]

Since \(0\leq r<n\) and ord(a)=n, it must be the case that \(r=0\). Thus, \[m=nq+0=nq,\] i.e. m is a multiple of n. 

Examples of proofs about order

(Using Th. 5)

1. Suppose ord(a)=\(n<\infty\). Show ord(\(a^{-1}\))=n as well.

\(\underline{\text{Proof}}\): Since \(a^n=e\), \[(a^{-1})^n=(a^n)^{-1}=e^{-1}=e.\]

Thus, by Theorem 5, n is a multiple of ord(\(a^{-1}\))

Let m=ord(\(a^{-1}\)). Then \[a^m=((a^{-1})^m)^{-1}=e^{-1}=e.\]

So, by Theorem 5, m is a multiple or ord(a)=n. 

We have that n is a multiple of m and vice-versa. Since m and n are positive integers, this implies m=n, i.e. \[\text{ord(a)}=\text{ord}(a^{-1}).\]

2. Let \(f:G_1\rightarrow G_2\) be an isomorphism. Suppose \(a\in G\), has order 3. Prove \(f(a)\in G_2\) has order 3.

\(\underline{\text{Proof}}\):

\[\begin{equation}\label{d15p2} \begin{split} f(a)^3 &= f(a)f(a)f(a)\\ &= f(a^2)f(a)\quad\quad\text{, since f is an isomorphism}\\ &= f(a^3)\quad\quad\text{, since f is an isomorphism}\\ &= f(e_1)\\ &= e_2 \end{split} \end{equation}\]

Note: we showed \(f(e_1)=e_2\) in class.

Since ord(a)=3, neither a nor \(a^2\) equal \(e_1\). So, because f is one-to-one, neither f(a) nor f(\(a^2\)) equals \(e_2\).

\[\Rightarrow f(a)\ne e_2\quad\quad\text{and}\quad\quad f(a)^2=f(a^2)\ne e_2.\]

Hence, by definition, ord(f(a))=3.

Ch. 11 Cyclic Groups

If ord(a)=\(n<\infty\), then

The groups \(\langle a\rangle\) and \(\mathbb{Z}_n\) are isomorphic. The function \(f:\langle a\rangle\rightarrow\mathbb{Z}_n\) defined by \[f(a^i)=i\] is an isomorphism: \[f(a^ia^j)=f(a^{i+j})=i+j=f(a^i)+f(a^j).\]

Will do Review on Wednesday!

W6D16: Feb. 9th, 2022

MTH 344 Midterm

• Friday February 11th, 11:30-12:35 in person

• covers chapters 2-9

• 5 questions

• no notes / book allowed (this means more partial credit)

• you will write your solutions on a separate paper. I will bring blank white paper to the exam. If you prefer to use your own paper that’s okay.

Topics

• Ch 2-3: Definition of a group (associative, identity, inverses)

• Ch 4: Cancellation Law, \((ab)^{-1}=b^{-1}a^{-1}\), \((a^{-1})^{-1}=a\)

• Ch 5: Subgroups

• Ch 7-8: Permutations in \(S_n\), cycle notation, even/ odd permutations

• Ch 9: Isomorphisms

HW 3 #5

Isomorphic to \(\mathbb{Z}_2\times\mathbb{Z}_2\) or \(\mathbb{Z_}_4\)?

HW 3 #5

\(f:G_1\rightarrow G_2\) isomorphsim, H is a subgroup of \(G_1\).

Show \(f(H)=\{f(h)|h\in H\}\) is a subgroup of \(G_2\).

1. Show \(e_2\in f(H)\)

We know \(e_1\in H\) since H is a subgroup. Since \(e_2=f(e_1)\), \(e_2\in f(H)\).

2. Let a,b \(\in f(H)\). Show \(ab^{-1}\in f(H)\).

This means \(a=f(h_1)\) and \(b=f(h_2)\) for some \(h_1,h_2\in H\).

\[\begin{equation}\label{D16 HW3ii} \begin{split} \Rightarrow ab^{-1} &= f(h_1)f(h_2)^{-1}\\ &= f(h_1)f(h_2^{-1})\\ &= f(h_1h_2)\quad\quad\text{, since f is an isomorphism} \end{split} \end{equation}\]

Since H is a subgroup of G, \(h_1h_2^{-1}\in H\). So \(ab^{-1}=f(h_1h_2^{-1})\in f(H)\).

Practice Problems

2. Let G be a group and a,b,c, x \(\in G\). Solve \[cx^2b=a\quad\quad\text{ and }\quad\quad x^3=e\] for x in terms of a, b, and c. 

\[\begin{equation}\label{pp2} \begin{split} cx^2b=a &\Rightarrow cx^2bb^{-1}=ab^{-1}\\ &\Rightarrow cx^2=ab^{-1}\\ &\Rightarrow cx^3=ab^{-1}x\\ &\Rightarrow c=ab^{-1}x\quad\quad\text{, because }x^3=e\\ &\Rightarrow a^{-1}c=a^{-1}ab^{-1}x\\ &\Rightarrow a^{-1}c=b^{-1}x\\ &\Rightarrow ba^{-1}c=bb^{-1}x\\ &\Rightarrow x=ba^{-1}c \end{split} \end{equation}\]

4. G is abelian group. Show \(H=\{x\in G|x=g^2\text{ for some } g\in G\}\) is a subgroup of G.

1. Show \(e\in H\).

Since \(e\in H\). Since \(e=e^2\), \(e\in H\).

2. Let a,b \(\in H\). Show \(ab^{-1}\in H\).

This means \(a=g_1^2\) and \(b=g_2^2\) for some \(g_1\), \(g_2\) \(\in G\).

\[\begin{equation}\label{pp4} \begin{split} \Rightarrow ab^{-1} &=g_1^2(g_2^2)^{-1}\\ &= g_1g_1(g_2g_2)^{-1}\\ &= g_1g_1g_2^{-1}g_2^{-1}\\ &= g_1g_2^{-1}g_1g_2^{-1}\\ &= g_1g_2^{-1}g_1g_2^{-1}\quad\quad\text{since G is abelian}\\ &= (g_1g_2^{-1})^2 \end{split} \end{equation}\]

We’ve shown \(ab^{-1}\) is the square of something from G, so \(ab^{-1}\in H\).

5. \(h=(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 7& 3 & 4 & 1 & 6 & 5\end{smallmatrix})\)

Write in cycle notation: \(h=(1275)\).

Write h as a composition of transpositions: \(h=(12)(27)(75)\)

note: the first and last numbers in the cycle aren’t repeated

\(\Rightarrow\) h is an odd permutation (since 3 is odd)

8. Show f is an isomorphsim.

Define \(f:G\rightarrow G\) by \(f(x)=gxg^{-1}\), where \(g\in G\) is constant.

one-to-one:

\[\begin{equation}\label{pp8} \begin{split} f(x_1)=f(x_2) & \Rightarrow gx_1g^{-1}= gx_2g^{-1}\\ &\Rightarrow x_1 = x_2 \end{split} \end{equation}\]

onto: Take \(y\in G\). Find x such that \(f(x)=y\).

\[\begin{equation}\label{pp82} \begin{split} f(x)=y &\Leftrightarrow gxg^{-1}=y\\ &\Leftrightarrow g^{-1}gxg^{-1}g=g^{-1}yg\\ &\Leftrightarrow x=g^{-1}yg \end{split} \end{equation}\]

Now let a,b \(\in G\). We need to show \(f(ab)=f(a)f(b)\).

1. Define * on \(\mathbb{R}\) by \[a*b=a+2b-ab\]

identity? Solve \(a*e=a\) for e.

\[\begin{equation}\label{pp1} \begin{split} a+2e-ae=a &\Rightarrow 2e-ae=0\\ &\Rightarrow e(2-a)=0\\ &\Rightarrow e=0 \end{split} \end{equation}\]

Check if for \(e=0\), \(e*a=a\): \[e*a=0*a=0+2a-0\cdot a=2a\ne a\]

Since \(e*a\ne a\) when \(e=0\), there is no identity element.

6. \(\alpha =(3714)\), \(\beta=(123)\), \(\rho=(24135)\) in \(S_7\).

\[\begin{equation}\label{pp6} \begin{split} \alpha^{-1}\beta &= (3714)^{-1}(123)\\ &= (4173)(123)\\ &= (124)(37) \end{split} \end{equation}\]

W6D17: Feb. 11th, 2022

MIDTERM!!!