Structures
\[\gdef\badDispatch#1{\textbf{\textcolor{e1432d}{#1}}} \gdef\noKatexForm#1{\badDispatch{#1}} \gdef\largeDot{\raisebox{0.06em}{\tiny∙}} \gdef\rarrbar{{\raisebox{-0.05em}{→}\mkern{-0.13em}{\large\shortmid}}} \gdef\larrbar{{{\large\shortmid}\mkern{-0.13em}{\raisebox{-0.05em}{←}}}} \gdef\suptrans{^\mathsf{T}} \gdef\supdagger{^\dagger} \gdef\cardinalRewrite#1#2{\rewrite{#1}{#2}} \gdef\primed#1{{#1}^{\prime}} \gdef\tinybullet{{\tiny●}} \gdef\factsym#1{\mathord{#1}} \gdef\forwardFactor{\factsym{\uparrow}} \gdef\backwardFactor{\factsym{\downarrow}} \gdef\forwardBackwardFactor{\factsym{\updownarrow}} \gdef\forwardBackwardNeutralFactor{\factsym{\mathrlap{\downarrow}{\mathrlap{\uparrow}{\endash} } }} \gdef\neutralFactor{\factsym{\shornarrow}} \gdef\edgedot{↫} \gdef\desym{\mathbin{↣}} \gdef\uesym{\mathbin{↢}} \gdef\de#1#2{{{#1}\desym{#2}}} \gdef\ue#1#2{{{#1}\uesym{#2}}} \gdef\shifttag#1{\raisebox{-1em}{$#1$}} \gdef\shifttag#1{#1} \gdef\tde#1#2#3{{#1}\:\xrightedge{\shifttag{#3}}\;{#2}} \gdef\tue#1#2#3{{#1}\;\xundirectededge{\shifttag{#3}}\;{#2}} \gdef\shiftunderset#1#2{\underset{\raisebox{0.15em}{\scriptsize $#1$}}{#2}} \gdef\mdtde#1#2#3#4{{#1}\,\;\shiftunderset{#4}{\xrightedge{#3}}\;{#2}} \gdef\mtue#1#2#3#4{{#1}\,\;\shiftunderset{#4}{\xundirectededge{#3}}\;\,{#2}} \gdef\mtde#1#2#3#4{{#1}\,\;\operatornamewithlimits{\xrightedge{#3}}\limits_{#4} \;{#2}} \gdef\mapsfrom{\htmlClass{hreflect}{\mapsto}} \gdef\longmapsfrom{\htmlClass{hreflect}{\longmapsto}} \gdef\diffd{𝕕} \gdef\partialdof#1{\partial {#1}} \gdef\textAnd{\text{\,and\,}} \gdef\identicallyEqualSymbol{\equiv} \gdef\congruentSymbol{\equiv} \gdef\isomorphicSymbol{\simeq} \gdef\homeomorphicSymbol{\cong} \gdef\homotopicSymbol{\simeq} \gdef\approxEqualSymbol{\approx} \gdef\bijectiveSymbol{\approx} \gdef\defeq{\mathrel{≝}} \gdef\defEqualSymbol{\mathrel{≝}} \gdef\syntaxEqualSymbol{\mathrel{\textcolor{888888}{\equiv}}} \gdef\tailEqualSymbol{\underdot{=}} \gdef\headEqualSymbol{\dot{=}} \gdef\ruledelayed{:\to} \gdef\mathdollar{\text{\textdollar}} \gdef\hyphen{\text{-}} \gdef\endash{\text{--}} \gdef\emdash{\text{---}} \gdef\updownarrows{\uparrow\!\downarrow} \gdef\vthinspace{\mkern{1pt}} \gdef\dlq{\text{\textquotedblleft}} \gdef\drq{\text{\textquotedblright}} \gdef\dprime{{\prime\prime}} \gdef\inverse#1{{{#1}^{-1}}} \gdef\inverseSymbol{\inverse{□}} \gdef\groupDirectProduct#1{#1} \gdef\groupDirectProductSymbol{\times} \gdef\groupInverse{\inverse} \gdef\groupPower#1#2{{#1}^{#2}} \gdef\groupCommutator#1#2{\left[{#1},{#2}\right]} \gdef\groupoidInverse{\inverse} \gdef\latticeBFS#1{\textrm{bfs}({#1})} \gdef\pathHomomorphism#1{#1} \gdef\groupoidFunction#1{#1} \gdef\groupoidHomomorphism#1{#1} \gdef\affineModifier#1{\overrightharpoon{#1}} \gdef\supercirc#1{#1^{\circ}} \gdef\supercircb#1{#1^{\bullet}} \gdef\blackCircleModifier#1{\supercircb{#1}} \gdef\whiteCircleModifier#1{\supercirc{#1}} \gdef\totalSpaceStyle#1{\piFo{#1}} \gdef\baseSpaceStyle#1{\blFo{#1}} \gdef\fiberSpaceStyle#1{\reFo{#1}} \gdef\totalSpaceElementStyle#1{\daPiFo{#1}} \gdef\baseSpaceElementStyle#1{\daBlFo{#1}} \gdef\fiberSpaceElementStyle#1{\daReFo{#1}} \gdef\bundleProjectionStyle#1{\daGrFo{#1}} \gdef\bundleGraphStyle#1{\piFo{#1}} \gdef\bundleSectionStyle#1{\daOrFo{#1}} \gdef\bundleFunctionStyle#1{\daPiFo{#1}} \gdef\graphFunctionStyle#1{\totalSpaceStyle{#1}} \gdef\projectionFunctionStyle#1{\totalSpaceStyle{#1}} \gdef\sectionFunctionStyle#1{\totalSpaceStyle{#1}} \gdef\functionGraph#1{G_{#1}} \gdef\toroidalModifier#1{\supercirc{#1}} \gdef\modulo#1{\supercirc{#1}} \gdef\dividesSymbol{\mathrel{|}} \gdef\groupFunction#1{#1} \gdef\groupHomomorphism#1{#1} \gdef\automorphisms{\operatorname{Aut}} \gdef\endomorphisms{\operatorname{End}} \gdef\transportMap#1{\transportMapSymbol_{#1}} \gdef\transportMapSymbol{\tau} \gdef\action#1{#1} \gdef\selfAction#1{\hat{#1}} \gdef\actionGroupoid#1{\utilde{#1}} \gdef\cardinalGroup#1{G^*({#1})} \gdef\signed#1{{#1}^*} \gdef\transportAtlas#1{T_{#1}} \gdef\inverted#1{\underline{#1}} \gdef\mirror#1{\overline{#1}} \gdef\pathComposeSymbol{\mathbin{∷}} \gdef\pathCompose#1#2{{#1}\pathComposeSymbol{#2}} \gdef\translateSymbol{\mathbin{\uparrow}} \gdef\backwardTranslateSymbol{\mathbin{\downarrow}} \gdef\pathHead#1{\pathHeadVector{#1}} \gdef\pathTail#1{\pathTailVector{#1}} \gdef\pathHeadVector#1{{#1}^{\bullet}} \gdef\pathTailVector#1{{#1}_{\bullet}} \gdef\pathReverse#1{{#1}^{\dagger}} \gdef\pathIntegral#1#2{{#1} \int {#2}} \gdef\pathIntegralSymbol{{\int}} \gdef\pathDot#1#2{{#1} \cdot {#2}} \gdef\pathDotSymbol{{\cdot}} \gdef\compactBasis#1{\mathscr{B}} \gdef\length{\operatorname{len}} \gdef\signedLength{\operatorname{len^*}} \gdef\andFn{\operatorname{and}} \gdef\orFn{\operatorname{or}} \gdef\notFn{\operatorname{not}} \gdef\vertexList{\operatorname{vertices}} \gdef\vertexList{\operatorname{vertices}} \gdef\edgeList{\operatorname{edges}} \gdef\pathList{\operatorname{paths}} \gdef\cardinalList{\operatorname{cards}} \gdef\signedCardinalList{\operatorname{cards^*}} \gdef\wordOf{\operatorname{word}} \gdef\headVertex{\operatorname{head}} \gdef\tailVertex{\operatorname{tail}} \gdef\basis{\operatorname{basis}} \gdef\split{\operatorname{split}} \gdef\lcm{\operatorname{lcm}} \gdef\minimalContractionSets{\operatorname{MCSets}} \gdef\minimalContractions{\operatorname{MC}} \gdef\grade{\operatorname{grade}} \gdef\support{\operatorname{support}} \gdef\coefficient{\operatorname{coeff}} \gdef\domain{\operatorname{domain}} \gdef\codomain{\operatorname{codomain}} \gdef\modFunction{\operatorname{mod}} \gdef\clip{\operatorname{clip}} \gdef\sign{\operatorname{sign}} \gdef\step{\operatorname{step}} \gdef\projection{\operatorname{proj}} \gdef\lift{\operatorname{lift}} \gdef\identity{\operatorname{id}} \gdef\total{\operatorname{total}} \gdef\torus{\operatorname{torus}} \gdef\mobius{\operatorname{mobius}} \gdef\stateCompose{\operatorname{glue}} \gdef\infixStateComposeSymbol{\_} \gdef\stateDecompose{\operatorname{melt}} \gdef\stateJoin{\operatorname{conj}} \gdef\stateMeet{\operatorname{disj}} \gdef\stateExtent{\operatorname{extent}} \gdef\stateIntent{\operatorname{intent}} \gdef\infixStateJoinSymbol{\sqcup} \gdef\infixStateMeetSymbol{\sqcap} \gdef\isPrime#1{#1\textrm{ prime}} \gdef\blank{\_} \gdef\emptyWord{} \gdef\multiwordSymbol#1{\mathbf{#1}} \gdef\wordSymbol#1{\mathtt{#1}} \gdef\word#1{#1} \gdef\pathMap#1{#1} \gdef\function#1{#1} \gdef\imageModifier#1{{#1}^{\rightarrow}} \gdef\preimageModifier#1{{#1}^{\leftarrow}} \gdef\multiImageColorModifier#1{\msetCol{#1}} \gdef\multiImageModifier#1{{#1}^{\Rightarrow}} \gdef\multiPreimageModifier#1{{#1}^{\Leftarrow}} \gdef\functionComposition#1{#1} \gdef\functionCompositionSymbol{\mathbin{\small ∘}} \gdef\rightFunctionComposition#1{#1} \gdef\rightFunctionCompositionSymbol{\mathbin{\tiny ●}} \gdef\route#1#2#3{[{#1}\!:\!{#2}\!:\!{#3}]} \gdef\multiroute#1#2#3{[{#1}\!:\!{#2}\!:\!{#3}]} \gdef\pathWord#1#2#3{{#1}\!:\!{#2}\!:\!{#3}} \gdef\parenPathWord#1#2#3{\left(\pathWord{#1}{#2}{#3}\right)} \gdef\nullPath{\bot} \gdef\nullElement{\bot} \gdef\path#1{#1} \gdef\vert#1{#1} \gdef\underdot#1{\underset{\raisebox{0.3em}{.}}{#1}} \gdef\headVertexSymbol{◨} \gdef\tailVertexSymbol{◧} \gdef\placeholderVertexSymbol{\mathrlap{◨}{◧}} \gdef\tvert#1{\underdot{#1}} \gdef\hvert#1{\dot{#1}} \gdef\edge#1{#1} \gdef\card#1{\mathtt{#1}} \gdef\path#1{#1} \gdef\quiver#1{#1} \gdef\bindingRuleSymbol{\to} \gdef\compactBindingRuleSymbol{:} \gdef\cayleyQuiverSymbol#1{\selfAction{#1}} \gdef\bindCayleyQuiver#1#2{\selfAction{#1}[#2]} \gdef\bindActionQuiver#1#2{#1[#2]} \gdef\bindSize#1#2{#1(#2)} \gdef\bindCardSize#1#2{#1[#2]} \gdef\bindCards#1#2{#1[#2]} \gdef\subSize#1#2{#1_{#2}} \gdef\gridQuiver#1{\textrm{Grid}^{#1}} \gdef\treeQuiver#1{\textrm{Tree}^{#1}} \gdef\bouquetQuiver#1{\textrm{Bq}^{#1}} \gdef\lineQuiver{\textrm{L}} \gdef\cycleQuiver{\textrm{C}} \gdef\squareQuiver{\textrm{Sq}} \gdef\cubicQuiver{\textrm{Cbc}} \gdef\triangularQuiver{\textrm{Tri}} \gdef\hexagonalQuiver{\textrm{Hex}} \gdef\rhombilleQuiver{\textrm{Rmb}} \gdef\limit#1#2{\lim_{#2}\,#1} \gdef\realVectorSpace#1{\mathbb{R}^{#1}} \gdef\complexVectorSpace#1{\mathbb{C}^{#1}} \gdef\matrixRing#1#2{M_{#2}(#1)} \gdef\groupoid#1{#1} \gdef\group#1{#1} \gdef\field#1{#1} \gdef\ring#1{#1} \gdef\variable#1{#1} \gdef\semiring#1{#1} \gdef\sym#1{#1} \gdef\matrix#1{#1} \gdef\tupleSym#1{#1} \gdef\polynomial#1{#1} \gdef\setLetter{\mathcal{S}} \gdef\signedSetLetter{\mathcal{S^*}} \gdef\multisetLetter{\mathcal{M}} \gdef\signedMultisetLetter{\mathcal{M^*}} \gdef\multisetSemiringSymbol#1{#1} \gdef\multisetSemiring#1#2{\multisetLetter\left[#1, #2\right]} \gdef\signedMultisetRingSymbol#1{#1} \gdef\signedMultisetRing#1#2{\signedMultisetLetter\left[#1, #2\right]} \gdef\polynomialRing#1#2{#1[{#2}]} \gdef\routeSymbol#1{#1} \gdef\multirouteSymbol#1{\mathbf{#1}} \gdef\planSymbol#1{\mathbf{#1}} \gdef\ringElement#1{#1} \gdef\tuplePart#1#2{#1\llbracket{#2}\rrbracket} \gdef\matrixPart#1#2#3{#1\llbracket{#2,#3}\rrbracket} \gdef\matrixRowPart#1{#1} \gdef\matrixColumnPart#1{#1} \gdef\subMatrixPart#1#2#3{#1_{#2,#3}} \gdef\matrixDotSymbol{\cdot} \gdef\matrixPlusSymbol{+} \gdef\wordGroup#1{\wordGroupSymbol_{#1}} \gdef\wordGroupSymbol{\Omega} \gdef\wordRing#1{\wordRingSymbol_{#1}} \gdef\wordRingSymbol{\Omega\!\degree} \gdef\wordRingElement#1{#1} \gdef\wordRingBasisElement#1{e_{#1}} \gdef\linearCombinationCoefficient#1{{\textcolor{888888}{#1}}} \gdef\plan#1{#1} \gdef\planRing#1{\planRingSymbol_{#1}} \gdef\planRingSymbol{\Phi} \gdef\basisPath#1#2{\mathbf{#1}_{#2}} \gdef\basisPathWeight#1#2{{#1}_{#2}} \gdef\unitSymbol{\mathbf{e}} \gdef\unitVertexField{\unitSymbol_1} \gdef\forwardSymbol{f} \gdef\backwardSymbol{b} \gdef\symmetricSymbol{s} \gdef\antisymmetricSymbol{a} \gdef\wordVector#1#2{\unitSymbol_{#1}^{#2}} \gdef\gradOf#1{\grad\,{#1}} \gdef\grad{\nabla} \gdef\divOf#1{\div\,{#1}} \gdef\div{\dot{\nabla}} \gdef\laplacianOf#1{\laplacian\,{#1}} \gdef\laplacian{\ddot{\nabla}} \gdef\suchThat#1#2{{#1}\,\big|\,{#2}} \gdef\chart#1{\chartSymbol_{#1}} \gdef\chartSymbol{C} \gdef\graphRegionIntersectionSymbol{\cap} \gdef\graphRegionUnionSymbol{\cup} \gdef\pathIso{\simeq} \gdef\factorial#1{#1!} \gdef\power#1#2{{#1}^{#2}} \gdef\repeatedPower#1#2{{#1}^{#2}} \gdef\kroneckerDeltaForm#1{\kroneckerDeltaSymbol_{#1}} \gdef\kroneckerDeltaSymbol{\delta} \gdef\contractionLattice#1{\operatorname{Con}(#1)} \gdef\contractedRelation#1{\sim_{#1}} \gdef\isContracted#1#2{{#1} \sim {#2}} \gdef\isContractedIn#1#2#3{{#1} \sim_{#3} {#2}} \gdef\isNotContracted#1#2{{#1} \not \sim {#2}} \gdef\isNotContractedIn#1#2#3{{#1} \not \sim_{#3} {#2}} \gdef\contractionSum#1{#1} \gdef\contractionSumSymbol{\sqcup} \gdef\contractionProduct#1{#1} \gdef\contractionProductSymbol{{\cdot}} \gdef\graph#1{#1} \gdef\graphHomomorphism#1{#1} \gdef\coversSymbol{\sqsupseteq} \gdef\coveredBySymbol{\sqsubseteq} \gdef\strictlyCoversSymbol{\sqsupset} \gdef\strictlyCoveredBySymbol{\sqsubset} \gdef\graphCovering#1#2#3{{#2} \sqsupseteq_{#1} {#3}} \gdef\quiverCovering#1#2#3{{#2} \sqsupseteq^{#1} {#3}} \gdef\powerSetSymbol{\mathcal{P}} \gdef\powerSet#1{\powerSetSymbol({#1})} \gdef\existsForm#1#2{\exists\,{#1}\,:\,{#2}} \gdef\forAllForm#1#2{\forall\,{#1}\,:\,{#2}} \gdef\notted#1{\notSymbol {#1}} \gdef\andSymbol{\land} \gdef\orSymbol{\lor} \gdef\notSymbol{\lnot} \gdef\latticeSymbol#1{#1} \gdef\meetSemilatticeSymbol#1{#1} \gdef\joinSemilatticeSymbol#1{#1} \gdef\posetSymbol#1{#1} \gdef\latticeElementSymbol#1{#1} \gdef\meetSemilatticeElementSymbol#1{#1} \gdef\joinSemilatticeElementSymbol#1{#1} \gdef\posetElementSymbol#1{#1} \gdef\latticeMeetSymbol{\wedge} \gdef\latticeJoinSymbol{\vee} \gdef\latticeTop{\top} \gdef\latticeBottom{\bot} \gdef\semilatticeMeetSymbol{\wedge} \gdef\semilatticeJoinSymbol{\vee} \gdef\semilatticeTop{\top} \gdef\semilatticeBottom{\bot} \gdef\semilatticeSemimeetSymbol{\wedge} \gdef\semilatticeSemijoinSymbol{\vee} \gdef\latticeGreaterSymbol{>} \gdef\latticeGreaterEqualSymbol{\ge} \gdef\latticeLessSymbol{<} \gdef\latticeLessEqualSymbol{\le} \gdef\posetGreaterSymbol{>} \gdef\posetGreaterEqualSymbol{\ge} \gdef\posetLessSymbol{<} \gdef\posetLessEqualSymbol{\le} \gdef\posetCoversSymbol{⋗} \gdef\posetCoveredBySymbol{⋖} \gdef\grpname#1{\operatorname{\mathsf{#1}}} \gdef\mkg#1#2#3{\grpname{#1}({#2},{#3})} \gdef\mka#1#2#3{\mathfrak{#1}({#2},{#3})} \gdef\generalLinearAlgebra#1#2{\mka{gl}{#1}{#2}} \gdef\generalLinearGroup#1#2{\mkg{GL}{#1}{#2}} \gdef\specialLinearAlgebra#1#2{\mka{sl}{#1}{#2}} \gdef\specialLinearGroup#1#2{\mkg{SL}{#1}{#2}} \gdef\projectiveGeneralLinearAlgebra#1#2{\mka{pgl}{#1}{#2}} \gdef\projectiveGeneralLinearGroup#1#2{\mkg{PGL}{#1}{#2}} \gdef\projectiveSpecialLinearAlgebra#1#2{\mka{psl}{#1}{#2}} \gdef\projectiveSpecialLinearGroup#1#2{\mkg{PSL}{#1}{#2}} \gdef\orthogonalAlgebra#1#2{\mka{o}{#1}{#2}} \gdef\orthogonalGroup#1#2{\mkg{O}{#1}{#2}} \gdef\specialOrthogonalAlgebra#1#2{\mka{so}{#1}{#2}} \gdef\specialOrthogonalGroup#1#2{\mkg{SO}{#1}{#2}} \gdef\unitaryAlgebra#1{\mka{u}{#1}{#2}} \gdef\unitaryGroup#1{\mkg{U}{#1}{#2}} \gdef\specialUnitaryAlgebra#1#2{\mka{su}{#1}{#2}} \gdef\specialUnitaryGroup#1#2{\mkg{su}{#1}{#2}} \gdef\spinAlgebra#1#2{\mka{spin}{#1}{#2}} \gdef\spinGroup#1#2{\mkg{Spin}{#1}{#2}} \gdef\pinAlgebra#1#2{\mka{pin}{#1}{#2}} \gdef\pinGroup#1#2{\mkg{Pin}{#1}{#2}} \gdef\symmetricGroup#1{\grpname{Sym}({#1})} \gdef\presentation#1{#1} \gdef\groupPresentation#1#2{\left\langle\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\rangle} \gdef\groupRelationIso{=} \gdef\groupGenerator#1{#1} \gdef\groupRelator#1{#1} \gdef\groupElement#1{#1} \gdef\identityElement#1{#1} \gdef\groupoidElement#1{#1} \gdef\groupIdentity#1{#1} \gdef\groupoidIdentityElement#1#2{#1_{#2}} \gdef\ringIdentity#1{#1} \gdef\iconstruct#1#2{{#1}\,\,\middle|{\large\mathstrut}\,\,{#2}} \gdef\setConstructor#1#2{\left\{\,\iconstruct{#1}{#2}\,\right\}} \gdef\multisetConstructor#1#2{\left\{\mkern{-2.3pt}\left|\,\,\iconstruct{#1}{#2}\,\right|\mkern{-2.3pt}\right\}} \gdef\cardinalityConstructor#1#2{\left|\,\iconstruct{#1}{#2}\,\right|} \gdef\setToMultiset#1{{#1}^\uparrow} \gdef\multisetToSet#1{{#1}^\downarrow} \gdef\subsets#1{\setLetter({#1})} \gdef\signedSubsets#1{\signedSetLetter({#1})} \gdef\multisets#1{\multisetLetter({#1})} \gdef\signedMultisets#1{\signedMultisetLetter({#1})} \gdef\circleSpaceSymbol{S} \gdef\topologicalSpace#1{#1} \gdef\bundleSection#1{#1} \gdef\bundleProjection#1{#1} \gdef\setSymbol#1{#1} \gdef\signedSetSymbol#1{#1} \gdef\multisetSymbol#1{#1} \gdef\signedMultisetSymbol#1{#1} \gdef\setElementSymbol#1{#1} \gdef\signedSetElementSymbol#1{#1} \gdef\multisetElementSymbol#1{#1} \gdef\signedMultisetElementSymbol#1{#1} \gdef\negated#1{\bar{#1}} \gdef\positiveSignedPart#1{{#1}^+} \gdef\negativeSignedPart#1{{#1}^-} \gdef\multisetMultiplicitySymbol{\,\raisebox{.1em}{\small\#}\mkern{.1em}\,} \gdef\signedMultisetMultiplicitySymbol{\,\raisebox{.1em}{\small\#}\mkern{.1em}\,} \gdef\boundMultiplicityFunction#1{{#1}^{\sharp}} \gdef\boundSignedMultiplicityFunction#1{\operatorname{{#1}^{\sharp}}} \gdef\constructor#1#2{\left.{#1}\,\,\middle|\mathstrut\,\,{#2}\right.} \gdef\elemOf#1#2{{ {#1} \in {#2} }} \gdef\notElemOf#1#2{{ {#1} \notin {#2} }} \gdef\edgeOf#1#2{{ {#1} {\in}_E {#2} }} \gdef\vertOf#1#2{{ {#1} {\in}_V {#2} }} \gdef\pathOf#1#2{{ {#1} {\in}_P {#2} }} \gdef\pathType#1{\operatorName{path}{#1}} \gdef\vertexType#1{\operatorName{vertex}{#1}} \gdef\edgeType#1{\operatorName{edge}{#1}} \gdef\multisetType#1{\operatorName{mset}{#1}} \gdef\signedMultisetType#1{\operatorName{mset^*}{#1}} \gdef\submset{\mathbin{\dot{\subset}}} \gdef\submseteq{\mathbin{\dot{\subseteq}}} \gdef\supmset{\mathbin{\dot{\supset}}} \gdef\supmseteq{\mathbin{\dot{\supseteq}}} \gdef\unitInterval{\mathbb{I}} \gdef\fromTo#1{#1} \gdef\fromToSymbol{\mapsto} \gdef\vertexCountOf#1{|{#1}|} \gdef\vertices#1{ V_{#1} } \gdef\edges#1{ E_{#1} } \gdef\vertexField#1{#1} \gdef\edgeField#1{#1} \gdef\pathVector#1{\mathbf{#1}} \gdef\pathVectorSpace#1{\mathscr{#1}} \gdef\baseField#1{#1} \gdef\finiteField#1{\mathbb{F}_{#1}} \gdef\functionSpace#1#2{#2^{#1}} \gdef\finiteTotalFunctionSpace#1#2{#2^{\sub #1}} \gdef\pathGroupoid#1{{ \Gamma_{#1} }} \gdef\forwardPathQuiver#1#2{{\overrightharpoon{#1}_{#2}}} \gdef\backwardPathQuiver#1#2{{\overrightharpoon{#1}^{#2}}} \gdef\pathQuiver#1{{\overrightharpoon{#1}}} \gdef\mto#1#2{{#1}\mapsto{#2}} \gdef\mtoSymbol{\mapsto} \gdef\groupWordRewriting#1{\langle{#1}\rangle} \gdef\rewrite#1#2{{#1}\mapsto{#2}} \gdef\rewritingRule#1#2{{#1}\mapsto{#2}} \gdef\rewritingSystem#1{\mathcal{#1}} \gdef\multiwayBFS#1{\textrm{bfs}({#1})} \gdef\rewritingStateBinding#1#2{{\left.{#1}\!\mid\!{#2}\right.}} \gdef\rewritingRuleBinding#1#2{#1{\left[\,{#2}\,\right]}} \gdef\namedSystem#1{\mathtt{#1}} \gdef\genericRewritingSystem{\namedSystem{Sys}} \gdef\stringRewritingSystem{\namedSystem{Str}} \gdef\circularStringRewritingSystem{\namedSystem{CStr}} \gdef\turingMachineRewritingSystem{\namedSystem{TM}} \gdef\cellularAutomatonRewritingSystem{\namedSystem{CA}} \gdef\graphRewritingSystem{\namedSystem{Gr}} \gdef\hypergraphRewritingSystem{\namedSystem{HGr}} \gdef\petriNetRewritingSystem{\namedSystem{Petri}} \gdef\localStates#1{\localStatesSymbol^#1} \gdef\regionalStates#1{\regionalStatesSymbol^#1} \gdef\globalStates#1{\globalStatesSymbol^#1} \gdef\keySubStates#1{\keySubStatesSymbol^#1} \gdef\valueSubStates#1{\valueSubStatesSymbol^#1} \gdef\localState#1#2{#2_{#1}} \gdef\regionalState#1{#1} \gdef\globalState#1{#1} \gdef\keySubState#1{#1} \gdef\valueSubState#1{#1} \gdef\lhsState#1{#1_{L}} \gdef\rhsState#1{#1_{R}} \gdef\rewriteLHSRegionalState#1{#1_{L}} \gdef\rewriteRHSRegionalState#1{#1_{R}} \gdef\regionalStateForm#1{\daGFo{(}#1\daGFo{)}} \gdef\invalidRegionalState{\reFo{\times}} \gdef\emptyRegionalState{\regionalStateForm{}} \gdef\regionalSubstateSymbol{\sqsubseteq} \gdef\regionalSuperstateSymbol{\sqsupseteq} \gdef\comparableRegionalStatesSymbol{\mathbin{\square}} \gdef\incomparableRegionalStatesSymbol{\mathbin{\boxtimes}} \gdef\namedStateSet#1{\mathbf #1} \gdef\localStatesSymbol{\namedStateSet L} \gdef\regionalStatesSymbol{\namedStateSet R} \gdef\globalStatesSymbol{\namedStateSet G} \gdef\keySubStatesSymbol{\namedStateSet L_K} \gdef\valueSubStatesSymbol{\namedStateSet L_V} \gdef\localStateSymbol#1{#1} \gdef\regionalStateSymbol#1{#1} \gdef\globalStateSymbol#1{#1} \gdef\keySubStateSymbol#1{#1} \gdef\valueSubStateSymbol#1{#1} \gdef\infixComposeLocalStatesSymbol{\_} \gdef\composeLocalStatesSymbol{\operatorname{glue}} \gdef\composeLocalStatesForm#1{\composeLocalStatesSymbol(#1)} \gdef\ncard#1{\card{\inverted{#1}}} \gdef\mcard#1{\card{\mirror{#1}}} \gdef\nmcard#1{\card{\inverted{\mirror{#1}}}} \gdef\assocArray#1{\left\langle {#1} \right\rangle} \gdef\openMultiset{\lBrace} \gdef\closeMultiset{\rBrace} \gdef\set#1{\{ {#1} \}} \gdef\signedSet#1{\{ {#1} \}} \gdef\list#1{\{ {#1} \}} \gdef\multiset#1{\openMultiset {#1} \closeMultiset} \gdef\signedMultiset#1{\openMultiset {#1} \closeMultiset} \gdef\styledSet#1#2{#1\{ {#1} #1\}} \gdef\styledList#1#2{#1\{ {#1} #1\}} \gdef\styledMultiset#1#2{#1\openMultiset {#2} #1\closeMultiset} \gdef\styledSignedMultiset#1#2{\openMultiset {#2} \closeMultiset} \gdef\permutationCycle#1{#1} \gdef\permutationCycleSymbol{\to} \gdef\permutationSet#1{#1} \gdef\permutationSetSymbol{;} \gdef\transposition#1#2{{#1} \leftrightarrow {#2}} \gdef\tuple#1{( {#1} )} \gdef\concat#1{ {#1} } \gdef\paren#1{\left( {#1} \right)} \gdef\ceiling#1{\lceil{#1}\rceil} \gdef\floor#1{\lfloor{#1}\rfloor} \gdef\translationVector#1{\left[{#1}\right]_{\textrm{T}}} \gdef\quotient#1#2{{#1} / {#2}} \gdef\compactQuotient#1#2#3{{#1}\;{\upharpoonright_{#2}}\;{#3}} \gdef\multilineQuotient#1#2{\frac{#1}{#2}} \gdef\idElem#1{e_{#1}} \gdef\minus#1{-{#1}} \gdef\elem{\ \in\ } \gdef\vsp{\mkern{0.4pt}} \gdef\iGmult{\vsp} \gdef\gmult{\vsp\ast\vsp} \gdef\Gmult{\vsp\ast\vsp} \gdef\gdot{\vsp\cdot\vsp} \gdef\gDot{\vsp\mathbin{\largeDot}\vsp} \gdef\mdot{\vsp\cdot\vsp} \gdef\smallblackcirc{\vsp\raisebox{0.15em}{\tiny∙}\vsp} \gdef\smallwhitecirc{\vsp\raisebox{0.15em}{\tiny∘}\vsp} \gdef\sgdot{\mathbin{\smallwhitecirc}} \gdef\srdot{\mathbin{\smallblackcirc}} \gdef\srplus{+} \gdef\verticalEllipsis{\vdots} \gdef\appliedRelation#1{#1} \gdef\setUnionSymbol{\cup} \gdef\setIntersectionSymbol{\cap} \gdef\setRelativeComplementSymbol{-} \gdef\msetCol{\textcolor{bb4444}} \gdef\repeatedMultiset#1#2{#1\,#2} \gdef\msrdot{\mathbin{\smallblackcirc}} \gdef\msrplus{+} \gdef\smrdot{\mathbin{\smallblackcirc}} \gdef\smrplus{+} \gdef\dotminus{\mathbin{\dot{-}}} \gdef\dotcap{\mathbin{\dot{\cap}}} \gdef\dotcup{\mathbin{\dot{\cup}}} \gdef\multisetUnionSymbol{\dotcup} \gdef\multisetIntersectionSymbol{\dotcap} \gdef\multisetRelativeComplementSymbol{\dotminus} \gdef\multisetSumSymbol{\dotplus} \gdef\cartesianProductSymbol{\times} \gdef\functionType#1#2{{#1} \to {#2}} \gdef\functionSignature#1#2#3{{{#1} : {#2} \to {#3}}} \gdef\partialFunctionSignature#1#2#3{{{#1} : {#2} \rightharpoonup {#3}}} \gdef\poly#1{#1} \gdef\quiverProdPoly#1{#1} \gdef\quiverProdPower#1#2{#1^{#2}} \gdef\quiverProdTimes#1{#1} \gdef\parenLabeled#1#2{#1\ ({#2})} \gdef\parenRepeated#1#2{\parenLabeled{#1}{{#2}\text{ times}}} \gdef\underLabeled#1#2{\underbrace{#1}_{#2}} \gdef\underRepeated#1#2{\underbrace{#1}_{#2\text{ times}}} \gdef\overLabeled#1#2{\overbrace{#1}^{#2}} \gdef\overRepeated#1#2{\overbrace{#1}^{#2\text{ times}}} \gdef\modLabeled#1#2{{#1 }\textrm{ mod }{#2}} \gdef\freeGroup#1{F_{#1}} \gdef\cyclicGroup#1{\mathbb{Z}_{#1}} \gdef\componentSuperQuiverOfSymbol{\succ} \gdef\setCardinality#1{|{#1}|} \gdef\multisetCardinality#1{|{#1}|} \gdef\dependentQuiverProductSymbol{\mathbin{\times}} \gdef\rightIndependentQuiverProductSymbol{\mathbin{⋊}} \gdef\leftIndependentQuiverProductSymbol{\mathbin{⋉}} \gdef\rightStrongQuiverProductSymbol{\mathbin{⧒}} \gdef\leftStrongQuiverProductSymbol{\mathbin{⧑}} \gdef\rightFiberQuiverProductSymbol{\mathbin{⧕}} \gdef\leftFiberQuiverProductSymbol{\mathbin{⧔}} \gdef\lockedQuiverProductSymbol{\mathbin{\searrow}} \gdef\rightFreeQuiverProductSymbol{\mathbin{\smallerthan}} \gdef\leftFreeQuiverProductSymbol{\mathbin{\largerthan}} \gdef\strongIndependentQuiverProductSymbol{\mathbin{⨝}} \gdef\cartesianQuiverProductSymbol{\mathbin{□}} \gdef\strongQuiverProductSymbol{\mathbin{⊠}} \gdef\graphUnionSymbol{\sqcup} \gdef\graphProductSymbol{\times} \gdef\inlineProdSymbol{|} \gdef\serialCardSymbol{{:}} \gdef\parallelCardSymbol{{\mid}} \gdef\cardinalSequenceSymbol{{:}} \gdef\cardinalProduct#1{(#1)} \gdef\vertexProduct#1{(#1)} \gdef\edgeProduct#1{(#1)} \gdef\cardinalProductSymbol{\inlineProdSymbol} \gdef\vertexProductSymbol{\inlineProdSymbol} \gdef\edgeProductSymbol{\inlineProdSymbol} \gdef\verticalVertexProduct#1#2{\cfrac{#1}{#2}} \gdef\verticalCardinalProduct#1#2{\cfrac{#1}{#2}} \gdef\indexSum#1#2#3{{\sum_{#2}^{#3} #1}} \gdef\indexProd#1#2#3{{\prod_{#2}^{#3} #1}} \gdef\indexMax#1#2#3{{\max_{#2}^{#3} #1}} \gdef\indexMin#1#2#3{{\min_{#2}^{#3} #1}} \gdef\indexUnion#1#2#3{{\bigcup_{#2}^{#3} #1}} \gdef\indexIntersection#1#2#3{{\bigcap_{#2}^{#3} #1}} \gdef\indexGraphUnion#1#2#3{{\bigcup_{#2}^{#3} #1}} \gdef\indexGraphDisjointUnion#1#2#3{{\bigcup_{#2}^{#3} #1}} \gdef\styledIndexSum#1#2#3#4{{#1\sum_{#3}^{#4} #2}} \gdef\styledIndexProd#1#2#3#4{{#1\prod_{#3}^{#4} #2}} \gdef\styledIndexMax#1#2#3#4{{#1\max_{#3}^{#4} #2}} \gdef\styledIndexMin#1#2#3#4{{#1\min_{#3}^{#4} #2}} \gdef\indexSumSymbol{\sum} \gdef\indexProdSymbol{\prod} \gdef\indexMaxSymbol{\max} \gdef\indexMinSymbol{\min} \gdef\openInterval#1#2{(#1,#2)} \gdef\closedInterval#1#2{[#1,#2]} \gdef\openClosedInterval#1#2{(#1,#2]} \gdef\closedOpenInterval#1#2{[#1,#2)} \gdef\oneTo#1{1..{#1}} \gdef\zeroTo#1{0..{#1}} \gdef\qstring#1{\mathtt{"}{#1}\mathtt{"}} \gdef\wstring#1{\textcolor{6b6b6b}{#1}} \gdef\qchar#1{\mathtt{'}{#1}\mathtt{'}} \gdef\lstr#1{\mathtt{#1}} \gdef\lchar#1{\mathtt{#1}} \gdef\string#1{{#1}} \gdef\character#1{{#1}} \gdef\homomorphismMapping#1{\assocArray{#1}} \gdef\starModifier#1{{#1}^*} \gdef\translationPresentation#1{\textrm{Z}_{#1}} \gdef\starTranslationPresentation#1{\textrm{Z}^*_{#1}} \gdef\translationPathValuation#1{\mathcal{\overrightharpoon Z}_{#1}} \gdef\starTranslationPathValuation#1{\overrightharpoon{\mathcal{Z}^*_{#1}}} \gdef\translationWordHomomorphism#1{\mathcal{Z}_{#1}} \gdef\starTranslationWordHomomorphism#1{\mathcal{Z}^*_{#1}} \gdef\translationCardinalValuation#1{\textrm{T}_{#1}} \gdef\starTranslationCardinalValuation#1{\textrm{T}^*_{#1}} \gdef\reFo#1{\textcolor{e1432d}{#1}} \gdef\grFo#1{\textcolor{4ea82a}{#1}} \gdef\blFo#1{\textcolor{3e81c3}{#1}} \gdef\orFo#1{\textcolor{dc841a}{#1}} \gdef\piFo#1{\textcolor{c74883}{#1}} \gdef\teFo#1{\textcolor{47a5a7}{#1}} \gdef\gFo#1{\textcolor{929292}{#1}} \gdef\puFo#1{\textcolor{8b7ebe}{#1}} \gdef\liReFo#1{\textcolor{ff775e}{#1}} \gdef\liGrFo#1{\textcolor{82dd63}{#1}} \gdef\liBlFo#1{\textcolor{6caff4}{#1}} \gdef\liOrFo#1{\textcolor{ffbb5f}{#1}} \gdef\liPiFo#1{\textcolor{fb77b0}{#1}} \gdef\liTeFo#1{\textcolor{7fdbdc}{#1}} \gdef\liGFo#1{\textcolor{c5c5c5}{#1}} \gdef\liPuFo#1{\textcolor{bbaff2}{#1}} \gdef\daReFo#1{\textcolor{b50700}{#1}} \gdef\daGrFo#1{\textcolor{217f00}{#1}} \gdef\daBlFo#1{\textcolor{165e9d}{#1}} \gdef\daOrFo#1{\textcolor{ae5900}{#1}} \gdef\daPiFo#1{\textcolor{9e1f61}{#1}} \gdef\daTeFo#1{\textcolor{0e7c7e}{#1}} \gdef\daGFo#1{\textcolor{6b6b6b}{#1}} \gdef\daPuFo#1{\textcolor{665996}{#1}} \gdef\boFo#1{\mathbf{#1}} \gdef\itFo#1{\mathit{#1}} \gdef\unFo#1{\underline{#1}} \gdef\stFo#1{\struckthrough{#1}} \gdef\plTeFo#1{\textrm{#1}} \gdef\maTeFo#1{\textrm{#1}} \gdef\ZNFuFo#1{\operatorname{#1}} \gdef\ZAFo#1#2{#1(#2)} \gdef\noApSy{\gFo{\text{---}}} \gdef\unSy{\gFo{?}} \gdef\emSeSy{\gFo{ \emptyset }} \gdef\tiSy{\boFo{ \vthinspace ✓ \vthinspace }} \gdef\unIn{\mathbb{I}} \gdef\blSy{\gFo{\_}} \gdef\plSqSy{□} \gdef\baToSy{\boFo{ \vthinspace | \vthinspace }} \gdef\fiToSy{●} \gdef\fiSqToSy{■} \gdef\fiReToSy{▮} \gdef\emToSy{○} \gdef\emSqToSy{□} \gdef\emReToSy{▯} \gdef\plElSy{\,...\,} \gdef\ceElSy{\,\cdot\!\cdot\!\cdot\,} \gdef\elSy{\,\gFo{...}\,} \gdef\veElSy{\vdots} \gdef\coFo{\sqsubseteq} \gdef\CoFo#1#2{#1 \coFo #2} \gdef\coByFo{⊑} \gdef\CoByFo#1#2{#1 \coByFo #2} \gdef\stCoFo{\sqsupset} \gdef\StCoFo#1#2{#1 \stCoFo #2} \gdef\stCoByFo{\sqsubset} \gdef\StCoByFo#1#2{#1 \stCoByFo #2} \gdef\inCoFo{\sqsubseteq} \gdef\InCoFo#1#2{#1 \inCoFo #2} \gdef\InCoFoⅡ#1#2#3{#1 \inCoFo_{#3} #2} \gdef\grInCoFo{\sqsubseteq} \gdef\GrInCoFo#1#2{#1 \grInCoFo #2} \gdef\GrInCoFoⅡ#1#2#3{#1 \grInCoFo_{#3} #2} \gdef\quInCoFo{\sqsubseteq} \gdef\QuInCoFo#1#2{#1 \quInCoFo #2} \gdef\QuInCoFoⅡ#1#2#3{#1 \quInCoFo_{#3} #2} \gdef\coPrFo{\cdot} \gdef\CoPrFo#1{#1} \gdef\coSuFo{\sqcup} \gdef\CoSuFo#1{#1} \gdef\isCoFo{\sim} \gdef\IsCoFo#1#2{#1 \isCoFo #2} \gdef\IsCoFoⅡ#1#2#3{#1 \isCoFo_{#3} #2} \gdef\isNoCoFo{\nsim} \gdef\IsNoCoFo#1#2{#1 \isNoCoFo #2} \gdef\IsNoCoFoⅡ#1#2#3{#1 \isNoCoFo_{#3} #2} \gdef\coReFo{\sim} \gdef\CoReFo#1{#1} \gdef\TuFo#1{(#1)} \gdef\SeFo#1{{#1}} \gdef\StSeFo#1#2#3{#1#3#2} \gdef\inArSy{⏵} \gdef\arSy{⏴} \gdef\upArSy{⏶} \gdef\doArSy{⏷} \gdef\leArSy{⏴} \gdef\riArSy{⏵} \gdef\grAuFu{\operatorname{Aut}} \gdef\PaFo#1{\;#1\;} \gdef\na{\mathbb{n}} \gdef\poNa{\mathbb{N} ^+} \gdef\poRe{\mathbb{R} ^+} \gdef\pr{\mathbb{P}} \gdef\re{\mathbb{R}} \gdef\piSy{\pi} \gdef\taSy{\tau}\]

Structures #

Introduction #

History #

The multiset is a simple and natural piece of mathematical technology that has been strangely underused in the last hundred years. That the multiset has failed to live up to its potential is due probably to historical accident. One possible explanation is that as the need for foundational rigor became urgent, modern mathematics quickly standardized on the set as a kind of universal building block, starving out other data structures, like the multiset. Such is the unfortunate role of fashion in mathematics. Luckily, multisets have seen renewed interest with the work of more computation-oriented mathematicians like Donald Knuth.

Motivation #

We are taking the time to explain multisets because they play an important interpretative role, giving us an alternative way of understanding algebraic structures. This role will only become clear in the next two sections: Word rings, where we'll elements of the word ring as multisets of words ("multiwords"), and Adjacency, where we'll interpret matrices as multisets of paths ("multipaths"). Interleaving the explanation of multisets with those topics would be confusing, so we'll front-load the work in understanding multisets here, in one place.

Sets and multisets #

Sets vs multisets #

To contrast sets with multisets, we first repeat some basic facts about sets.

Sets are the building blocks of modern mathematics. They consist of a collection of elements: \( \sym{X} = \SeFo{\sym{x_1}, \sym{x_2}, \elSy, \sym{x_{\sym{n}}}} \). We can express that an element is a member of a set with the notation \( \elemOf{\setElementSymbol{x}}{\setSymbol{X}} \).

Among the fundamental properties of a sets is that the elements have no defined order. Hence, the expressions \( \SeFo{\reFo{\card{r}}, \blFo{\card{b}}}\textAnd \SeFo{\blFo{\card{b}}, \reFo{\card{r}}} \) describe the same set. Furthermore, an object is either an element of a set or it is not. It is meaningless to say that it occurs twice, for example. Hence, the expressions \( \SeFo{\reFo{\card{r}}, \reFo{\card{r}}, \blFo{\card{b}}}\textAnd \SeFo{\reFo{\card{r}}, \blFo{\card{b}}} \) describe the same set -- especially when constructing sets we rely on this redundancy being irrelevant.

If we instead specify that repetition does matter, we arrive at the idea of a multiset. A multiset can contain an object more than once. The number of times a multiset contains an object will be called the multiplicity of that object.

We'll write multisets with double-struck braces: \( \sym{X} = \multiset{\sym{x_1},\sym{x_2},\elSy,\sym{x_{\sym{n}}}} \). Hence, \( \multiset{\reFo{\card{r}},\reFo{\card{r}},\blFo{\card{b}}}\textAnd \multiset{\reFo{\card{r}},\blFo{\card{b}}} \) describe different multisets: the multiplicity of \( \reFo{\card{r}} \) is \( 1 \) in the first and \( 2 \) in the second.

We’ll denote the multiplicity of an object \( \multisetElementSymbol{x} \) in a multiset \( \multisetSymbol{M} \) by \( \multisetSymbol{M}\multisetMultiplicitySymbol \multisetElementSymbol{x} \). For example, in the multiset \( \multisetSymbol{M} = \multiset{\reFo{\card{r}},\reFo{\card{r}},\blFo{\card{b}}} \), we have that \( \multisetSymbol{M}\multisetMultiplicitySymbol \reFo{\card{r}} = 2 \), \( \multisetSymbol{M}\multisetMultiplicitySymbol \blFo{\card{b}} = 1 \), and \( \multisetSymbol{M}\multisetMultiplicitySymbol \grFo{\card{g}} = 0 \).

The set of multisets #

The powerset \( \powerSet{\multisetSymbol{B}} \) of a set \( \multisetSymbol{B} \) is the set of subsets of \( \multisetSymbol{B} \). We'll call these the sets on \( \multisetSymbol{B} \), and \( \multisetSymbol{B} \) the base set.

We can similarly form the set of multisets whose objects are taken from \( \multisetSymbol{B} \), written \( \multisets{\multisetSymbol{B}} \). We'll call these the multisets on \( \multisetSymbol{B} \).

Any particular object from the base set can occur any finite number of times in one such multiset, so \( \multisets{\multisetSymbol{B}} \) is generally an infinite set (unless \( \multisetSymbol{B} \) is empty). Let's look at some examples of this simple and natural idea.

If \( \multisetSymbol{B} \) is a singleton, that is, contains only one element, then the multisets in \( \multisets{\multisetSymbol{B}} \) can contain this element any finite number of times. Here we list some multisets in \( \multisets{\multisetSymbol{B}} \) for \( \multisetSymbol{B} = \SeFo{\reFo{\card{r}}} \):

\[ \multisets{\SeFo{\reFo{\card{r}}}} = \SeFo{\multiset{}, \multiset{\reFo{\card{r}}}, \multiset{\reFo{\card{r}},\reFo{\card{r}}}, \multiset{\reFo{\card{r}},\reFo{\card{r}},\reFo{\card{r}}}, \elSy} \]

Clearly, we can identify these multisets with the positive integers, since they count the number of times that \( \reFo{\card{r}} \) is present.

If \( \multisetSymbol{B} \) contains two elements, then the multisets in \( \multisets{\multisetSymbol{B}} \) can be identified with pairs of positive integers, counting how many times the two elements are present. Here we list some elements of the set \( \multisets{\multisetSymbol{B}} \) for \( \multisetSymbol{B} = \SeFo{\reFo{\card{r}}, \blFo{\card{b}}} \):

\[ \multisets{\SeFo{\reFo{\card{r}}, \blFo{\card{b}}}} = \SeFo{\multiset{}, \multiset{\reFo{\card{r}}}, \multiset{\blFo{\card{b}}}, \multiset{\reFo{\card{r}},\reFo{\card{r}}}, \multiset{\reFo{\card{r}},\blFo{\card{b}}}, \multiset{\blFo{\card{b}},\blFo{\card{b}}}, \multiset{\reFo{\card{r}},\reFo{\card{r}},\reFo{\card{r}}}, \multiset{\reFo{\card{r}},\reFo{\card{r}},\blFo{\card{b}}}, \elSy} \]

For example, we can identify the multiset \( \multisetSymbol{M} = \multiset{\reFo{\card{r}},\reFo{\card{r}},\blFo{\card{b}}} \) with the function \( \boundMultiplicityFunction{\multisetSymbol{M}} = \assocArray{\mto{\reFo{\card{r}}}{2},\mto{\blFo{\card{b}}}{1}} \).

Formally, then, we have a bijection between multisets on \( \multisetSymbol{B} \) on one side and functions from \( \multisetSymbol{B} \) to the natural numbers on the other (multiplicity functions):

\[ \multisets{\setSymbol{B}}\bijectiveSymbol \functionSpace{\setSymbol{B}}{\baseField{\na}} \]

We'll shortly see how we can encode the natural operations on a multiset in terms of operations on such multiplicity functions.

Projection and lift #

We can define this bijection via two functions called projection and lift:

\[ \begin{csarray}{ccccc}{acccc} \lift & : & \subsets{\setSymbol{X}} & \rarr & \multisets{X}\\ \projection & : & \multisets{X} & \rarr & \subsets{\setSymbol{X}} \end{csarray} \]

Lift takes a set and gives the multiset that contains each element exactly once:

\[ \lift(\setSymbol{A})\defEqualSymbol \multisetConstructor{\multisetElementSymbol{x}}{\elemOf{\multisetElementSymbol{x}}{\setSymbol{A}}} \]

Projection takes a multiset and gives the set of its elements:

\[ \projection(\setSymbol{A})\defEqualSymbol \setConstructor{\multisetElementSymbol{x}}{\elemOf{\multisetElementSymbol{x}}{\setSymbol{A}}} \]

Lifting and projecting a set yields the same set:

\[ \projection(\lift(\setSymbol{A}))\identicallyEqualSymbol \setSymbol{A} \]

Conversely, the set-like multisets are precisely those for which:

\[ \lift(\projection(\multisetSymbol{B}))\identicallyEqualSymbol \multisetSymbol{B} \]

Realms #

Realms have sum, union, intersection, and a zero. The sum and zero form a semiring. Define a preorder.

Natural numbers form a real.

Functions from something to a realm, form a realm under pointwise max, min, etc.

Multiset-multiplicity duality #

We saw that multisets can be represented one-to-one by multiplicity functions.

There is a bijection between \( \multisets{\setSymbol{X}} \), the set of finite multisets on a base set \( \setSymbol{X} \), and the integrable functions from \( \setSymbol{X} \) to the natural numbers. By this we mean the set of functions with finite total. We'll write this set of functions as \( \finiteTotalFunctionSpace{\setSymbol{X}}{\baseField{\na}} \), because it necessarily consists of those functions in \( \functionSpace{\setSymbol{X}}{\baseField{\na}} \) that are only non-zero on a finite subset of \( \setSymbol{X} \):

\[ \finiteTotalFunctionSpace{\setSymbol{X}}{\baseField{\na}}\defEqualSymbol \setConstructor{\function{f}}{\elemOf{\function{f}}{\functionSpace{\setSymbol{X}}{\baseField{\na}}},\total(\function{f})< \infty } \]

Then the bijection between multisets and their multiplicity functions is given by:

\[ \begin{aligned} \multisets{\setSymbol{X}}& \approx \finiteTotalFunctionSpace{\setSymbol{X}}{\baseField{\na}}\\ \multisetSymbol{M}& \approx \boundMultiplicityFunction{\multisetSymbol{M}}\end{aligned} \]

More importantly, this bijection is an isomorphism, because it preserves the multiset operations of union, intersection, sum, etc., which we revisit here:

\[ \begin{aligned} \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetSumSymbol \multisetSymbol{N}}}&= \boundMultiplicityFunction{\multisetSymbol{M}} + \boundMultiplicityFunction{\multisetSymbol{N}}\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetUnionSymbol \multisetSymbol{N}}}&= \max(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetIntersectionSymbol \multisetSymbol{N}}}&= \min(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetRelativeComplementSymbol \multisetSymbol{N}}}&= \max(\boundMultiplicityFunction{\multisetSymbol{M}} - \boundMultiplicityFunction{\multisetSymbol{N}},0)\\ \boundMultiplicityFunction{\paren{\repeatedMultiset{\sym{n}}{\multisetSymbol{M}}}}&= \sym{n} \, \paren{\boundMultiplicityFunction{\multisetSymbol{M}}}\end{aligned} \]

