Some group theory questions

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Some group theory questions

I feel I must be a bit dense at not getting this one, but maybe it really is as hard as it appears to me to be. Wikipedia says that the group of real numbers R under addition is an example of a non-Hopfian group (isomorphic to a non-trivial factor group of itself). I'm finding it pretty tough though to think of a surjective endomorphism on R which isn't injective. It just feels like any surjective homomorphism which sends a non-trivial element to the identity is going to somehow break the group structure; obivously that's not the case if one exists, but it seems to be getting in the way. I feel like something involving the floor function would work, but I've not found anything yet after playing about with maps like x->floor(x/2)+x. Any help would be greatly appreciated.
Last edited by Talith on Mon Mar 12, 2012 4:04 pm UTC, edited 1 time in total.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

Talith wrote:I feel I must be a bit dense at not getting this one, but maybe it really is as hard as it appears to me to be. Wikipedia says that the group of real numbers R under addition is an example of a non-Hopfian group (isomorphic to a non-trivial factor group of itself). I'm finding it pretty tough though to think of a surjective endomorphism on R which isn't injective. It just feels like any surjective homomorphism which sends a non-trivial element to the identity is going to somehow break the group structure; obivously that's not the case if one exists, but it seems to be getting in the way. I feel like something involving the floor function would work, but I've not found anything yet after playing about with maps like x->floor(x/2)+x. Any help would be greatly appreciated.

I think that you're being too "nice". Start with a basis for the reals as a field over the rationals. Any vector endomorphism from R to R will also be a group endomorphism (addition of real numbers thought of as vectors over Q is addition of real numbers). Fix a countable subset of the basis, {a_i}. Define a linear map that sends a_1 to zero, and a_i to a_{i-1}. That looks like it works to me, though I'm prepared to be convinced that I've missed something.

I think anything that doesn't use choice wont get you there, but that's just a feeling.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: the reals are a non-hopfian group

Is that map well defined when, R as a vector space over Q, isn't a countable dimensional vector space? Or is that ok if you're invoking the WOT to send some least basis element to zero?

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

Its well defined in my head, just not on paper . Let B be a basis for R over Q. Partition B into A={a_i}_{i in N} and B' = B\A. A linear map is well defined if you know the image of the basis elements. For basis elements in A, f(a_1) = 0, f(a_i) = a_{i-1} for i>1, and f(b) = b for b in B'. f is well defined, has a non trivial kernel, and is onto.

So, I forgot to tell you what happens on the rest of the basis. R is definitely not a countable dimensional vector space over Q, and just to get B you need to use choice. Picking a countable subset and a map from that countable subset to the naturals assumes no more than I used to get the basis.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: the reals are a non-hopfian group

Ah right I see it now, it's actually a nice little arguement. That's definitely an order of magnitude more complicated than the sort of difficulty I was expecting this seemingly harmless theorem to be. This seems to be one of those propositions which is equivalent to the AoC (or at least a weaker version).

As a slight follow up; I'm looking for an example of a non-Hopfian group that I can use as an example in a project I'm writing. I'm not sure if the reals is a good idea for an example now - the ideas used in your proof seem to be too far removed from the pretty standard group theoretic ideas in the rest of the project. Any other example I can think of seems to be a little too simple to show (eg the circle group). Any idea's on an example that would be a reasonable difficulty?

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

The circle is a lot better than the one I immediately thought of, Z direct summed with itself an infinity of times. The free group on two generators can maybe be made to work too? Or Z_2 + Z_4 + Z_8 + ... + Z_{2^n} + ... ?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: the reals are a non-hopfian group

jestingrabbit wrote:I think anything that doesn't use choice wont get you there, but that's just a feeling.

In fact, this is equivalent to a question I've wondered about before: is ZF+"every Q-linear transformation from R to R is also R-linear" consistent? I suspect the answer is yes, but I'm not sure how to prove it.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: the reals are a non-hopfian group

Finitely generated free groups are Hopfian actually, this is the main result I needed to get out of all of this Hopfian business. The infinite sum of cyclic groups looks like it might be nice, I'll have a play about with that. Thanks for the help.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

skeptical scientist wrote:
jestingrabbit wrote:I think anything that doesn't use choice wont get you there, but that's just a feeling.

In fact, this is equivalent to a question I've wondered about before: is ZF+"every Q-linear transformation from R to R is also R-linear" consistent? I suspect the answer is yes, but I'm not sure how to prove it.

