Math 360, Fall 2021, Assignment 13

"Reeling and Writhing, of course, to begin with," the Mock Turtle replied; "And then the different branches of Arithmetic - Ambition, Distraction, Uglification, and Derision."

- Lewis Carroll, Alice's Adventures in Wonderland

Read:

1. Section 13.

Carefully define the following terms, then give one example and one non-example of each:

1. Even permutation.
2. Odd permutation.
3. $A_n$ (the alternating group on $n$ letters).
4. Homomorphism.
5. Monomorphism.
6. Epimorphism.
7. Forward image (of a subset, under a function).
8. Pre-image (of a subset, under a function).
9. Pushforward (of a subgroup, under a homomorphism).
10. Pullback (of a subgroup, under a homomorphism).
11. Image (of a homomorphism).
12. Kernel (of a homomorphism).

Carefully state the following theorems (you do not need to prove them):

1. Theorem concerning the orbit count of $\tau\pi$, where $\tau$ is a transposition and $\pi$ is an arbitrary permutation.
2. Theorem concerning the sign of $\tau\pi$, where $\tau$ is a transposition and $\pi$ is an arbitrary permutation.
3. Formula for $\mathrm{sgn}(\tau_1\dots\tau_k)$, where $\tau_1,\dots,\tau_k$ are transpositions.
4. Formula for $\mathrm{sgn}(\pi\sigma)$, where $\pi$ and $\sigma$ are arbitrary permutations.
5. Formula for the order of $A_n$.
6. Theorem characterizing the pushforward of a subgroup ("The pushforward of a subgroup is a...")
7. Theorem characterizing the pullback of a subgroup ("The pullback of a subgroup is a...")

Solve the following problems:

1. Section 13, problems 1, 2, 3, 8, 9, 10, 17, and 18.
2. Determine whether the following permutations are odd or even: (i) $(12)$, (ii) $(123)$, and (iii) $(1234)$.
3. Suppose $\sigma$ is an $l$-cycle, where $l$ is even. Is $\sigma$ an even permutation or an odd permutation?
4. Suppose $\sigma$ is an $l$-cycle, where $l$ is odd. Is $\sigma$ an even permutation or an odd permutation?
5. Define a function $f:\{1,2,3,4\}\rightarrow\{a,b,c,d\}$ as follows: $f(1)=a, f(2)=a, f(3)=b, f(4)=c$. Compute the following: (i) $f[f^{-1}[\{c,d\}]]$ and (ii) $f^{-1}[f[\{2,3\}]]$.
6. Suppose $f:A\rightarrow B$ is a function, and $S\subseteq A$. Prove that $f^{-1}[f[S]]\supseteq S$. Give examples to show that equality may or may not hold.
7. Suppose $f:A\rightarrow B$ is a function, and $T\subseteq B$. Prove that $f[f^{-1}[T]]\subseteq T$. Give examples to show that equality may or may not hold.

--------------------End of assignment--------------------

Questions:

1. Book Problem 17: $Ker(\phi ) $ and $\phi (25)$ for $\phi: \mathbb Z \rightarrow \mathbb Z_7$ such that $\phi (1) = 4$.

Definitions:

1. Even permutation: $orb(\pi )$ is orbit count of $\pi$ and $sgn(\pi )$ is the "sign" of $\pi$, def: $sgn(\pi ) = (-1)^{n+orb(\pi )}$. If $sgn((\pi ) = 1$, we say the permutation $\pi$ is even.
2. Odd permutation.$orb(\pi )$ is obit count of $\pi$ and $sgn(\pi )$ is the "sign" of $\pi$, def: $sgn(\pi ) = (-1)^{n+orb(\pi )}$. If $sgn((\pi ) = -1$, we say the permutation $\pi$ is odd.
3. $A_n$ (the alternating group on $n$ letters): $A_n = \{\pi \in S_n | sgn(\pi ) = 1\}$ (set of even permutations).
4. Homomorphism : Suppose $G, H$ are graps, and $\phi: G \rightarrow H$ is a function. We say that $\phi$ is a homomorphism if, $\forall g_1, g_2,\phi (g_1, g_2) = \phi (g_1)\phi (g_2).$. Example: $sgn: S_n \rightarrow \mathbb R*$ (Operation on $S_n$ is $\circ$. operation on $\mathbb R*$ is $*$). This is a homomorphism, not a monomorphism or an epimorphism.
5. Monomorphism: If $\phi : G \rightarrow H$ is a homomorphism, and $\phi$ also happens to be injective. We say that $\phi$ is a monomorphism.
6. Epimorphism: If $\phi : G \rightarrow H$ is a homomorphism,and $\phi$ also happens to be surjective. We say that $\phi$ is a Epimorphism. Example: $sgn: S_n \rightarrow {1, -1}$ is an Epimorphism.
7. Isomorphism: If $\phi : G \rightarrow H$ is a homomorphism,and $\phi$ also happens to be bijective. We say that $\phi$ is a isomorphism.
8. Forward image (of a subset, under a function): Suppose $\phi: G \rightarrow B$ is a homomorphism. If $A, B$ are sets and $f: A \rightarrow B$ is a function, and $C \subset A$, define $f[c] = \{f(c) | c \in C\}.$ This is the forward image of $C$ under $f$.
9. Pre-image (of a subset, under a function): Same as pullback.
10. Pushforward (of a subgroup, under a homomorphism): Same thing as Forward imagine. Suppose $\pi : G \rightarrow H$ is a homomorphism. If $A, B$ are sets and $f:A \rightarrow B$ is a function, and $C \subseteq A$, define $f[c] = \{f(c) | c \in C\}$. This is the forward image of C under f.
11. Pullback (of a subgroup, under a homomorphism): Suppose $\pi : G \rightarrow H$ is a homomorphism. If $A, B$ are sets and $f:A \rightarrow B$ is a function, and $D \subseteq B$. Then $f^{-1}[D] = \{a \in A | f(a) \in D\}$.
12. Image (of a homomorphism): $\phi [\{e_G\}] = \{e_H\}, \phi [G] = im\phi$ (Pushforward the whole set, should be subset of the target group).
13. Kernel (of a homomorphism): $\pi: G \rightarrow H$ ,$\pi^{-1}[H] = G, \pi^{-1}[\{e_H\}] = ker\phi$. Pullback the whole thing. Set output to the identity of the target.

Theorems:

1. Theorem concerning the orbit count of $\tau\pi$, where $\tau$ is a transposition and $\pi$ is an arbitrary permutation: Suppose $\pi \in S$ and $\pi$ is a transposition. Then $orb(\tau \pi ) = orb(\pi ) \pm 1$. (Consequently $sgn(\tau \pi ) = - sgn(\pi ))$.
2. Theorem concerning the sign of $\tau\pi$, where $\tau$ is a transposition and $\pi$ is an arbitrary permutation: Consequently $sgn(\tau \pi ) = - sgn(\pi )$
3. Formula for $\mathrm{sgn}(\tau_1\dots\tau_k)$, where $\tau_1,\dots,\tau_k$ are transpositions: $sgn(\pi ) = sgn(\tau_1 \tau_2 ...\tau_k ) = -sgn(\tau_2 ... \tau_k) = (-1)^2 sgn(\tau_3 ... \tau_k) = (-1)^k sgn(\iota ) = (-1)^k$.
4. Formula for $\mathrm{sgn}(\pi\sigma)$, where $\pi$ and $\sigma$ are arbitrary permutations: $sgn(\pi \sigma ) = sgn(\pi )sgn(\sigma )$
5. Formula for the order of $A_n$: If $2\leq n$ then $|A_n| = \frac{n!}{2}$
6. Theorem characterizing the pushforward of a subgroup ("The pushforward of a subgroup is a..."): Suppose $\pi : G \rightarrow H$ is a homomorphism. Suppose $K <= G$, then $\pi [K] <= H$.
7. Theorem characterizing the pullback of a subgroup ("The pullback of a subgroup is a..."): Suppose $L <= H$ Then $\pi^{-1}[L] <= G$. Usually $\pi^{-1}[\pi [K]] \neq K, \pi [\pi^{-1}[L]] \neq L$.

Book Problems:

1. Yes, $\phi (n_1 n_2) = n_1 n_2, \phi (n_1) \phi(n_2) = n_1 n_2$.

2. No, $x + y - 1 \neq (x-1) + (y-1) = x + y - 2$

3. Yes, $|xy| = |x||y|$

8. Not sure. $(fg)^-1*fg = identity$, $(fg)^{-1} = g^{-1}f^{-1}$, $f^{-1}g^{-1}gf = identity$, but when the group is abelian...

9. Yes

10. Yes

17. <7>, 2

other Problems:

2. $(12): odd (n+n-1 = 2n-1), (123): even (n+n-2 = 2n-2), (1234): odd (n+n-3 = 2n-3)$

3. odd $(n + (n - l + 1)) = 2n - (l-1) = 2n - 2k + 1 = 2(n - k) + 1 =$odd

4. even: $(n + (n - l + 1)) = 2n - (l-1) = 2n - (2k + 1) + 1 = 2(n - k) = $even

5. $\{c\}, \{1,2,3\}$

6. $f(1)=a, f(2)=a, f(3)=b, f(4)=c$, $f^{-1}[f[\{2,3\}]] = \{1,2,3\}$

7. $f(1)=a, f(1)=b, f(3)=c, f(4)=d$, $f[f^{-1}[\{b,c\}]] = \{a,b,c\}$