We say that the multiset \( \multisetSymbol{M} \) is dual to the multiplicity function \( \boundMultiplicityFunction{\multisetSymbol{M}} \).

We can express this isomorphism as a isomorphism of realms, where a realm is a set with the algebraic structure of sums, unions, and intersections. We will not enter into the realm of realms, however.

We can also see this duality as a particularly simple example of the duality between a space and its rings of functions. Here, the space is just \( \setSymbol{X} \) with the discrete topology, and the (semi)ring is the ring of functions \( \functionSignature{\function{f}}{\setSymbol{X}}{\na} \).

Multiset constructors #

Let's consider a general multiset constructor:

\[ \multisetConstructor{\function{F}(\multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\elSy,\multisetElementSymbol{x}_{\sym{n}})}{\elemOf{\multisetElementSymbol{x}_1}{\multisetSymbol{M}_1},\elemOf{\multisetElementSymbol{x}_2}{\multisetSymbol{M}_2},\elSy,\elemOf{\multisetElementSymbol{x}_{\sym{n}}}{\multisetSymbol{M}_{\sym{n}}}} \]

Here, \( \function{F} \) is some function that computes an output value from inputs \( \multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\elSy,\multisetElementSymbol{x}_{\sym{n}} \). Where do these inputs come from? The values of \( \multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\elSy,\multisetElementSymbol{x}_{\sym{n}} \) are drawn from multisets (or sets) \( \multisetSymbol{M}_1,\multisetSymbol{M}_2,\elSy,\multisetSymbol{M}_{\sym{n}} \) via the bindings \( \elemOf{\multisetElementSymbol{x}_{\sym{i}}}{\multisetSymbol{M}_{\sym{i}}} \). Bindings are indications that the multiset constructor should "draw an element from \( \multisetSymbol{M}_{\sym{i}} \) and place it in \( \multisetElementSymbol{x}_{\sym{i}} \)". The multiset constructor performs bindings in all possible ways in order to build a multiset of results.

