Permutations (and isomorphisms)

  • Thread starter quasar987
  • Start date

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
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:
694
0
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:

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
f o x o f^-1 would write f^1(x(f)).. but what is the function x(f)?
 
694
0
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

Science Advisor
Homework Helper
Gold Member
4,771
7
My post had an error too :smile:

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

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
Mmmh, but still, thus defined, phi sends an element of Y to another element of Y, not of S(X) to S(Y).
 
694
0
No it doesn't. I believe you're confusing "phi" with "phi(x)".
 
Last edited:

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
surely you meant "phi(z)" :wink: but I get your point.
 
694
0
Actually, if we're reusing the variables from earlier posts, I DID mean phi(x)...
 

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
Oh.. and so by "phi" you meant phi(x(z))?
 
694
0
No, I meant phi, as defined in post #2 :confused: 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

Science Advisor
Homework Helper
9,394
3
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Science Advisor
Homework Helper
Gold Member
4,771
7
I'm having trouble showing phi is an homomorphism. What I did:

consider x_1, x_2 in S(X). Then

[tex]\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})))[/tex]

But when it comes to

[tex]\phi(x_1)\cdot \phi(x_2)[/tex]

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

[tex]\phi(x_1)\circ \phi(x_2) = \phi(\phi(x_2))[/tex]

but [itex]\phi(x_2) \in S(Y)[/itex], not S(X). :frown:
 
694
0
[tex]\phi(x_1)\circ \phi(x_2) = \phi(\phi(x_2))[/tex]
That's false, and I'm not sure how you got that. Try this instead:

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

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
Ok ok ok. I understand my mitake. It's that [itex]\phi(x)[/itex] represents the permutation of S(Y) that phi associates to x. So it would make sense to write things like

[tex]\phi(x):Y\rightarrow Y[/tex],

[tex][\phi(x)](z) = f(x(f^{-1}(z)))[/tex]
 
694
0
Yes, precisely!
 

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
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:H\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.
 
694
0
Define your [tex]g \in S_{n - 1}[/tex] as

[tex]g(a) = f(a)[/tex]

for all [tex]a \in \{1, 2, ..., n - 1\}[/tex].
 

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
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:H\rightarrow S_{n-1}[/tex]
[tex](X,X,f) \mapsto (X\backslash \{n\}, X\backslash \{n\},f)[/tex]
 

matt grime

Science Advisor
Homework Helper
9,394
3
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.
 
Last edited:

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
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

[tex]h(a\cdot b) = h_{a\cdot b} = g\cdot a \cdot b[/tex]

and

[tex]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[/tex]

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

matt grime

Science Advisor
Homework Helper
9,394
3
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 possess the inverse operator so there's no real difference.
 
Last edited:

quasar987

Science Advisor
Homework Helper
Gold Member
4,771
7
matt grime said:
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:

[tex]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[/tex]
 
Last edited:

matt grime

Science Advisor
Homework Helper
9,394
3
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.
 

Related Threads for: Permutations (and isomorphisms)

  • Posted
Replies
11
Views
12K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
4
Views
7K
Replies
2
Views
2K
  • Posted
Replies
2
Views
2K
Replies
3
Views
541
  • Posted
Replies
2
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top