Mixing
$(G,cdot)$ and $M subseteq G$. Prove that the following algorithm computes the subgroup generated by M.
$begingroup$
Let $(G,cdot)$ be a finite group and $M subseteq G$, $Mne emptyset$.
Prove that the following algorithm computes the subgroup generated by M :
$$S_{0}:={{e}} , H_{0}:={{e}}\
S_{n+1}:=(S_{n}cdot M)setminus H_{n}\
if: S_{n+1}=emptyset : :then : : langle M rangle = H_{n}\
else : : H_{n+1}:= H_{n}cup S_{n+1}$$
Well, I know how to prove it informally but I wonder if there is some more formal-math-not-words proof or if my proof is sufficiently good. Here it is :
Let's look at the nature of the algorithm, if $M={{e}}:then:S_{1}=emptyset : so : langle M rangle=H_{0}={{e}} $,
otherwise everytime $S_{1}=M$ and $H_1={{e}}cup M$. We can interpret the set $H_{n+1}$ as the set that stores the values that are generated by $M$ and the set $S_{n+1}$ as the set that generates only new values. $S_{n+1}=emptyset$ when $S_ncdot M subseteq H_n$ and that happens if new values can't be generated anymore. Therefore the set of the subgroup generated by $M$ is $H_n$.
Cheers!
group-theory elementary-set-theory algorithms recursive-algorithms
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
$endgroup$
add a comment |
$begingroup$
Let $(G,cdot)$ be a finite group and $M subseteq G$, $Mne emptyset$.
Prove that the following algorithm computes the subgroup generated by M :
$$S_{0}:={{e}} , H_{0}:={{e}}\
S_{n+1}:=(S_{n}cdot M)setminus H_{n}\
if: S_{n+1}=emptyset : :then : : langle M rangle = H_{n}\
else : : H_{n+1}:= H_{n}cup S_{n+1}$$
Well, I know how to prove it informally but I wonder if there is some more formal-math-not-words proof or if my proof is sufficiently good. Here it is :
Let's look at the nature of the algorithm, if $M={{e}}:then:S_{1}=emptyset : so : langle M rangle=H_{0}={{e}} $,
otherwise everytime $S_{1}=M$ and $H_1={{e}}cup M$. We can interpret the set $H_{n+1}$ as the set that stores the values that are generated by $M$ and the set $S_{n+1}$ as the set that generates only new values. $S_{n+1}=emptyset$ when $S_ncdot M subseteq H_n$ and that happens if new values can't be generated anymore. Therefore the set of the subgroup generated by $M$ is $H_n$.
Cheers!
group-theory elementary-set-theory algorithms recursive-algorithms
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
$endgroup$
add a comment |
$begingroup$
Let $(G,cdot)$ be a finite group and $M subseteq G$, $Mne emptyset$.
Prove that the following algorithm computes the subgroup generated by M :
$$S_{0}:={{e}} , H_{0}:={{e}}\
S_{n+1}:=(S_{n}cdot M)setminus H_{n}\
if: S_{n+1}=emptyset : :then : : langle M rangle = H_{n}\
else : : H_{n+1}:= H_{n}cup S_{n+1}$$
Well, I know how to prove it informally but I wonder if there is some more formal-math-not-words proof or if my proof is sufficiently good. Here it is :
Let's look at the nature of the algorithm, if $M={{e}}:then:S_{1}=emptyset : so : langle M rangle=H_{0}={{e}} $,
otherwise everytime $S_{1}=M$ and $H_1={{e}}cup M$. We can interpret the set $H_{n+1}$ as the set that stores the values that are generated by $M$ and the set $S_{n+1}$ as the set that generates only new values. $S_{n+1}=emptyset$ when $S_ncdot M subseteq H_n$ and that happens if new values can't be generated anymore. Therefore the set of the subgroup generated by $M$ is $H_n$.
Cheers!
group-theory elementary-set-theory algorithms recursive-algorithms
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
$endgroup$
Let $(G,cdot)$ be a finite group and $M subseteq G$, $Mne emptyset$.
Prove that the following algorithm computes the subgroup generated by M :
$$S_{0}:={{e}} , H_{0}:={{e}}\
S_{n+1}:=(S_{n}cdot M)setminus H_{n}\
if: S_{n+1}=emptyset : :then : : langle M rangle = H_{n}\
else : : H_{n+1}:= H_{n}cup S_{n+1}$$
Well, I know how to prove it informally but I wonder if there is some more formal-math-not-words proof or if my proof is sufficiently good. Here it is :
Let's look at the nature of the algorithm, if $M={{e}}:then:S_{1}=emptyset : so : langle M rangle=H_{0}={{e}} $,
otherwise everytime $S_{1}=M$ and $H_1={{e}}cup M$. We can interpret the set $H_{n+1}$ as the set that stores the values that are generated by $M$ and the set $S_{n+1}$ as the set that generates only new values. $S_{n+1}=emptyset$ when $S_ncdot M subseteq H_n$ and that happens if new values can't be generated anymore. Therefore the set of the subgroup generated by $M$ is $H_n$.
Cheers!
group-theory elementary-set-theory algorithms recursive-algorithms
group-theory elementary-set-theory algorithms recursive-algorithms
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
asked Jan 28 at 13:44
Alexe Luca SpataruAlexe Luca Spataru
83
83
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The informal idea is OK. Some remarks:
You will first need some kind of lemma that we only need a subset to be closed under powers to conclude it is a subgroup (this follows from the fact that all $g$ have finite order as $|G|$ is finite, and some basic group theory).
The algorithm is just a way to compute all the products among the set $M$ and their powers as well, keeping track of only the new elements. By finiteness of the group some $S_n$ will have to be empty, as they are pairwise disjoint for different $n$ (which you can probably show by induction). So the algorithm terminates. It's also clear (by induction) that all $H_n subseteq langle M rangle$ and then you have to come up with an argument why we have equality precisely when $S_{n+1} = emptyset$.
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
$begingroup$
Thanks, this is helpful!
$endgroup$
– Alexe Luca Spataru
Jan 28 at 15:58
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%2f3090869%2fg-cdot-and-m-subseteq-g-prove-that-the-following-algorithm-computes-the%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The informal idea is OK. Some remarks:
You will first need some kind of lemma that we only need a subset to be closed under powers to conclude it is a subgroup (this follows from the fact that all $g$ have finite order as $|G|$ is finite, and some basic group theory).
The algorithm is just a way to compute all the products among the set $M$ and their powers as well, keeping track of only the new elements. By finiteness of the group some $S_n$ will have to be empty, as they are pairwise disjoint for different $n$ (which you can probably show by induction). So the algorithm terminates. It's also clear (by induction) that all $H_n subseteq langle M rangle$ and then you have to come up with an argument why we have equality precisely when $S_{n+1} = emptyset$.
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
$begingroup$
Thanks, this is helpful!
$endgroup$
– Alexe Luca Spataru
Jan 28 at 15:58
add a comment |
$begingroup$
The informal idea is OK. Some remarks:
You will first need some kind of lemma that we only need a subset to be closed under powers to conclude it is a subgroup (this follows from the fact that all $g$ have finite order as $|G|$ is finite, and some basic group theory).
The algorithm is just a way to compute all the products among the set $M$ and their powers as well, keeping track of only the new elements. By finiteness of the group some $S_n$ will have to be empty, as they are pairwise disjoint for different $n$ (which you can probably show by induction). So the algorithm terminates. It's also clear (by induction) that all $H_n subseteq langle M rangle$ and then you have to come up with an argument why we have equality precisely when $S_{n+1} = emptyset$.
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
$begingroup$
Thanks, this is helpful!
$endgroup$
– Alexe Luca Spataru
Jan 28 at 15:58
add a comment |
$begingroup$
The informal idea is OK. Some remarks:
You will first need some kind of lemma that we only need a subset to be closed under powers to conclude it is a subgroup (this follows from the fact that all $g$ have finite order as $|G|$ is finite, and some basic group theory).
The algorithm is just a way to compute all the products among the set $M$ and their powers as well, keeping track of only the new elements. By finiteness of the group some $S_n$ will have to be empty, as they are pairwise disjoint for different $n$ (which you can probably show by induction). So the algorithm terminates. It's also clear (by induction) that all $H_n subseteq langle M rangle$ and then you have to come up with an argument why we have equality precisely when $S_{n+1} = emptyset$.
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
$endgroup$
The informal idea is OK. Some remarks:
You will first need some kind of lemma that we only need a subset to be closed under powers to conclude it is a subgroup (this follows from the fact that all $g$ have finite order as $|G|$ is finite, and some basic group theory).
The algorithm is just a way to compute all the products among the set $M$ and their powers as well, keeping track of only the new elements. By finiteness of the group some $S_n$ will have to be empty, as they are pairwise disjoint for different $n$ (which you can probably show by induction). So the algorithm terminates. It's also clear (by induction) that all $H_n subseteq langle M rangle$ and then you have to come up with an argument why we have equality precisely when $S_{n+1} = emptyset$.
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
answered Jan 28 at 15:53
Henno BrandsmaHenno Brandsma
114k348123
114k348123
$begingroup$
Thanks, this is helpful!
$endgroup$
– Alexe Luca Spataru
Jan 28 at 15:58
add a comment |
$begingroup$
Thanks, this is helpful!
$endgroup$
– Alexe Luca Spataru
Jan 28 at 15:58
$begingroup$
Thanks, this is helpful!
$endgroup$
– Alexe Luca Spataru
Jan 28 at 15:58
$begingroup$
Thanks, this is helpful!
$endgroup$
– Alexe Luca Spataru
Jan 28 at 15:58
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%2f3090869%2fg-cdot-and-m-subseteq-g-prove-that-the-following-algorithm-computes-the%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