This is very similar to how ordinary set constructor notation works, except for one important distinction. In set constructor notation, a particular value can only be drawn from a set once -- or more precisely, if we draw a particular value more than once, we would correspondingly collect a particular result \( \function{F}(\multisetElementSymbol{x}_1,\multisetElementSymbol{x}_2,\elSy,\multisetElementSymbol{x}_{\sym{n}}) \) more than once, but this would still result in the same constructed set, since multiplicity is ignored! In contrast, multisets care about multiplicity. Therefore we draw an element from each \( \multisetSymbol{M}_{\sym{i}} \) exactly as many times as it appears. Here we show this difference for a simple example:

\[ \begin{aligned} \setConstructor{\power{\setElementSymbol{x}}{2}}{\elemOf{\setElementSymbol{x}}{\SeFo{0, 1, 2, 3, 4}}}&= \SeFo{0, 1, 4, 9, 16}\\[1em] \multisetConstructor{\power{\setElementSymbol{x}}{2}}{\elemOf{\setElementSymbol{x}}{\multiset{0,0,0,1,2,2,3,4}}}&= \multiset{0,0,0,1,4,4,9,16}\end{aligned} \]

Similarly, when \( \function{F} \) produces a particular result multiple times, it will appear in the constructed multiset with the corresponding multiplicity. In the following example, \( \modFunction(\setElementSymbol{x},2) \) outputs the value \( 0 \) three times as \( \setElementSymbol{x} \) is bound the integers \( \zeroTo{4} \), because \( \modFunction(0,2) = \modFunction(2,2) = \modFunction(4,2) = 0 \):

\[ \multisetConstructor{\modFunction(\setElementSymbol{x},2)}{\elemOf{\setElementSymbol{x}}{\SeFo{0, 1, 2, 3, 4}}} = \multiset{0,0,0,1,1} \]

The set version of this construction doesn't capture this multiplicity:

\[ \setConstructor{\modFunction(\setElementSymbol{x},2)}{\elemOf{\setElementSymbol{x}}{\SeFo{0, 1, 2, 3, 4}}} = \SeFo{0, 1} \]

Images and preimages of sets #

We now review some basic facts about images and preimages of functions, to set the stage for analogous definitions for multisets. These ideas can be found in any undergraduate text on set theory. If this is familiar, you can jump to .

Definition #

Consider a function \( \functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}} \). We wish to apply it "set-wise", asking how it acts on a set of inputs (\( \setSymbol{A} \subseteq \setSymbol{X} \)) to give a set of outputs (\( \setSymbol{B} \subseteq \setSymbol{Y} \)). We similarly might wish to know what set of inputs corresponds to a given set of outputs.

To formalize these ideas, we define the image and preimage functions of \( \function{f} \), written \( \imageModifier{\function{f}} \) and \( \preimageModifier{\function{f}} \) respectively. They have the following signatures:

\[ \begin{csarray}{ccccc}{acccc} \function{f} & : & \setSymbol{X} & \rarr & \setSymbol{Y}\\ \imageModifier{\function{f}} & : & \subsets{X} & \rarr & \subsets{Y}\\ \preimageModifier{\function{f}} & : & \subsets{Y} & \rarr & \subsets{X} \end{csarray} \]

We define the image and preimage functions by using set constructor notation, where the image \( \imageModifier{\function{f}} \) function collects the outputs corresponding to the provided set of inputs, and the preimage \( \preimageModifier{\function{f}} \) collects the inputs corresponding to the provided set of outputs:

\[ \begin{aligned} \function{\imageModifier{\function{f}}}(\reFo{\setSymbol{A}})&\defEqualSymbol \setConstructor{\multisetElementSymbol{\daBlFo{y}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\reFo{\setSymbol{A}}},\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}},\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\\ \function{\preimageModifier{\function{f}}}(\blFo{\setSymbol{B}})&\defEqualSymbol \setConstructor{\multisetElementSymbol{\daReFo{x}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}},\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\blFo{\setSymbol{B}}},\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\end{aligned} \]

We can use a more compact, equivalent definition:

\[ \begin{aligned} \function{\imageModifier{\function{f}}}(\reFo{\setSymbol{A}})&\defEqualSymbol \setConstructor{\function{f}(\multisetElementSymbol{\daReFo{x}})}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\reFo{\setSymbol{A}}}}\\ \function{\preimageModifier{\function{f}}}(\blFo{\setSymbol{B}})&\defEqualSymbol \setConstructor{\multisetElementSymbol{\daReFo{x}}}{\elemOf{\function{f}(\multisetElementSymbol{\daReFo{x}})}{\blFo{\setSymbol{B}}}}\end{aligned} \]

