1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Abstract Algebra: Bijection, Isomorphism, Symmetric Sets

  1. Mar 13, 2016 #1

    RJLiberator

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    Suppose X is a set with n elements. Prove that Bij(X) ≅ S_n.

    2. Relevant equations
    S_n = Symmetric set
    ≅ = isomorphism

    Definition: Let G and G2 be groups. G and G2 are called Isomorphic if there exists a bijection ϑ:G->G2 such that for all x,y∈G, ϑ(xy) = ϑ(x)ϑ(y) where the LHS is operation in G and the RHS is operation in G2.

    3. The attempt at a solution

    So if we have a set X with n elements.
    A Bijection simply sends one element to some other unique element.
    The symmetric operation just sends one element to a unique other element as well.

    So clearly both sides have unique elements.

    IF we take ϑ(xy) in the Bij(x) that sends them to ϑ(x)ϑ(y) in the symmetric group

    I dont know enough about bijections to prove this tho.
     
  2. jcsd
  3. Mar 13, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Let ##Z(n)\equiv \{1,...,n\}##. Then ##S_n## is the set of all bijective maps from ##Z(n)## to itself.

    ##Bij(X)## is the set of all bijective maps from ##X## to itself.

    When we say ##X## has ##n## elements, we mean precisely that there exists a bijection ##\psi: X\to Z(n)##.

    Given all that, for any bijection ##\pi:X\to X##, we can construct a bijection ##F(\pi):Z(n)\to Z(n)## - by composing the maps ##\psi## and ##\pi## and/or their inverses in a suitable fashion. So construct that. If you're not sure, draw a four-cornered map diagram, with two adjacent corners being ##Z(n)## and two being ##X##.

    If there is an isomorphism of the sort you want, the map ##F:Bij(X)\to S_n## will be it.

    Then all you need to prove is that ##F## is one-to-one and onto, that is, that:

    1. ##F(\pi)=F(\pi')\Rightarrow \pi=\pi'##
    2. ##\forall \sigma\in S_n## there exists ##\pi:X\to X## such that ##F(\pi)=\sigma##

    Edit: I just realised you used the isomorphism symbol. So we not only need to prove that ##F## is a bijection. We also need to prove it's a homomorphism, that is, that

    3. ##F(\pi)\circ F(\pi')=F(\pi\circ\pi')## where ##\circ## denotes function composition.

    These three things, plus the initial construction of ##F##, are fairly straightforward. No tricks are needed.
     
  4. Mar 13, 2016 #3

    RJLiberator

    User Avatar
    Gold Member

    Thank you for the help. You are making this problem already much more clear to me.

    So, what I need to do is show that the composition of the two maps (aka F) are one to one and onto.

    I'm not quite sure what you mean by four-cornered map diagram. But I think you simply mean a square with the 4 corners being the points as you described.

    I can try to prove one-to-one and onto tomorrow with this understanding.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Abstract Algebra: Bijection, Isomorphism, Symmetric Sets
Loading...