Thread: function from quotient group to orbit, well defines, 1-1, onto

f: G/G_s------>Os, defined by f(gG_s)=gs.
O_s={s'in S st s'=gs for some g in G}
G_s={g in G st gs=s}

I am supposed to show f is well defined, 1-1, and onto.

I know that to be well defined, if a=b then f(a)=f(b). In this case I think that would mean, if g₁G_s=g₂G_s, then g₁s=g₂s. So I assume that g₁G_s=g₂G_s is true. Does that mean that g₁₌g₂? If so, can I then substitute a generic g in for g₁ and g₂?

I know 1-1 means that if f(a)=f(b), then a=b. For this case, if g₁s=g₂s, then g₁G_s=g₂G_s. _{So I assume} g1s=g2s, and show g1Gs=g2G_s. Since g1s=g2s, g₁=g₂? Am I allowed to divide by s? I know I can't multiply by the reciprocal because S isn't a group, it's a set.

I know that onto means that for every element in the codomain-y_, there exists and element in the domain-x with f(x)=y. So in this case, for every element in O_s, the orbit of s, there must exist an element in the domain, the quotient group of G_s in G (which is the (left) cosets of G_s in G) with f(g'G_s)=g's? I really don't know what to do here?

Any guidance would be appreciated.

it's often customary to write g.s instead of gs, just so we don't get confused and think gs is a product in G.

here's the thing: we want to make sure that f(gG_s) only depends on the coset gG_s, and not on which "representative" g we pick.

(in other words, we might have gG_s = g'G_s, for different g,g' and we need to be sure that we get the same value for f, that gs = g's).

now gG_s = g'G_s DOES NOT MEAN g = g'. what it DOES mean is that: g'^-1g is in G_s.

and (by the definition of G_s) that means:

g'^-1gs = s.

now what we CAN do, is have g' act on both sides (both sides are elements of S). this gives:

g'(g'^-1gs) = g's (*)

now, for ANY action of a group G on a set S, for g,h in G, we have:

g(hs) = (gh)s. in our situation that means (looking at the LHS of (*)):

g'(g'^-1gs) = (g'(g'^-1g))s = ((g'g'^-1)g)s = (eg)s = gs, so NOW we have gs = g's, as desired.

***********

for your second problem, we need to pick two elements f(gG_s) in the orbit of s (Os), and show that if they are equal, they are images of the same coset of G_s.

in short, we need to show gs = g's implies gG_s = g'G_s (as luck/fate would have it, this is the REVERSE implication of showing f is well-defined).

now you can't "divide by s" (S is just a set, it may not have any "multiplication/division" structure).

what you CAN do, is act on both sides by g'^-1.

this gives:

g'^-1(gs) = g'^-1(g's), and BECAUSE WE HAVE AN ACTION:

(g'^-1g)s = (g'^-1g')s = es = s (because with a group action es = s, for all s in S).

but this tells us that g'^-1g stabilizes s (or fixes s, when we act on s by g'^-1g, nothing happens, we "stay" at s).

and THIS means that therefore g'^-1g is in the stabilizer of s, which is what G_s is.

but if g'^-1g is in G_s, then the two cosets g'G_s and gG_s are equal, and we're done.

finally, what we need to show is that the function f is ONTO Os.

that is, given an element in Os, say, t, for example, we need to find "some coset" of G_s, gG_s with f(gG_s) = t.

since t is in the orbit of s, t = gs, for some g in G. so why not try the coset gG_s (for that same g).

well, then we have f(gG_s) = gs (by the definition of f), and gs = t, so, yep, that works.

**************

i suspect that part of your trouble is you are having difficulty seeing how this all works. so let's find a simple G and a simple set S to actually work with.

let G be this subgroup of S₄: G = {e, (1 2 3 4), (1 3)(2 4), (1 4 3 2)}. this is a cyclic group of order 4.

what set shall we have G act on? well an obvious choice is S = {1,2,3,4}.

so for g = (1 2 3 4), and s = 3, for example, gs = 4. note that the only element of G that stabilizes anything is e, so for all s, G_s = {e}.

what is the orbit of 1? well 2 = (1 2 3 4)1, 3 = (1 3)(2 4)1, and 4 = (1 2 3 4)1, so the orbit of 1 is all of S.

so what we did above shows we have a bijection between G/{e} (= G) and O1 = S:

e ---> 1
(1 2 3 4) ---> 2
(1 3)(2 4) ---> 3
(1 4 3 2) ---> 4

let's pick a different G, and a different S. this time we'll pick S = G, and we'll let G = {e,a,a²,b,ab,a²b}, where a³ = b² = e, and ba = a²b. this time, our action will be:

g.x = gxg^-1.

we can ask, what is the orbit of a? let's find out:

eae^-1 = a
aaa^-1 = a
a²aa^-2 = a
bab^-1 = bab = (a²b)b = a²
(ab)a(ab)^-1 = (ab)a(ab) = a(ba)ab = a(a²b)(ab) = a³(bab) = bab = a²
(a²b)a(a²b)^-1 = (a²b)a(a²b) = a²ba³b = a²b² = a².

so the orbit of a is {a,a²}.

looking above, we see that the elements of G that stabilize a, are {e,a,a²}, which is <a>. and what we did above says we have a bijection between:

G/G_a = G/<a> and Oa.

it is easy to see that the (left) cosets of <a> are <a> and b<a>. the bijection we established above is:

<a> <---> {a}
b<a> <---> {a²}

Okay...this is beginning to make some sense. I have some follow up questions.

In the section about well defined, you wrote, "now gGs = g'Gs DOES NOT MEAN g = g'. what it DOES mean is that: g'-1g is in Gs." I don't understand why g'-1g is in Gs if gGs = g'Gs. Is that a definition or a property I just don't know or remember? or did you multiply both sides by g'-1? If so, you get g'-1gGs=Gs. So that means that g'-1g is an element of Gs. I don't understand why.

In the section on 1-1, you wrote but if g'-1g is in Gs, then the two cosets g'Gs and gGs are equal, and we're done. I think my question here is the same as the one above. I think I am missing something fundamental, and I don't know where to find it...

you wrote, "i suspect that part of your trouble is you are having difficulty seeing how this all works. so let's find a simple G and a simple set S to actually work with.

let G be this subgroup of S4: G = {e, (1 2 3 4), (1 3)(2 4), (1 4 3 2)}. this is a cyclic group of order 4.

what set shall we have G act on? well an obvious choice is S = {1,2,3,4}.

so for g = (1 2 3 4), and s = 3, for example, gs = 4. note that the only element of G that stabilizes anything is e, so for all s, Gs = {e}."

I don't understand how gs = 4. Actually, I don't understand how any of this actually works. I feel like I need remedial abstract algebra...

it comes from THIS theorem:

two (left) cosets of a subgroup H of a group G, aH and bH, are equal if and only if b^-1a is in H.

proof: suppose aH = bH. since a = ae is in aH, and aH = bH, we have a = bh, for some element h in H.

thus:

b^-1a = b^-1(bh) = (b^-1b)h = eh = h is in H.

on the other hand, suppose that b^-1a is in H, so b^-1a = h, for some h in H.

then a = ea = (bb^-1)a = b(b^-1a) = bh.

so for any element ah' of aH, we have ah' = (bh)h' = b(hh').

