Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations (and isomorphisms)

  1. Jul 11, 2005 #1

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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. jcsd
  3. Jul 12, 2005 #2
    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
  4. Jul 12, 2005 #3

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    f o x o f^-1 would write f^1(x(f)).. but what is the function x(f)?
     
  5. Jul 12, 2005 #4
    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).
     
  6. Jul 12, 2005 #5

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    My post had an error too :smile:

    I meant to write f o x o f^-1 = f(x(f^-1)).
     
  7. Jul 12, 2005 #6

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Mmmh, but still, thus defined, phi sends an element of Y to another element of Y, not of S(X) to S(Y).
     
  8. Jul 12, 2005 #7
    No it doesn't. I believe you're confusing "phi" with "phi(x)".
     
    Last edited: Jul 12, 2005
  9. Jul 12, 2005 #8

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    surely you meant "phi(z)" :wink: but I get your point.
     
  10. Jul 12, 2005 #9
    Actually, if we're reusing the variables from earlier posts, I DID mean phi(x)...
     
  11. Jul 12, 2005 #10

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Oh.. and so by "phi" you meant phi(x(z))?
     
  12. Jul 12, 2005 #11
    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.
     
  13. Jul 12, 2005 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Jul 12, 2005 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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).
     
  15. Jul 12, 2005 #14

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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:
     
  16. Jul 12, 2005 #15
    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.
     
  17. Jul 12, 2005 #16

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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]
     
  18. Jul 12, 2005 #17
    Yes, precisely!
     
  19. Jul 12, 2005 #18

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  20. Jul 13, 2005 #19
    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].
     
  21. Jul 13, 2005 #20

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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]
     
  22. Jul 13, 2005 #21

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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: Jul 13, 2005
  23. Jul 13, 2005 #22

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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:
     
  24. Jul 13, 2005 #23

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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: Jul 13, 2005
  25. Jul 13, 2005 #24

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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: Jul 13, 2005
  26. Jul 13, 2005 #25

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook