# Multisets

A multiset can be viewed as type of set, or even as a proto-set. The only difference between a set and a multiset can be seen when considering multiplicity. In the case of a set multiplicity has no meaning, i.e `{a,a}={a}`, but in the case of a multiset it does.

A multiset over `S` is a function `f:S→N` where `f(x)` is called the multiplicity, i.e. how many times the element `x` occurs in the multiset. If `f(x)=i` then each of the `i` `x` elements is called an occurrence. The elements of `f` are given by `D(f)` which is defined as

```	```
D(f) = {s∈S|f(s)≠0}
```
```

The multiset `f` is called finite if `D(f)` is finite. The number of elements of a finite multiset is given by

```	```
|f| = Σx∈D(f)f(x)
```
```

Sometimes multisets are written in a set-like notation as shown below:

```	```
{{1,1,0,99,99,99}}
```
```

The usual set operations (union, intersection, and difference) can be used:

```	```
{{1,1,0,99,99,99}} ∪ {{0,3,3}} = {{1,1,0,0,3,3,99,99,99}}
```
```

## References

Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.