Thread: Showing a Function on Groups is One-to-One

1. Showing a Function on Groups is One-to-One

I've got a problem and i'm not sure how to start this. Could somebody give me a hand?

Let G be a group of odd order.
Show that the function f: G --> G defined by f(x) = x^2 is one-to-one.

2. To show that a function is one-to-one, you need to show that the only element that maps to the identity is the identity. In other words, $\displaystyle \ker f=\{e\}$. You can try to combine this with Lagrange's theorem: the order of a subgroup divides the order of the group.

Can you see what to do?

3. if x^2 = e (trivially, e^2 = e in any group) and x is not e, what can we say about the order of G?

4. Originally Posted by roninpro
To show that a function is one-to-one, you need to show that the only element that maps to the identity is the identity.

This is false in general: the function $\displaystyle f(x)=x^2$ is not 1-1 on $\displaystyle \mathbb{R}^*$ , yet

$\displaystyle f(1)=1$.

It is true if we talk about a group (unitary ring) homomorphism, though.

Tonio

In other words, $\displaystyle \ker f=\{e\}$. You can try to combine this with Lagrange's theorem: the order of a subgroup divides the order of the group.

Can you see what to do?
.

5. Originally Posted by Deveno
if x^2 = e (trivially, e^2 = e in any group) and x is not e, what can we say about the order of G?

I think this won't help if the given function isn't a group homomorphism...

Tonio

6. Originally Posted by tonio
I think this won't help if the given function isn't a group homomorphism...

Tonio
it's a hint, not the answer. my intent was to get the asker to think about the implications of G having odd order.

if x is any element in such a group, x has odd order, because....

continuing, this means that if x^2 = y^2, and if the order of x is k = 2m+1, x = xe = x(x^k) = x(x^(2m+1)) = x^(2m+2) = (x^2)^(m+1)

= (y^2)^(m+1) = y^(2m+2) so x is in <y>, so <x> < <y>. but by the same token, if the order of y is r = 2n+1, y = ye = y(y^(2n+1))

= y^(2n+2) = (y^2)^(n+1) = (x^2)^(n+1).

so y is in <x>, hence <x> = <y>, so k = r, and m = n. hence x = y^(2m+2) = y^(2m+1)y = ey = y, so g-->g^2 is injective, homomorphism or not.

7. Originally Posted by Deveno
it's a hint, not the answer. my intent was to get the asker to think about the implications of G having odd order.

if x is any element in such a group, x has odd order, because....

continuing, this means that if x^2 = y^2, and if the order of x is k = 2m+1, x = xe = x(x^k) = x(x^(2m+1)) = x^(2m+2) = (x^2)^(m+1)

= (y^2)^(m+1) = y^(2m+2) so x is in <y>, so <x> < <y>. but by the same token, if the order of y is r = 2n+1, y = ye = y(y^(2n+1))

= y^(2n+2) = (y^2)^(n+1) = (x^2)^(n+1).

so y is in <x>, hence <x> = <y>, so k = r, and m = n. hence x = y^(2m+2) = y^(2m+1)y = ey = y, so g-->g^2 is injective, homomorphism or not.
That is interesting that you were able to show this without using Lagrange's theorem at all. I understand how this proof works, but i don't think i ever would've thought of it. Thank you for your help

8. Originally Posted by tonio
This is false in general: the function is not 1-1 on , yet

.

It is true if we talk about a group (unitary ring) homomorphism, though.

Tonio
What you said isn't true - the function you give maps two elements to the identity, f(-1)=1=f(1), so what you've written doesn't form a counter-example. Specifically, it doesn't form a counter-example because your map is a homomorphism (as your group is abelian)...

I am not sure what your point is - are you perhaps getting confused with 1-1, which means injection, and a "there exists a 1-1 correspondence between the sets", which means there exists a bijection?

Alternatively, counter-example to the comment: A function is an injection if the only element which maps to the identity is the identity' would be $\displaystyle \phi: \mathbb{Z}_3\rightarrow \mathbb{Z}_2, 0\mapsto 0, 1\mapsto 1, 2\mapsto 1$. This isn't a homomorphism, and so your statement works. In general, the kernel of a homomorphism is trivial if and only if the function is an injection. This is easy to prove, and was what Roninpro was trying to say, and indeed did say when you realise he said ker(f)=e...normal functions don't have kernels...

9. i think the point tonio was trying to make was, there is a distinction between:

a) a homomorphism f is injective iff ker(f) = {e}, and

b) a function f is injective only if f^-1(e) = {*}, a singleton set (note the "only if").

the thing is, if f is only a function, and not a homomorphism, it could well be that the pre-image of the identity is a singleton set, without f being 1-1. tonio's example

is not the best one, since for his map f^-1(1) = {-1,1}. swlabr's example is a good counter-example for a function, but not for a function of the form x-->x^2.

