I've seen the term "real multiset" but it doesn't seem to be very appropriate so i wonder whether there are any others.

My second question is about multisets. In most sources i've seen one of the following definitions:

  • multiset is an ordered pair $~~(X,~~f:X\rightarrow\mathbb{N}_0)$

  • multiset is an ordered pair $~~(X,~~f:X\rightarrow\mathbb{N}_+)$

I consider the first definition to be more convenient but wikipedia, ncatlab and planetmath use the second one. So i'd like to understand what's the conceptual difference between them and which one is currently the most accepted in mathematical literature?

Thanks in advance.


A multiset is a set that can contain an element multiple times. Therefore you can define it as $(X,f)$ where $X$ is an underlying old-fashioned set containing the elements and $f$ is a function that associates to each element of $X$ the number of times it appears (which is a natural number). The difference lies in which natural number you allow.

On one hand if you allow elements to be present 0 times, then you may take $(X, f:X \to \mathbb{N}_0)$ as your definition. This has the disadvantage that a conceptual multiset can be formalized in an infinite number of ways, by adding arbitrary elements and letting their $f$-value be 0.

On the other hand you can force the presence of at least an object by defining the multiset as $(X,f: X \to \mathbb{N}_+)$. It does not suffer from the same disadvantage and it is the reason this definition is more popular.

I am not an expert in multisets so I cannot tell you which version is more widespread. I heard they are used a lot in theoretical computer science, so you might look there.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.