Thread: proof modern algebra

Let f:G--->G' be a homomorphism of group (G, *) onto (G', *) with kernal K. Let H' be a subgroup of G'. Let H={x in G such that f(x) is in H"}. Prove H is a subgroup of G and that K is a subset of H.

What I know:

definition of homomorphism: for all a, b in G, f(a*b)=f(a)*f(b)

properties of homomorphisms: f(e)=e', where e is in G and e' is in G' and f(x^-1) = (f(x))^-1

Also, the kernal, K={a in G such that f(a) = e'}

To prove H is a subgroup of G, I need to show H is non-empty, closed, that * is associative in H, H has an identity, and H has inverses.

closed: for all a, b in H, a*b is in H
associative: since * is associative in G, it's associative in H
identity: there exists and e in H such that for all a in H a*e=e*a=a
inverses: for all a in H, aa^-1=a^-1a=e

I don't know how to start...please help.

You goal is to show H is a subgroup.
The multiplication * in H is inherited from the multiplication * in G, so the associativity property of that multiplication is also inherited.
The work is in showing that H is closed under *, that H is closed under *-inverses, and that the *-identity e is in H.
However, once you've shown that H is closed under *, and under *-inverses (and that H isn't empty), then if x in H, then so is x^-1, and so x*(x^-1) = e.
Thus the only work is to show that H is closed under *, and that H is closed under *-inverses.
Now those two things can actually be combined into a single thing, but since you're not comfortable with this stuff yet, maybe it's best if you show them each separately for now.

-------------------------------------------------------------------------------
So: You need to show two things. 1) H is closed under *. 2) H is closed under *-inverses.
Your work should look like this:
1) Claim H is closed under *.
Proof:
Let a, b in H.
Then ... (your arguments here)...
Therefore a*b in H. That proves that H is closed under *.

2) Claim H is closed under *-invereses.
Proof:
Let a in H.
Then ... (your arguments here)...
Therefore a^-1 in H. That proves that H is closed under *-inverses.
-------------------------------------------------------------------------------
The way to proceed is virtually forced. At each step, there's pretty much only one thing to say, and saying it will get you to your result.
In both proofs, you begin with something, x, in H. What can you do with that? There's only one thing conceivable to say next, because there's only one thing you know when x in H, and that's what the definition of H tells you.
So when you have x in H, you then basically have no choice but to write on the next line: "Therefore, f(x) is in H'."
OK, so then what? Well, you know nothing about H' except it's a subgroup of G'. But that tells you a lot. It tells you that H' is closed under multiplications and inverses in G'.
Not to give it all away to directly, from there, you'll have only one path to follow - use that f is a homomorphism.
From there, you'll have only one path to follow - use the definition of H again. At that point, you will have reached your desired conclusion and the claim will be proven.
-------------------------------------------------------------------------------
The idea of the proof is that we can use that " push it into H' ", then "use that H' is a subgroup" then "bring it back to H because f is a homomorphism" so that all those nice properties hold for H as well.

we don't really need to prove this (from johnsomeone's remarks above) but it might be instructive to see how these kinds of things work out:

the identity of G, e, is in H.

proof: e' is in H', and f(e) = e', so e is an element of G that f maps into H', so e is in H.

the set H (because we don't know yet it's a subgroup of G) is call the pre-image under f of H', often written like this:

H = f^-1(H').

now, we don't know that the set of homomorphisms from G to G' (a set often abbreviated as Hom(G,G')) forms a group, so we don't really think of f^-1as group inverse, so this notation can be confusing. for one thing, f^-1 might not even be a function, because we might have f(g₁) = f(g₂) = h, so we can't decide on a UNIQUE value for f^-1(h) (the pre-image contains at least two elements, g₁ and g₂).

in this notation:

ker(f) = f^-1({e'}).

********

what is really going on here:

the set of all g' in G' which HAVE some g in G with f(g) = g' is called the image of f, im(f) or f(G). this is a subgroup of G' (it might not be the entire group G', because f might not be surjective (onto)).

now f "shrinks" all of its kernel, ker(f), down to the single element e' in G'.

so watch what happens when we take an element of the form g*k, with k in ker(f):

f(g*k) = f(g)*f(k) = f(g)*e' = f(g).

for convenience, i'll write K instead of ker(f).

now K "splits" up G into K-sized pieces called (left) cosets of K (think of co- meaning like in co-pilot). the pieces look like this:

gK = {g*k: k in K}.

now all of these elements g*k, for each different k in K, all go to the same element of G', f(g).

so the "shrinkage" is "all across G", G shrinks "by a factor of (the size of) K".

it turns out that none of the different gK (for different g's) "overlap partially", either g₁K and g₂K are the same set, or they have nothing in common.

we say: the left cosets of K PARTITION G, and f respects this partition, sending different cosets to different elements of G'.

it also turns out that gK = f^-1(f(g)). here, we are doing "the opposite" of what f does, we're "inflating" f(G) by a factor of K.

since we have a 1-1 correspondence between the cosets gK, and the elements f(g) that lie in H, you might suspect that we can turn the cosets gK into a "group of sets", and we CAN (warning: this may fail for general subgroups of G. kernels are SPECIAL).

now in the group G', we have the following order of inclusion:

{e'} ≤ H' ≤ f(G) ≤ G'

in G, we have the following inclusions:

K ≤ f^-1(H') ≤ G.

this holds for ANY subgroup H' of G', and in fact we get the following 1-1 correspondence:

subgroups of G containing K = ker(f) <---> subgroups of f(G) = im(f)

(all the subgroups of G inside K "get shrunk to the identity" e' of G').

i don't know how clearly i am expressing this, but the very fact of a multiplication * on G limits the size of subgroup-pieces. it introduces a certain "regularity" into the internal structure of a group. homomorphisms (because they preserve products) have to conform to the regularity, and the kernel of a homomorphism f tells us "how much shrinkage" we get (and this shrinkage occurs at a uniform rate across all of G).

here is an example:

we have the homomorphism f:Z-->Z₄ given by f(n) = n (mod 4) (here the group operation is ordinary addition in Z, and addition mod 4 in Z₄)

this IS a homomorphism:

f(m+n) = m+n (mod 4) = m (mod 4) + n (mod 4) = f(m) + f(n).

what is IN ker(f)? ker(f) = {k in Z: k = 0 (mod 4)}. if k = 0 (mod 4), then k - 0 is a multiple of 4, so k is a multiple of 4.

on the other hand, if k = 4u, for some integer u, then f(k) = f(4u) = 4u (mod 4) = 0 (mod 4) (since 4u = 0 = 4u is a multiple of 4), so all multiples of 4 lie in the kernel.

hence ker(f) = 4Z = {4k: k in Z}, the multiples of 4.

now let's look at a subgroup of Z₄ = {[0],[1],[2],[3]} (i put brackets around them to remind you the elements of Z₄ aren't normal integers).

one subgroup is {[0}}. what is {k in Z: f(k) = [0]}? why, that's just the kernel of f.

another subgroup of Z₄ is H' = {[0],[2]}. what is f^-1(H')? well we already know the pre-images of [0], that's just ker(f) = 4Z.

how about the pre-images of [2]? suppose f(k) = [2]. this means k = 2 (mod 4), so k - 2 = 4t, for some integer t. thus k = 4t - 2 = 2(2t - 1).

so at the very least, pre-images of [2] are even integers.

now suppose k is an even integer, say k = 2u. what is f(k)? there are two cases:

1) u is even. in this case, u = 2v, so k = 2u = 2(2v) = 4v, so k is a multiple of 4, so f(k) = [0].
2) u is odd, say u = 2v+1. thus k = 2u = 2(2v+1) = 4v + 2, so k - 2 = 4v, thus k = 2 (mod 4), therefore f(k) = [2].

so the pre-images of [2] are the ODD multiples of 2 in Z.

so the set of ALL pre-images of {[0],[2]} are: {even multiples of 2} U {odd multiples of 2} = {all multiples of 2} = 2Z.

clearly, 2Z IS a subgroup of Z, and contains 4Z (the kernel of f) as a subgroup.

so what does f really do?

it sends every integer of the form 4k to [0]
it sends every integer of the form 4k+1 to [1]
it sends every integer of the form 4k+2 to [2]
it sends every integer of the form 4k+3 to [3]

any integer has one, and ONLY one of those 4 forms. that is our partition: every fourth integer goes in the same "clump":

[0] [1] [2] [3]
-4 -3 ..-2 ..-1
0... 1 ...2 ...3
4... 5 ...6 ...7

etc. (you'll have to imagine this extending to -∞ and +∞ in both directions since i can't list the ENITRE set of integers).

I don't really understand how to use the definition of H. I let h be an element of H. So by the definition of H, f(h) is in H'. I know you said that, but I'm still foggy...Since H' is a subgroup of G', H' is a group, with all the cool things that groups are known for. Now I need to use the fact that f is a homomorphism, but I don't know how to tie all that together. I know I'm seeming a bit dense, but I just don;t see this...

Amyw

2) Claim H is closed under *-inverses.
Proof:

here's "the other part":

suppose a,b are in H.

what, exactly does this mean?

it means that f(a), and f(b), are in H'.

now...let's look at a*b.

since f is a homomorphism:

f(a*b) = f(a)*f(b) (this is the defining rule that EVERY homomorphism obeys).

now f(a) and f(b) are both in H', and since H' is a SUBGROUP of G', we know that f(a)*f(b) IS in H' (subgroups are closed under multiplication).

but f(a)*f(b) is just f(a*b) (see above), so we know that f(a*b) is in H', thus a*b is in H.

we have proved: a*b is in H, whenever a,b are in H, so H is closed under multiplication.

********

so what happened here? we want to prove some stuff about H (a subset of G). we don't (at first) know too much about H, except that everything in it gets sent by f to H'.

but f is a homomorphism, and we can use that fact to prove stuff about H, given stuff we already know about H' (in particular, that H' is a subgroup of G').

let's look one more time at what being a homomorphism means:

f(a*b) <---this is a statement about a*b, which is in G

= f(a)*f(b) <---this is a statement about f(a),f(b), which lie in G'.

in other words, f "connects" or "links", "group properties of G" to similar properties in f(G) (a subset, actually a subgroup, of G').

********

in johnsomeone's post above, we have:

e' = f(e) = f(a*a^-1) = f(a)*f(a^-1).

since f(a^-1) is "something" that when multiplied by f(a) gives e', the identity of G', it MUST be the inverse of f(a) (because that is how inverses are defined. think about it, for example with rational numbers x,y:

if x + y = 0, then y has to be -x.

if xy = 1, then y has to be 1/x.

that's what inverses DO, "undo the multiplication" e*a = a, to get back to e again. sometimes an identity is called "a neutral element", because "it does nothing").

now if f(a) is in H' (which is what happens when a is in H), BECAUSE H' IS A SUBGROUP, it has all inverses (every subgroup is a group unto itself, and therefore must obey all the group axioms).

so we know [f(a)]^-1 is in H'. and because of what we just did above (and in the previous post), we know that [f(a)]^-1 = f(a^-1).

but this means that a^-1 (which up till now we might have suspected was only in G, and not in the subset H), is in fact, in H, since f takes it to an element of H'.

*********

what homomorphisms DO, is preserve "group-ness". in other words:

they take products to products
they take identities to identities
they take inverses to inverses

part of the cool thing about (group) homomorphisms is, once we know the first fact (that products are preserved), we get the second 2 "for free". this is a feature restricted to groups, it turns out that in less restrictive structures like monoids (which may lack inverses), or semi-groups (which may lack inverses AND an identity), just knowing a map preserves products is no guarantee it will preserve identities OR inverses.

*********

i suppose it's only fair we prove that for a homomorphism f:G→G', we prove that f(e) is in fact the identity e' of G'.

note that for any x in f(G), we have x = f(g), for some g in G.

now x*f(e) = f(g)*f(e) = f(g*e) = f(g) = x (because f is a homomorphism. this is KEY).

thus: x^-1*(x*f(e)) = x^-1*x (certainly we can multiply both sides by x^-1, which is some element of G', since G' is a group).

(x^-1*x)*f(e) = e'

e'*f(e) = e'

f(e) = e'

***********

perhaps you are thinking: ok, but this is all for "abstract" groups, what does a real honest-to-god homomorphism LOOK like?

consider the following two groups (very important ones!):

G = (R⁺,*), the group of all POSITIVE real numbers under multiplication.
G' = (R,+), the group of ALL real numbers under addition.

the function f(x) = log(x) is a homomorphism, because:

log(xy) = log(x) + log(y)

note that log(1) = 0 (preservation of identity), and log(1/x) = log(x^-1) = (-1)log(x) = -log(x) (preservation of inverses).

for another example, let G = (Z,+) the addtive group of integers (and a very "friendly group". learn to love it). and let G' = (2Z,+) (the "even integers").

here, our homomorphism is f(x) = 2x (the "doubling" function).

it preserves products: f(x+y) = 2(x+y) = 2x + 2y = f(x) + f(y)
it preserves the identity: f(0) = 2(0) = 0
it preserves inverses: f(-x) = 2(-x) = -(2x) = -f(x).

the idea of a homomophism is pretty simple:

take 2 things
multiply them
send them into another group

EQUALS

take 2 things
send them both into another group
multiply them

because the only things we have to say about a group G have to do with its group operation, homomorphisms preserve most of those things we can say.