Sunday, March 15, 2009

A Little Math Before Bedtime

Frequently, I'll swap my current novel for an old college math book before bedtime. It calms my mind since, as most of you know, my thoughts typically race from one idea to the next. The latest book I've been re-reading is my Abstract Algebra book which I used for a required three-course series for my B.S. in Mathematics. I've been stuck on a particular problem and felt like journaling about it here. I realize that most readers of this post will be bored to tears. However, this is my blog, and I'm going to write about what I want. :-)

Here's the setup. I'm done reading about functions and permutations. In the homework problems for permutations, I'm on a section that focuses on the properties of permutations of a set A. The symmetric group on A, SA, is the set of all the permutations of A. In all the problems, G is a subset of SA, and you have to prove that G is a subgroup of SA given specific information. I'm stuck on the 4th problem. I'll go through #1-3 first, giving informal proofs along the way.

1. Let A be a set and a be an element of A. Let G be the subset of SA consisting of all the permutations f of A such that f(a)=a. Prove that G is a subgroup of SA. To prove this, you have to show closure for operation (composition) and for inverses.
  • Let g be an element of G. Then g(a)=a. f(g(a))=f(a)=a, and g(f(a))=g(a)=a. Therefore, G is closed with respect to composition.
  • If f(a)=a, then f-1(a)=a. Therefore, G is closed under inverses.
2. If f is a permutation of A and a is an element of A, we say that f moves a if f(a) doesn't equal a. Let A be an infinite set, and let G be the subset of SA which consists of all the permutations f of A which move only a finite number of elements of A. Prove that G is a subgroup of SA.
  • When performing fog and gof, the number of elements that get moved are at most the combined total number of finite moveable elements of each permutation. So if {a1,..., am} are the moveable elements of f and {b1,...,bn} are the moveable elements of g, and both sets of moveable elements are mutually exclusive; then fog and gof have at most the combined total number from both sets of finite moveable elements. Since this number of elements is finite, composition is closed for G.
  • Elements of f and g that don't move are of the form f(x)=x. This keeps the images of the moveable elements within the set of finite moveable elements because f-1(x)=x and permutations are bijective. Therefore, if ai and aj are moveable elements of f, then f(ai)=aj and f-1(aj)=ai. The inverse of a f has a finite number of moveable elements. Hence, G is closed under inverses.
3. Let A be a finite set, and B a subset of A. Let G be the subset of SA consisting of all the permutations f of A such that f(x) is contained in B for every x in B. Prove that G is a subgroup of SA.
  • Let g be a permutation contained in G. If x is in B, then g(x) is in B. Since g(x) is in B, then f(g(x)) is in B as well. Similarly you can prove that [gof](x) is in B. Therefore, G is closed under composition.
  • Since the images of all the elements of B are in B and permutations are bijective, then f-1 carries elements of B to B, too. Therefore, G is closed under inverses.
4. Give an example to show that the conclusion of #3 is not necessarily true if A is infinite. This is where I got stumped. The only ideas I have are these:

B could be infinite which could affect the outcome. If B was infinite, then it might be possible for an element outside of B to have an image in B. Although that wouldn't make any sense since G is bijective. I cannot for the life of me think of a counterexample where either [fog] or f-1 isn't in B, especially since permutations are bijective. I'm a little muddy on how A being infinite would change anything.

Knitting News? Well, I'll save that for next time since I'm willing to bet that no one is reading this anyway ;-)

No comments: