An abstract algebra question

  • Thread starter AdrianZ
  • Start date
  • #1
319
0

Homework Statement


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?

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:

Answers and Replies

  • #2
22,097
3,283
Could you explain your notation first?? That is=

Homework Statement


Let T be a subset of S
What is S??
and consider the subset {f [itex]\in[/itex] A(S) | f(t)[itex]\in[/itex] for every t[itex]\in[/itex]T}.
What is A(S)?? We must have [itex]f(t)\in [/itex] what?

1) If S has n elements and T has m elements, how many elements are there in U(T)?
What is 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
Is Sm the group of permutations on m elements?
 
  • #3
319
0
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?
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.
 
  • #4
22,097
3,283
And what is A(S)?
 
  • #5
319
0
And what is A(S)?
The group of bijective maps on S under composition.
 
  • #6
22,097
3,283

Homework Statement


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?

The Attempt at a Solution


1) m!*n! ?
This is incorrect. Your m! factor is correct. but I don't see where the n! comes from.

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.
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].

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
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.
 
  • #7
319
0
This is incorrect. Your m! factor is correct. but I don't see where the n! comes from.
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.


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].
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).


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

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.
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?
 
  • #8
22,097
3,283
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.
Correct! :smile:

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).
Hmm, it's the first time I see that notation. But I guess it makes sense.

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?
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.
 
  • #9
319
0
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.

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.
 
  • #10
22,097
3,283
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.
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).
 
  • #11
319
0
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).
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?
 
  • #12
22,097
3,283
What you did there is quotienting out of ker(F). So you indeed did something similar to the first isomorphism theorem.
 

Related Threads on An abstract algebra question

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
4
Views
986
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
897
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
2
Views
2K
Top