What does the endofunctor/monad that sends a set to the set of finite words on the set do to morphisms?
$begingroup$
Suppose we have a monad $T:Set rightarrow Set$ that sends a set X to the set of finite words on the set X, with the unit and multiplication being inclusion and concatenation respectively. What does such a monad do to a function $f: X rightarrow Y$ for two sets $X$ and $Y$?
I assume it defines the image pointwise, i.e. $T(f)(xy) = f(x)f(y)$, however I cannot find a source confirming this. I suppose it is a question of convention, and if so then I am just looking for the conventional answer. I assume there are other (not so sensible) monads, however I am not interested in these.
If this is the case, then I think problems will arise when the domain contains composite words. Consider a function $f: {x,y,xy} rightarrow {x,y}$, where $xy$ is the word formed by the concatenation of the words $x$ and $y$. Then what is $T(f)$? If it is defined pointwise, then we would have to have a coherence $f(xy) = f(x)f(y)$ in order for the pointwise definition to make sense.
If anyone could offer any clarification on this matter (or sources discussing it) it would be much appreciated.
It is possible that my understanding of the set image of the functor is incorrect. I am currently working under the assumption that $T^2(X) = T(X)$, however the more I think about this the more silly this seems. This is probably the root of my problem.
category-theory functors monads
asked Dec 31 '18 at 12:28
DavenDaven
40229
$endgroup$
add a comment |
$begingroup$
Suppose we have a monad $T:Set rightarrow Set$ that sends a set X to the set of finite words on the set X, with the unit and multiplication being inclusion and concatenation respectively. What does such a monad do to a function $f: X rightarrow Y$ for two sets $X$ and $Y$?
I assume it defines the image pointwise, i.e. $T(f)(xy) = f(x)f(y)$, however I cannot find a source confirming this. I suppose it is a question of convention, and if so then I am just looking for the conventional answer. I assume there are other (not so sensible) monads, however I am not interested in these.
If this is the case, then I think problems will arise when the domain contains composite words. Consider a function $f: {x,y,xy} rightarrow {x,y}$, where $xy$ is the word formed by the concatenation of the words $x$ and $y$. Then what is $T(f)$? If it is defined pointwise, then we would have to have a coherence $f(xy) = f(x)f(y)$ in order for the pointwise definition to make sense.
If anyone could offer any clarification on this matter (or sources discussing it) it would be much appreciated.
It is possible that my understanding of the set image of the functor is incorrect. I am currently working under the assumption that $T^2(X) = T(X)$, however the more I think about this the more silly this seems. This is probably the root of my problem.
category-theory functors monads
asked Dec 31 '18 at 12:28
DavenDaven
40229
$endgroup$
add a comment |
$begingroup$
Suppose we have a monad $T:Set rightarrow Set$ that sends a set X to the set of finite words on the set X, with the unit and multiplication being inclusion and concatenation respectively. What does such a monad do to a function $f: X rightarrow Y$ for two sets $X$ and $Y$?
I assume it defines the image pointwise, i.e. $T(f)(xy) = f(x)f(y)$, however I cannot find a source confirming this. I suppose it is a question of convention, and if so then I am just looking for the conventional answer. I assume there are other (not so sensible) monads, however I am not interested in these.
If this is the case, then I think problems will arise when the domain contains composite words. Consider a function $f: {x,y,xy} rightarrow {x,y}$, where $xy$ is the word formed by the concatenation of the words $x$ and $y$. Then what is $T(f)$? If it is defined pointwise, then we would have to have a coherence $f(xy) = f(x)f(y)$ in order for the pointwise definition to make sense.
If anyone could offer any clarification on this matter (or sources discussing it) it would be much appreciated.
It is possible that my understanding of the set image of the functor is incorrect. I am currently working under the assumption that $T^2(X) = T(X)$, however the more I think about this the more silly this seems. This is probably the root of my problem.
category-theory functors monads
asked Dec 31 '18 at 12:28
DavenDaven
40229
$endgroup$
Suppose we have a monad $T:Set rightarrow Set$ that sends a set X to the set of finite words on the set X, with the unit and multiplication being inclusion and concatenation respectively. What does such a monad do to a function $f: X rightarrow Y$ for two sets $X$ and $Y$?
I assume it defines the image pointwise, i.e. $T(f)(xy) = f(x)f(y)$, however I cannot find a source confirming this. I suppose it is a question of convention, and if so then I am just looking for the conventional answer. I assume there are other (not so sensible) monads, however I am not interested in these.
If this is the case, then I think problems will arise when the domain contains composite words. Consider a function $f: {x,y,xy} rightarrow {x,y}$, where $xy$ is the word formed by the concatenation of the words $x$ and $y$. Then what is $T(f)$? If it is defined pointwise, then we would have to have a coherence $f(xy) = f(x)f(y)$ in order for the pointwise definition to make sense.
If anyone could offer any clarification on this matter (or sources discussing it) it would be much appreciated.
It is possible that my understanding of the set image of the functor is incorrect. I am currently working under the assumption that $T^2(X) = T(X)$, however the more I think about this the more silly this seems. This is probably the root of my problem.
category-theory functors monads
category-theory functors monads
asked Dec 31 '18 at 12:28
DavenDaven
40229
asked Dec 31 '18 at 12:28
DavenDaven
40229
edited Dec 31 '18 at 12:33
Daven
asked Dec 31 '18 at 12:28
DavenDaven
40229
asked Dec 31 '18 at 12:28
DavenDaven
40229
asked Dec 31 '18 at 12:28
DavenDaven
40229
40229
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You seem to be referring to the free monoid monad. The underlying functor $Tcolon mathbf {Set}to mathbf{Set}$ of this monad is the free monoid functor which sends a set $S$ to the free monoid on $S$, namely all finite words in the alphabet $S$. This functor is defined on morphisms in the pointwise manner you suggest, namely for a function $fcolon Sto T$ and a word $w=s_1dots s_n$ in $T(S)$ we have $T(f)(w)=f(s_1)dots f(s_n)$. This is not ambiguous though since in the free monoid $T(S)$ every word decomposes uniquely as a concatenation of letters. In the example you are giving you need to treat $xy$ as a single symbol. Your set $S={x,y,xy}$ is simply a set with three things in it. The set does not 'know' (nor does it care) that to you it seems like one of these things is already a concatenation of the other two things.
You can, of course, consider the monoid generated by ${x,y,z}$ subject to the relation $z=xy$. But this isn't a free monoid (but it is a quotient of one, namely the free monoid on three elements).
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
$endgroup$
1
$begingroup$
This monad is also known as the List monad in computer science, and the way it operates on morphisms is also known as map: see e.g. zvon.org/other/haskell/Outputprelude/map_f.html
$endgroup$
– Qiaochu Yuan
Dec 31 '18 at 20:55
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%2f3057662%2fwhat-does-the-endofunctor-monad-that-sends-a-set-to-the-set-of-finite-words-on-t%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$
You seem to be referring to the free monoid monad. The underlying functor $Tcolon mathbf {Set}to mathbf{Set}$ of this monad is the free monoid functor which sends a set $S$ to the free monoid on $S$, namely all finite words in the alphabet $S$. This functor is defined on morphisms in the pointwise manner you suggest, namely for a function $fcolon Sto T$ and a word $w=s_1dots s_n$ in $T(S)$ we have $T(f)(w)=f(s_1)dots f(s_n)$. This is not ambiguous though since in the free monoid $T(S)$ every word decomposes uniquely as a concatenation of letters. In the example you are giving you need to treat $xy$ as a single symbol. Your set $S={x,y,xy}$ is simply a set with three things in it. The set does not 'know' (nor does it care) that to you it seems like one of these things is already a concatenation of the other two things.
You can, of course, consider the monoid generated by ${x,y,z}$ subject to the relation $z=xy$. But this isn't a free monoid (but it is a quotient of one, namely the free monoid on three elements).
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
$endgroup$
1
$begingroup$
This monad is also known as the List monad in computer science, and the way it operates on morphisms is also known as map: see e.g. zvon.org/other/haskell/Outputprelude/map_f.html
$endgroup$
– Qiaochu Yuan
Dec 31 '18 at 20:55
add a comment |
$begingroup$
You seem to be referring to the free monoid monad. The underlying functor $Tcolon mathbf {Set}to mathbf{Set}$ of this monad is the free monoid functor which sends a set $S$ to the free monoid on $S$, namely all finite words in the alphabet $S$. This functor is defined on morphisms in the pointwise manner you suggest, namely for a function $fcolon Sto T$ and a word $w=s_1dots s_n$ in $T(S)$ we have $T(f)(w)=f(s_1)dots f(s_n)$. This is not ambiguous though since in the free monoid $T(S)$ every word decomposes uniquely as a concatenation of letters. In the example you are giving you need to treat $xy$ as a single symbol. Your set $S={x,y,xy}$ is simply a set with three things in it. The set does not 'know' (nor does it care) that to you it seems like one of these things is already a concatenation of the other two things.
You can, of course, consider the monoid generated by ${x,y,z}$ subject to the relation $z=xy$. But this isn't a free monoid (but it is a quotient of one, namely the free monoid on three elements).
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
$endgroup$
1
$begingroup$
This monad is also known as the List monad in computer science, and the way it operates on morphisms is also known as map: see e.g. zvon.org/other/haskell/Outputprelude/map_f.html
$endgroup$
– Qiaochu Yuan
Dec 31 '18 at 20:55
add a comment |
$begingroup$
You seem to be referring to the free monoid monad. The underlying functor $Tcolon mathbf {Set}to mathbf{Set}$ of this monad is the free monoid functor which sends a set $S$ to the free monoid on $S$, namely all finite words in the alphabet $S$. This functor is defined on morphisms in the pointwise manner you suggest, namely for a function $fcolon Sto T$ and a word $w=s_1dots s_n$ in $T(S)$ we have $T(f)(w)=f(s_1)dots f(s_n)$. This is not ambiguous though since in the free monoid $T(S)$ every word decomposes uniquely as a concatenation of letters. In the example you are giving you need to treat $xy$ as a single symbol. Your set $S={x,y,xy}$ is simply a set with three things in it. The set does not 'know' (nor does it care) that to you it seems like one of these things is already a concatenation of the other two things.
You can, of course, consider the monoid generated by ${x,y,z}$ subject to the relation $z=xy$. But this isn't a free monoid (but it is a quotient of one, namely the free monoid on three elements).
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
$endgroup$
You seem to be referring to the free monoid monad. The underlying functor $Tcolon mathbf {Set}to mathbf{Set}$ of this monad is the free monoid functor which sends a set $S$ to the free monoid on $S$, namely all finite words in the alphabet $S$. This functor is defined on morphisms in the pointwise manner you suggest, namely for a function $fcolon Sto T$ and a word $w=s_1dots s_n$ in $T(S)$ we have $T(f)(w)=f(s_1)dots f(s_n)$. This is not ambiguous though since in the free monoid $T(S)$ every word decomposes uniquely as a concatenation of letters. In the example you are giving you need to treat $xy$ as a single symbol. Your set $S={x,y,xy}$ is simply a set with three things in it. The set does not 'know' (nor does it care) that to you it seems like one of these things is already a concatenation of the other two things.
You can, of course, consider the monoid generated by ${x,y,z}$ subject to the relation $z=xy$. But this isn't a free monoid (but it is a quotient of one, namely the free monoid on three elements).
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
answered Dec 31 '18 at 12:44
Ittay WeissIttay Weiss
64.2k7102185
64.2k7102185
1
$begingroup$
This monad is also known as the List monad in computer science, and the way it operates on morphisms is also known as map: see e.g. zvon.org/other/haskell/Outputprelude/map_f.html
$endgroup$
– Qiaochu Yuan
Dec 31 '18 at 20:55
add a comment |
1
$begingroup$
This monad is also known as the List monad in computer science, and the way it operates on morphisms is also known as map: see e.g. zvon.org/other/haskell/Outputprelude/map_f.html
$endgroup$
– Qiaochu Yuan
Dec 31 '18 at 20:55
1
1
$begingroup$
This monad is also known as the List monad in computer science, and the way it operates on morphisms is also known as map: see e.g. zvon.org/other/haskell/Outputprelude/map_f.html
$endgroup$
– Qiaochu Yuan
Dec 31 '18 at 20:55
$begingroup$
This monad is also known as the List monad in computer science, and the way it operates on morphisms is also known as map: see e.g. zvon.org/other/haskell/Outputprelude/map_f.html
$endgroup$
– Qiaochu Yuan
Dec 31 '18 at 20:55
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%2f3057662%2fwhat-does-the-endofunctor-monad-that-sends-a-set-to-the-set-of-finite-words-on-t%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