I'm glad I'm in good company, and you will of course understand that I can't help you at all. Its clear that ZF+L(R) (known to be as consistent as ZF I believe) implies your statement, but I can't see how to work out if there are models of your axioms with not L(R). I mean, what is true about non measurable sets in general?? If they exist, can I get a Vitali set?

This is all that weird stuff with models that I just don't get at all, and so will shut up about.

Talith wrote:Finitely generated free groups are Hopfian actually, this is the main result I needed to get out of all of this Hopfian business.

Then I will stop thinking about making F_2 work. Thanks.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: the reals are a non-hopfian group

jestingrabbit wrote:I'm glad I'm in good company, and you will of course understand that I can't help you at all. Its clear that ZF+L(R) (known to be as consistent as ZF I believe) implies your statement, but I can't see how to work out if there are models of your axioms with not L(R).

What is L(R)? Are you saying that ZF proves that if R is a non-hopfian group, then there is a non-measurable set? How does that go? Can you show there is a Vitali set? Does ZF prove that every Vitali set is nonmeasurable? At least ZF+ACω implies every Vitali set is nonmeasurable.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

L(R) is every subset of the reals is measurable. I was thinking that R being non-hopfian would imply the existence of a non measurable set, as I think that any Q-linear, non R-linear transformation from R to R must be non measurable.

But that first link has shaken me, (especially "In particular, it is consistent that the real line is a countable union of countable sets, and thus a countable union of measure zero sets.") I'm obviously far too used to using choice.

I mean, even "The standard proof that Vitali sets are not Lebesgue measurable uses countable additivity of Lebesgue measure, which is not a theorem of ZF." In the presentations of measure theory that I've seen, It was part of the definition of "measure" that it was countably additive. This is obviously starting from a definition of lebesgue measure and ending up proving things about it, which always seemed to be too real line centric to be worth pursuing.

Though I would ask whether "the measure of a countable set is 0" is a theorem of ZF. It seems to be something assumed at a few points in that first link.

edit: I'd say the answer to my question there is "yes" according to WP on lebesgue measure. I must have got an antiquated version of measure theory, starting with the sigma algebra, defining the measure on it, rather than starting with the measure and arriving at a sigma algebra.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: the reals are a non-hopfian group

jestingrabbit wrote:L(R) is every subset of the reals is measurable. I was thinking that R being non-hopfian would imply the existence of a non measurable set, as I think that any Q-linear, non R-linear transformation from R to R must be non measurable.

Leaving aside the question of whether this is true in ZF for the moment, do you have a ZFC-proof of this?

If you have a Q-linear function f: R -> R such that Im(f) is one-dimensional as a Q-vector space, then you can get a Vitali set by taking {x/a : x in Ker(f)} where a is such that f(a)≠0. But if Im(f) is not one-dimensional, I'm not sure how to use f to construct a Vitali set.

I mean, even "The standard proof that Vitali sets are not Lebesgue measurable uses countable additivity of Lebesgue measure, which is not a theorem of ZF." In the presentations of measure theory that I've seen, It was part of the definition of "measure" that it was countably additive.

It's part of the definition of measure that it's countably additive, but it's not part of the definition of Lebesgue measure that it's a measure. That requires proof, and that proof can fail without countable choice.

Though I would ask whether "the measure of a countable set is 0" is a theorem of ZF. It seems to be something assumed at a few points in that first link.

I think so, for Lebesgue measure. If X is countable, that means that X={f(0),f(1),f(2),...} for some function f. Then X is covered by
Un (f(n)-2-n-c,f(n)+2-n-c) = 4/2c,

so the Lebesgue outer measure of X is 0. I think this implies that the Lebesgue measure is 0, but I'm not sure if that's true in ZF.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

skeptical scientist wrote:
jestingrabbit wrote:L(R) is every subset of the reals is measurable. I was thinking that R being non-hopfian would imply the existence of a non measurable set, as I think that any Q-linear, non R-linear transformation from R to R must be non measurable.

Leaving aside the question of whether this is true in ZF for the moment, do you have a ZFC-proof of this?

I've been casting around for a proof of this, but I've had no luck yet. Its clear that Q linear implies R linear if we have monotonicity or continuity, and I believe those results hold regardless of whether we have choice.

I'm confident that the result is true though, because I remember reading that there's only one measurable logarithm (after you fix the image of a single point). WP references Bourbaki for the continuous result. The measurable result might also be there.