Example #

Consider the function \( \functionSignature{\function{f}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}}}{\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}} \) defined by \( \function{f} = \assocArray{\mto{\reFo{\card{r}}}{\teFo{\card{x}}},\mto{\grFo{\card{g}}}{\teFo{\card{x}}},\mto{\blFo{\card{b}}}{\orFo{\card{y}}}} \).

We’ll say that e.g. \( \SeFo{\teFo{\card{x}}} \) is the image of \( \SeFo{\reFo{\card{r}}} \) under \( \function{f} \), meaning that \( \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) = \SeFo{\teFo{\card{x}}} \) (for singletons, people sometimes elide the braces). For \( \function{f} \), we have the following images:

\[ \begin{csarray}{rclrclrclrcl}{accicciccicc} & & & \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & = & \SeFo{\teFo{\card{x}}} & \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}, \grFo{\card{g}}}) & = & \SeFo{\teFo{\card{x}}} & & & \\[0.5em] \function{\imageModifier{\function{f}}}(\SeFo{}) & = & \SeFo{} & \function{\imageModifier{\function{f}}}(\SeFo{\grFo{\card{g}}}) & = & \SeFo{\teFo{\card{x}}} & \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}, \blFo{\card{b}}}) & = & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}} & \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}}) & = & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}}\\[0.5em] & & & \function{\imageModifier{\function{f}}}(\SeFo{\blFo{\card{b}}}) & = & \SeFo{\orFo{\card{y}}} & \function{\imageModifier{\function{f}}}(\SeFo{\grFo{\card{g}}, \blFo{\card{b}}}) & = & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}} & & & \end{csarray} \]

Since we've listed the images of all subsets of \( \SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}} \), we can collect these together to give the explicit value of \( \imageModifier{\function{f}} \):

\[ \imageModifier{\function{f}} = \begin{csarray}{rrclrclrclrcll}{abbbcbbcbbcbba} \langle & \SeFo{} & \mtoSymbol & \SeFo{}, & \SeFo{\reFo{\card{r}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}}, & \SeFo{\grFo{\card{g}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}}, & \SeFo{\blFo{\card{b}}} & \mtoSymbol & \SeFo{\orFo{\card{y}}}, & \\ & \SeFo{\reFo{\card{r}}, \grFo{\card{g}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}}, & \SeFo{\reFo{\card{r}}, \blFo{\card{b}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}}, & \SeFo{\grFo{\card{g}}, \blFo{\card{b}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}}, & \SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}} & \rangle \end{csarray} \]

Note the important but elementary fact that the image function \( \imageModifier{\function{f}} \) preserves unions for any function \( \function{f} \):

\[ \function{\imageModifier{\function{f}}}(\reFo{\setSymbol{A}}\setUnionSymbol \setSymbol{\teFo{\primed{A}}}) = \function{\imageModifier{\function{f}}}(\reFo{\setSymbol{A}})\setUnionSymbol \function{\imageModifier{\function{f}}}(\setSymbol{\teFo{\primed{A}}}) \]

We show one example of this identity in action :

\[ \function{\preimageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}\setUnionSymbol \SeFo{\blFo{\card{b}}}) \] \[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\SeFo{\reFo{\card{r}}} & \cup & \SeFo{\blFo{\card{b}}}) & = & \function{\preimageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}, \blFo{\card{b}}}) & = & \lbrace \teFo{\card{x}} , \orFo{\card{y}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & \cup & \function{\preimageModifier{\function{f}}}(\SeFo{\blFo{\card{b}}}) & = & \SeFo{\teFo{\card{x}}}\setUnionSymbol \SeFo{\orFo{\card{y}}} & = & \lbrace \teFo{\card{x}} , \orFo{\card{y}} \rbrace \end{csarray} \]

However, the image function does not preserve intersections or relative complements. Here are counterexamples for each case:

\[ \begin{csarray}{rclcccc}{acccccc} \imageModifier{\function{f}}(\SeFo{\reFo{\card{r}}} & \cap & \SeFo{\grFo{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\SeFo{}) & = & \lbrace \rbrace \\[0.5em] \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & \cap & \function{\imageModifier{\function{f}}}(\SeFo{\grFo{\card{g}}}) & = & \SeFo{\teFo{\card{x}}}\setIntersectionSymbol \SeFo{\teFo{\card{x}}} & = & \lbrace \teFo{\card{x}} \rbrace \end{csarray} \] \[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\SeFo{\reFo{\card{r}}} & \setminus & \SeFo{\grFo{\card{g}}}) & = & \function{\preimageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & = & \lbrace \teFo{\card{x}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & \setminus & \function{\preimageModifier{\function{f}}}(\SeFo{\grFo{\card{g}}}) & = & \SeFo{\teFo{\card{x}}}\setRelativeComplementSymbol \SeFo{\teFo{\card{x}}} & = & \lbrace \rbrace \end{csarray} \] \[ \begin{csarray}{rclcccc}{acccccc} \imageModifier{\function{f}}(\SeFo{\reFo{\card{r}}} & \cap & \SeFo{\grFo{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\SeFo{}) & = & \lbrace \rbrace \\[0.5em] \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & \cap & \function{\imageModifier{\function{f}}}(\SeFo{\grFo{\card{g}}}) & = & \SeFo{\teFo{\card{x}}}\setIntersectionSymbol \SeFo{\teFo{\card{x}}} & = & \lbrace \teFo{\card{x}} \rbrace \\[1em] \imageModifier{\function{f}}(\SeFo{\reFo{\card{r}}} & \setminus & \SeFo{\grFo{\card{g}}}) & = & \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & = & \lbrace \teFo{\card{x}} \rbrace \\[0.5em] \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}}) & \setminus & \function{\imageModifier{\function{f}}}(\SeFo{\grFo{\card{g}}}) & = & \SeFo{\teFo{\card{x}}}\setRelativeComplementSymbol \SeFo{\teFo{\card{x}}} & = & \lbrace \rbrace \end{csarray} \]

In general, however, we do have that have the following inequalities for intersections and complements:

\[ \begin{csarray}{rclcrcr}{acccccc} \imageModifier{\function{f}}(\reFo{\setSymbol{A}} & \cap & \setSymbol{\teFo{\primed{A}}}) & \subseteq & \function{\imageModifier{\function{f}}}(\reFo{\setSymbol{A}}) & \cap & \function{\imageModifier{\function{f}}}(\setSymbol{\teFo{\primed{A}}})\\[1em] \imageModifier{\function{f}}(\reFo{\setSymbol{A}} & \setminus & \setSymbol{\teFo{\primed{A}}}) & \supseteq & \function{\imageModifier{\function{f}}}(\reFo{\setSymbol{A}}) & \setminus & \function{\imageModifier{\function{f}}}(\setSymbol{\teFo{\primed{A}}}) \end{csarray} \]

Let's examine the preimage function \( \preimageModifier{\function{f}} \), which again we can write as a literal mapping for our example:

\[ \preimageModifier{\function{f}} = \assocArray{\mto{\SeFo{}}{\SeFo{}},\mto{\SeFo{\teFo{\card{x}}}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}}},\mto{\SeFo{\orFo{\card{y}}}}{\SeFo{\blFo{\card{b}}}},\mto{\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}}}} \]

The preimage function of \( \function{f} \) is quite nice, since it preserves intersections*,* unions, and relative complements for any \( \function{f} \):

\[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\blFo{\setSymbol{B}} & \cup & \setSymbol{\orFo{\primed{B}}}) & = & \function{\preimageModifier{\function{f}}}(\blFo{\setSymbol{B}}) & \cup & \function{\preimageModifier{\function{f}}}(\setSymbol{\orFo{\primed{B}}})\\[0.5em] \preimageModifier{\function{f}}(\blFo{\setSymbol{B}} & \cap & \setSymbol{\orFo{\primed{B}}}) & = & \function{\preimageModifier{\function{f}}}(\blFo{\setSymbol{B}}) & \cap & \function{\preimageModifier{\function{f}}}(\setSymbol{\orFo{\primed{B}}})\\[0.5em] \preimageModifier{\function{f}}(\blFo{\setSymbol{B}} & \setminus & \setSymbol{\orFo{\primed{B}}}) & = & \function{\preimageModifier{\function{f}}}(\blFo{\setSymbol{B}}) & \setminus & \function{\preimageModifier{\function{f}}}(\setSymbol{\orFo{\primed{B}}}) \end{csarray} \]

Here we show some examples for these identities for our specific function, but leave the general proofs as exercises:

\[ \begin{csarray}{rclcccc}{acccccc} \preimageModifier{\function{f}}(\SeFo{\teFo{\card{x}}} & \cup & \SeFo{\orFo{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}) & = & \lbrace \reFo{\card{r}} , \grFo{\card{g}} , \blFo{\card{b}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\SeFo{\teFo{\card{x}}}) & \cup & \function{\preimageModifier{\function{f}}}(\SeFo{\orFo{\card{y}}}) & = & \SeFo{\reFo{\card{r}}, \grFo{\card{g}}}\setUnionSymbol \SeFo{\blFo{\card{b}}} & = & \lbrace \reFo{\card{r}} , \grFo{\card{g}} , \blFo{\card{b}} \rbrace \\[1em] \preimageModifier{\function{f}}(\SeFo{\teFo{\card{x}}} & \cap & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\SeFo{\teFo{\card{x}}}) & = & \lbrace \reFo{\card{r}} , \grFo{\card{g}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\SeFo{\teFo{\card{x}}}) & \cap & \function{\preimageModifier{\function{f}}}(\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}) & = & \SeFo{\reFo{\card{r}}, \grFo{\card{g}}}\setIntersectionSymbol \SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}} & = & \lbrace \reFo{\card{r}} , \grFo{\card{g}} \rbrace \\[1em] \preimageModifier{\function{f}}(\SeFo{\teFo{\card{x}}, \orFo{\card{y}}} & \setminus & \SeFo{\orFo{\card{y}}}) & = & \function{\preimageModifier{\function{f}}}(\SeFo{\teFo{\card{x}}}) & = & \lbrace \reFo{\card{r}} , \grFo{\card{g}} \rbrace \\[0.5em] \function{\preimageModifier{\function{f}}}(\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}) & \setminus & \function{\preimageModifier{\function{f}}}(\SeFo{\orFo{\card{y}}}) & = & \SeFo{\reFo{\card{r}}, \grFo{\card{g}}}\setRelativeComplementSymbol \SeFo{\blFo{\card{b}}} & = & \lbrace \reFo{\card{r}} , \grFo{\card{g}} \rbrace \end{csarray} \]

We now extend the image and preimage functions to the setting of multisets.

Images and preimages of multisets #

The multi-image function \( \multiImageModifier{\function{f}} \) and multi-preimage function \( \multiPreimageModifier{\function{f}} \)are functions that play the same role as the image function \( \imageModifier{\function{f}} \) and preimage function \( \preimageModifier{\function{f}} \), but operate on multisets on the domain and codomain:

