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!

Homework Help: An abstract algebra question

  1. Sep 26, 2011 #1
    1. The problem statement, all variables and given/known data
    Let T be a subset of S and consider the subset U(T)={f [itex]\in[/itex] A(S) | f(t)[itex]\in[/itex]T for every t[itex]\in[/itex]T}.
    1) If S has n elements and T has m elements, how many elements are there in U(T)?
    2) Show that there is a mapping F:U(T) -> Sm such that F(fg)=F(f)F(g) for f,g[itex]\in[/itex]U(T) and F is onto Sm
    3) If m<n, can F ever be 1-1? If so, when?

    3. The attempt at a solution
    1) m!*n! ?

    2) I've already shown in the previous problem (Problem 18 in baby Herstein) that if f and g are in U(T), so is their product fg. Now, If I define F as a function that takes an element in U(T) and restricts the domain to only the elements in T and I denote it by F=f[T], then It's obvious that the mapping F=f[t] under composition satisfies F(fg)=F(f)F(g). because F(fg)=(fg)[T]=f[T]og[T]=F(f)F(g). To show that this mapping is surjective, for any element in Sm like h one could define the element f={ f(n)=h(n) for every t in T & f(n)=n otherwise}, It's obvious that F(f)=h, hence, F is onto Sm.

    3) No, F is not injective. because If we assume T={1,2,3} and S={1,2,3,4,5,6} and we consider the mapping F:U(T)->S6 and then we define f(1)=2 f(2)=3 f(3)=1 f(4)=4 f(5)=5 and g(1)=2 g(2)=3 g(3)=1 g(4)=5 g(5)=4, then both f and g are mapped to the same element in S6. However, we can define another map that is injective. we define f~g iff F(f)=F(g). we define the equivalence class of f as [f]={g| f~g} and we define the quotient set U(T)/~ as U(T)/~={[f]|f[itex]\in[/itex]U(T)}. We define [f][g]=[fg] and It's easy to show that this multiplication law is well-defined on U(T)/~ and it turns U(T)/~ into a group. then the mapping F': U(T)/~ -> Sm is injective.
    I guess We can also reform F in another way. We can form a subgroup of U(T) by choosing only those permutations that permute the elements in T to new elements in T and keep the rest as they are. This is a subgroup of U(T) that I like to denote it by K and It's obvious that composition of permutations is a well-defined operation over it. The mapping F'': K->Sm is injective.

    Well, I just wanna know whether my proof is correct or not.
    Last edited: Sep 26, 2011
  2. jcsd
  3. Sep 26, 2011 #2
    Could you explain your notation first?? That is=

    What is S??
    What is A(S)?? We must have [itex]f(t)\in [/itex] what?

    What is U(T)?

    Is Sm the group of permutations on m elements?
  4. Sep 26, 2011 #3
    I had made a lot of typos. sorry. I edited my post. and yes, Sm is the group of permutations on m elements. S can be any countable set.
  5. Sep 26, 2011 #4
    And what is A(S)?
  6. Sep 26, 2011 #5
    The group of bijective maps on S under composition.
  7. Sep 26, 2011 #6
    This is incorrect. Your m! factor is correct. but I don't see where the n! comes from.

    I can see that your idea is correct, but your notations are not. I find it hard to see what you mean with things like F=f[T] or F=f[t].

    OK, but your codomain is incorrect. It needs to be [itex]S_3[/itex] in this case, no?

    Furthermore, you can't just assume T={1,2,3} and S={1,2,3,4,5,6}. You must show it in ALL cases. I think a cardinality argument should be your best bet here.
  8. Sep 26, 2011 #7
    Well, I was chatting and listening to music when I was writing this post, that's why It's full of typos :|. I meant m!*(n-m)!. because we got n-m choices for the remaining elements.

    by f[T] I mean that we restrict the domain of f to the elements in its domain that are in T. the same notation as f|T. (I guess most books prefer the later notation).

    Yes. Typo! :|

    Yea, the Pigeonhole principle would do the trick. |T|>|Sm|, therefore there is no 1-1 injective function F: T-> Sm. well, if it doesn't work for one Sm, Wouldn't that be a counter-example?

    Is everything OK now?
  9. Sep 26, 2011 #8
    Correct! :smile:

    Hmm, it's the first time I see that notation. But I guess it makes sense.

    Yes, your example certainly is a counterexample! But they're asking whether the equality ever holds. This requires you to show that it can never be an injection. Just finding a counterexample is not good enough here.
  10. Sep 26, 2011 #9

    I see. Would it work if we change U(T) in the way I said? I think I've unintentionally used the first isomorphism theorem for this particular example.
  11. Sep 26, 2011 #10
    But your pigeonhole-argument is a good one!! Just show that the cardinalities do not agree. In that case, a surjective function can never be injective.

    I don't really see what you want to accomplish by changing the U(T).
  12. Sep 26, 2011 #11
    the cardinalities surely do not agree, cuz the first one has |T|=m!(n-m)! elements and |Sm| has m! elements. That's not what I asked though.

    I just wanna know whether my argument about finding a new mapping that is injective is correct or not. because I see a similarity between my argument and the first isomorphism theorem but nowhere I've used the fact that U(T) is normal. So, either it must be false in general or U(T) is a normal subgroup of Sn by chance. Am I right?
  13. Sep 26, 2011 #12
    What you did there is quotienting out of ker(F). So you indeed did something similar to the first isomorphism theorem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook