# What is wrong with this fake proof that subgroup of a cyclic group is cyclic?

Let $$G$$ be a cyclic group generated by $$a$$ and $$H$$ its subgroup. This is a proof by contradiction. Assume there is no $$r$$ in $$H$$ such that $$\langle r \rangle = H$$. If some $$s$$ in $$G$$ is not in $$H$$ then $$\langle s \rangle \neq H$$. So for all $$s$$ in $$G$$, $$\langle s \rangle \neq H$$ Thus for all $$s$$ in $$G$$ there exists an $$h\in H$$ such that $$h \notin \langle s \rangle$$. But this is a contradiction with the fact that $$a$$ generates $$G$$.

I know this proof is fake, because it does not use the fact that $$H$$ is a subgroup but I am unable to find the mistake(s).

• If $H$ is not equal to any $<s>$ then for each $<s>$ we have either some $h_s\in H$ \ $<s>$ or $H$ is a proper subset of $<s>$. – DanielWainfleet Oct 23 '18 at 5:22

You are correct in proving that, for every $$x\in G$$, $$\langle x\rangle\ne H$$. But this doesn't imply that, for every $$x\in G$$, there is $$h\in H$$ such that $$h\notin\langle x\rangle$$.

For instance, this is false as soon as $$H\ne G$$ and $$x$$ is a generator of $$G$$.

• Do you mean $\neg (\forall x \in G, \langle x\rangle = H)$? The you've worded it, it sounds like you're saying $\forall x \in G, \langle x\rangle\ne H$. – Acccumulation Oct 22 '18 at 20:46
• @Acccumulation The additional hypothesis (for the proof by contradiction) is that $H$ is not cyclic; thus, for every $x\in H$, $\langle x\rangle\ne H$; on the other hand, $\langle x\rangle\ne H$ when $x\notin H$; thus $\langle x\rangle\ne H$ for every $x\in G$. This doesn't lead to an easy contradiction, though. – egreg Oct 22 '18 at 20:51

No $$s\in G$$ such that $$\langle s\rangle=H$$ is clear.

But then you can't follow with for all $$s\in G$$ there's $$h\in H$$ such that $$h\notin\langle s\rangle$$ because $$H$$ could be a subset of $$\langle s\rangle$$ even though $$s\notin G$$.

Which, incidentally, is what happens if $$s$$ is a generator of $$G$$

It is correct that $$\forall s \in G, \langle s\rangle \ne H$$, but this does not imply $$\exists h \in H, h \notin \langle s\rangle$$, because $$\langle s\rangle$$ may be a proper superset of $$H$$.

If some $$s$$ in $$G$$ is not in $$H$$ then $$\langle s \rangle \neq H$$. So for all $$s$$ in $$G$$, $$\langle s \rangle \neq H$$

That doesn't make any sense. Your saying "$$(s \not \in H \rightarrow \langle s \rangle \neq H)\rightarrow (\forall s, \langle s \rangle \neq H)$$". That's like saying "if an animal doesn't have a tail, it's not a dog, therefore no animals are dogs".