Permutations (and isomorphisms)

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

 

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

 

[quasar987]

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

 

[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).

 

[quasar987]

My post had an error too

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

 

[quasar987]

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

 

[Muzza]

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

 

[quasar987]

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

 

[Muzza]

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

 

[quasar987]

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

 

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

 

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

 

[Hurkyl]

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

 

[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).

 

[Muzza]

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

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.

 

[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)))$$

 

[Muzza]

Yes, precisely!

 

[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 [itex]\psi\rightarrow S_{n-1}[/itex] 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.

 

[Muzza]

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

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

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

 

[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

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

 

[matt grime]

well, that is one formal way of writing down a function, and it is a bad one for doing any work, apparently, since this is an easy function to write down. define a function as you need. and the function

I from S_{n-1} to S_n that sends f in S_{n-1} to the g in S_n g(r)=f(r) for 1<=r<=n-1 and g(n)=n is clearly a bijection between S_{n-1} and the permutations that fix n in S_n since it is invertible, the inverse being the function muzza gave in the last post but one.

 

[quasar987]

Little problem with Cayley's thm. proof

Cayley's theorem is stated at the end of pp.31 and the 3 main points of the proof are given.

First off, I don't see how the first point is relevant to the proof.

In the second point, if I try to show homomorphism, I get

$$h(a\cdot b) = h_{a\cdot b} = g\cdot a \cdot b$$

and

$$h(a)\cdot h(b) = h(a) \circ h(b) = h_a(h_b(g)) = h_b(g)\cdot a = g\cdot b \cdot a$$

but no mention of G being abelian is made. So I can't conclude. :yuck:

 

[matt grime]

point one shows that the map is a bijection of a set with n elements thus the map sending a in G to something is indeed a map into S_n

second remember to what you're applying these maps: h_b is applied to g.a *not* g, ie it it h_b(g.a)=g.a.b

my way of thinking abut cayley's theorem is this:

let G eb a finite group with elemetns g_1,..., g_n, if we apply any element h of G to these then we get the element hg_1,..hg_2. these must be exactly the elements of g is some different order because of the rules governing group composition: hg_i=hg_j implies i=j (inverses). and closure tells me that hg_i=g_j. thus if i write down the permuation of {1,..,n} that sends i to j accoriding to the rule that hg_i=g_j then i get an element of S_n. what other rules do groups have? well, there's an identity element and that is sent to the trivial permutation, and there is associativity which corresponds to associativity of composition of functions.

edit: i may have meant to write (g_i)h for the action, but it is largely academic. one works directly, and the other works but gives the 'opposite' group, which is the 'same' group except that all elements should be inverted. i see that your notes have rings in them. they ought to explain the opposite ring and if i made a mistake that's what I've done here. but groups possesses the inverse operator so there's no real difference.

 

[quasar987]

second remember to what you're applying these maps: h_b is applied to g.a *not* g, ie it it h_b(g.a)=g.a.b

I don't see what you mean; I never get to calculate h_b(g.a). Here's how I see it in every detail:

$$h(a)\cdot h(b) = h(a) \circ h(b) = h_a\circ h_b = h_a(h_b) = h_a(g \cdot b) = (g\cdot b)\cdot a = g\cdot b \cdot a$$

 

[matt grime]

okay, let's correct my error by doing it directly rather than me trying to work out what you're doing.

we (you and me) want to show that h_{ab}(g)=h_a(h_b(g)) agreed? well do it:

h_{ab}(g) = gab

and h_a(h_b(g)) = h_a(gb)

now this would be a genuine probelm vut for the fact that the book you're wotking with writes maps on the right and not the left. so actually we ought not to be showing what we think we ought to be showing

read the notes. he chooses the convention that

(g)h_a=ga

so we need to check that

(g)h_ab = ((g)h_a)h_b

or that gab=gab evaluating them properly.

so check you are using the same conventions.

 

[quasar987]

I decided not to use this convention, because it gets confusing when you have permutations composed with non-permutations functions.. you then have to stare at the thing forever just to see what's in what.

So how would the proof go w/o this silly notation? It seems we still have to show the same thing, namely, that

$$h(a\cdot b) = h(a) \circ h(b)$$

since the definition of homomorphism is independant of the notation we use. But now the problem is genuine, since

$$h(a) \circ h(b) = h_a(gb)$$

 

[matt grime]

you have to use the opposite notation or similar.

one way is to define h_a(g)=ag and then
h_ab(g) = abg

and h_a(h_b(g))=h_a(bg)=abg

another is to use the inverse operator and define h_a(g)=ga^{-1}

you cannot mix conventions and expect them to work like you did. the existence of the homomorphism doesn't depend on the notation, agreed, but what you wrote down is not a homomorphism with the mixed conventions you used.

 

[quasar987]

Oh right, adjust the definition of h_a, great!

 

[dimuk]

"I from S_{n-1} to S_n that sends f in S_{n-1} to the g in S_n g(r)=f(r) for 1<=r<=n-1 and g(n)=n is clearly a bijection between S_{n-1} and the permutations that fix n in S_n since it is invertible, the inverse being the function muzza gave in the last post but one. "

Can u explain this more.