I mean, even "The standard proof that Vitali sets are not Lebesgue measurable uses countable additivity of Lebesgue measure, which is not a theorem of ZF." In the presentations of measure theory that I've seen, It was part of the definition of "measure" that it was countably additive.

It's part of the definition of measure that it's countably additive, but it's not part of the definition of Lebesgue measure that it's a measure.

Normally I would just apply Caratheodory's theorem to get the result, but it seems that the full result isn't available to us without choice.

Though I would ask whether "the measure of a countable set is 0" is a theorem of ZF. It seems to be something assumed at a few points in that first link.

I think so, for Lebesgue measure. If X is countable, that means that X={f(0),f(1),f(2),...} for some function f. Then X is covered by
Un (f(n)-2-n-c,f(n)+2-n-c) = 4/2c,

so the Lebesgue outer measure of X is 0. I think this implies that the Lebesgue measure is 0, but I'm not sure if that's true in ZF.

I think the only way that this could fail to be true is if there were countable sets that aren't measurable. Absurd with choice, completely ineffable by me without. Their existence would resurrect the possibility of countable additivity though.

edit: If there are countable sets that aren't measurable, then the set of measureable sets, using the definition here would have to not be a sigma algebra, which would suck so much.

edit: A countable set, C, has outer measure 0, so for any A, 0 = l*(C) = l*(CnA) + l*(C-A) = 0+ 0 = 0. Therefore, C is measurable and l(C) = 0. So, absent choice, we have no chance of countable additivity.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: the reals are a non-hopfian group

jestingrabbit wrote:
skeptical scientist wrote:
jestingrabbit wrote:L(R) is every subset of the reals is measurable. I was thinking that R being non-hopfian would imply the existence of a non measurable set, as I think that any Q-linear, non R-linear transformation from R to R must be non measurable.

Leaving aside the question of whether this is true in ZF for the moment, do you have a ZFC-proof of this?

I've been casting around for a proof of this, but I've had no luck yet. Its clear that Q linear implies R linear if we have monotonicity or continuity, and I believe those results hold regardless of whether we have choice.

Note that merely per wikipedia: "In general, the study of L(R) assumes a wide array of large cardinal axioms, since without these axioms one cannot show even that L(R) is distinct from L. But given that sufficient large cardinals exist, L(R) does not satisfy the axiom of choice, but rather the axiom of determinacy."

