Validity of Using Induction to Show Union of an Infinite Ascending Chain of Subgroups is a Subgroup
$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_1le H_2le....$$
Is the union
$$bigcup_{i=1}^infty{H_i}le G$$
For the first case, we have that $H_1le H_2$ and thus, $H_1subseteq H_2$ means that in terms of their union,
$$bigcup_{i=1}^2{H_i}=H_2le G$$
Thus, for an arbitrary $n>2$ we can assume that
$$bigcup_{i=1}^n{H_i}=H_nle G$$
Then
$$bigcup_{i=1}^{n+1}{H_i}=left(bigcup_{i=1}^{n}{H_i}right)cup H_{n+1}=H_ncup 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.
abstract-algebra group-theory induction alternative-proof
$endgroup$
|
show 1 more comment
$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_1le H_2le....$$
Is the union
$$bigcup_{i=1}^infty{H_i}le G$$
For the first case, we have that $H_1le H_2$ and thus, $H_1subseteq H_2$ means that in terms of their union,
$$bigcup_{i=1}^2{H_i}=H_2le G$$
Thus, for an arbitrary $n>2$ we can assume that
$$bigcup_{i=1}^n{H_i}=H_nle G$$
Then
$$bigcup_{i=1}^{n+1}{H_i}=left(bigcup_{i=1}^{n}{H_i}right)cup H_{n+1}=H_ncup 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.
abstract-algebra group-theory induction alternative-proof
$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 form0.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 have0.[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
|
show 1 more comment
$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_1le H_2le....$$
Is the union
$$bigcup_{i=1}^infty{H_i}le G$$
For the first case, we have that $H_1le H_2$ and thus, $H_1subseteq H_2$ means that in terms of their union,
$$bigcup_{i=1}^2{H_i}=H_2le G$$
Thus, for an arbitrary $n>2$ we can assume that
$$bigcup_{i=1}^n{H_i}=H_nle G$$
Then
$$bigcup_{i=1}^{n+1}{H_i}=left(bigcup_{i=1}^{n}{H_i}right)cup H_{n+1}=H_ncup 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.
abstract-algebra group-theory induction alternative-proof
$endgroup$
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_1le H_2le....$$
Is the union
$$bigcup_{i=1}^infty{H_i}le G$$
For the first case, we have that $H_1le H_2$ and thus, $H_1subseteq H_2$ means that in terms of their union,
$$bigcup_{i=1}^2{H_i}=H_2le G$$
Thus, for an arbitrary $n>2$ we can assume that
$$bigcup_{i=1}^n{H_i}=H_nle G$$
Then
$$bigcup_{i=1}^{n+1}{H_i}=left(bigcup_{i=1}^{n}{H_i}right)cup H_{n+1}=H_ncup 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.
abstract-algebra group-theory induction alternative-proof
abstract-algebra group-theory induction alternative-proof
edited Feb 14 at 13:46
Shaun
9,268113684
9,268113684
asked Feb 13 at 13:14
Eleven-ElevenEleven-Eleven
5,73572759
5,73572759
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 form0.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 have0.[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
|
show 1 more comment
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 form0.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 have0.[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
1
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$
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
$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
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$
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
$begingroup$
100%. That was as clear as could be written..
$endgroup$
– Eleven-Eleven
Feb 13 at 19:05
1
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
$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
|
show 1 more comment
3 Answers
3
active
oldest
votes
$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$
add a comment |
$begingroup$
Of course $1inbigcup_{i=1}^{infty}H_i$ and for any $gin H_i$,$hin H_j$ say without loss of generality that $ileq j$ then $gin H_j$ too and since this is a subgroup You have
$$ghin H_jsubset 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 $ginbigcup_{i=1}^{infty}H_i$ there exists an $i$ so that $gin H_i$, actually this implies $gin H_j$ for all $ileq j$, but we don't need this here. Since $H_i$ is a subgroup $g^{-1}in H_isubseteq 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
add a comment |
$begingroup$
(I should have read the question more carefully. What follows is a proof by the method the OP excluded.)
Since $ein H_1$, we have $$ein H_1subseteqbigcup_{i=1}^{infty}H_i=:mathcal{U}.$$ Hence $mathcal{U}$ is nonempty.
Let $g, hinmathcal{U}$. Then $gin H_k$ and $hin H_ell$ for some $k, ell$. Assume w.l.o.g. that $k<ell$. Then the ascending chain condition gives that $gin H_ell$. Since $hin 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$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3111368%2fvalidity-of-using-induction-to-show-union-of-an-infinite-ascending-chain-of-subg%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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$
add a comment |
$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$
add a comment |
$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$
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.
edited Feb 13 at 13:36
answered Feb 13 at 13:31
ArthurArthur
116k7116198
116k7116198
add a comment |
add a comment |
$begingroup$
Of course $1inbigcup_{i=1}^{infty}H_i$ and for any $gin H_i$,$hin H_j$ say without loss of generality that $ileq j$ then $gin H_j$ too and since this is a subgroup You have
$$ghin H_jsubset 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 $ginbigcup_{i=1}^{infty}H_i$ there exists an $i$ so that $gin H_i$, actually this implies $gin H_j$ for all $ileq j$, but we don't need this here. Since $H_i$ is a subgroup $g^{-1}in H_isubseteq 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
add a comment |
$begingroup$
Of course $1inbigcup_{i=1}^{infty}H_i$ and for any $gin H_i$,$hin H_j$ say without loss of generality that $ileq j$ then $gin H_j$ too and since this is a subgroup You have
$$ghin H_jsubset 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 $ginbigcup_{i=1}^{infty}H_i$ there exists an $i$ so that $gin H_i$, actually this implies $gin H_j$ for all $ileq j$, but we don't need this here. Since $H_i$ is a subgroup $g^{-1}in H_isubseteq 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
add a comment |
$begingroup$
Of course $1inbigcup_{i=1}^{infty}H_i$ and for any $gin H_i$,$hin H_j$ say without loss of generality that $ileq j$ then $gin H_j$ too and since this is a subgroup You have
$$ghin H_jsubset 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 $ginbigcup_{i=1}^{infty}H_i$ there exists an $i$ so that $gin H_i$, actually this implies $gin H_j$ for all $ileq j$, but we don't need this here. Since $H_i$ is a subgroup $g^{-1}in H_isubseteq bigcup_{i=1}^{infty}H_i$.
$endgroup$
Of course $1inbigcup_{i=1}^{infty}H_i$ and for any $gin H_i$,$hin H_j$ say without loss of generality that $ileq j$ then $gin H_j$ too and since this is a subgroup You have
$$ghin H_jsubset 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 $ginbigcup_{i=1}^{infty}H_i$ there exists an $i$ so that $gin H_i$, actually this implies $gin H_j$ for all $ileq j$, but we don't need this here. Since $H_i$ is a subgroup $g^{-1}in H_isubseteq bigcup_{i=1}^{infty}H_i$.
edited Feb 14 at 12:32
answered Feb 13 at 13:31
Peter MelechPeter Melech
2,657813
2,657813
$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
add a comment |
$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
$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
$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
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$
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
$begingroup$
@Eleven-Eleven I understand, in this case Arthur's answer seems perfect to me.
$endgroup$
– Peter Melech
Feb 14 at 12:25
1
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
$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
1
$begingroup$
I edited my post.
$endgroup$
– Peter Melech
Feb 14 at 12:32
$begingroup$
I edited my post.
$endgroup$
– Peter Melech
Feb 14 at 12:32
add a comment |
$begingroup$
(I should have read the question more carefully. What follows is a proof by the method the OP excluded.)
Since $ein H_1$, we have $$ein H_1subseteqbigcup_{i=1}^{infty}H_i=:mathcal{U}.$$ Hence $mathcal{U}$ is nonempty.
Let $g, hinmathcal{U}$. Then $gin H_k$ and $hin H_ell$ for some $k, ell$. Assume w.l.o.g. that $k<ell$. Then the ascending chain condition gives that $gin H_ell$. Since $hin 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$
add a comment |
$begingroup$
(I should have read the question more carefully. What follows is a proof by the method the OP excluded.)
Since $ein H_1$, we have $$ein H_1subseteqbigcup_{i=1}^{infty}H_i=:mathcal{U}.$$ Hence $mathcal{U}$ is nonempty.
Let $g, hinmathcal{U}$. Then $gin H_k$ and $hin H_ell$ for some $k, ell$. Assume w.l.o.g. that $k<ell$. Then the ascending chain condition gives that $gin H_ell$. Since $hin 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$
add a comment |
$begingroup$
(I should have read the question more carefully. What follows is a proof by the method the OP excluded.)
Since $ein H_1$, we have $$ein H_1subseteqbigcup_{i=1}^{infty}H_i=:mathcal{U}.$$ Hence $mathcal{U}$ is nonempty.
Let $g, hinmathcal{U}$. Then $gin H_k$ and $hin H_ell$ for some $k, ell$. Assume w.l.o.g. that $k<ell$. Then the ascending chain condition gives that $gin H_ell$. Since $hin 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$
(I should have read the question more carefully. What follows is a proof by the method the OP excluded.)
Since $ein H_1$, we have $$ein H_1subseteqbigcup_{i=1}^{infty}H_i=:mathcal{U}.$$ Hence $mathcal{U}$ is nonempty.
Let $g, hinmathcal{U}$. Then $gin H_k$ and $hin H_ell$ for some $k, ell$. Assume w.l.o.g. that $k<ell$. Then the ascending chain condition gives that $gin H_ell$. Since $hin 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.$$
edited Feb 13 at 16:53
community wiki
3 revs
Shaun
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3111368%2fvalidity-of-using-induction-to-show-union-of-an-infinite-ascending-chain-of-subg%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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 have0.[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