since hh' is in H (because subgroups are closed under multiplication), ah' is in bH. thus aH is contained in bH.

on the other hand, if b^-1a = h, then (b^-1a)^-1 = a^-1b = h^-1 is also in H.

this means b = ah^-1.

so for any element bh" in bH, we have bh" = (ah^-1)h" = a(h^-1h"), where h^-1h" is in H,

so bh" = a(h^-1h"), which is in aH. thus aH is contained in bH. since the two sets contain each other, they are equal.

*****

to sum this all up, saying aH = bH or saying b^-1a is in H are equivalent conditions, one is always true when the other is.

in fact, we can define an equivalence (called "equivalence modulo H") on G by: a~b if b^-1a is in H.

the equivalence class of a under this equivalence is just the left coset of a, aH = {ah: h is in H}.

an equivalence is just a fancy name for a partition of a set: any partition generates an equivalence relation:

a~b if a,b lie in the same subset of a partition.

and any equivalence generates a partition of the set it is on: the equivalence classes.

*****

now to your second question. let me explain what "cycle-notation" of a permutation means. when i write: (1 2 3 4), i mean the following function:

f:{1,2,3,4}-->{1,2,3,4} given by:

f(1) = 2
f(2) = 3
f(3) = 4
f(4) = 1

as you can see, this is a 1-1, onto function on the set {1,2,3,4}. so (1 2 3 4) should be read as:

"1 goes to 2, 2 goes to 3, 3 goes to 4, 4 goes back to 1".

this is called a 4-cycle, and you could picture it like a clock dial, with 1 at the 12 o' clock position, 2 at the 3 o' clock position, 3 at the 6 o'clock position, and 4 at the 9 o'clock position, and arrows between them (going...clock-wise. see what i did there?).

what happens if we perform f twice?

f(f(1)) = f(2) = 3
f(f(2)) = f(3) = 4
f(f(3)) = f(4) = 1
f(f(4)) = f(1) = 2

so f² is the function:

1-->3
2-->4
3-->1
4-->2

in cycle notation, 1-->3, and 3-->1 so we start with the 2-cycle (1 3) (this means 1 and 3 change places). 2 and 4 also change places, so f² = (1 3)(2 4).

ok, what about f performed 3 times in a row?

f(f(f(1))) = f(f(2)) = f(3) = 4
f(f(f(2))) = f(f(3)) = f(4) = 1
f(f(f(3))) = f(f(4)) = f(1) = 2
f(f(f(4))) = f(f(1)) = f(2) = 3, so the function f³ is:

1-->4
2-->1
3-->2
4-->3

in cycle notation this is (1 4 3 2).

finally, let's look at f performed FOUR times in a row:

f(f(f(f(1)))) = f(f(f(2))) = f(f(3)) = f(4) = 1
f(f(f(f(2)))) = f(f(f(3))) = f(f(4)) = f(1) = 2
f(f(f(f(3)))) = f(f(f(4))) = f(f(1)) = f(2) = 3
f(f(f(f(4)))) = f(f(f(1))) = f(f(2)) = f(3) = 4

so we see that f⁴ is the function:

1-->1
2-->2
3-->3
4-->4

which is the identity function on the set {1,2,3,4}.

so when i write (1 2 3 4)3, what i MEAN is f(3), which is 4.

similarly, when i write (1 3)(2 4)1, what i mean is f²(1) which is f(f(1)) = f(2) = 3.

********

permutations of a set S = {a,b,c....,x} are just "rearrangements of that set". we can identify a permutation (re-arrangement) uniquely with a bijective function on S.

for example, if our set is {a,b,c} we can identify the re-arrangement abc --> cba with the function:

a-->c
b-->b
c-->a

so if we want to call our function f:

f(a) = c
f(b) = b
f(c) = a.

the things we're "re-arranging" don't really matter, all that really matters is how MANY of them there are. so it's customary to use the set {1,2,...,n} where:

1 = "first thing"
2 = "second thing"
etc.

now, the reason i'm going on at length about permutations is this:

an ACTION of a group G on a set S, is really this:

for every g in G, we get a PERMUTATION of S, defined by:

s--->gs

the group of permutations on a set S, forms a group, called Sym(S) (the symmetric group of S), and our action is really a homomorphism from G to Sym(S).

that is for every ELEMENT g of G, we get a MAPPING g_ :S-->S with g_(s) = gs.

this let's us "multiply" set-elements by a group element we set g.s = g_(s) = gs. this multiplication takes a pair (g,s) and spits out an element gs in S.

if S is a FINITE set, with n elements, then Sym(S) is isomorphic to S_n.

and yes, elements of S_n (which are bijective functions on the set {1,2,...,n}) have a natural action on this set,

if the permutation g takes a to b, then we set ga = b.

in naive terms, we use a group G to "shuffle" elements of S. the possible places an element s may wander during this shuffling, is called the ORBIT of s.

now some elements of G may not touch s at all during this shuffling process. these elements are called the stabilizer of s, and it turns out they form a subgroup of G.

an example (again).

using S₃, consider the permutation:

1-->3
2-->2
3-->1 this is usually called (1 3).

if we let this group act on {1,2,3} in the natural way, we can ask: what is the stabilizer of 2?

well the identity stabilizes 2 (since it stabilizes EVERYTHING, nothing moves under the identity). and as you can see (1 3) also stabilizes 2 (it only moves 1 & 3, by swapping them).

it turns out that everything else moves 2, so

Stab(2) = {e, (1 3)}.

(Stab(x) is another way that G_x is written).

now the permutation:

1-->2
2-->3
3-->1 ...this is usually written (1 2 3)

takes 2 to 3. so (1 2 3) is not in the stabilizer of 2, and also it shows that 3 is in the orbit (under S₃'s action) of 2.

and the permutation:

1-->1
2-->1
3-->3 ...this is written (1 2)

takes 2 to 1, so it's not in the stabilizer of 2, and it shows 1 is in the orbit of 2.

so the orbit of 2 is {1,2,3} which is our entire set.

so from what we JUST proved (from your original post), there had better be just 3 cosets of Stab(2).

the theorem we are talking about is called "the orbit-stabilizer theorem" and it says:

"the size of an orbit of an element s, is equal to the index of the stabilizer of s"

(the index of a subgroup is the number of cosets there are).

for a finite group G, the index of H in G, [G:H] is equal to |G|/|H|.

so the orbit stabilizer theorem (for a finite group) can be written:

[G:G_s] = |Os|, or, if we like:

|G| = |Os|*|G_s|.

in our example for G = S₃, S = {1,2,3} and s = 2, this becomes:

6 = |S₃| = |{1,2,3}|*|Stab(2)| = 3*2.

********

just for completeness' sake, let's compute the left cosets of H = Stab(2) = {e, (1 3)}. they are:

H = {e, (1 3)}
(1 2 3)H = {(1 2 3)e, (1 2 3)(1 3)} = {(1 2 3), (2 3)}

here is how we compute (1 2 3)(1 3). first we take the function (1 3):

1-->3
2-->2
3-->1

next we apply the function (1 2 3):

1-->3-->1
1-->2-->3
3-->1-->2, we see the result is:

1-->1
2-->3
3-->2, which is (2 3) (2 and 3 swap places).

and our last coset:

(1 3 2)H = {(1 3 2), (1 2)}

what is the bijection between these cosets and the orbit of 2?

H<--->2 (these elements of S₃ send 2-->2)
(1 2 3)H <---> 3 (these elements of S₃ send 2-->3)
(1 3 2)H <---> 1 (these elements of S₃ send 2-->1)

everything works out just as the theory says it should.

This has been very helpful. Thanks so much for taking the time to explain this to me.