While generally that leaves several options, for any platonist (who can't refute AoC) or any ontological maximalist, the above does not model mathemetical reality if interpreted as a set univeerse.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

Seems I was taking a conclusion of L(R), ie every subset of the reals is measurable, and calling it L(R). My apologies.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Some group theory questions

I figured I'd rename the thread and use it to pose another problem I'm having (and maybe others if i come across them). Hopefully that doesn't cause any confusion to others reading the thread for the first time.

The problem I have now is, I have a homomorphism of groups p:G->H and I want to show that ker(p)=[G,G], the commutator subgroup of G. If I know that H is abelian, G is a finitely generated group on the generators {x1, x2,...,xn}, and that p([xi,xj])=0 for all i,j, is this sufficient to show that ker(p)=[G,G]? If not, could someone offer some general advice on how one might show such a thing; i.e. what kinds of properties of the group might be useful, what element I should look at the image of under p, etc.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Some group theory questions

p(G) being abelian is necessary and sufficient for [G,G] being in the kernel, but you'll also need to show that this is the entire kernel. Checking that the generators are mapped to commuting elements is also necessary and sufficient, but is unnecessary to check if you know that H is abelian.

Checking that the kernel isn't bigger, I'm less clear on. What do you know about the group?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Some group theory questions

Talith wrote:The problem I have now is, I have a homomorphism of groups p:G->H and I want to show that ker(p)=[G,G], the commutator subgroup of G. If I know that H is abelian, G is a finitely generated group on the generators {x1, x2,...,xn}, and that p([xi,xj])=0 for all i,j, is this sufficient to show that ker(p)=[G,G]? If not, could someone offer some general advice on how one might show such a thing; i.e. what kinds of properties of the group might be useful, what element I could look at the image of under p, etc.

I think you have enough to show that ker(p) contains [G,G]. I don't think you could rule out that ker(p) is larger, for example it could be the whole of G.

[ninja'd]

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Some group theory questions

Ok I guess that approach was a bit of a misguided one. It's almost trivial in my example to show that ker(p) is a superset of [G,G]. The example I'm trying to work this out for is:

G is the braid group Bn, H is the integers, and p sends the generators xi to 1 (so for an arbitrary word, p sends the word to the sum of the exponents of the letters in the word). In this example, the generators of Bn are the usual artin generators of the braid group.

(for those that aren't following mod madness 2012, loaf = w o r d)

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Some group theory questions

Ah, then yes, all you need to do is show that B_n/[B_n,B_n] is equal to Z (which is easy), and that the canonical map is what you have (which is also easy)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Some group theory questions

Thanks! That's all the nudge I needed. I'm not sure about it being easy though, showing that the coset of x1 generates the entire factor group wasn't a one liner never mind, it was a one liner after I looked at my stupidly long winded proof..
Last edited by Talith on Mon Mar 12, 2012 6:29 pm UTC, edited 1 time in total.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Some group theory questions

With the standard relations on the generators, x_i x_i+1 x_i = x_i+1 x_i x_i+1, once abelianized and cancelled out, becomes x_i = x_i+1
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Some group theory questions

Yeh I realised there was a nicer way after I made my post . Thanks again.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: the reals are a non-hopfian group

skeptical scientist wrote:
jestingrabbit wrote:any Q-linear, non R-linear transformation from R to R must be non measurable.

Leaving aside the question of whether this is true in ZF for the moment, do you have a ZFC-proof of this?

Just for completeness, and because this wasn't something I could find by googling, I thought I should leave a proof of this here.

Spoiler:
So, assume [imath]f:R\to R[/imath] is measurable and Q-linear. Furthermore, wlog, f(1) = 0. If not, replace f with f'(x) = f(x) - xf(1). I claim that this is also measurable and Q-linear (measurability and linearity are preserved by addition).

As before, define g(x) = f(x)/x and g(0) = 0, and we note that g(rx) = g(x) and, further, that g(r) = f(r) = 0 for r rational. The basic idea will be to use algebraic properties of g (of which there are many) to demonstrate relationships between the behaviour of g on (0,1] and (n-1, n]. One such property that we'll use later is g(x+n) = g(x) x/(x+n).

Let
$A_{n, L} = g^{-1}( [0,L] ) \cap (n-1, n] = \{ x\in (n-1, n]\ |\ 0\leq g(x) \leq L\}.$
I claim that [imath]\lambda(A_{1, L}) = \lambda(A_{n, L}).[/imath] To see this, fix L and n, and let
$B_k = \left\{ x\in A_{1, L} \ \left|\ \frac{(n-1)^{k+1}}{n^{k+1}} < x \leq \frac{(n-1)^k}{n^k} \right. \right\} .$
Note that [imath]x\in B_k[/imath] iff [imath]\frac{n^{k+1}}{(n-1)^k} x \in A_{n, L}[/imath] so
$\lambda(B_k) = \frac{n^{k+1}}{(n-1)^k} \lambda(A_{n, L})$
and the result follows from a geometric sum and a countable union.

For [imath]x\in (0,1],[/imath]
$g(x+n-1) = g(x) \frac{x}{x+n-1} \leq \frac{g(x)}{n},$
from which we may infer that
$\{ x+n-1 \ |\ x \in A_{1, L}\} \subseteq A_{n, L/n} \subseteq A_{n, L}$
So, [imath]\lambda( A_{n, L} ) = \lambda( A_{1, L} ) \leq \lambda( A_{n, L/n} ) \leq \lambda( A_{n, L} ),[/imath] from which we may conclude that [imath]\lambda( A_{1, L} ) = \lambda( A_{1, L/n} )[/imath] for any L and n. Therefore, [imath]\lambda(g^{-1}(\{x>0\})) = 0[/imath] and similarly, [imath]\lambda(g^{-1}(\{x<0\})) = 0.[/imath]

We conclude that g(x) = 0 for almost all x, and the same goes for f.

Now, pick a z>0 such that g(z) = C\neq 0. Let [imath]A = \{ 0 < x \leq z\ |\ g(x) = 0\}[/imath] and note that [imath]\lambda(A) = z > 0[/imath]. By translation invariance of Lebesgue measure, [imath]B = \{ z+x\ |\ x \in A\}[/imath] is such that [imath]\lambda(B) = z.[/imath] But, for x in A,

$g(z+x) = \frac{f(z) + f(x)}{z + x} = \frac{Cz}{z+ x} \neq 0$

which is a contradiction: we proved g is 0 ae, but here it is taking nonzero values on a positive measure set. Therefore, no such z exists, and g is 0 everywhere. Therefore, f is 0 everywhere, and so f is R-linear.

Anyway, carry on with what you were discussing.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.