\[ \begin{csarray}{ccccc}{acccc} \function{f} & : & \setSymbol{X} & \rarr & \setSymbol{Y}\\ \multiImageModifier{\function{f}} & : & \multisets{\setSymbol{X}} & \rarr & \multisets{\setSymbol{Y}}\\ \multiPreimageModifier{\function{f}} & : & \multisets{\setSymbol{Y}} & \rarr & \multisets{\setSymbol{X}} \end{csarray} \]

They are defined as follows, where \( \elemOf{\multisetSymbol{\reFo{A}}}{\multisets{\setSymbol{X}}}\textAnd \elemOf{\multisetSymbol{\blFo{B}}}{\multisets{\setSymbol{Y}}} \):

\[ \begin{aligned} \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}})&\defEqualSymbol \multisetConstructor{\multisetElementSymbol{\daBlFo{y}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}},\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}},\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\\ \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})&\defEqualSymbol \multisetConstructor{\multisetElementSymbol{\daReFo{x}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}},\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\multisetSymbol{\blFo{B}}},\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\end{aligned} \]

Or more compactly:

\[ \begin{aligned} \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}})&\defEqualSymbol \multisetConstructor{\function{f}(\multisetElementSymbol{\daReFo{x}})}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}}}\\ \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})&\defEqualSymbol \multisetConstructor{\multisetElementSymbol{\daReFo{x}}}{\elemOf{\function{f}(\multisetElementSymbol{\daReFo{x}})}{\multisetSymbol{\blFo{B}}}}\end{aligned} \]

The only difference from the definitions of the image and preimage functions are that we are now using multiset constructor notation, rather than set constructor notation.

Example #

Let's compute the multi-image function for an example function \( \function{f} \). We'll use the same function \( \function{f} \) we examined above, which was \( \functionSignature{\function{f}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}}}{\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}} \) defined by \( \function{f} = \assocArray{\mto{\reFo{\card{r}}}{\teFo{\card{x}}},\mto{\grFo{\card{g}}}{\teFo{\card{x}}},\mto{\blFo{\card{b}}}{\orFo{\card{y}}}} \).

Then we can show the multi-image function \( \multiImageModifier{\function{f}} \) for set-like multisets inputs (those with maximum multiplicity 1):

\[ \multiImageModifier{\function{f}} = \begin{csarray}{rrclrclrclrcll}{abbbcbbcbbcbba} \langle & \multiset{} & \mtoSymbol & \multiset{}, & \multiset{\reFo{\card{r}}} & \mtoSymbol & \multiset{\teFo{\card{x}}}, & \multiset{\grFo{\card{g}}} & \mtoSymbol & \multiset{\teFo{\card{x}}}, & \multiset{\blFo{\card{b}}} & \mtoSymbol & \multiset{\orFo{\card{y}}}, & \\ & \multiset{\reFo{\card{r}},\grFo{\card{g}}} & \mtoSymbol & \multiset{\teFo{\card{x}},\teFo{\card{x}}}, & \multiset{\reFo{\card{r}},\blFo{\card{b}}} & \mtoSymbol & \multiset{\teFo{\card{x}},\orFo{\card{y}}}, & \multiset{\grFo{\card{g}},\blFo{\card{b}}} & \mtoSymbol & \multiset{\teFo{\card{x}},\orFo{\card{y}}}, & \multiset{\reFo{\card{r}},\grFo{\card{g}},\blFo{\card{b}}} & \mtoSymbol & \multiset{\teFo{\card{x}},\teFo{\card{x}},\orFo{\card{y}}}, & \\ & & \veElSy & & & \veElSy & & & \veElSy & & & \veElSy & & \rangle \end{csarray} \]

Compare with the image function \( \imageModifier{\function{f}} \):

\[ \imageModifier{\function{f}} = \begin{csarray}{rrclrclrclrcll}{abbbcbbcbbcbba} \langle & \SeFo{} & \mtoSymbol & \SeFo{}, & \SeFo{\reFo{\card{r}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}}, & \SeFo{\grFo{\card{g}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}}, & \SeFo{\blFo{\card{b}}} & \mtoSymbol & \SeFo{\orFo{\card{y}}}, & \\ & \SeFo{\reFo{\card{r}}, \grFo{\card{g}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}}, & \SeFo{\reFo{\card{r}}, \blFo{\card{b}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}}, & \SeFo{\grFo{\card{g}}, \blFo{\card{b}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}}, & \SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}} & \mtoSymbol & \SeFo{\teFo{\card{x}}, \orFo{\card{y}}} & \rangle \end{csarray} \]

Note differences between the multi-image function \( \multiImageModifier{\function{f}} \)and the image function \( \imageModifier{\function{f}} \), for example:

\[ \begin{aligned} \function{\imageModifier{\function{f}}}(\SeFo{\reFo{\card{r}}, \grFo{\card{g}}})&= \SeFo{\teFo{\card{x}}}\\ \function{\multiImageModifier{\function{f}}}(\multiset{\reFo{\card{r}},\grFo{\card{g}}})&= \multiset{\teFo{\card{x}},\teFo{\card{x}}}\end{aligned} \]

Now compare the multi-preimage function \( \multiPreimageModifier{\function{f}} \) with the ordinary preimage function \( \preimageModifier{\function{f}} \):

\[ \begin{aligned} \multiPreimageModifier{\function{f}}&= \assocArray{\mto{\multiset{}}{\multiset{}},\mto{\multiset{\teFo{\card{x}}}}{\multiset{\reFo{\card{r}},\grFo{\card{g}}}},\mto{\multiset{\orFo{\card{y}}}}{\multiset{\blFo{\card{b}}}},\mto{\multiset{\teFo{\card{x}},\orFo{\card{y}}}}{\multiset{\reFo{\card{r}},\grFo{\card{g}},\blFo{\card{b}}}},\elSy}\\ \preimageModifier{\function{f}}&= \assocArray{\mto{\SeFo{}}{\SeFo{}},\mto{\SeFo{\teFo{\card{x}}}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}}},\mto{\SeFo{\orFo{\card{y}}}}{\SeFo{\blFo{\card{b}}}},\mto{\SeFo{\teFo{\card{x}}, \orFo{\card{y}}}}{\SeFo{\reFo{\card{r}}, \grFo{\card{g}}, \blFo{\card{b}}}}}\end{aligned} \]

Note that \( \multiPreimageModifier{\function{f}}\textAnd \preimageModifier{\function{f}} \) are identical when we restrict \( \multiPreimageModifier{\function{f}} \) to the set-like multisets.

#

s obvious: if \( \multisetSymbol{B} \) is a set-like multiset, i.e. if \( \max(\boundMultiplicityFunction{\multisetSymbol{B}}) \le 1 \), then the preimages s

#

What is the reason for this? For a singleton multiset \( \multiset{\setElementSymbol{y}} \), the multi preimage \( \function{\multiPreimageModifier{\function{f}}}(\multiset{\setElementSymbol{y}}) \) is a set-like multiset, since there is only one way that we can satisfy \( \elemOf{\function{f}(\setElementSymbol{x})}{\multiset{\setElementSymbol{y}}} \). Therefore, we have that:

\[ \projection(\function{\multiPreimageModifier{\function{f}}}(\multiset{\setElementSymbol{y}})) = \function{\preimageModifier{\function{f}}}(\SeFo{\setElementSymbol{y}}) \]

Since pre-images preserve union, we can write any multi preimage of a set-like multiset \( \setSymbol{B} \) as a union of multi preimages of such singletons:

\[ \begin{aligned} \function{\preimageModifier{\function{f}}}(\setSymbol{B})&= \indexUnion{\function{\preimageModifier{\function{f}}}(\SeFo{\sym{y}})}{\elemOf{\sym{y}}{\multisetSymbol{B}}}{}\\ &= \indexUnion{\projection(\function{\multiPreimageModifier{\function{f}}}(\multiset{\setElementSymbol{y}}))}{\elemOf{\sym{y}}{\multisetSymbol{B}}}{}\\ &= \projection(\indexUnion{\function{\multiPreimageModifier{\function{f}}}(\multiset{\setElementSymbol{y}})}{\elemOf{\sym{y}}{\multisetSymbol{B}}}{})\\ &= \projection(\indexUnion{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{B})}{\elemOf{\sym{y}}{\multisetSymbol{B}}}{})\end{aligned} \]

First, observe that preimages of different singleton sets \( \SeFo{\setElementSymbol{y}},\SeFo{\setElementSymbol{\primed{y}}} \) are disjoint, because any element in the intersection \( \function{\preimageModifier{\function{f}}}(\SeFo{\setElementSymbol{y}})\setIntersectionSymbol \function{\preimageModifier{\function{f}}}(\SeFo{\setElementSymbol{\primed{y}}}) \) would imply \( \function{f}(\setElementSymbol{x}) = \setElementSymbol{y}\textAnd \function{f}(\setElementSymbol{x}) = \setElementSymbol{\primed{y}} \) -- impossible when \( \function{f} \) is an ordinary, single-valued function. Therefore, for a set-like multiset \( \multisetSymbol{X} \) where \( \max(\boundMultiplicityFunction{\multisetSymbol{X}}) \le 1 \), we can write \( \multisetSymbol{X} \) as the union of such disjoint singletons, and its pre-image would be

Therefore, the multiplicities of objects in \( \function{\multiPreimageModifier{\function{f}}}(\setSymbol{X}) \) cannot exceed 1: they are setlike. Therefore \( \function{\multiPreimageModifier{\function{f}}}(\setSymbol{X}) \) projects to the set \( \function{\multiPreimageModifier{\function{f}}}(\setSymbol{X}) \):

\[ \projection(\function{\multiPreimageModifier{\function{f}}}(\setSymbol{X})) = \function{\preimageModifier{\function{f}}}(\projection(\setSymbol{X})) \]

Multiplicity functions of multi-image functions #

Just as we can characterize multisets in terms of multiplicity functions, we can do the same for multi-image functions.

Let us interrogate the behavior of \( \multiImageModifier{\function{f}} \) via the output multiset \( \multisetSymbol{\blFo{B}}\defEqualSymbol \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}) \) for a particular input multiset \( \elemOf{\multisetSymbol{\reFo{A}}}{\multisets{\setSymbol{X}}} \). Recall that this output is simply:

\[ \begin{aligned} \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}})&= \multisetConstructor{\function{f}(\multisetElementSymbol{\daReFo{x}})}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}}}\\ &= \multisetConstructor{\multisetElementSymbol{\daBlFo{y}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}},\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}},\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\end{aligned} \]

The multiplicity function \( \boundMultiplicityFunction{\multisetSymbol{\blFo{B}}} \) will count how many times any \( \elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}} \) occurs in the multi-image \( \multisetSymbol{\blFo{B}} = \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}) \).

Let us compute it pointwise -- i.e. for a given \( \multisetElementSymbol{\daBlFo{y}} \):

\[ \begin{aligned} \multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}&= \function{\multiImageModifier{\function{f}}}(\reFo{\setSymbol{A}})\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}\\ &= \multisetCardinality{\multisetConstructor{\multisetElementSymbol{\daBlFo{y}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\reFo{\setSymbol{A}}},\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}}\\ &= \indexSum{\reFo{\setSymbol{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}}}{\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\end{aligned} \]

We've written the multiplicity \( \multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}} \) as a count of the number of ways we can bind \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\reFo{\setSymbol{A}}} \) to achieve the condition \( \multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}}) \).

Preservation of sums #

It is clear that the number of ways that \( \multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}}) \) can be true when \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}\multisetSumSymbol \multisetSymbol{\teFo{\primed{A}}}} \) is the number of ways it can be true when \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\reFo{A}}} \) plus the number of ways when \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\multisetSymbol{\teFo{\primed{A}}}} \):

