# Permutations (and isomorphisms)

1. Jul 11, 2005

### quasar987

I'm on page 31 now (of this book: http://www.math.miami.edu/~ec/book/).

The question is: Show that if there is a bijection between X and Y , there is an isomorphism between S(X) and S(Y).

I see the bijection btw S(X) and S(Y) in my head, but can't find the right mathematical symbols to express it. The bijection would take a permutation in S(X) and assign to it the permutation in S(Y) that is ""identical in essence"" to it. I.e. if we somehow manage to order the sets X and Y, then the bijection from S(X) to S(Y) assigns to the permutation in S(X) that warps the n^th element of X to the m^th element of X, the i^th element to the j^th element, and so on, to the permutation of S(Y) that warps the n^th element of Y to the m^th element of Y, the i^th element to the j^th element, and so on.

Last edited: Jul 11, 2005
2. Jul 12, 2005

### Muzza

After consulting the book, it appears that S(X) denotes the set of all permutations of X (just in case anyone else but me got confused).

Let f: X -> Y be a bijection.

Define phi: S(X) -> S(Y), phi(x) = f o x o f^-1 (for all elements x in S(X). o denotes composition) and prove that it's an isomorphism.

Last edited: Jul 12, 2005
3. Jul 12, 2005

### quasar987

f o x o f^-1 would write f^1(x(f)).. but what is the function x(f)?

4. Jul 12, 2005

### Muzza

Oops, I said "x in X", that should be "x in S(X)" (now fixed). x is a permutation of X, i.e. a bijective function from X to X. x(f) doesn't make sense, the (co)domains of f and x don't match.

I meant f(x(f^-1)) by f o x o f^-1 (i.e. if I wanted to calculate the value of f o x o f^-1 at some point z, I would first apply f^-1, then x, and lastly f).

5. Jul 12, 2005

### quasar987

My post had an error too

I meant to write f o x o f^-1 = f(x(f^-1)).

6. Jul 12, 2005

### quasar987

Mmmh, but still, thus defined, phi sends an element of Y to another element of Y, not of S(X) to S(Y).

7. Jul 12, 2005

### Muzza

No it doesn't. I believe you're confusing "phi" with "phi(x)".

Last edited: Jul 12, 2005
8. Jul 12, 2005

### quasar987

surely you meant "phi(z)" but I get your point.

9. Jul 12, 2005

### Muzza

Actually, if we're reusing the variables from earlier posts, I DID mean phi(x)...

10. Jul 12, 2005

### quasar987

Oh.. and so by "phi" you meant phi(x(z))?

11. Jul 12, 2005

### Muzza

No, I meant phi, as defined in post #2 You seemed to have confused phi, which is a function which eats permutations of X and spits back permutations of Y, and phi(x), which is a permutation of Y.

12. Jul 12, 2005

### matt grime

obviously the question has been asnwered, but to explain how you should have come to the answer i would have suggested:

i know X and Y are in bijection, so let f:X to Y be a bijection. now i need to produce a biejction of Y for each one of X, and the only thing i can do is compose bijections (and the composition of bijectiions is a bijetction) so fgf^{-1} is all i can do to get a map from Y to Y from one from X to X. obviuosly this is a bijection between S(X) and S(Y) since it is invertible,a nd equally clearly it's going to be a group isomorphism, cos it's just like a change of basisi in linear algebra.

13. Jul 12, 2005

### Hurkyl

Staff Emeritus
I think the easiest way is to draw pictures!

Draw an element of S(X) as an arrow X ---> X. You want to attach more arrows (corresponding to some other functions) to the diagram so that the end result is a path Y ---> Y. With any luck, the composition of those arrows will be an element of S(Y). Then, you have to prove whatever method you used yields an isomorphism of S(X) with s(Y).

14. Jul 12, 2005

### quasar987

I'm having trouble showing phi is an homomorphism. What I did:

consider x_1, x_2 in S(X). Then

$$\phi (x_1\cdot x_2) = \phi (x_1 \circ x_2) = f \circ (x_1 \circ x_2) \circ f^{-1} = f(x_1(x_2(f^{-1})))$$

But when it comes to

$$\phi(x_1)\cdot \phi(x_2)$$

, how do I treat the binary operation btw these 2 phi? The composition doesn't work, since

$$\phi(x_1)\circ \phi(x_2) = \phi(\phi(x_2))$$

but $\phi(x_2) \in S(Y)$, not S(X).

15. Jul 12, 2005

### Muzza

That's false, and I'm not sure how you got that. Try this instead:

$$\phi(x_1)\circ \phi(x_2) = f \circ x_1 \circ f^{-1} \circ f \circ x_2 \circ f^{-1}$$, and things cancel out.

16. Jul 12, 2005

### quasar987

Ok ok ok. I understand my mitake. It's that $\phi(x)$ represents the permutation of S(Y) that phi associates to x. So it would make sense to write things like

$$\phi(x):Y\rightarrow Y$$,

$$[\phi(x)](z) = f(x(f^{-1}(z)))$$

17. Jul 12, 2005

### Muzza

Yes, precisely!

18. Jul 12, 2005

### quasar987

I have the same problem with the next exercise:

"Show that o(S_n) = n!. Let X = {1, 2, ..., n}, S_n = S(X), and H =
{f in S_n | f(n) = n}. Show H is a subgroup of S_n which is isomorphic to S_{n-1}."

Remains to show H is isom. to S_n. I see the isom but don't know how to express it mathematically. The isomorphism is a function $\psi\rightarrow S_{n-1}$ that takes an f in H and assigns to it the function g in S_{n-1} such that g is the exact replica of f except for the part that says f(n) = n.

19. Jul 13, 2005

### Muzza

Define your $$g \in S_{n - 1}$$ as

$$g(a) = f(a)$$

for all $$a \in \{1, 2, ..., n - 1\}$$.

20. Jul 13, 2005

### quasar987

In the book I used, the author refined functions as an ordered triple constituted of the domain set, the codomain set, and the "rule" f connecting the two. So a function f in H would write formally as (X,X,f) and so the function psi would write formally as

$$\psi\rightarrow S_{n-1}$$
$$(X,X,f) \mapsto (X\backslash \{n\}, X\backslash \{n\},f)$$