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]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutations (and isomorphisms)
  1. Are they isomorphic? (Replies: 4)

  2. Isomorphic Subfields (Replies: 1)

  3. Isomorphic groups (Replies: 12)

Loading...