Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

was just wondering if this is a valid proof for the aforementioned question? I am quite confident that it isn't, but not exactly sure why. Maybe I am missing the point of proofs by induction (amateur...).

Let $G$ be a cyclic group generated by $g$ and $H$ a subgroup of it. Since $H$ is a subgroup, $1_G\in H$ thus the trivial subgroup is cyclic. Proceeding by induction: $H=\lbrace g^i:0\leq i<k, \rbrace$ is true for case $k=1$.

So assume true for $n=k$ thus $H=\lbrace g^i:0\leq i<k \rbrace$ and $H\cup \lbrace g^{k}\rbrace=\lbrace g^i:0\leq i<k \rbrace \cup \lbrace g^{k}\rbrace=\lbrace g^i:0\leq i<k+1 \rbrace$ so since it is true for $n=k+1$ we have that it is true for all $n\in \mathbb{N}$.

Hopefully someone can point out the flaw, thanks.

share|improve this question
    
What is $g$? $\,\,$ –  Berci Jun 1 '14 at 21:07
    
Presumably the element which generates the cyclic group. –  Dan Jun 1 '14 at 21:08
    
I don't think you can use an induction argument in this proof. See proofwiki.org/wiki/Subgroup_of_Cyclic_Group_is_Cyclic –  ABC Jun 1 '14 at 21:08
    
$g$ is a generator of G, edited it now. –  lifin Jun 1 '14 at 21:09
2  
Here is one point where your attempted proof isn't working: Assume my group $G$ consists of $\{1_{G}, g, g^{2}, \ldots g^{n-1}\}$. Then you seem to be claiming that the subsets $\{1_{G}, g\}$, $\{1_{G},g,g^{2}\}$, etc. are all subgroups. But that's definitely not the case! For example, think about $G = \mathbb{Z}_{10} = \{0,1,2,3,4,5,6,7,8,9\}$. Then you could choose $1$ as the generator of $G$, but the subgroups are things like $\{0,5\}$, $\{0,2,4,6,8\}$. Subgroups of $\mathbb{Z}_{n}$ look like "every other element" or "every third element", etc.; not "the first 5 elements". –  coolpapa Jun 1 '14 at 21:14

5 Answers 5

I would abandon induction as it does not help you for the infinite case. Let $g$ be the generator of $G$. Suppose $H$ is not cyclic. Then there exists $j$ and $k$ relatively prime where $g^j$ and $g^k$ are in $H$. But since $j$ and $k$ are relatively prime there exists $a,b$ such that $aj+bk = 1$. Hence $(g^j)^a+(g^k)^b = g$, so $g$ is in $H$. Hence $H=G$ which is cyclic, contradiction.

share|improve this answer
5  
" Then there exists j and k relatively prime where g^j and g^k are in H." Proof? –  Pedro Tamaroff Jun 1 '14 at 21:11
2  
If j and k are not relatively prime then g^j and g^k are both generated by g^x where x is the GCD of j and k. We can construct g^x the same way I do in my answer. If the group is not cyclic there are two elements in distinct orbits, but we have seen that if j and k are not relatively prime they are in the same orbit. –  Jonathan Aronson Jun 1 '14 at 21:22
    
(I just thought the proof was in order.) –  Pedro Tamaroff Jun 1 '14 at 21:24
    
Fair enough, I did gloss over that point. OP do you like this answer? Any questions? –  Jonathan Aronson Jun 1 '14 at 21:30
1  
Yeah my notation is a bit confusing, since there is only one operation which is the group product. More appropriate would be ((g^j)^a)*((g^k)^b)) = g^(aj+bk) = g^1 = g. Makes sense? –  Jonathan Aronson Jun 1 '14 at 21:37

Since $H$ is a subgroup of $G$ every element of $H$ can be expressed as $g^r$ for some $r\in \mathbb Z$. One possibility is that $H$ is trivial, hence cyclic. Else Let $m$ be the least positive value of $r$. Then $H$ is the cyclic group generated by $g^m$. Else there is an element $g^n\in H$ with $n=km+l$ and $1\leq l \lt m$, whence $g^l\in H$, which is a contradiction.

Least positive is justified by $g^r\in H \implies g^{-r}\in H$ - excluding the trivial group.

share|improve this answer
  1. If your proof is true, you proofed that subgroup $H$ of group $\langle a \rangle$ is always $\{a^i \mid 0 \le i < k\}$, for some $k$. That's False.

  2. The induction is false, I don't finally understand the try, but if you add an element $x$ to group $H$, and not add $x^{-1}$, $H \cup \{x\}$ is not a group.

share|improve this answer

No, you can't do induction in that way. Why should $H=\{g^i:0\le i<k\}$?

The cleanest proof exploits the knowledge of the subgroups of $\mathbb{Z}$ and the homomorphism theorems.

  1. If $H$ is a subgroup of $\mathbb{Z}$ (with respect to addition, of course), then $H=n\mathbb{Z}$ for a unique integer $n\ge0$.

  2. If $N$ is a normal subgroup of $G$, then the subgroups of $G/N$ are exactly those of the form $H/N$, where $H$ is a subgroup of $G$ containing $N$.

Now, with this knowledge, consider a cyclic group $G$; then there is a surjective homomorphism $\varphi\colon\mathbb{Z}\to G$, so its kernel $\ker\varphi=n\mathbb{Z}$ for a unique $n\ge0$.

Therefore, we can reduce to the case where $G=\mathbb{Z}/n\mathbb{Z}$.

A subgroup of $\mathbb{Z}/n\mathbb{Z}$ is of the form $H/n\mathbb{Z}$, where $H$ is a subgroup of $\mathbb{Z}$ containing $n\mathbb{Z}$; thus $H=m\mathbb{Z}$ where $m$ divides $n$. Since $m\mathbb{Z}$ is obviously cyclic, also its quotient $m\mathbb{Z}/n\mathbb{Z}$ is cyclic.

share|improve this answer
    
This is the only right way to put it (the part of the argument that uses Bezout's identity is then hidden in the classification of subgroups of $\mathbb{Z}$, where it belongs). –  Ryan Reich Jun 1 '14 at 22:27
    
@RyanReich I've always found that reusing that argument several times is conceptually and didactically bad. The order of an element is the number of elements of the cyclic subgroup it generates. Then the fact it is the minimal positive exponent such that the power is the identity becomes trivial. –  egreg Jun 1 '14 at 22:35

For $\mathbb{Z}$, use division algorithm to show that any subgroup $H\le \mathbb{Z}$ is of the form $\langle n \rangle$ where $n$ is the smallest positive element of $H$.

Let $G$ be a cyclic group with generator $a$, then define a group homomorphism $f:\mathbb{Z}\to G$ where $1\mapsto a$. This map is surjective since $\langle a\rangle = G$. Therefore $G\cong \mathbb{Z}/\ker f$. But $\ker f$ being a subgroup of $G$ is in the form $\langle n\rangle$, and we conclude that $G\cong \mathbb{Z}/\langle n\rangle$. If $n = 0$, then $G\cong \mathbb{Z}$. If $n = 1$, then $G\cong 0$. If $n$ is anything else, then $G\cong \mathbb{Z}_n$. These are up to isomorphism only possible cyclic groups.

For $\mathbb{Z}_n$, use Lagrange's theorem. Its possible subgroups are $\langle d\rangle \cong\mathbb{Z}_{n/d}$ where $d|n$.

share|improve this answer
    
Well, how do you show "cyclic groups are either $\Bbb Z$ or $\Bbb Z_n$"? –  Pedro Tamaroff Jun 1 '14 at 21:46
    
@PedroTamaroff edited. –  mez Jun 2 '14 at 16:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.