Mixing
The category of Multisets and Spans: morphism composition and tensor product
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I have been thinking about multisets for a while. These are sets where elements can repeat, so $S = a,a,b,c,b$ is a multiset on the set $A = a,b,c$.
I have also been looking into morphisms between multisets. Take two multisets $S_A, S_B$ with underlying sets $A, B$. I would like to define a morphism between multisets $S_A, S_B$ as a span on the underlying sets, so $f = A leftarrow C rightarrow B$, and $f: S_A rightarrow S_B$. I am not sure how to define span composition. I am thinking a lot about David Spivak's work these days, so I am going to suggest a definition from his text, see section 2.5.2.3, which I cannot reproduce here. He uses fiber products.
I have two questions. Firstly, does my definition of the objects and morphisms define a category? Secondly, is it the case that the definition of morphism, as given, also constitutes a tensor product between multisets in the category as defined?
I have only an intuition that tells me that this definition of morphism is both a morphism of multisets in the category defined but is also a tensor product. We know that the Eilenberg-Moore category for the multiset monad is actually $mathbbN$-modules. We should find a notion of tensor product there. I am guessing that we can define a monad on Set that maps a set to its set of multisets and spans as defined. There should be a similar category of modules, and thus a tensor product. I can only guess that what I am thinking means that the spans, as defined, map to both morphisms in the category of modules and the tensor product in the category of modules.
ct.category-theory monoidal-categories multiset
asked 4 hours ago
Ben Sprott
648416
add a comment |Â
up vote
2
down vote
favorite
I have been thinking about multisets for a while. These are sets where elements can repeat, so $S = a,a,b,c,b$ is a multiset on the set $A = a,b,c$.
I have also been looking into morphisms between multisets. Take two multisets $S_A, S_B$ with underlying sets $A, B$. I would like to define a morphism between multisets $S_A, S_B$ as a span on the underlying sets, so $f = A leftarrow C rightarrow B$, and $f: S_A rightarrow S_B$. I am not sure how to define span composition. I am thinking a lot about David Spivak's work these days, so I am going to suggest a definition from his text, see section 2.5.2.3, which I cannot reproduce here. He uses fiber products.
I have two questions. Firstly, does my definition of the objects and morphisms define a category? Secondly, is it the case that the definition of morphism, as given, also constitutes a tensor product between multisets in the category as defined?
I have only an intuition that tells me that this definition of morphism is both a morphism of multisets in the category defined but is also a tensor product. We know that the Eilenberg-Moore category for the multiset monad is actually $mathbbN$-modules. We should find a notion of tensor product there. I am guessing that we can define a monad on Set that maps a set to its set of multisets and spans as defined. There should be a similar category of modules, and thus a tensor product. I can only guess that what I am thinking means that the spans, as defined, map to both morphisms in the category of modules and the tensor product in the category of modules.
ct.category-theory monoidal-categories multiset
asked 4 hours ago
Ben Sprott
648416
1
1. You haven't defined composition so you haven't defined a category. 2. I don't understand what you mean by "a tensor product between multisets". What's the tensor product supposed to be?
– Najib Idrissi
3 hours ago
1
Span composition is defined in 2.5.2.3 that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow?
– áƒ›áƒÂმუკრჯიბლáƒÂძე
3 hours ago
Yes, the span composition would depend on $S_A$ and $S_B$, I was hoping I would not have to modify it. I am saying that the morpisms are just spans and then morphism composition is just span composition.
– Ben Sprott
3 hours ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I have been thinking about multisets for a while. These are sets where elements can repeat, so $S = a,a,b,c,b$ is a multiset on the set $A = a,b,c$.
I have also been looking into morphisms between multisets. Take two multisets $S_A, S_B$ with underlying sets $A, B$. I would like to define a morphism between multisets $S_A, S_B$ as a span on the underlying sets, so $f = A leftarrow C rightarrow B$, and $f: S_A rightarrow S_B$. I am not sure how to define span composition. I am thinking a lot about David Spivak's work these days, so I am going to suggest a definition from his text, see section 2.5.2.3, which I cannot reproduce here. He uses fiber products.
I have two questions. Firstly, does my definition of the objects and morphisms define a category? Secondly, is it the case that the definition of morphism, as given, also constitutes a tensor product between multisets in the category as defined?
I have only an intuition that tells me that this definition of morphism is both a morphism of multisets in the category defined but is also a tensor product. We know that the Eilenberg-Moore category for the multiset monad is actually $mathbbN$-modules. We should find a notion of tensor product there. I am guessing that we can define a monad on Set that maps a set to its set of multisets and spans as defined. There should be a similar category of modules, and thus a tensor product. I can only guess that what I am thinking means that the spans, as defined, map to both morphisms in the category of modules and the tensor product in the category of modules.
ct.category-theory monoidal-categories multiset
asked 4 hours ago
Ben Sprott
648416
I have been thinking about multisets for a while. These are sets where elements can repeat, so $S = a,a,b,c,b$ is a multiset on the set $A = a,b,c$.
I have also been looking into morphisms between multisets. Take two multisets $S_A, S_B$ with underlying sets $A, B$. I would like to define a morphism between multisets $S_A, S_B$ as a span on the underlying sets, so $f = A leftarrow C rightarrow B$, and $f: S_A rightarrow S_B$. I am not sure how to define span composition. I am thinking a lot about David Spivak's work these days, so I am going to suggest a definition from his text, see section 2.5.2.3, which I cannot reproduce here. He uses fiber products.
I have two questions. Firstly, does my definition of the objects and morphisms define a category? Secondly, is it the case that the definition of morphism, as given, also constitutes a tensor product between multisets in the category as defined?
I have only an intuition that tells me that this definition of morphism is both a morphism of multisets in the category defined but is also a tensor product. We know that the Eilenberg-Moore category for the multiset monad is actually $mathbbN$-modules. We should find a notion of tensor product there. I am guessing that we can define a monad on Set that maps a set to its set of multisets and spans as defined. There should be a similar category of modules, and thus a tensor product. I can only guess that what I am thinking means that the spans, as defined, map to both morphisms in the category of modules and the tensor product in the category of modules.
ct.category-theory monoidal-categories multiset
ct.category-theory monoidal-categories multiset
asked 4 hours ago
Ben Sprott
648416
asked 4 hours ago
Ben Sprott
648416
edited 3 hours ago
asked 4 hours ago
Ben Sprott
648416
asked 4 hours ago
Ben Sprott
648416
asked 4 hours ago
Ben Sprott
648416
648416
1
1. You haven't defined composition so you haven't defined a category. 2. I don't understand what you mean by "a tensor product between multisets". What's the tensor product supposed to be?
– Najib Idrissi
3 hours ago
1
Span composition is defined in 2.5.2.3 that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow?
– áƒ›áƒÂმუკრჯიბლáƒÂძე
3 hours ago
Yes, the span composition would depend on $S_A$ and $S_B$, I was hoping I would not have to modify it. I am saying that the morpisms are just spans and then morphism composition is just span composition.
– Ben Sprott
3 hours ago
add a comment |Â
1
1. You haven't defined composition so you haven't defined a category. 2. I don't understand what you mean by "a tensor product between multisets". What's the tensor product supposed to be?
– Najib Idrissi
3 hours ago
1
Span composition is defined in 2.5.2.3 that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow?
– áƒ›áƒÂმუკრჯიბლáƒÂძე
3 hours ago
Yes, the span composition would depend on $S_A$ and $S_B$, I was hoping I would not have to modify it. I am saying that the morpisms are just spans and then morphism composition is just span composition.
– Ben Sprott
3 hours ago
1
1
1. You haven't defined composition so you haven't defined a category. 2. I don't understand what you mean by "a tensor product between multisets". What's the tensor product supposed to be?
– Najib Idrissi
3 hours ago
1. You haven't defined composition so you haven't defined a category. 2. I don't understand what you mean by "a tensor product between multisets". What's the tensor product supposed to be?
– Najib Idrissi
3 hours ago
1
1
Span composition is defined in 2.5.2.3 that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow?
– áƒ›áƒÂმუკრჯიბლáƒÂძე
3 hours ago
Span composition is defined in 2.5.2.3 that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow?
– áƒ›áƒÂმუკრჯიბლáƒÂძე
3 hours ago
Yes, the span composition would depend on $S_A$ and $S_B$, I was hoping I would not have to modify it. I am saying that the morpisms are just spans and then morphism composition is just span composition.
– Ben Sprott
3 hours ago
Yes, the span composition would depend on $S_A$ and $S_B$, I was hoping I would not have to modify it. I am saying that the morpisms are just spans and then morphism composition is just span composition.
– Ben Sprott
3 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
One possibility is as follows. I'll think of a multiset as a finite set $X$ equipped with a multiplicity function $m_X colon X to 1,2,3,dotsc$. We can then define a morphism from $X$ to $Y$ to be a function such that $m_Y(y)=sum_xin f^-1ym_X(x)$ for all $y$. These can be thought of as "bijections up to multiplicity". Let $mathcalM$ be the resulting category of multisets, and let $mathcalM_leq k$ be the subcategory where all multiplicities are at most $k$. These are symmetric monoidal categories under the evident disjoint union operation, so they have $K$-theory spectra in the sense of stable homotopy theory. Standard arguments show that $K(mathcalM_leq 1)$ is just the sphere spectrum. We can also consider $mathbbN$ as a symmetric monoidal category, and there is an adjunction between $mathcalM$ and $mathbbN$ and $K(mathcalM)$, which gives rise to a homotopy equivalence between $K(mathcalM)$ and $K(mathbbN)$, which is just the integer Eilenberg-MacLane spectrum. The really interesting point is that $K(mathcalM_leq k)$ is equivalent to $SP^k(S^0)$, the $k$'th symmetric power of the sphere spectrum, which is important for a variety of reasons. This is essentially a translation of an old theorem of Kathryn Lesh, which she formulated in rather different terms.
As well as the disjoint union, we can also use the function $m_Xtimes Y(x,y)=m_X(x)m_Y(y)$ to make $Xtimes Y$ into a multiset. This makes $mathcalM$ into a symmetric bimonoidal category, with $mathcalM_leq 1$ as a symmetric bimonoidal subcategory; this corresponds to the fact that $S$ and $H$ are ring spectra. This construction also restricts to give functors $mathcalM_leq jtimesmathcalM_leq ktomathcalM_leq jk$, which again have natural counterparts in stable homotopy theory.
answered 2 hours ago
Neil Strickland
35.5k591184
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
One possibility is as follows. I'll think of a multiset as a finite set $X$ equipped with a multiplicity function $m_X colon X to 1,2,3,dotsc$. We can then define a morphism from $X$ to $Y$ to be a function such that $m_Y(y)=sum_xin f^-1ym_X(x)$ for all $y$. These can be thought of as "bijections up to multiplicity". Let $mathcalM$ be the resulting category of multisets, and let $mathcalM_leq k$ be the subcategory where all multiplicities are at most $k$. These are symmetric monoidal categories under the evident disjoint union operation, so they have $K$-theory spectra in the sense of stable homotopy theory. Standard arguments show that $K(mathcalM_leq 1)$ is just the sphere spectrum. We can also consider $mathbbN$ as a symmetric monoidal category, and there is an adjunction between $mathcalM$ and $mathbbN$ and $K(mathcalM)$, which gives rise to a homotopy equivalence between $K(mathcalM)$ and $K(mathbbN)$, which is just the integer Eilenberg-MacLane spectrum. The really interesting point is that $K(mathcalM_leq k)$ is equivalent to $SP^k(S^0)$, the $k$'th symmetric power of the sphere spectrum, which is important for a variety of reasons. This is essentially a translation of an old theorem of Kathryn Lesh, which she formulated in rather different terms.
As well as the disjoint union, we can also use the function $m_Xtimes Y(x,y)=m_X(x)m_Y(y)$ to make $Xtimes Y$ into a multiset. This makes $mathcalM$ into a symmetric bimonoidal category, with $mathcalM_leq 1$ as a symmetric bimonoidal subcategory; this corresponds to the fact that $S$ and $H$ are ring spectra. This construction also restricts to give functors $mathcalM_leq jtimesmathcalM_leq ktomathcalM_leq jk$, which again have natural counterparts in stable homotopy theory.
answered 2 hours ago
Neil Strickland
35.5k591184
add a comment |Â
up vote
4
down vote
One possibility is as follows. I'll think of a multiset as a finite set $X$ equipped with a multiplicity function $m_X colon X to 1,2,3,dotsc$. We can then define a morphism from $X$ to $Y$ to be a function such that $m_Y(y)=sum_xin f^-1ym_X(x)$ for all $y$. These can be thought of as "bijections up to multiplicity". Let $mathcalM$ be the resulting category of multisets, and let $mathcalM_leq k$ be the subcategory where all multiplicities are at most $k$. These are symmetric monoidal categories under the evident disjoint union operation, so they have $K$-theory spectra in the sense of stable homotopy theory. Standard arguments show that $K(mathcalM_leq 1)$ is just the sphere spectrum. We can also consider $mathbbN$ as a symmetric monoidal category, and there is an adjunction between $mathcalM$ and $mathbbN$ and $K(mathcalM)$, which gives rise to a homotopy equivalence between $K(mathcalM)$ and $K(mathbbN)$, which is just the integer Eilenberg-MacLane spectrum. The really interesting point is that $K(mathcalM_leq k)$ is equivalent to $SP^k(S^0)$, the $k$'th symmetric power of the sphere spectrum, which is important for a variety of reasons. This is essentially a translation of an old theorem of Kathryn Lesh, which she formulated in rather different terms.
As well as the disjoint union, we can also use the function $m_Xtimes Y(x,y)=m_X(x)m_Y(y)$ to make $Xtimes Y$ into a multiset. This makes $mathcalM$ into a symmetric bimonoidal category, with $mathcalM_leq 1$ as a symmetric bimonoidal subcategory; this corresponds to the fact that $S$ and $H$ are ring spectra. This construction also restricts to give functors $mathcalM_leq jtimesmathcalM_leq ktomathcalM_leq jk$, which again have natural counterparts in stable homotopy theory.
answered 2 hours ago
Neil Strickland
35.5k591184
add a comment |Â
up vote
4
down vote
up vote
4
down vote
One possibility is as follows. I'll think of a multiset as a finite set $X$ equipped with a multiplicity function $m_X colon X to 1,2,3,dotsc$. We can then define a morphism from $X$ to $Y$ to be a function such that $m_Y(y)=sum_xin f^-1ym_X(x)$ for all $y$. These can be thought of as "bijections up to multiplicity". Let $mathcalM$ be the resulting category of multisets, and let $mathcalM_leq k$ be the subcategory where all multiplicities are at most $k$. These are symmetric monoidal categories under the evident disjoint union operation, so they have $K$-theory spectra in the sense of stable homotopy theory. Standard arguments show that $K(mathcalM_leq 1)$ is just the sphere spectrum. We can also consider $mathbbN$ as a symmetric monoidal category, and there is an adjunction between $mathcalM$ and $mathbbN$ and $K(mathcalM)$, which gives rise to a homotopy equivalence between $K(mathcalM)$ and $K(mathbbN)$, which is just the integer Eilenberg-MacLane spectrum. The really interesting point is that $K(mathcalM_leq k)$ is equivalent to $SP^k(S^0)$, the $k$'th symmetric power of the sphere spectrum, which is important for a variety of reasons. This is essentially a translation of an old theorem of Kathryn Lesh, which she formulated in rather different terms.
As well as the disjoint union, we can also use the function $m_Xtimes Y(x,y)=m_X(x)m_Y(y)$ to make $Xtimes Y$ into a multiset. This makes $mathcalM$ into a symmetric bimonoidal category, with $mathcalM_leq 1$ as a symmetric bimonoidal subcategory; this corresponds to the fact that $S$ and $H$ are ring spectra. This construction also restricts to give functors $mathcalM_leq jtimesmathcalM_leq ktomathcalM_leq jk$, which again have natural counterparts in stable homotopy theory.
answered 2 hours ago
Neil Strickland
35.5k591184
One possibility is as follows. I'll think of a multiset as a finite set $X$ equipped with a multiplicity function $m_X colon X to 1,2,3,dotsc$. We can then define a morphism from $X$ to $Y$ to be a function such that $m_Y(y)=sum_xin f^-1ym_X(x)$ for all $y$. These can be thought of as "bijections up to multiplicity". Let $mathcalM$ be the resulting category of multisets, and let $mathcalM_leq k$ be the subcategory where all multiplicities are at most $k$. These are symmetric monoidal categories under the evident disjoint union operation, so they have $K$-theory spectra in the sense of stable homotopy theory. Standard arguments show that $K(mathcalM_leq 1)$ is just the sphere spectrum. We can also consider $mathbbN$ as a symmetric monoidal category, and there is an adjunction between $mathcalM$ and $mathbbN$ and $K(mathcalM)$, which gives rise to a homotopy equivalence between $K(mathcalM)$ and $K(mathbbN)$, which is just the integer Eilenberg-MacLane spectrum. The really interesting point is that $K(mathcalM_leq k)$ is equivalent to $SP^k(S^0)$, the $k$'th symmetric power of the sphere spectrum, which is important for a variety of reasons. This is essentially a translation of an old theorem of Kathryn Lesh, which she formulated in rather different terms.
As well as the disjoint union, we can also use the function $m_Xtimes Y(x,y)=m_X(x)m_Y(y)$ to make $Xtimes Y$ into a multiset. This makes $mathcalM$ into a symmetric bimonoidal category, with $mathcalM_leq 1$ as a symmetric bimonoidal subcategory; this corresponds to the fact that $S$ and $H$ are ring spectra. This construction also restricts to give functors $mathcalM_leq jtimesmathcalM_leq ktomathcalM_leq jk$, which again have natural counterparts in stable homotopy theory.
answered 2 hours ago
Neil Strickland
35.5k591184
answered 2 hours ago
Neil Strickland
35.5k591184
answered 2 hours ago
Neil Strickland
35.5k591184
answered 2 hours ago
Neil Strickland
35.5k591184
35.5k591184
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f314846%2fthe-category-of-multisets-and-spans-morphism-composition-and-tensor-product%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
1. You haven't defined composition so you haven't defined a category. 2. I don't understand what you mean by "a tensor product between multisets". What's the tensor product supposed to be?
– Najib Idrissi
3 hours ago
1
Span composition is defined in 2.5.2.3 that you refer to. You mean you want to modify it so as to depend on $S_A$ and $S_B$ somehow?
– áƒ›áƒÂმუკრჯიბლáƒÂძე
3 hours ago
Yes, the span composition would depend on $S_A$ and $S_B$, I was hoping I would not have to modify it. I am saying that the morpisms are just spans and then morphism composition is just span composition.
– Ben Sprott
3 hours ago