in my orginal reply, i hinted at the fact that any group of even order must have an element of order 2 (the map x-->x^-1 on G-{e} must have a fixed point),

so there aren't any such counter-examples for groups of even order, x-->x^2 is never injective. as he (rightfully) pointed out, this is not the same as saying for

groups of odd order, x-->x^2 is always injective (~A --> ~B is not the same as A-->B, we have to rule out A --> ~B. here "A" is: G is of odd order,

and "B" is: the squaring map is injective).

judge's decision: tonio gets 5 points for pointing out the logical subtleties of the problem, and loses 2 for improper rebuttal.

10. Originally Posted by Deveno
i think the point tonio was trying to make was, there is a distinction between:

a) a homomorphism f is injective iff ker(f) = {e}, and

b) a function f is injective only if f^-1(e) = {*}, a singleton set (note the "only if").

the thing is, if f is only a function, and not a homomorphism, it could well be that the pre-image of the identity is a singleton set, without f being 1-1. tonio's example

is not the best one, since for his map f^-1(1) = {-1,1}. swlabr's example is a good counter-example for a function, but not for a function of the form x-->x^2.

in my orginal reply, i hinted at the fact that any group of even order must have an element of order 2 (the map x-->x^-1 on G-{e} must have a fixed point),

so there aren't any such counter-examples for groups of even order, x-->x^2 is never injective. as he (rightfully) pointed out, this is not the same as saying for

groups of odd order, x-->x^2 is always injective (~A --> ~B is not the same as A-->B, we have to rule out A --> ~B. here "A" is: G is of odd order,

and "B" is: the squaring map is injective).

judge's decision: tonio gets 5 points for pointing out the logical subtleties of the problem, and loses 2 for improper rebuttal.

I think the rebuttal was not only proper but necessary and important since what was being

rebutted was incorrect, so I should lose only 1 point for giving an incorrect counterexample.

Tonio

Pd. You know what? Take away an other point from me for being a pest and rebutting again...

11. Originally Posted by Swlabr
What you said isn't true -

No, what I said is true, but the example I gave was flawed. Nevertheless it's easy to

fix it: $\displaystyle f:\mathbb{R}\rightarrow \mathbb{R}\,,\,f(x)=|x|$ .

This is not a 1-1 function yet $\displaystyle \ker f=\{0\}$ ...

the function you give maps two elements to the identity, f(-1)=1=f(1), so what you've written doesn't form a counter-example. Specifically, it doesn't form a counter-example because your map is a homomorphism (as your group is abelian)...

I am not sure what your point is - are you perhaps getting confused with 1-1, which means injection, and a "there exists a 1-1 correspondence between the sets", which means there exists a bijection?

No. My point was that to show in general that a function is 1-1 you must show

that $\displaystyle f(x)=f(y)\Longrightarrow x=y$ , and it won't help showing that the unit, in case the

set has an algebraic structure that admits one, is the only elt. mapped to the unit.

The famous $\displaystyle "\mbox{f is 1-1 }\iff \ker f=\{1\}"$ works in general only for homomorphisms, not

for general functions.

Tonio

Alternatively, counter-example to the comment: A function is an injection if the only element which maps to the identity is the identity' would be $\displaystyle \phi: \mathbb{Z}_3\rightarrow \mathbb{Z}_2, 0\mapsto 0, 1\mapsto 1, 2\mapsto 1$. This isn't a homomorphism, and so your statement works. In general, the kernel of a homomorphism is trivial if and only if the function is an injection. This is easy to prove, and was what Roninpro was trying to say, and indeed did say when you realise he said ker(f)=e...normal functions don't have kernels...
.

12. Originally Posted by tonio
.
A counter-example where the function $\displaystyle x\mapsto x^2$ maps only the identity to the identity but isn't 1-1 is group with presentation,

$\displaystyle \langle a, b; a^2=b^2\rangle$.

It is torsion free (a group with one-relator is has torsion if and only if the relator is a true power) and so the only element which maps to the identity is the identity. If a and b are non-equal elements then the function is not 1-1 since a and b are mapped to the same element. However, a and b are non-equal elements as the group is not infinite cyclic. This is because it isomorphic to the group with relator $\displaystyle abab^{-1}$ (replace $\displaystyle a$ with $\displaystyle ab$ via a Tietze transformation) and so the group has abelianisation $\displaystyle \mathbb{Z} \times C_2$, and so cannot be infinite cyclic.

Also - my statement `what you said isn't true' was a remenant of a previous edit, when I was still trying to work out what you were saying. It was late. I was tired...

13. Originally Posted by tonio
I think the rebuttal was not only proper but necessary and important since what was being

rebutted was incorrect, so I should lose only 1 point for giving an incorrect counterexample.

Tonio

Pd. You know what? Take away an other point from me for being a pest and rebutting again...

duly noted, and extra point deducted. but +1 for humor.