# Homomorphism Problem - Need work checked

• Samuelb88
In summary: I think you're misunderstanding something here. I'm not sure what you're asking. Do you want me to explain what I mean by "generated by f"? :biggrin:In summary, the surjective homomorphism f : G \rightarrow H is cyclic if and only if G is cyclic, and abelian if and only if H is abelian.
Samuelb88

## Homework Statement

Let $f : G \rightarrow H$ be a surjective homomorphism. Prove that if G is cyclic, then H is cyclic, and if G is abelian, then H is abelian.

## Homework Equations

Notation: Let it be understood that $f^n(x) = [f(x)]^n$.

## The Attempt at a Solution

Just would like to see if I am right.

Proof. (of G cyclic $\Rightarrow$ H cyclic)Suppose that $f$ is a surjective homomorphism, and suppose that $G$ is cyclic. Let $G$ be generated by $x$. I want to show that there exists $y$ such that $y$ generates $H$.

First I will prove that $\forall x^n \in G$ $\Rightarrow$ $f(x^n) = f^n(x)$. As our base case for $n=1$ we cite that $f(x e_G) = f(x) f(e_G) = f(x)$. Next suppose that $f(x^n) = f^n(x)$ (Inductive hypothesis). Then $f(x^{n+1}) = f(x^n x) = f(x^n) f(x) = f^n(x) f(x) =f^{n+1}(x)$, which from our inductive hypothesis.

The proof that $\forall x^{-n} \in G$ $\Rightarrow$ $f(x^{-n}) = f^{-n}(x)$ is similar.

Now since $f$ is surjective $\Rightarrow$ $\mathrm{im}(f) = H$ and therefore $H$ is generated by $f(x)$ and is therefore cyclic.

Proof. (of G abelian $\Rightarrow$ H abelian) Suppose now that $G$ is abelian and let $x, y \in G$. I want to show that $\forall f(x) , f(y)$ $\Rightarrow$ $f(x)f(y) = f(y)f(x)$. Then $f(xy) = f(x)f(y)$ and $f(yx) = f(y)f(x)$, but $f(xy) = f(yx)$ $\Rightarrow$ $f(x)f(y) = f(y)f(x)$. Since $f$ is surjective $\mathrm{im}(f) = H$ $\Rightarrow$ $\forall f(x), f(y) \in H$ $f(x)f(y) = f(y)f(x)$ $\Rightarrow$ $H$ is abelian.

My intuition says I'm right, but it seems my intuition is wrong more than right this quarter.

Hi Samuelb88!

Samuelb88 said:

## Homework Statement

Let $f : G \rightarrow H$ be a surjective homomorphism. Prove that if G is cyclic, then H is cyclic, and if G is abelian, then H is abelian.

## Homework Equations

Notation: Let it be understood that $f^n(x) = [f(x)]^n$.

## The Attempt at a Solution

Just would like to see if I am right.

Proof. (of G cyclic $\Rightarrow$ H cyclic)Suppose that $f$ is a surjective homomorphism, and suppose that $G$ is cyclic. Let $G$ be generated by $x$. I want to show that there exists $y$ such that $y$ generates $H$.

First I will prove that $\forall x^n \in G$ $\Rightarrow$ $f(x^n) = f^n(x)$. As our base case for $n=1$ we cite that $f(x e_G) = f(x) f(e_G) = f(x)$. Next suppose that $f(x^n) = f^n(x)$ (Inductive hypothesis). Then $f(x^{n+1}) = f(x^n x) = f(x^n) f(x) = f^n(x) f(x) =f^{n+1}(x)$, which from our inductive hypothesis.

The proof that $\forall x^{-n} \in G$ $\Rightarrow$ $f(x^{-n}) = f^{-n}(x)$ is similar.

Now since $f$ is surjective $\Rightarrow$ $\mathrm{im}(f) = H$ and therefore $H$ is generated by $f(x)$ and is therefore cyclic.

Could you explain in more detail why H is generated by f(x). I'm sure you know it, but it's a crucial detail that should be mentioned.

Proof. (of G abelian $\Rightarrow$ H abelian) Suppose now that $G$ is abelian and let $x, y \in G$. I want to show that $\forall f(x) , f(y)$ $\Rightarrow$ $f(x)f(y) = f(y)f(x)$. Then $f(xy) = f(x)f(y)$ and $f(yx) = f(y)f(x)$, but $f(xy) = f(yx)$ $\Rightarrow$ $f(x)f(y) = f(y)f(x)$. Since $f$ is surjective $\mathrm{im}(f) = H$ $\Rightarrow$ $\forall f(x), f(y) \in H$ $f(x)f(y) = f(y)f(x)$ $\Rightarrow$ $H$ is abelian.

That proof is correct! But it's perhaps a bit chaotic, here's a proposal to clean it:

Take h and h' in H. We want to show that hh'=h'h. Because of surjectivity, we know that there are g and g' in G such that f(g)=h and f(g')=h'. Since G is abelian, we know that gg'=g'g. But then it follows that hh'=f(g)f(g')=f(gg')=f(g'g)=f(g')f(g)=h'h.

I'm not saying your proof is wrong, though.

Since $f$ is surjective $\Rightarrow$ $\mathrm{im}(f)=\{ ..., f^{-1}(x), e_H , f(x) , f^2(x) , ... \} = H$. Doesn't this imply that $H$ is generated by $f$?

Samuelb88 said:
Since $f$ is surjective $\Rightarrow$ $\mathrm{im}(f)=\{ ..., f^{-1}(x), e_H , f(x) , f^2(x) , ... \} = H$. Doesn't this imply that $H$ is generated by $f$?

Yes, of course, I just wanted some more explanation on that part
Well, it seems it is all correct!

Great to hear! Hehe. Thanks much, micromass!

## 1. What is the Homomorphism Problem?

The Homomorphism Problem is a mathematical concept in which a function is defined to map elements from one algebraic structure to another, preserving the operations between the elements. In simpler terms, it is the study of whether two mathematical structures can be mapped onto each other in a way that preserves their structure.

## 2. Why is the Homomorphism Problem important?

The Homomorphism Problem is important because it has many practical applications in fields such as computer science, cryptography, and graph theory. It also has connections to other important problems in mathematics, such as the Isomorphism Problem and the Automorphism Problem.

## 3. What are some examples of Homomorphism?

One example of Homomorphism is the function f(x) = x^2, which maps the set of real numbers onto itself, preserving the operation of multiplication between the elements. Another example is the function f(x) = 2x, which maps the set of integers onto itself, preserving the operation of addition between the elements.

## 4. How is the Homomorphism Problem solved?

The Homomorphism Problem can be solved through various methods, such as using algorithms to find a mapping between the two structures, or by proving that no such mapping exists. It can also be solved by finding a specific type of homomorphism, such as an isomorphism or an endomorphism.

## 5. Are there any open problems related to the Homomorphism Problem?

Yes, there are still many open problems related to the Homomorphism Problem, such as the Graph Isomorphism Problem, which asks whether two given graphs are isomorphic or not. There is also ongoing research into finding efficient algorithms for solving the Homomorphism Problem for specific types of structures, such as graphs or groups.

Replies
6
Views
744
Replies
3
Views
1K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
20
Views
3K
Replies
2
Views
1K
Replies
1
Views
2K
Replies
7
Views
2K
Replies
6
Views
2K
Replies
2
Views
917