3
$\begingroup$

Can this be done by induction instead of just proving the subgroup criterion? I can prove using the essentials tools of group theory, but looking at the problem, I was wondering if we can simply use an induction argument.

Given we have a chain of ascending subgroups of a group $G$... $$H_1\le H_2\le....$$ Is the union $$\bigcup_{i=1}^\infty{H_i}\le G$$

For the first case, we have that $H_1\le H_2$ and thus, $H_1\subseteq H_2$ means that in terms of their union,

$$\bigcup_{i=1}^2{H_i}=H_2\le G$$

Thus, for an arbitrary $n>2$ we can assume that $$\bigcup_{i=1}^n{H_i}=H_n\le G$$ Then $$\bigcup_{i=1}^{n+1}{H_i}=\left(\bigcup_{i=1}^{n}{H_i}\right)\cup H_{n+1}=H_n\cup H_{n+1}=H_{n+1}\le G$$

Thus, for any whole value of $n$, the claim is true.

My worry is the infinite upper bound. But I feel like induction takes care of that.

$\endgroup$
  • 1
    $\begingroup$ Judging by some of the comments on this page, you might want to clarify (in the title as well) that you're asking specifically whether or not induction is enough. $\endgroup$ – Asaf Karagila Feb 13 at 17:34
  • $\begingroup$ @AsafKaragila, thank you. I changed the title, and reframed the post a bit to more accurately depict my inquiry. $\endgroup$ – Eleven-Eleven Feb 13 at 17:50
  • 2
    $\begingroup$ Theorem: a decimal of the form 0.abc... with n digits after the decimal place is a rational. Proof: Plainly this is true for n = 0. Suppose it is true for n=k. We have 0.[k digits] rational, we add to it x/10^(-k-1) for x between 0 and 9, which is a rational. The sum of two rationals is rational. Therefore we have proven the theorem by induction. Have I now proven that pi is rational? Now do you see why "induction takes care of the infinite bound" is wrong? $\endgroup$ – Eric Lippert Feb 13 at 18:08
  • $\begingroup$ 100%. That was as clear as could be written.. $\endgroup$ – Eleven-Eleven Feb 13 at 19:05
  • 1
    $\begingroup$ In some sense, you haven't proved anything... the fact that $H_n$ is a subgroup for any $n$ was already given as part of the problem statement. $\endgroup$ – MartianInvader Feb 13 at 19:42
7
$\begingroup$

Induction (the conventional way) only takes care of the "for any whole value of $n$" part. It can never let you conclude anything for the entire infinite union. There is such a thing as transfinite induction, but even then the induction step is split into separate steps for the cases which have an immediate predecessor and cases which don't. The infinite union doesn't have an immediate predecessor, and thus the standard induction step will never reach it.

However, clearly the union is a subset, and clearly that subset contains the identity element, so we're a good way of the way there. When showing that it has inverses and that it's closed under products, it pays to know that any finite collection of elements in the union is contained in some finite union as well. And you already know that any of the finite unions is a group.

$\endgroup$
4
$\begingroup$

Of course $1\in\bigcup_{i=1}^{\infty}H_i$ and for any $g\in H_i$,$h\in H_j$ say without loss of generality that $i\leq j$ then $g\in H_j$ too and since this is a subgroup You have $$gh\in H_j\subset \bigcup_{i=1}^{\infty}H_i$$ and thus $\bigcup_{i=1}^{\infty}H_i$ is a subgroup. That's all. You don't argue via induction!

$\textbf{Edit:}$ what was missing, for any $g\in\bigcup_{i=1}^{\infty}H_i$ there exists an $i$ so that $g\in H_i$, actually this implies $g\in H_j$ for all $i\leq j$, but we don't need this here. Since $H_i$ is a subgroup $g^{-1}\in H_i\subseteq \bigcup_{i=1}^{\infty}H_i$.

$\endgroup$
  • $\begingroup$ That was my question... I knew how to prove using the subgroup criterion, but I was thinking about it in terms of induction and wanted to know why it was a valid or invalid proof. $\endgroup$ – Eleven-Eleven Feb 13 at 14:45
  • 1
    $\begingroup$ This is not sufficient. You need to show, also, that the inverse of an arbitrary element of the candidate group is in the candidate group. Don't mix the one-step and two-step subgroup lemmas without due care. $\endgroup$ – Shaun Feb 13 at 16:14
  • $\begingroup$ @Eleven-Eleven I understand, in this case Arthur's answer seems perfect to me. $\endgroup$ – Peter Melech Feb 14 at 12:25
  • 1
    $\begingroup$ @Shaun Sure, of course this is even more trivial, but You are right to point this out $\endgroup$ – Peter Melech Feb 14 at 12:26
  • 1
    $\begingroup$ I edited my post. $\endgroup$ – Peter Melech Feb 14 at 12:32
2
$\begingroup$

(I should have read the question more carefully. What follows is a proof by the method the OP excluded.)


Since $e\in H_1$, we have $$e\in H_1\subseteq\bigcup_{i=1}^{\infty}H_i=:\mathcal{U}.$$ Hence $\mathcal{U}$ is nonempty.

Let $g, h\in\mathcal{U}$. Then $g\in H_k$ and $h\in H_\ell$ for some $k, \ell$. Assume w.l.o.g. that $k<\ell$. Then the ascending chain condition gives that $g\in H_\ell$. Since $h\in H_\ell$ and $H_\ell$ is a subgroup of $G$, $h^{-1}\in H_\ell$. Thus $gh^{-1}\in H_\ell$. Hence $gh^{-1}\in \mathcal{U}$.

Hence, by the one-step subgroup lemma, we have

$$\mathcal{U}\le G.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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