\[ \begin{aligned} \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}\multisetSumSymbol \multisetSymbol{\teFo{\primed{A}}})\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}&= \indexSum{\paren{\multisetSymbol{\reFo{A}}\multisetSumSymbol \multisetSymbol{\teFo{\primed{A}}}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}}}{\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\\ &= \indexSum{\paren{\multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}} + \multisetSymbol{\teFo{\primed{A}}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}}}{}{}\\ &= \paren{\indexSum{\multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}}{}{}} + \paren{\indexSum{\multisetSymbol{\teFo{\primed{A}}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}}{}{}}\\ &= \paren{\function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}})\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}} + \paren{\function{\multiImageModifier{\function{f}}}(\multisetSymbol{\teFo{\primed{A}}})\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}}\end{aligned} \]

Therefore we have that multi-image functions are linear -- they preserve multiset sums:

\[ \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}\multisetSumSymbol \multisetSymbol{\teFo{\primed{A}}}) = \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}})\multisetSumSymbol \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\teFo{\primed{A}}}) \]

The same is not true for multiset intersection (or relative complement), for the same reason that ordinary image functions do not preserve set intersection and relative complement. However, we can put bounds on these multisets, whose proofs are left as an exercise:

\[ \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}\multisetIntersectionSymbol \multisetSymbol{\teFo{\primed{A}}}) \submseteq \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}),\function{\multiImageModifier{\function{f}}}(\multisetSymbol{\teFo{\primed{A}}}) \submseteq \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}\multisetUnionSymbol \multisetSymbol{\teFo{\primed{A}}}) \]

Multiplicity functions of multi-preimage functions #

Let's run the same game for multi-preimage functions. Here, \( \multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}} \) will count how many times \( \elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}} \) occurs in the multi-preimage \( \multisetSymbol{\reFo{A}}\defEqualSymbol \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}) \). This is the number of ways that we can bind \( \elemOf{\multisetElementSymbol{\daBlFo{y}}}{\multisetSymbol{\blFo{B}}} \) to satisfy \( \multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}}) \):

\[ \begin{aligned} \multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}&= \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}\\ &= \multisetCardinality{\multisetConstructor{\multisetElementSymbol{\daReFo{x}}}{\elemOf{\function{f}(\multisetElementSymbol{\daReFo{x}})}{\multisetSymbol{\blFo{B}}}}}\\ &= \multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \function{f}(\multisetElementSymbol{\daReFo{x}})\end{aligned} \]

Again, it is easy to verify pointwise that \( \boundMultiplicityFunction{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetSumSymbol \multisetSymbol{\orFo{\primed{B}}})} = \boundMultiplicityFunction{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})} + \boundMultiplicityFunction{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\orFo{\primed{B}}})} \) and hence that multi-preimage functions are linear:

\[ \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetSumSymbol \multisetSymbol{\orFo{\primed{B}}}) = \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})\multisetSumSymbol \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\orFo{\primed{B}}}) \]

However, we do have the additional properties that multi-preimage functions preserve union, intersection, and complement.

To prove this, let us evaluate multiplicity of the multiset \( \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetUnionSymbol \multisetSymbol{\orFo{\primed{B}}}) \) pointwise, using the definition of \( \multisetUnionSymbol \) as the pointwise \( \max \) of multiplicity functions:

\[ \begin{aligned} \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetUnionSymbol \multisetSymbol{\orFo{\primed{B}}})\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}&= \paren{\multisetSymbol{\blFo{B}}\multisetUnionSymbol \multisetSymbol{\orFo{\primed{B}}}}\multisetMultiplicitySymbol \function{f}(\multisetElementSymbol{\daReFo{x}})\\ &= \max(\multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \function{f}(\multisetElementSymbol{\daReFo{x}}),\multisetSymbol{\orFo{\primed{B}}}\multisetMultiplicitySymbol \function{f}(\multisetElementSymbol{\daReFo{x}}))\\ &= \max(\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}},\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\orFo{\primed{B}}})\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}})\\ &= \paren{\function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})\multisetUnionSymbol \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\orFo{\primed{B}}})}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}\end{aligned} \]

Hence under duality we have that:

\[ \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetUnionSymbol \multisetSymbol{\orFo{\primed{B}}}) = \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})\multisetUnionSymbol \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\orFo{\primed{B}}}) \]

Similar arguments run for intersection and relative complement.

Images and pre-images as matrix algebra #

We can easily connect the multi-image and multi-preimage to matrix algebra.

The transfer matrix of a function \( \functionSignature{\function{f}}{\setSymbol{X}}{\setSymbol{Y}} \) is a generalized matrix \( \matrix{\boFo{F}} \) whose rows and columns are indexed by \( \setSymbol{X} \) and \( \setSymbol{Y} \) respectively, and which has the following entries:

\[ \matrixPart{\matrix{\boFo{F}}}{\multisetElementSymbol{\daReFo{x}}}{\multisetElementSymbol{\daBlFo{y}}}\defEqualSymbol \begin{cases} 1 &\text{if } \function{f}(\multisetElementSymbol{\daReFo{x}}) = \multisetElementSymbol{\daBlFo{y}}\\ 0 &\text{otherwise} \end{cases} \]

The fact that \( \function{f} \) is a function -- i.e. single-valued -- is equivalent to the property \( \forAllForm{\multisetElementSymbol{\daReFo{x}}}{\indexSum{\matrixPart{\matrix{\boFo{F}}}{\multisetElementSymbol{\daReFo{x}}}{\multisetElementSymbol{\daBlFo{y}}}}{\multisetElementSymbol{\daBlFo{y}}}{} = 1} \).

The transfer matrix \( \matrix{\boFo{F}} \) associated with \( \sym{f} \) can be thought of as the multiplicity function for the graph \( \setSymbol{F} \), which is the set of input-output tuples from \( \function{f} \):

\[ \begin{aligned} \setSymbol{F}&\defEqualSymbol \setConstructor{\TuFo{\multisetElementSymbol{\daReFo{x}}, \multisetElementSymbol{\daBlFo{y}}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}},\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\end{aligned} \]

The way \( \matrix{\boFo{F}} \) encodes the multiplicity function of \( \setSymbol{F} \) is:

\[ \matrixPart{\matrix{\boFo{F}}}{\multisetElementSymbol{\daReFo{x}}}{\multisetElementSymbol{\daBlFo{y}}} = \setSymbol{F}\multisetMultiplicitySymbol \TuFo{\multisetElementSymbol{\daReFo{x}}, \multisetElementSymbol{\daBlFo{y}}} \]

Similarly we can define the multiplicity tuple \( \tupleSym{\reFo{\boFo{A}}} \) of a multiset \( \elemOf{\reFo{\setSymbol{A}}}{\multisets{\setSymbol{X}}} \) to be the generalized tuple of multiplicities whose components are indexed by the base set \( \setSymbol{X} \):

\[ \tuplePart{\tupleSym{\reFo{\boFo{A}}}}{\multisetElementSymbol{\daReFo{x}}}\defEqualSymbol \reFo{\setSymbol{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}} \]

The transfer matrix and multiplicity tuple allows us to compute the multi-image \( \blFo{\setSymbol{B}}\defEqualSymbol \function{\multiImageModifier{\function{f}}}(\reFo{\setSymbol{A}}) \) as a sum:

\[ \begin{aligned} \multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}&= \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}})\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}\\ &= \indexSum{\paren{\multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}}}{\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\\ &= \indexSum{\paren{\multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}} \, \paren{\setSymbol{F}\multisetMultiplicitySymbol \TuFo{\multisetElementSymbol{\daReFo{x}}, \multisetElementSymbol{\daBlFo{y}}}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}}}{}\\ \tuplePart{\tupleSym{\blFo{\boFo{B}}}}{\multisetElementSymbol{\daBlFo{y}}}&= \indexSum{\tuplePart{\tupleSym{\reFo{\boFo{A}}}}{\multisetElementSymbol{\daReFo{x}}} \, \matrixPart{\matrix{\boFo{F}}}{\multisetElementSymbol{\daReFo{x}}}{\multisetElementSymbol{\daBlFo{y}}}}{\elemOf{\multisetElementSymbol{\daReFo{x}}}{\setSymbol{X}}}{}\end{aligned} \]

This computation is pointwise, for a fixed \( \elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}} \). But we can write it pointfree, where we compute the multiplicity tuple \( \tupleSym{\blFo{\boFo{B}}} \) for the multiset \( \elemOf{\blFo{\setSymbol{B}}}{\multisets{\setSymbol{Y}}} \) in one go using vector-matrix multiplication:

\[ \tupleSym{\blFo{\boFo{B}}} = \tupleSym{\reFo{\boFo{A}}}\matrixDotSymbol \matrix{\boFo{F}} \]

Multi-preimages can also be expressed this way. We can compute \( \reFo{\setSymbol{A}}\defEqualSymbol \function{\multiPreimageModifier{\function{f}}}(\blFo{\setSymbol{B}}) \) pointwise as:

\[ \begin{aligned} \multisetSymbol{\reFo{A}}\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}&= \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})\multisetMultiplicitySymbol \multisetElementSymbol{\daReFo{x}}\\ &= \indexSum{\paren{\multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}}}{\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}}}{\multisetElementSymbol{\daBlFo{y}} = \function{f}(\multisetElementSymbol{\daReFo{x}})}\\ &= \indexSum{\paren{\multisetSymbol{\blFo{B}}\multisetMultiplicitySymbol \multisetElementSymbol{\daBlFo{y}}} \, \paren{\setSymbol{F}\multisetMultiplicitySymbol \TuFo{\multisetElementSymbol{\daReFo{x}}, \multisetElementSymbol{\daBlFo{y}}}}}{\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}}}{}\\ \tuplePart{\tupleSym{\reFo{\boFo{A}}}}{\multisetElementSymbol{\daReFo{x}}}&= \indexSum{\tuplePart{\tupleSym{\blFo{\boFo{B}}}}{\multisetElementSymbol{\daBlFo{y}}} \, \matrixPart{\matrix{\boFo{F}}}{\multisetElementSymbol{\daReFo{x}}}{\multisetElementSymbol{\daBlFo{y}}}}{\elemOf{\multisetElementSymbol{\daBlFo{y}}}{\setSymbol{Y}}}{}\end{aligned} \]

Here, we can represent this pointfree as a matrix-vector multiplication:

\[ \tupleSym{\reFo{\boFo{A}}} = \matrix{\boFo{F}}\matrixDotSymbol \tupleSym{\blFo{\boFo{B}}} \]

Linearity #

The fact that multi-image and multi-preimage preserve multiset sums is then equivalent to the statement that matrix-vector multiplication is linear:

\[ \begin{aligned} \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}}\multisetSumSymbol \primed{\multisetSymbol{\reFo{A}}})&= \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\reFo{A}})\multisetSumSymbol \function{\multiImageModifier{\function{f}}}(\multisetSymbol{\teFo{\primed{A}}})\\ \iff \\ \paren{\tupleSym{\reFo{\boFo{A}}}\matrixPlusSymbol \tupleSym{\teFo{\primed{\boFo{A}}}}}\matrixDotSymbol \matrix{\boFo{F}}&= \paren{\tupleSym{\reFo{\boFo{A}}}\matrixDotSymbol \matrix{\boFo{F}}}\matrixPlusSymbol \paren{\tupleSym{\teFo{\primed{\boFo{A}}}}\matrixDotSymbol \matrix{\boFo{F}}}\end{aligned} \] \[ \begin{aligned} \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}}\multisetSumSymbol \multisetSymbol{\orFo{\primed{B}}})&= \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\blFo{B}})\multisetSumSymbol \function{\multiPreimageModifier{\function{f}}}(\multisetSymbol{\orFo{\primed{B}}})\\ \iff \\ \matrix{\boFo{F}}\matrixDotSymbol \paren{\tupleSym{\blFo{\boFo{B}}}\matrixPlusSymbol \tupleSym{\orFo{\primed{\boFo{B}}}}}&= \paren{\matrix{\boFo{F}}\matrixDotSymbol \tupleSym{\blFo{\boFo{B}}}}\matrixPlusSymbol \paren{\matrix{\boFo{F}}\matrixDotSymbol \tupleSym{\orFo{\primed{\boFo{B}}}}}\end{aligned} \]