I have a graph $G(V,E)$ and each $v_i\in V$ has a value $v_i\cdot s$ ($v_i\cdot s$'s are not unique). How can I show a multiset representing the $v_i\cdot s$'s? This is what I have come up with so far which doesn't seem to be correct ($V$ is the set of vertices and $S$ is the set of values).

$\forall v_i\in V$ and $S=\{v_i\cdot s\mid v_i\in V\}$ and $f:S\to{\mathbb N}$ which finds the frequency of each $v_i\cdot s$, we define multiset $(S,f)$.


1 Answer 1


Your question is not entirely clear to me, but if by multiset you mean a set in which elements may appear more than once but only a finite number of time, then one way to represent such objects is as follows. A multiset is a set $S$ together with a function $S\to \mathbb N$ from the set $S$ to the non-negative integers.

  • $\begingroup$ that's exactly what I mean, however I don't exactly know how to write it using proper notation.How can I mathematically define s multiset for the specified requirement? $\endgroup$
    – HHH
    Commented Feb 4, 2014 at 22:59
  • $\begingroup$ Define it as a pair $(S,f)$ where $S$ is an arbitrary ordinary set and $f:S \to \mathbb N$ is a function to the positive naturals. $\endgroup$ Commented Feb 4, 2014 at 23:01
  • $\begingroup$ Alternative methods include a set of ordered pairs, $\langle x,n\rangle$ where $x$ is an element and $n>0$ is the multiplicity of $x$ in the multiset. (Note that this is really just the graph of the function $f$ as suggested by Ittay. This is also the difference between the category theory notion of a function as a triplet, and the set theory notion of a function as a set of ordered pairs.) $\endgroup$
    – Asaf Karagila
    Commented Feb 4, 2014 at 23:06
  • $\begingroup$ is the revision correct? $\endgroup$
    – HHH
    Commented Feb 4, 2014 at 23:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .