Please Login to access more options.


Today

« October 2013 »

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

Here's what we'll do in class.

  • Hand in your induction proofs. Review this.
  • View and comment on Joe's proof.
  • In front of the whole class, have the following people present their work.
2.1Alexander
2.2Kimberly
3Lilia
4Megan
5Brennan
6Rich

Problem (Write up an induction proof)

Please make sure you write up a final draft induction proof for the problem Closed Under Function Composition. Use complete sentences, just as you would on the wiki. You are welcome to type it up on the wiki (in which case you can use copy/paste to get the LaTeX code). Make sure you bring a copy to class (hand written or typed), and hand it in. I want to read your proofs and help you each improve. Make sure that whatever words you use are your own. DO NOT LOOK at someone else's proof, as then I won't be able to give you feedback about your writing.

Click to show the problem.

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

This does not replace your week 4 write up, so you'll need to pick a different problem and write it up by Wednesday.

Problem (Review two problems from last time)

We did not have time in class to review the solutions to the following problems:

  1. Characterizing Closed Sets Of Permutations
  2. The Identity And Inverses Are Unique - You'll find solutions to this in chapter 2 of your text.

A ton of you had these, so if you did, please move on. If you did not yet get these, please spend some time with them before proceeding. If you are unable to get them, then assume they are true and keep working on the problem set.

Click to show these problems.

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.

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.

Let's start today by analyzing a new type of encryption that we have not yet introduced. 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 and October 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$.

For more problems, see AllProblems