Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
| Open 1.2.12 | Nick | Class | ||
| Open 1.2.3 | Rich | Class | ||
| Open 1.3 | Br. Woodruff | |||
| 1 | Joe | Justin | Laura | |
| 1 | Megan | Rich | ||
| 2 | Kimberly | Bryce | Li | |
| 3 | Tara | Terry | Tim | |
| 4 | Sam | Carla | Laura | |
| 5 | Caley | Brennan | Cassie | |
| 6 | Nick | Alexander | Kinsey | Lilia |
I'll add more connecting words between the problems later today, but here is the list of problems.
Last time we looked at the map $f:\mathbb{Z}_{12}\to \mathbb{Z}_3$ defined by $f(x)=x\pmod 3$ and showed that this was a homomorphism. Make sure you can prove the following exercise.
Exercise (A Homomorphism From $\mathbb{Z}_n$ to $\mathbb{Z}_d$ when $d$ is a divisor of $n$)
Consider the map $f:\mathbb{Z}_{n}\to \mathbb{Z}_d$ defined by $f(x)=x\pmod d$ where $d$ is a divisor of $n$. Show that $f$ is a homomorphism.
Click to see a solution
We need to show that $((x+y)\pmod n)\pmod d = (x\pmod d+y\pmod d)\pmod d$. We know that $a\pmod d=b\pmod d$ if and only if $a-b$ is a multiple of $d$ (does this look like the coset property that says $Ha=Hb$ if and only if $ab^{-1}\in H$?). We just need to show that $(x+y)\pmod n - (x\pmod d+y\pmod d)$ is a multiple of $d$. To do this, first note that using the division algorithm we can write $x\pmod d = x-q_xd$ and $y\pmod d = y-q_yd$ for some integers $q_x$ and $q_y$, and we can write $(x+y)\pmod n = (x+y)-qn$ for some integer $q$. Since we know $d$ is a divisor of $n$, we can also write $n=md$ for some integer $m$. We then compute $$\begin{align} (x+y)\pmod n - (x\pmod d+y\pmod d) &=(x+y-qn)-(x-q_xd)-(y-q_yd)\\ &=-qmd+q_xd+q_yd\\ &=d(q_x+q_y-qm), \end{align}$$ which is a multiple of $d$ as desired.
What happens if $d$ is not a divisor of $n$? Does the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ result in a homomorphism?
Problem 94 (When is $x \pmod d$ a homomorphism from $\mathbb{Z}_n$ to $\mathbb{Z}_d$)
Let $G=\mathbb{Z}_{12}$ and $H=\mathbb{Z}_5$. Let $f:G\to H$ be the map defined by $f(x)=x\mod 5$.
- Is the map $f:G\to H$ a homomorphism? Either prove that it is, or produce a counter example.
- Let $n$ be an integer and suppose that the positive integer $d<n$ is not a divisor of $n$. Is the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ a homomorphism?
The problems above also give us homomorphisms from $U(n)$ to $U(d)$, as the next problem shows. These maps are crucial in understanding cryptography.
Problem 95 (The set $U_d(n)$ and the homomorphism from $U(n)$ to $U(d)$)
For each integer $n\geq 2$ and each divisor $d$ of $n$, consider the map $f:U(n)\to U(d)$ defined by $f(x)=x\pmod d$.
- Show that this map is a homomorphism. [Hint: You will probably want to use the fact that $a\pmod k=b\pmod k$ if and only if $a-b$ is a multiple of $k$. This is the easiest way to prove statements about modular arithmetic. You have to show that two things are equal, namely that $((x\cdot y)\pmod n)\pmod d = ((x \pmod d)\cdot (y \pmod d))\pmod d$. You can remove the outermost $\pmod d$ by instead showing that the difference is a multiple of $d$.]
- Then explain why the set $U_d(n)=\{x\in U(n)\mid x\pmod d = 1\}$ is a subgroup of $U(n)$. (Hint: What is the kernel of $f$?)
- List the elements of $U_{5}(60)$.
The next theorem should come as no surprise. We've already shown that given any subgroup $H$ of $G$, that every element of $H$ is in one of the cosets of $H$. We've also shown that the cosets of $H$ are disjoint. These two facts to gether show that we can partition $G$ into a disjoint union of cosets of $H$. We also know that the size of each coset matches the order of $H$. So if we have $r$ disjoint cosets $Ha_1$, $Ha_2$, $Ha_3$, ..., $Ha_r$, all of which have the same number of elements, then we should be able to use this information to show that the order of $H$ divides the order of the group. This fact is called Lagranges theorem.
Problem 86 (Lagrange's Theorem Proof)
Prove Lagrange's Theorem.
Theorem (Lagrange's Theorem)
Suppose that $G$ is a finite group and that $H$ is a subgroup of $G$. Then the order of $H$ divides the order of $G$. In particular, we know that $|G|/|H|$ equals the number of distinct right (or left) cosets of $H$ in $G$.
We now have shown that the $|G|/|H|$ is precisely the number of cosets of $H$ there are in $G$. From a Cayley graph perspective, this is how many copies of $H$ are visible in the graph, as they are translated throughout the graph. The number of such cosets is called the index of $H$ in $G$, and written $|G:H|$.
Definition (Index of $H$ in $G$, or $|G:H|$)
If $H$ is a subgroup of $G$, then the index of $H$ in $G$, written $|G:H|$, is the number of distinct right (or left) cosets of $H$. Because of Lagrange's theorem, we know that $|G:H|=|G|/|H|$.
For the rest of today, we'll return to looking at when the left and right cosets of a subgroup agree, namely we'll be looking at normal subgroups.
Problem 87 (Some Normal Subgroups)
Prove the following facts.
- If $G$ is Abelian, then every subgroup of $G$ is normal.
- The center $Z(G)$ of any group $G$ is always a normal subgroup of $G$.
To prove many of the coset properties, we used the fact that $(Ha)b=H(ab)$. This looks a lot like an associative property. There's a bigger idea going on in the background than just the fact that $(Ha)b=H(ab)$. This is a set product of the form $(HA)B=H(AB)$ where the sets $A=\{a\}$ and $B=\{b\}$ consist of just one element. What if the sets $A$ and $B$ consist of more than one element. We would then have a binary operation on subsets of $G$ that is associative. This is precisely what it means to be a semigroup. The higher level idea is the concept of a semigroup.
Definition (Semigroup And Monoid)
Please look up the definitions of semigroup and monoid from Wikipedia.
We need the second property from the list below to proceed with group theory. The first property below should follow from the fact that $G$ is a group (why). The second property will require that you write down both sets in terms of their definitions, and then make some observations. The last property is for fun, skip it if you want.
Problem (The Collection Of Nonempty Subsets Of A Group Is A Monoid)
Let $G$ be a group, and consider the binary operation $HK$ on the collection $\mathscr{C}$ of nonempty subsets of $G$. Recall that $$HK=\{hk\mid h\in H, k\in K\}.$$ Prove the following:
- The set product $HK$ is indeed a binary operation on the collection $\mathscr{C}$ of nonempty subsets of $G$.
- The set product is associative, namely $(HK)L = H(KL)$. This proves that we have a semigroup.
- (Extra - We won't present this in class) The set $E=\{e\}$ is an identity element of $\mathscr{C}$, namely $EH=HE=H$ for any $H\in \mathscr{C}$. This proves that we have a monoid.
The key we need is that the set product is associative, which means that for any subgroup $H$, the coset product $(Ha)(Hb)$ is associative. Now if $N$ is a normal subgroup of $G$, then this means that the binary operation $(Na)(Nb)=N(ab)$ is an associative binary operation. These are two of the four things we need to obtain a group. We're now ready to prove that the collection of cosets of a normal subgroup is actually a group, and we call this the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, and write $G/N$.
Definition (Factor Group or Quotient Group of $G$ by $N$, or $G/N$)
Let $G$ be a group. Let $N$ be a normal subgroup of $G$. Then we define the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, to be the set $G/N = \{Na\mid a\in G\}$, i.e the collection of right cosets of $N$ using the set product $(Na)(Nb)=N(ab)$ as the binary operation.
Problem 88 (The Quotient Group $G/N$ Is A Group)
Let $G$ be a group and let $N$ be a normal subgroup of $G$. Prove that the set $G/N$ is actually a group under the operation of coset products.
For more problems, see AllProblems